Graph Coloring with Quantum Heuristics

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Constraint Satisfaction

We present a quantum computer heuristic search algorithm for graph coloring. This algorithm uses a new quantum operator, appropriate for nonbinary-valued constraint satisfaction problems, and information available in partial colorings. We evaluate the algorithm empirically with small graphs near a phase transition in search performance. It improves on two prior quantum algorithms: unstructured search and a heuristic applied to the satisfiability (SAT) encoding for graph coloring. An approximate asymptotic analysis suggests polynomial-time cost for hard graph coloring problems, on average.