论文标题
量子退火的图形着色
Graph Coloring with Quantum Annealing
论文作者
论文摘要
我们开发了一种启发式图着色近似算法，该近似算法将D-Wave 2X用作独立的SET采样器，并根据完全经典的实现评估其性能。随机生成的一组小而硬的图实例作为我们的测试集。我们的性能分析表明在混合量子古典算法中有限的量子优势。量子边缘在多个指标上保持，并表明图形问题应用非常适合量子退火器。
We develop a heuristic graph coloring approximation algorithm that uses the D-Wave 2X as an independent set sampler and evaluate its performance against a fully classical implementation. A randomly generated set of small but hard graph instances serves as our test set. Our performance analysis suggests limited quantum advantage in the hybrid quantum-classical algorithm. The quantum edge holds over multiple metrics and suggests that graph problem applications are a good fit for quantum annealers.
