Research at HP Labs : Information Dynamics Lab : Research Areas : Quantum Computing

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.

Contents of this page:

examples of algorithm behaviors
Quantum algorithms with no classical analog are useful for some problems:
- Experimental Implementation of an Adiabatic Quantum Optimization Algorithm, 2003
- Adiabatic Quantum Computing for Random Satisfiability Problems, 2003
- Quantum Optimization, 2000
- Quantum Search Heuristics, 2000 (with further improvements using portfolios)
- Single-Step Quantum Search Using Problem Structure, 1998
- Highly Structured Searches with Quantum Computers, 1998
Conventional search heuristics give analogous quantum algorithms:
- Local Search Methods for Quantum Computers, 1998
- A Framework for Structured Quantum Search, 1997 and an animation
- Quantum Computing and Phase Transitions in Combinatorial Search, 1996
More complex algorithms can be developed using Tools for Quantum Algorithms, 1998
For an application to smart matter, see Quantum Smart Matter
Using quantum information technology for economic mechanisms

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.

@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}

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.

@ARTICLE {,
AUTHOR = "Tad Hogg",
TITLE = "Adiabatic Quantum Computing for Random Satisfiability Problems",
JOURNAL = "Physical Review A",
VOLUME = "67",
PAGES = "022314",
YEAR = 2003}

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.

@ARTICLE {,
AUTHOR = "Sebastian Maurer and Tad Hogg and Bernardo A. Huberman",
TITLE = "Quantum Portfolios",
JOURNAL = "Physical Review Letters",
VOLUME = "87",
PAGES = "257901",
YEAR = 2001}

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 NP-complete problems such as 3-SAT.

@ARTICLE {,
AUTHOR = "Tad Hogg and Dmitriy Portnov",
TITLE = "Quantum Optimization",
JOURNAL = "Information Sciences",
VOLUME = "128",
PAGES = "181--197",
YEAR = 2000}

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 low-cost 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.

@ARTICLE {,
AUTHOR = "Tad Hogg",
TITLE = "Quantum Search Heuristics",
JOURNAL = "Physical Review A",
VOLUME = "61",
PAGES = "052311",
YEAR = 2000}

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.

@ARTICLE {,
AUTHOR = "Tad Hogg",
TITLE = "Single-Step Quantum Search Using Problem Structure",
JOURNAL = "Intl. J. of Modern Physics C",
VOLUME = "11",
PAGES = "739-773",
YEAR = 2000}

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 k-SAT 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.

@ARTICLE {,
AUTHOR = "Tad Hogg",
TITLE = "Highly Structured Searches with Quantum Computers",
JOURNAL = "Physical Review Letters",
VOLUME = "80",
PAGES = "2473--2476",
YEAR = "1998"}

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.

Tad Hogg and Mehmet Yanik,
Local Search Methods for Quantum Computers,
Xerox PARC technical report, 1998

Local search algorithms use the neighborhood relations among search states and often perform well for a variety of NP-hard 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.

@ARTICLE {,
AUTHOR = "Tad Hogg",
TITLE = "A Framework for Structured Quantum Search",
JOURNAL = "Physica D",
VOLUME = "120",
PAGES = "102--116",
YEAR = "1998"}

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.

Some animated examples of this algorithm solving small search problems are available.

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.

@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 = "1347--1361",
YEAR = 1999}

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.

Quantum Computing

HP Labs

» Information Dynamics Lab