Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

hp.com home

Quantum Computing

printable version

HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» People
» Worldwide sites
» Downloads
Content starts here

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.

Contents of this page:


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 IJCAI-2001 tutorial on quantum computing includes animations of amplitudes for a quantum heuristic.

Click to view larger version of this image.

A quantum algorithm shifting probability toward low conflict states of a satisfiability problem instance with 20 variables, 80 clauses.

Experimental Implementation of an Adiabatic Quantum Optimization Algorithm

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.

Available as arxiv preprint quant-ph/0302057.

Adiabatic Quantum Computing for Random Satisfiability Problems

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.

Available as arxiv preprint quant-ph/0206059.

Quantum Portfolios

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.

Available as arxiv preprint quant-ph/0105071.

Quantum Optimization

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.

Available as arxiv preprint quant-ph/0006090.

Quantum Search Heuristics

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.

Available as APS preprint aps1999oct19_002

A nontechnical description appears in A Quantum Leap for AI of Intelligent Systems, July/August 1999.

Single-Step Quantum Search Using Problem Structure

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.

Available as arxiv preprint quant-ph/9812049

Highly Structured Searches with Quantum Computers

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.

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


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.

Available as arxiv preprint quant-ph/9802043

A Framework for Structured Quantum Search

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.

Available as arxiv preprint quant-ph/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, 91-128 (1996).


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

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.

Available as arxiv preprint quant-ph/9811073

Economic Mechanisms

» Information Dynamics Lab

» Research areas
» Results
» People
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.