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

SIAM Journal on Computing

Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation

Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph A. Landau, Seth Lloyd, Oded Regev

Published Jan 1, 2007• 474 citations
Publisher

Abstract

Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power was unknown. We describe an efficient adiabatic simulation of any given quantum algorithm, which implies that the adiabatic computation model and the conventional quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two‐dimensional grid with nearest neighbor interactions. The equivalence between the models allows stating the main open problems in quantum computation using well‐studied mathematical objects such as eigenvectors and spectral gaps of sparse matrices.

DOI
10.1137/s0097539705447323

Related papers

Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation

Dorit Aharonov, Wim van Dam, Julia Kempe +3 more

The model of adiabatic quantum computation is a relatively recent model of quantum computation that has attracted attention in the physics and computer science communities. We describe an efficient adiabatic simulation of any given quantum circuit. This implies that the adiabatic computation model and the standard circuit-based quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models allows one to state the main open problems in quantum computation using well-studied mathematical objects such as eigenvectors and spectral gaps of Hamiltonians.

SIAM Review•Jan 1, 2008•414 citations

Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation

Dorit Aharonov, Wim van Dam, Julia Kempe +3 more

Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power was unknown. We describe an efficient adiabatic simulation of any given quantum algorithm, which implies that the adiabatic computation model and the conventional quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models provides a new vantage point from which to tackle the central issues in quantum computation, namely designing new quantum algorithms and constructing fault tolerant quantum computers. In particular, by translating the main open questions in the area of quantum algorithms to the language of spectral gaps of sparse matrices, the result makes these questions accessible to a wider scientific audience, acquainted with mathematical physics, expander theory and rapidly mixing Markov chains.

arXiv:quant-ph/0405098•May 18, 2004•165 citations

Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation

Dorit Aharonov, Wim van Dam, Julia Kempe +3 more

The model of adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its exact computational power has been unknown. We settle this question and describe an efficient adiabatic simulation of any given quantum algorithm. This implies that the adiabatic computation model and the standard quantum circuit model are polynomially equivalent. We also describe an extension of this result with implications to physical implementations of adiabatic computation. We believe that our result highlights the potential importance of the adiabatic computation model in the design of quantum algorithms and in their experimental realization.

Annual Symposium on Foundations of Computer Science•Dec 23, 2004•185 citations

Simulating quantum circuits by adiabatic computation: Improved spectral gap bounds

Shane Dooley, Graham Kells, Hosho Katsura +1 more

Adiabatic quantum computing is a framework for quantum computing that is superficially very different to the standard circuit model. However, it can be shown that the two models are computationally equivalent. The key to the proof is a mapping of a quantum circuit to an adiabatic evolution, and then showing that the minimum spectral gap of the adiabatic Hamiltonian is at least inverse polynomial in the number of computational steps $L$. In this paper we provide two simplified proofs that the gap is inverse polynomial. Both proofs result in the same lower bound for the minimum gap, which for $L\ensuremath{\gg}1$ is ${min}_{s}{\mathrm{\ensuremath{\Delta}}}_{0}\ensuremath{\gtrsim}{\ensuremath{\pi}}^{2}/[8{(L+1)}^{2}]$, an improvement over previous bounds. Our first method is a direct approach based on an eigenstate ansatz, while the second uses Weyl's theorem to leverage known exact results into a bound for the gap. Our results suggest that it may be possible to use these methods to find bounds for spectral gaps of Hamiltonians in other scenarios.

arXiv:1906.05233•Physical Review A•Apr 1, 2020•5 citations

Adiabatic quantum computation: Noise in the adiabatic theorem and using the Jordan -Wigner transform to find effective Hamiltonians

Michael J. O’Hara

This thesis explores two mathematical aspects of adiabatic quantum computation. Adiabatic quantum computation depends on the adiabatic theorem of quantum mechanics, and (a) we provide a rigorous formulation of the adiabatic theorem with explicit definitions of constants, and (b) we bound error in the adiabatic approximation under conditions of noise and experimental error. We apply the new results to a standard example of violation of the adiabatic approximation, and to a superconducting flux qubit. Further, adiabatic quantum computation requires large ground-state energy gaps throughout a Hamiltonian evolution if it is to solve problems in polynomial time. We identify a class of random Hamiltonians with non-nearest-neighbor interactions and a ground-state energy gap of $\mathcal{O}(1/\sqrt{n})$, where $n$ is the number of qubits. We also identify two classes of Hamiltonians with non-nearest-neighbor interactions whose ground state can be found in polynomial time with adiabatic quantum computing. We then use the Jordan-Wigner transformation to derive equivalent results for Hamiltonians defined using Pauli operators.

•Apr 22, 2008•0 citations

SIGEST

The Monaldi Archives for Chest Disease Editors

This issue's SIGEST paper, from the SIAM Journal on Computing (SICOMP), takes SIAM readers into the world of quantum computing, a world with its roots in physics that still probably is better known to many physicists and theoretical computer scientists than to a good portion of SIAM readers. Quantum computation is a form of computing based upon quantum mechanics, rather than the classical physics that conventional computers utilize. The distinction between conventional and quantum computers starts to become apparent at the most basic level of bits: whereas standard computers utilize binary bits that may have either the state 0 or 1, quantum computers are based upon “qubits” (quantum binary digits) that may have the state 0, 1, or a superposition of these two states with a complex number that specifies the probability for being in each state. Mathematically, the state of a quantum computer can change through a sequence of unitary transformations to the initial state. One reason for the great interest in quantum computation is that it has been shown that quantum computers can solve some important problems, such as the factorization of very large integers (which has important implications for cryptography), far more efficiently than we currently are able to solve these problems on conventional computers. The selected paper, “Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation” by Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev, which was originally published in SICOMP in 2007, establishes an important theoretical result in the field of quantum computation. As the title indicates, it involves adiabatic quantum computation, a form of quantum computing that has attracted interest in recent years in part because it may offer promise in the effort to build effective quantum computers. Adiabatic quantum computation is distinctly different from standard quantum computation. In the standard model, computations are represented similarly to classical circuits, except that the circuits carry qubits instead of bits. In contrast, the adiabatic model is inspired by the adiabatic theorem in quantum mechanics which states that a system in its lowest energy or ground state will remain in that state if it is subjected to conditions that change sufficiently slowly. It already was known that standard quantum computers can efficiently simulate adiabatic quantum computers. The key contribution of this paper is to show the reverse: that adiabatic quantum computation can efficiently simulate standard quantum computation. In the words of the SICOMP editorial board in nominating this paper, “This is a surprising result that continues to be very influential.” It established that the two forms of quantum computation are theoretically equivalent, one implication of which is to bolster the potential practical importance of adiabatic quantum computation. The paper by Aharonov et al. is very nicely suited to SIGEST—it is important in its field, it is nicely and accessibly written, it offers a glimpse into an area of applied mathematics and computation that is of growing importance, and it touches on many areas of applied mathematics, including linear algebra, Markov chains, and optimization. We hope it will provide SIAM readers a glimpse of current theoretical research that may, some day, help lead to a brave new world of practical computation.

SIAM Review•Jan 1, 2008•0 citations
Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power was unknown. We describe an efficient adiabatic simulation of any given quantum algorithm, which implies that the adiabatic computation model and the conventional quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two‐dimensional grid with nearest neighbor interactions. The equivalence between the models allows stating the main open problems in quantum computation using well‐studied mathematical objects such as eigenvectors and spectral gaps of sparse matrices.
The model of adiabatic quantum computation is a relatively recent model of quantum computation that has attracted attention in the physics and computer science communities. We describe an efficient adiabatic simulation of any given quantum circuit. This implies that the adiabatic computation model and the standard circuit-based quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models allows one to state the main open problems in quantum computation using well-studied mathematical objects such as eigenvectors and spectral gaps of Hamiltonians.
Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power was unknown. We describe an efficient adiabatic simulation of any given quantum algorithm, which implies that the adiabatic computation model and the conventional quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models provides a new vantage point from which to tackle the central issues in quantum computation, namely designing new quantum algorithms and constructing fault tolerant quantum computers. In particular, by translating the main open questions in the area of quantum algorithms to the language of spectral gaps of sparse matrices, the result makes these questions accessible to a wider scientific audience, acquainted with mathematical physics, expander theory and rapidly mixing Markov chains.
The model of adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its exact computational power has been unknown. We settle this question and describe an efficient adiabatic simulation of any given quantum algorithm. This implies that the adiabatic computation model and the standard quantum circuit model are polynomially equivalent. We also describe an extension of this result with implications to physical implementations of adiabatic computation. We believe that our result highlights the potential importance of the adiabatic computation model in the design of quantum algorithms and in their experimental realization.
Adiabatic quantum computing is a framework for quantum computing that is superficially very different to the standard circuit model. However, it can be shown that the two models are computationally equivalent. The key to the proof is a mapping of a quantum circuit to an adiabatic evolution, and then showing that the minimum spectral gap of the adiabatic Hamiltonian is at least inverse polynomial in the number of computational steps LLL. In this paper we provide two simplified proofs that the gap is inverse polynomial. Both proofs result in the same lower bound for the minimum gap, which for $L\ensuremath{\gg}1$ is ${min}_{s}{\mathrm{\ensuremath{\Delta}}}_{0}\ensuremath{\gtrsim}{\ensuremath{\pi}}^{2}/[8{(L+1)}^{2}]$, an improvement over previous bounds. Our first method is a direct approach based on an eigenstate ansatz, while the second uses Weyl's theorem to leverage known exact results into a bound for the gap. Our results suggest that it may be possible to use these methods to find bounds for spectral gaps of Hamiltonians in other scenarios.
This thesis explores two mathematical aspects of adiabatic quantum computation. Adiabatic quantum computation depends on the adiabatic theorem of quantum mechanics, and (a) we provide a rigorous formulation of the adiabatic theorem with explicit definitions of constants, and (b) we bound error in the adiabatic approximation under conditions of noise and experimental error. We apply the new results to a standard example of violation of the adiabatic approximation, and to a superconducting flux qubit. Further, adiabatic quantum computation requires large ground-state energy gaps throughout a Hamiltonian evolution if it is to solve problems in polynomial time. We identify a class of random Hamiltonians with non-nearest-neighbor interactions and a ground-state energy gap of O(1/n)\mathcal{O}(1/\sqrt{n})O(1/n​), where nnn is the number of qubits. We also identify two classes of Hamiltonians with non-nearest-neighbor interactions whose ground state can be found in polynomial time with adiabatic quantum computing. We then use the Jordan-Wigner transformation to derive equivalent results for Hamiltonians defined using Pauli operators.
This issue's SIGEST paper, from the SIAM Journal on Computing (SICOMP), takes SIAM readers into the world of quantum computing, a world with its roots in physics that still probably is better known to many physicists and theoretical computer scientists than to a good portion of SIAM readers. Quantum computation is a form of computing based upon quantum mechanics, rather than the classical physics that conventional computers utilize. The distinction between conventional and quantum computers starts to become apparent at the most basic level of bits: whereas standard computers utilize binary bits that may have either the state 0 or 1, quantum computers are based upon “qubits” (quantum binary digits) that may have the state 0, 1, or a superposition of these two states with a complex number that specifies the probability for being in each state. Mathematically, the state of a quantum computer can change through a sequence of unitary transformations to the initial state. One reason for the great interest in quantum computation is that it has been shown that quantum computers can solve some important problems, such as the factorization of very large integers (which has important implications for cryptography), far more efficiently than we currently are able to solve these problems on conventional computers. The selected paper, “Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation” by Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev, which was originally published in SICOMP in 2007, establishes an important theoretical result in the field of quantum computation. As the title indicates, it involves adiabatic quantum computation, a form of quantum computing that has attracted interest in recent years in part because it may offer promise in the effort to build effective quantum computers. Adiabatic quantum computation is distinctly different from standard quantum computation. In the standard model, computations are represented similarly to classical circuits, except that the circuits carry qubits instead of bits. In contrast, the adiabatic model is inspired by the adiabatic theorem in quantum mechanics which states that a system in its lowest energy or ground state will remain in that state if it is subjected to conditions that change sufficiently slowly. It already was known that standard quantum computers can efficiently simulate adiabatic quantum computers. The key contribution of this paper is to show the reverse: that adiabatic quantum computation can efficiently simulate standard quantum computation. In the words of the SICOMP editorial board in nominating this paper, “This is a surprising result that continues to be very influential.” It established that the two forms of quantum computation are theoretically equivalent, one implication of which is to bolster the potential practical importance of adiabatic quantum computation. The paper by Aharonov et al. is very nicely suited to SIGEST—it is important in its field, it is nicely and accessibly written, it offers a glimpse into an area of applied mathematics and computation that is of growing importance, and it touches on many areas of applied mathematics, including linear algebra, Markov chains, and optimization. We hope it will provide SIAM readers a glimpse of current theoretical research that may, some day, help lead to a brave new world of practical computation.