Combinatorial searches, such as arise, for example, in scheduling,
gene sequencing, cryptography and discrete statistical physics models,
are difficult to solve because the computation time grows
exponentially with the size of the problem. Quantum computers, by
evaluating all possible combinations simultaneously, offer the
possibility of much faster searches.
Beyond the challenge of building quantum computers, realizing this
possibility requires matching the quantum algorithm to the
combinatorial properties of particular problems. Since these are not
known in advance, it appears unlikely quantum computers can rapidly
solve all combinatorial searches.
Fortunately, random ensembles of search problems have robust
regularities related to phase transitions in search behavior. This
talk will describe how these regularities apply to give heuristic
search algorithms for quantum computers, i.e., algorithms that work
well for many, but not all, searches. The heuristics use a sequence of
small changes to the amplitudes associated with the quantum computer,
so can be viewed as a discrete version of the recently introduced
technique of adiabatic quantum computing. The heuristics also help
match algorithms to limited hardware capabilities, e.g., by reducing
required coherence times.
I will also present open questions on the design and behavior of these
algorithms. In particular, a mean-field analysis suggests heuristics
can be quite effective, on average, for commonly studied NP-hard
combinatorial searches such as satisfiability, graph coloring and
traveling salesman. Thus a significant open question is whether more
accurate statistical methods can verify this conclusion or identify
even better heuristics.
For further background, see T. Hogg, Quantum Search Heuristics,
Physical Review A, 61:052311, 2000
(http://publish.aps.org/abstract/pra/v61/e052311) or, for a
nontechnical overview, the 2nd essay in
http://www.computer.org/intelligent/ex1999/pdf/x4009.pdf
Copyright. All Rights Reserved.