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"}
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)