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:1611.04471 · Reviews of Modern Physics

Adiabatic quantum computation

Tameem Albash, Daniel A. Lidar

Published Jan 29, 2018• 1,546 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/revmodphys.90.015002

Related papers

From quantum circuits to adiabatic algorithms

M. Stewart Siu

This paper explores several aspects of the adiabatic quantum-computation model. We first show a way that directly maps any arbitrary circuit in the standard quantum-computing model to an adiabatic algorithm of the same depth. Specifically, we look for a smooth time-dependent Hamiltonian whose unique ground state slowly changes from the initial state of the circuit to its final state. Since this construction requires in general an $n$-local Hamiltonian, we will study whether approximation is possible using previous results on ground-state entanglement and perturbation theory. Finally we will point out how the adiabatic model can be relaxed in various ways to allow for 2-local partially adiabatic algorithms as well as 2-local holonomic quantum algorithms.

arXiv:quant-ph/0409024•Physical Review A•Jun 14, 2005•35 citations

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

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

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.

arXiv:quant-ph/0609067•Physical Review Letters•Aug 16, 2007•218 citations

Case studies in quantum adiabatic optimization

David Gosset

Quantum adiabatic optimization is a quantum algorithm for solving classical optimization problems (E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum computation by adiabatic evolution, 2000. arXiv:quant-ph/0001106). The solution to an optimization prob-lem is encoded in the ground state of a "problem Hamiltonian " Hp which acts on the Hilbert space of n spin 1/2 particles and is diagonal in the Pauli z basis. To produce this ground state, one first initializes the quantum system in the ground state of a different Hamiltonian and then adiabatically changes the Hamiltonian into Hp. Farhi et al suggest the interpolating Hamiltonian i where the parameter s is slowly changed as a function of time between 0 and 1. The running time of this algorithm is related to the minimum spectral gap of H(s) for s E (0, 11. We study such transverse field spin Hamiltonians using both analytic and numerical techniques. Our approach is example-based, that is, we study some specific choices for the problem Hamiltonian Hp which illustrate the breadth of phenomena which can occur. We

•Jan 1, 2011•1 citation

Optimality of Quantum Adiabatic Search Algorithm and Its Circuit Model

Jie Sun, Zhimin Zhang, Songfeng Lu

In this paper, we study two aspects of quantum adiabatic evolution for a prototypical search problem: the optimality of the corresponding algorithm and its relation to the quantum circuit model. Firstly, we propose a general framework for proving the square-root speedup of the quantum adiabatic algorithm to be optimal over classical computation, which is readily applicable to the case of multiple targets. Through this framework, we also find that it is possible to further reduce the time complexity by increasing the physical energy of the system, encompassing results from previous works. Secondly, we find that, on the one hand, when the quantum adiabatic algorithm that achieves quadratic speedup is implemented on a quantum circuit, the time slice needed is always consistent with its time complexity, which also encompasses previous results; on the other hand, however, if a further algorithmic improvement is considered, the time slice always remains invariant. This phenomenon represents a significant observation with potential applications. We anticipate that the main results of this paper will interest the quantum adiabatic computation community and may help us to design efficient quantum algorithms for practical problems in the future.

Quantum Reports•Mar 26, 2026•2 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•64 citations

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

Edward Farhi, Jeffrey Goldstone, Sam Gutmann +3 more

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.

arXiv:quant-ph/0104129•Science•Apr 20, 2001•2,055 citations
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.
This paper explores several aspects of the adiabatic quantum-computation model. We first show a way that directly maps any arbitrary circuit in the standard quantum-computing model to an adiabatic algorithm of the same depth. Specifically, we look for a smooth time-dependent Hamiltonian whose unique ground state slowly changes from the initial state of the circuit to its final state. Since this construction requires in general an nnn-local Hamiltonian, we will study whether approximation is possible using previous results on ground-state entanglement and perturbation theory. Finally we will point out how the adiabatic model can be relaxed in various ways to allow for 2-local partially adiabatic algorithms as well as 2-local holonomic quantum algorithms.
Quantum adiabatic optimization is a quantum algorithm for solving classical optimization problems (E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum computation by adiabatic evolution, 2000. arXiv:quant-ph/0001106). The solution to an optimization prob-lem is encoded in the ground state of a "problem Hamiltonian " Hp which acts on the Hilbert space of n spin 1/2 particles and is diagonal in the Pauli z basis. To produce this ground state, one first initializes the quantum system in the ground state of a different Hamiltonian and then adiabatically changes the Hamiltonian into Hp. Farhi et al suggest the interpolating Hamiltonian i where the parameter s is slowly changed as a function of time between 0 and 1. The running time of this algorithm is related to the minimum spectral gap of H(s) for s E (0, 11. We study such transverse field spin Hamiltonians using both analytic and numerical techniques. Our approach is example-based, that is, we study some specific choices for the problem Hamiltonian Hp which illustrate the breadth of phenomena which can occur. We
In this paper, we study two aspects of quantum adiabatic evolution for a prototypical search problem: the optimality of the corresponding algorithm and its relation to the quantum circuit model. Firstly, we propose a general framework for proving the square-root speedup of the quantum adiabatic algorithm to be optimal over classical computation, which is readily applicable to the case of multiple targets. Through this framework, we also find that it is possible to further reduce the time complexity by increasing the physical energy of the system, encompassing results from previous works. Secondly, we find that, on the one hand, when the quantum adiabatic algorithm that achieves quadratic speedup is implemented on a quantum circuit, the time slice needed is always consistent with its time complexity, which also encompasses previous results; on the other hand, however, if a further algorithmic improvement is considered, the time slice always remains invariant. This phenomenon represents a significant observation with potential applications. We anticipate that the main results of this paper will interest the quantum adiabatic computation community and may help us to design efficient quantum algorithms for practical problems in the future.
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 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.