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/0405098

Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation

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

Published May 18, 2004• 165 citations
arXivHTMLPDF

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 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.

DOI
10.48550/arxiv.quant-ph/0405098

Related papers

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 allows stating the main open problems in quantum computation using well‐studied mathematical objects such as eigenvectors and spectral gaps of sparse matrices.

SIAM Journal on Computing•Jan 1, 2007•474 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 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

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

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

Adiabatic quantum state generation and statistical zero knowledge

Dorit Aharonov, Amnon Ta‐Shma

The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to the problem, by studying the problem of 'quantum state generation'.We first show that any problem in Statistical Zero Knowledge (including eg. discrete log, quadratic residuosity and gap closest vector in a lattice) can be reduced to an instance of the quantum state generation problem. Having shown the generality of the state generation problem, we set the foundations for a new paradigm for quantum state generation. We define 'Adiabatic State Generation' (ASG), which is based on Hamiltonians instead of unitary gates. We develop tools for ASG including a very general method for implementing Hamiltonians (The sparse Hamiltonian lemma), and ways to guarantee non negligible spectral gaps (The jagged adiabatic path lemma). We also prove that ASG is equivalent in power to state generation in the standard quantum model. After setting the foundations for ASG, we show how to apply our techniques to generate interesting superpositions related to Markov chains.The ASG approach to quantum algorithms provides intriguing links between quantum computation and many different areas: the analysis of spectral gaps and groundstates of Hamiltonians in physics, rapidly mixing Markov chains, statistical zero knowledge, and quantum random walks. We hope that these links will bring new insights and methods into quantum algorithms.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2003•353 citations

Adiabatic Quantum State Generation

Dorit Aharonov, Amnon Ta‐Shma

The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to this task by studying the problem of quantum state generation. We motivate this problem by showing that the entire class of statistical zero knowledge, which contains natural candidates for efficient quantum algorithms such as graph isomorphism and lattice problems, can be reduced to the problem of quantum state generation. To study quantum state generation, we define a paradigm which we call adiabatic state generation (ASG) and which is based on adiabatic quantum computation. The ASG paradigm is not meant to replace the standard quantum circuit model or to improve on it in terms of computational complexity. Rather, our goal is to provide a natural theoretical framework, in which quantum state generation algorithms could be designed. The new paradigm seems interesting due to its intriguing links to a variety of different areas: the analysis of spectral gaps and ground‐states of Hamiltonians in physics, rapidly mixing Markov chains, adiabatic computation, and approximate counting. To initiate the study of ASG, we prove several general lemmas that can serve as tools when using this paradigm. We demonstrate the application of the paradigm by using it to turn a variety of (classical) approximate counting algorithms into efficient quantum state generators of nontrivial quantum states, including, for example, the uniform superposition over all perfect matchings in a bipartite graph.

SIAM Journal on Computing•Jan 1, 2007•76 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 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.
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.
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.
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.
The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to the problem, by studying the problem of 'quantum state generation'.We first show that any problem in Statistical Zero Knowledge (including eg. discrete log, quadratic residuosity and gap closest vector in a lattice) can be reduced to an instance of the quantum state generation problem. Having shown the generality of the state generation problem, we set the foundations for a new paradigm for quantum state generation. We define 'Adiabatic State Generation' (ASG), which is based on Hamiltonians instead of unitary gates. We develop tools for ASG including a very general method for implementing Hamiltonians (The sparse Hamiltonian lemma), and ways to guarantee non negligible spectral gaps (The jagged adiabatic path lemma). We also prove that ASG is equivalent in power to state generation in the standard quantum model. After setting the foundations for ASG, we show how to apply our techniques to generate interesting superpositions related to Markov chains.The ASG approach to quantum algorithms provides intriguing links between quantum computation and many different areas: the analysis of spectral gaps and groundstates of Hamiltonians in physics, rapidly mixing Markov chains, statistical zero knowledge, and quantum random walks. We hope that these links will bring new insights and methods into quantum algorithms.
The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to this task by studying the problem of quantum state generation. We motivate this problem by showing that the entire class of statistical zero knowledge, which contains natural candidates for efficient quantum algorithms such as graph isomorphism and lattice problems, can be reduced to the problem of quantum state generation. To study quantum state generation, we define a paradigm which we call adiabatic state generation (ASG) and which is based on adiabatic quantum computation. The ASG paradigm is not meant to replace the standard quantum circuit model or to improve on it in terms of computational complexity. Rather, our goal is to provide a natural theoretical framework, in which quantum state generation algorithms could be designed. The new paradigm seems interesting due to its intriguing links to a variety of different areas: the analysis of spectral gaps and ground‐states of Hamiltonians in physics, rapidly mixing Markov chains, adiabatic computation, and approximate counting. To initiate the study of ASG, we prove several general lemmas that can serve as tools when using this paradigm. We demonstrate the application of the paradigm by using it to turn a variety of (classical) approximate counting algorithms into efficient quantum state generators of nontrivial quantum states, including, for example, the uniform superposition over all perfect matchings in a bipartite graph.