Graph Coloring with Quantum Heuristics

Alex Fabrikant, University of California, Berkeley; Tad Hogg, HP Labs

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.