Quantum computer search algorithms based on the structure of hard combinatorial search problems. As with conventional heuristics, using problem structure greatly reduces search cost in many cases, compared to unstructured search. Applications of quantum information technology to economic mechanisms.
A short nontechnical review is Quantum Search Heuristics in A Quantum Leap for AI in the July/August 1999 issue of Intelligent Systems.
Examples
Demonstrations comparing several quantum search algorithms: a Java demonstration illustrating how amplitudes change during the search for problems up to 16 variables, and a Mathematica demonstration showing evolution of probability and associated eigenvalues change during the search with 5 variables.
A IJCAI2001 tutorial on quantum computing includes animations of amplitudes for a quantum heuristic.
Experimental Implementation of an Adiabatic Quantum Optimization Algorithm
@ARTICLE {,
AUTHOR = "Matthias Steffen and Wim van Dam and Tad Hogg and Greg Breyta and Isaac Chuang",
TITLE = "Experimental Implementation of an Adiabatic Quantum Optimization Algorithm",
JOURNAL = "Physical Review Letters",
VOLUME = "90",
PAGES = "067903",
YEAR = 2003}
Abstract
We report the realization of a nuclear magnetic resonance computer
with three quantum bits that simulates an adiabatic quantum
optimization algorithm. Adiabatic quantum algorithms offer new
insight into how quantum resources can be used to solve hard
problems. This experiment uses a particularly well suited three
quantum bit molecule and was made possible by introducing a
technique that encodes general instances of the given optimization
problem into an easily applicable Hamiltonian. Our results indicate
an optimal run time of the adiabatic algorithm that agrees well with
the prediction of a simple decoherence model.
Available as arxiv preprint quantph/0302057.
Adiabatic Quantum Computing for Random Satisfiability Problems
@ARTICLE {,
AUTHOR = "Tad Hogg",
TITLE = "Adiabatic Quantum Computing for Random Satisfiability Problems",
JOURNAL = "Physical Review A",
VOLUME = "67",
PAGES = "022314",
YEAR = 2003}
Abstract
The discrete formulation of adiabatic quantum computing is compared
with other search methods, classical and quantum, for random
satisfiability (SAT) problems. With the number of steps growing only
as the cube of the number of variables, the adiabatic method gives
solution probabilities close to one for problem sizes feasible to
evaluate. However, for these sizes the minimum energy gaps are fairly
large, so may not reflect asymptotic behavior where costs are
dominated by tiny gaps. Moreover, the resulting search costs are much
higher than other methods, but can be reduced by using fewer
steps. Variants of the quantum algorithm that do not match the
adiabatic limit give lower costs, on average, and slower growth than
the conventional GSAT heuristic method.
Available as arxiv preprint quantph/0206059.
Quantum Portfolios
@ARTICLE {,
AUTHOR = "Sebastian Maurer and Tad Hogg and Bernardo A. Huberman",
TITLE = "Quantum Portfolios",
JOURNAL = "Physical Review Letters",
VOLUME = "87",
PAGES = "257901",
YEAR = 2001}
Abstract
Quantum computation holds promise for the solution of many
intractable problems. However, since many quantum algorithms are stochastic in nature they can only find the solution of hard
problems probabilistically. Thus the efficiency of the algorithms
has to be characterized both by the expected time to completion
and the associated variance. In order to minimize both the
running time and its uncertainty, we show that portfolios of
quantum algorithms analogous to those of finance can outperform
single algorithms when applied to the NPcomplete problems such as 3SAT.
Available as arxiv preprint quantph/0105071.
Quantum Optimization
@ARTICLE {,
AUTHOR = "Tad Hogg and Dmitriy Portnov",
TITLE = "Quantum Optimization",
JOURNAL = "Information Sciences",
VOLUME = "128",
PAGES = "181197",
YEAR = 2000}
Abstract
We present a quantum algorithm for combinatorial optimization using the cost
structure of the search states. Its behavior is illustrated for overconstrained
satisfiability and asymmetric traveling salesman problems. Simulations with
randomly generated problem instances show each step of the algorithm shifts
amplitude preferentially towards lower cost states, thereby concentrating
amplitudes into lowcost states, on average. These results are compared with
conventional heuristics for these problems.
This algorithm uses the same techniques as applied to decision problems in Quantum Search Heuristics.
Available as arxiv preprint quantph/0006090.
Quantum Search Heuristics
@ARTICLE {,
AUTHOR = "Tad Hogg",
TITLE = "Quantum Search Heuristics",
JOURNAL = "Physical Review A",
VOLUME = "61",
PAGES = "052311",
YEAR = 2000}
Abstract
A new quantum algorithm for combinatorial search, adjusting amplitudes based
on number of conflicts in search states, performs well, on average, for hard
random satisfiability problems near a phase
transition in search difficulty. In many cases, the algorithm exploits
correlations among problem properties more effectively than current heuristics,
and improves on prior quantum algorithms that ignore these correlations.
Available as APS preprint aps1999oct19_002
A nontechnical description appears in A Quantum Leap for AI of Intelligent Systems, July/August 1999.
SingleStep Quantum Search Using Problem Structure
@ARTICLE {,
AUTHOR = "Tad Hogg",
TITLE = "SingleStep Quantum Search Using Problem Structure",
JOURNAL = "Intl. J. of Modern Physics C",
VOLUME = "11",
PAGES = "739773",
YEAR = 2000}
Abstract
The structure of satisfiability problems is used to improve search algorithms
for quantum computers and reduce their required coherence times. The asymptotic
average behavior of the these algorithms is determined exactly, and used to
identify the best algorithm from among a class of methods that use only a single
coherent evaluation of problem properties. The resulting algorithm improves on
previous quantum algorithms for most random kSAT problems, but remains
exponential for hard problem instances. Compared to good classical methods, the
algorithm performs better, on average, for weakly and highly constrained
problems but worse for hard cases, indicating the need to include additional
problem structure in quantum algorithms.
Available as arxiv preprint quantph/9812049
Highly Structured Searches with Quantum Computers
@ARTICLE {,
AUTHOR = "Tad Hogg",
TITLE = "Highly Structured Searches with Quantum Computers",
JOURNAL = "Physical Review Letters",
VOLUME = "80",
PAGES = "24732476",
YEAR = "1998"}
Abstract
A quantum algorithm for a class of highly structured combinatorial search
problems is introduced. This algorithm finds a solution in a single step,
contrasting with the linear growth in the number of steps required by the best
classical algorithms as the problem size increases, and the exponential growth
required by classical and quantum methods that ignore the problem structure. In
some cases, the algorithm can also guarantee that insoluble problems in fact
have no solutions, unlike previously proposed quantum search algorithms.
Available as APS preprint aps1997oct30_002
For an expanded discussion of this algorithm see Solving Highly Constrained Search Problems with Quantum Computers.
Local Search Methods for Quantum Computers
Tad Hogg and Mehmet Yanik,
Local Search Methods for Quantum Computers,
Xerox PARC technical report, 1998
Abstract
Local search algorithms use the neighborhood relations among search states
and often perform well for a variety of NPhard combinatorial search problems.
This paper shows how quantum computers can also use these neighborhood
relations. An example of such a local quantum search is evaluated empirically
for the satisfiability (SAT) problem and shown to be particularly effective for
highly constrained instances. For problems with an intermediate number of
constraints, it is somewhat less effective at exploiting problem structure than
incremental quantum methods, in spite of the much smaller search space used by the local method.
Available as arxiv preprint quantph/9802043
A Framework for Structured Quantum Search
@ARTICLE {,
AUTHOR = "Tad Hogg",
TITLE = "A Framework for Structured Quantum Search",
JOURNAL = "Physica D",
VOLUME = "120",
PAGES = "102116",
YEAR = "1998"}
Abstract
A quantum algorithm for general combinatorial search that uses the underlying
structure of the search space to increase the probability of finding a solution
is presented. This algorithm shows how coherent quantum systems can be matched
to the underlying structure of abstract search spaces, and is analytically
simpler than previous structured search methods. The algorithm is evaluated empirically with a
variety of search problems, and shown to be particularly effective for searches
with many constraints. Furthermore, the algorithm provides a simple framework
for utilizing search heuristics. It also exhibits the same phase transition in
search difficulty as found for sophisticated classical search methods,
indicating it is effectively using the problem structure.
Available as arxiv preprint quantph/9701013
Some animated examples of this algorithm solving small search problems are available.
Quantum Computing and Phase Transitions in Combinatorial Search
Tad Hogg, Quantum Computing and Phase Transitions in Combinatorial Search, J. of Artificial Intelligence Research 4, 91128 (1996).
Abstract
We introduce an algorithm for combinatorial search on quantum computers that
is capable of significantly concentrating amplitude into solutions for some NP
search problems, on average. This is done by exploiting the same aspects of
problem structure as used by classical backtrack methods to avoid unproductive
search choices. This quantum algorithm is much more likely to find solutions
than the simple direct use of quantum parallelism. Furthermore, empirical
evaluation on small problems shows this quantum algorithm displays the same
phase transition behavior, and at the same location, as seen in many previously
studied classical search methods. Specifically, difficult problem instances are
concentrated near the abrupt change from underconstrained to overconstrained
problems.
Available in postscript and html versions.
Further experiments with this algorithm and analysis of its performance are reported in A Framework for Quantum Search Heuristics, 1996.
Tools for Quantum Algorithms
@ARTICLE {,
AUTHOR = "Tad Hogg and Carlos Mochon and Eleanor Rieffel and Wolfgang Polak",
TITLE = "Tools for Quantum Algorithms",
JOURNAL = "Intl. J. of Modern Physics C",
VOLUME = "10",
PAGES = "13471361",
YEAR = 1999}
Abstract
We present efficient implementations of a number of operations for quantum
computers. These include controlled phase adjustments of the amplitudes in a
superposition, permutations, approximations of transformations and
generalizations of the phase adjustments to block matrix transformations. These
operations generalize those used in proposed quantum search algorithms.
Available as arxiv preprint quantph/9811073
Economic Mechanisms
