Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0104129 · Science

A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua M. Lapan, A. P. Lundgren, Daniel Preda

Published Apr 20, 2001• 2,100 citations
arXivHTMLPDF

Abstract

A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.

DOI
10.1126/science.1057726

Related papers

Adiabatic quantum optimization fails for random instances of NP-complete problems

B. L. Altshuler, Hari Krovi, Jérémie Roland

Adiabatic quantum optimization has attracted a lot of attention because small scale simulations gave hope that it would allow to solve NP-complete problems efficiently. Later, negative results proved the existence of specifically designed hard instances where adiabatic optimization requires exponential time. In spite of this, there was still hope that this would not happen for random instances of NP-complete problems. This is an important issue since random instances are a good model for hard instances that can not be solved by current classical solvers, for which an efficient quantum algorithm would therefore be desirable. Here, we will show that because of a phenomenon similar to Anderson localization, an exponentially small eigenvalue gap appears in the spectrum of the adiabatic Hamiltonian for large random instances, very close to the end of the algorithm. This implies that unfortunately, adiabatic quantum optimization also fails for these instances by getting stuck in a local minimum, unless the computation is exponentially long.

arXiv:0908.2782•Aug 19, 2009•48 citations

A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability

Edward Farhi, Jeffrey Goldstone, Sam Gutmann

Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.

arXiv:quant-ph/0007071•Jul 19, 2000•74 citations

Adiabatic Quantum Optimization and Anderson Localization

B. L. Altshuler

Understanding NP-complete problems is a central topic in computer science. This is why adiabatic quantum optimization has attracted so much attention, as it provided a new approach to tackle NP-complete problems using a quantum computer. The efficiency of this approach is limited by small spectral gaps between the ground and excited states of the quantum computer's Hamiltonian. We will discuss the statistics of the gaps using the borrowed from the theory of quantum disordered systems. It turns out that due to a phenomenon similar to Anderson localization exponentially small gaps appear close to the end of the adiabatic algorithm for large random instances of NP-complete problems. We will present the quantitative analysis of the small spectral gaps and discuss possible consequence of this phenomenon on the adiabatic optimization paradigm.

•Jan 1, 2010•0 citations

Quantum Adiabatic Evolution Algorithms with Different Paths

Edward Farhi, Jeffrey Goldstone, Sam Gutmann

In quantum adiabatic evolution algorithms, the quantum computer follows the ground state of a slowly varying Hamiltonian. The ground state of the initial Hamiltonian is easy to construct; the ground state of the final Hamiltonian encodes the solution of the computational problem. These algorithms have generally been studied in the case where the "straight line" path from initial to final Hamiltonian is taken. But there is no reason not to try paths involving terms that are not linear combinations of the initial and final Hamiltonians. We give several proposals for randomly generating new paths. Using one of these proposals, we convert an algorithmic failure into a success.

arXiv:quant-ph/0208135•Aug 21, 2002•132 citations

An evaluation of the performance of the quantum adiabatic algorithm on random instances of k-SAT

James R. McBride

A quantum computational framework has been developed based on the adiabatic theorem. The theorem guarantees that a system with a time dependent Hamiltonian that is placed into its ground state will remain in its ground state provided that the Hamiltonian of the system varies slowly enough with time. This work investigates the performance of the quantum adiabatic algorithm on random instances of k-SAT. The performance of the algorithm is examined on subsets of k-SAT that are classically easy and on subsets that are classically difficult. The evaluation attempts to determine how the typical time required to solve the problems grows with the size of the problems. This evaluation is done by directly determining the required time from numerical integration of the dynamics of the system and by inferring this time using a result from the adiabatic theorem. This evaluation considers quantum systems composed of up to 23 bits and is performed on several large scale Beowulf clusters. As was seen in previous work, the direct integration studies show what appears to be only a quadratic growth rate in the required running time with the number of bits in problems that classically require exponential time. However, further studies show that these effects are caused by polynomial bounded matrix elements and are not indicative of the asymptotic behavior of the performance of the algorithm. The real asymptotic scaling of the performance of the algorithm is controlled by the ground state energy gap. When this is examined directly it is not currently possible to determine whether the growth rate of the running time of the algorithm is exponential or polynomial.

•Jan 1, 2002•1 citation

Number Partitioning via Quantum Adiabatic Computation

Vadim Smelyanskiy, U. von Toussaint

We study both analytically and numerically the complexity of the adiabatic quantum evolution algorithm applied to random instances of combinatorial optimization problems. We use as an example the NP-complete set partition problem and obtain an asymptotic expression for the minimal gap separating the ground and exited states of a system during the execution of the algorithm. We show that for computationally hard problem instances the size of the minimal gap scales exponentially with the problem size. This result is in qualitative agreement with the direct numerical simulation of the algorithm for small instances of the set partition problem. We describe the statistical properties of the optimization problem that are responsible for the exponential behavior of the algorithm.

•Feb 19, 2002•4 citations
A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.
Adiabatic quantum optimization has attracted a lot of attention because small scale simulations gave hope that it would allow to solve NP-complete problems efficiently. Later, negative results proved the existence of specifically designed hard instances where adiabatic optimization requires exponential time. In spite of this, there was still hope that this would not happen for random instances of NP-complete problems. This is an important issue since random instances are a good model for hard instances that can not be solved by current classical solvers, for which an efficient quantum algorithm would therefore be desirable. Here, we will show that because of a phenomenon similar to Anderson localization, an exponentially small eigenvalue gap appears in the spectrum of the adiabatic Hamiltonian for large random instances, very close to the end of the algorithm. This implies that unfortunately, adiabatic quantum optimization also fails for these instances by getting stuck in a local minimum, unless the computation is exponentially long.
Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.
Understanding NP-complete problems is a central topic in computer science. This is why adiabatic quantum optimization has attracted so much attention, as it provided a new approach to tackle NP-complete problems using a quantum computer. The efficiency of this approach is limited by small spectral gaps between the ground and excited states of the quantum computer's Hamiltonian. We will discuss the statistics of the gaps using the borrowed from the theory of quantum disordered systems. It turns out that due to a phenomenon similar to Anderson localization exponentially small gaps appear close to the end of the adiabatic algorithm for large random instances of NP-complete problems. We will present the quantitative analysis of the small spectral gaps and discuss possible consequence of this phenomenon on the adiabatic optimization paradigm.
In quantum adiabatic evolution algorithms, the quantum computer follows the ground state of a slowly varying Hamiltonian. The ground state of the initial Hamiltonian is easy to construct; the ground state of the final Hamiltonian encodes the solution of the computational problem. These algorithms have generally been studied in the case where the "straight line" path from initial to final Hamiltonian is taken. But there is no reason not to try paths involving terms that are not linear combinations of the initial and final Hamiltonians. We give several proposals for randomly generating new paths. Using one of these proposals, we convert an algorithmic failure into a success.
A quantum computational framework has been developed based on the adiabatic theorem. The theorem guarantees that a system with a time dependent Hamiltonian that is placed into its ground state will remain in its ground state provided that the Hamiltonian of the system varies slowly enough with time. This work investigates the performance of the quantum adiabatic algorithm on random instances of k-SAT. The performance of the algorithm is examined on subsets of k-SAT that are classically easy and on subsets that are classically difficult. The evaluation attempts to determine how the typical time required to solve the problems grows with the size of the problems. This evaluation is done by directly determining the required time from numerical integration of the dynamics of the system and by inferring this time using a result from the adiabatic theorem. This evaluation considers quantum systems composed of up to 23 bits and is performed on several large scale Beowulf clusters. As was seen in previous work, the direct integration studies show what appears to be only a quadratic growth rate in the required running time with the number of bits in problems that classically require exponential time. However, further studies show that these effects are caused by polynomial bounded matrix elements and are not indicative of the asymptotic behavior of the performance of the algorithm. The real asymptotic scaling of the performance of the algorithm is controlled by the ground state energy gap. When this is examined directly it is not currently possible to determine whether the growth rate of the running time of the algorithm is exponential or polynomial.
We study both analytically and numerically the complexity of the adiabatic quantum evolution algorithm applied to random instances of combinatorial optimization problems. We use as an example the NP-complete set partition problem and obtain an asymptotic expression for the minimal gap separating the ground and exited states of a system during the execution of the algorithm. We show that for computationally hard problem instances the size of the minimal gap scales exponentially with the problem size. This result is in qualitative agreement with the direct numerical simulation of the algorithm for small instances of the set partition problem. We describe the statistical properties of the optimization problem that are responsible for the exponential behavior of the algorithm.