Graph Coloring with Quantum Heuristics
Abstract
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 of graph coloring. An approximate asymptotic analysis suggests polynomial-time cost for hard graph coloring problems, on average.
Cite
Text
Fabrikant and Hogg. "Graph Coloring with Quantum Heuristics." AAAI Conference on Artificial Intelligence, 2002. doi:10.5555/777092.777099Markdown
[Fabrikant and Hogg. "Graph Coloring with Quantum Heuristics." AAAI Conference on Artificial Intelligence, 2002.](https://mlanthology.org/aaai/2002/fabrikant2002aaai-graph/) doi:10.5555/777092.777099BibTeX
@inproceedings{fabrikant2002aaai-graph,
title = {{Graph Coloring with Quantum Heuristics}},
author = {Fabrikant, Alex and Hogg, Tad},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2002},
pages = {22-27},
doi = {10.5555/777092.777099},
url = {https://mlanthology.org/aaai/2002/fabrikant2002aaai-graph/}
}