← Back to papers
Graph Coloring with Quantum Annealing
Julia Kwok, K. Pudenz·December 8, 2020
PhysicsComputer Science
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
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.