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

How Powerful is Adiabatic Quantum Computation

Wim van Dam, Michele Mosca, Umesh V. Vazirani

Published Jun 1, 2002• 202 citations
OpenAlex

Abstract

We analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'.

Related papers

How powerful is adiabatic quantum computation?

W. van Dam, M. Mosca, U. Vazirani

The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.

arXiv:quant-ph/0206003•Annual Symposium on Foundations of Computer Science•Jan 1, 2001•236 citations

Study on the computational power of neuromorphic adiabatic quantum computation

Aiko Ono, Sato Shigeo, Kinjo Mitsunaga +1 more

IEICE Technical Report; IEICE Tech. Rep.•Oct 7, 2008•0 citations

The complexity of the Quantum Adiabatic Algorithm

A. P. Young, Sergey Knysh, Vadim Smelyanskiy

Computer Physics Communications•Jun 9, 2010•7 citations

How fast can quantum annealers count?

Itay Hen

We outline an algorithm for the quantum counting problem using adiabatic quantum computation (AQC). We show that the mechanism of quantum-adiabatic evolution may be utilized toward estimating the number of solutions to a problem, and not only to find them. Using local adiabatic evolution, a process in which the adiabatic procedure is performed at a variable rate, the problem of counting the number of marked items in an unstructured database is solved quadratically faster than the corresponding classical algorithm. The above algorithm provides further evidence for the potentially powerful capabilities of AQC as a paradigm for more efficient problem solving on a quantum computer, and may be used as the basis for solving more sophisticated problems.

arXiv:1301.4956•Journal of Physics A Mathematical and Theoretical•May 27, 2014•11 citations

Quantum Adiabatic Computation with a Constant Gap Is Not Useful in One Dimension

M. B. Hastings

We show that it is possible to use a classical computer to efficiently simulate the adiabatic evolution of a quantum system in one dimension with a constant spectral gap, starting the adiabatic evolution from a known initial product state. The proof relies on a recently proven area law for such systems, implying the existence of a good matrix product representation of the ground state, combined with an appropriate algorithm to update the matrix product state as the Hamiltonian is changed. This implies that adiabatic evolution with such Hamiltonians is not useful for universal quantum computation. Therefore, adiabatic algorithms which are useful for universal quantum computation either require a spectral gap tending to zero or need to be implemented in more than one dimension (we leave open the question of the computational power of adiabatic simulation with a constant gap in more than one dimension).

arXiv:0902.2960•Physical Review Letters•Jul 27, 2009•20 citations

How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory?

Tomoyuki Yamakami

Lecture notes in computer science•Jan 1, 2019•0 citations
The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.
We outline an algorithm for the quantum counting problem using adiabatic quantum computation (AQC). We show that the mechanism of quantum-adiabatic evolution may be utilized toward estimating the number of solutions to a problem, and not only to find them. Using local adiabatic evolution, a process in which the adiabatic procedure is performed at a variable rate, the problem of counting the number of marked items in an unstructured database is solved quadratically faster than the corresponding classical algorithm. The above algorithm provides further evidence for the potentially powerful capabilities of AQC as a paradigm for more efficient problem solving on a quantum computer, and may be used as the basis for solving more sophisticated problems.
We show that it is possible to use a classical computer to efficiently simulate the adiabatic evolution of a quantum system in one dimension with a constant spectral gap, starting the adiabatic evolution from a known initial product state. The proof relies on a recently proven area law for such systems, implying the existence of a good matrix product representation of the ground state, combined with an appropriate algorithm to update the matrix product state as the Hamiltonian is changed. This implies that adiabatic evolution with such Hamiltonians is not useful for universal quantum computation. Therefore, adiabatic algorithms which are useful for universal quantum computation either require a spectral gap tending to zero or need to be implemented in more than one dimension (we leave open the question of the computational power of adiabatic simulation with a constant gap in more than one dimension).