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/0609067 · Physical Review Letters

Simple Proof of Equivalence between Adiabatic Quantum Computation and the Circuit Model

Ari Mizel, Daniel A. Lidar, Morgan W. Mitchell

Published Aug 16, 2007• 218 citations
arXivHTMLPDF

Abstract

We prove the equivalence between adiabatic quantum computation and quantum computation in the circuit model. An explicit adiabatic computation procedure is given that generates a ground state from which the answer can be extracted. The amount of time needed is evaluated by computing the gap. We show that the procedure is computationally efficient.

DOI
10.1103/physrevlett.99.070502

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•395 citations

Adiabatic quantum computation

Tameem Albash, Daniel A. Lidar

The simple act of slowly varying the parameters of a quantum system so that it remains always in its ground state is extremely rich from an information processing point of view. For an ideal, closed system, this adiabatic evolution is equivalent to full quantum computation, and it is convenient for establishing quantum algorithms for optimization. This review presents adiabatic quantum algorithms, proves the closed-system equivalence of the adiabatic and circuit models of quantum computation, reviews the placement of adiabatic quantum computation in the more general classification of computational complexity theory, and discusses the case of ``stoquastic'' quantum evolutions.

arXiv:1611.04471•Reviews of Modern Physics•Jan 29, 2018•1,546 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

An Alternative Approach to Construct the Initial Hamiltonian of the Adiabatic Quantum Computation

Qian-Heng Duan, Shuo Zhang, Wei Wu +1 more

The adiabatic quantum computation (AQC) has been proven to be equivalent to the standard circuit model. Conventionally, AQC evolves from the initial Hamiltonian which has a uniform equal superposition of the computational basis to the final Hamiltonian whose ground state encodes the solution to a computation problem. We propose an alternative approach to construct the initial Hamiltonian of the AQC which has an unequal superposition of the possible solutions to the problem and show that an educated guess can improve the performance of AQC.

Chinese Physics Letters•Jan 1, 2013•18 citations

Proof of efficient, parallelized, universal adiabatic quantum computation

Ari Mizel

We give a careful proof that a parallelized version of adiabatic quantum computation can efficiently simulate universal gate model quantum computation. The proof specifies an explicit parameter-dependent Hamiltonian $H(\ensuremath{\lambda})$ that is based on ground state quantum computation [Mizel et al., Phys. Rev. A. 63, 040302 (2001)]. We treat both a 1-dimensional configuration in which qubits on a line undergo nearest-neighbor 2-qubit gates and an all-to-all configuration in which every qubit undergoes 2-qubit gates with every other qubit in the system.

arXiv:1807.10379•Physical Review A•Feb 12, 2019•6 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•159 citations
We prove the equivalence between adiabatic quantum computation and quantum computation in the circuit model. An explicit adiabatic computation procedure is given that generates a ground state from which the answer can be extracted. The amount of time needed is evaluated by computing the gap. We show that the procedure is computationally efficient.
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.
The simple act of slowly varying the parameters of a quantum system so that it remains always in its ground state is extremely rich from an information processing point of view. For an ideal, closed system, this adiabatic evolution is equivalent to full quantum computation, and it is convenient for establishing quantum algorithms for optimization. This review presents adiabatic quantum algorithms, proves the closed-system equivalence of the adiabatic and circuit models of quantum computation, reviews the placement of adiabatic quantum computation in the more general classification of computational complexity theory, and discusses the case of ``stoquastic'' quantum evolutions.
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.
The adiabatic quantum computation (AQC) has been proven to be equivalent to the standard circuit model. Conventionally, AQC evolves from the initial Hamiltonian which has a uniform equal superposition of the computational basis to the final Hamiltonian whose ground state encodes the solution to a computation problem. We propose an alternative approach to construct the initial Hamiltonian of the AQC which has an unequal superposition of the possible solutions to the problem and show that an educated guess can improve the performance of AQC.
We give a careful proof that a parallelized version of adiabatic quantum computation can efficiently simulate universal gate model quantum computation. The proof specifies an explicit parameter-dependent Hamiltonian $H(\ensuremath{\lambda})$ that is based on ground state quantum computation [Mizel et al., Phys. Rev. A. 63, 040302 (2001)]. We treat both a 1-dimensional configuration in which qubits on a line undergo nearest-neighbor 2-qubit gates and an all-to-all configuration in which every qubit undergoes 2-qubit gates with every other qubit in the system.
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.