A Framework for Quantum Search Heuristics

Tad Hogg
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com

@INPROCEEDINGS {,
 AUTHOR = "Tad Hogg",
 TITLE = "A Framework for Quantum Search Heuristics",
 BOOKTITLE = "Proceedings of the Workshop on Physics and Computation",
 EDITOR = "T. Toffoli and others",
 PAGES = "140-146",
 PUBLISHER = "New England Complex Systems Institute",
 ADDRESS = "Cambridge, MA",
 YEAR = "1996"}

Abstract

A quantum algorithm for combinatorial search is presented that provides a simple framework for utilizing search heuristics. The algorithm is evaluated in a new case that is an unstructured version of the graph coloring problem. It performs significantly better than the direct use of quantum parallelism, on average, in cases corresponding to previously identified phase transitions in search difficulty. The conditions underlying this improvement are described. Much of the algorithm is independent of particular problem instances, making it suitable for implementation as a special purpose device.
postcript (334K, 8 pages)