Graph Coloring with Quantum Annealing

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.

References in corpus (5)

• Defining and detecting quantum speedup
• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• A NASA Perspective on Quantum Computing: Opportunities and Challenges
• A Near-Term Quantum Computing Approach for Hard Computational Problems in Space Exploration
• Quantum Annealing and the Satisfiability Problem

Cited by in corpus (2)

• Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem
• Quantum annealer accelerates the variational quantum eigensolver in a triple-hybrid algorithm