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:1202.3646 · Physical Review Letters

Quantum Adiabatic Algorithm and Scaling of Gaps at First-Order Quantum Phase Transitions

Chris R. Laumann, Roderich Moessner, Antonello Scardicchio, Shivaji L. Sondhi

Published Jul 19, 2012• 71 citations
arXivHTMLPDF

Abstract

Motivated by the quantum adiabatic algorithm (QAA), we consider the scaling of the Hamiltonian gap at quantum first-order transitions, generally expected to be exponentially small in the size of the system. However, we show that a quantum antiferromagnetic Ising chain in a staggered field can exhibit a first-order transition with only an algebraically small gap. In addition, we construct a simple classical translationally invariant one-dimensional Hamiltonian containing nearest-neighbor interactions only, which exhibits an exponential gap at a thermodynamic quantum first-order transition of essentially topological origin. This establishes that (i) the QAA can be successful even across first-order transitions but also that (ii) it can fail on exceedingly simple problems readily solved by inspection, or by classical annealing.

DOI
10.1103/physrevlett.109.030502

Related papers

Numerical Studies of the Quantum Adiabatic Algorithm

A. P. Young, Itay Hen

Quantum annealers promise to solve practical optimization problems potentially faster than conventional classical computers. One of the major ongoing debates in this context pertains to their robustness against the decohering effects of finite temperature and interactions with the environment. We argue that even in an ideal setting of very low temperatures and in the absence of a decohering environment, quantum annealers do not necessarily perform better than classical heuristic solvers. Here, we numerically study the performance of the quantum adiabatic algorithm (QAA) on a variety of constraint satisfaction problems and a spin glass problem by studying the size dependence of the minimum energy gap during the evolution of the QAA. We do so by employing Quantum Monte Carlo schemes as these allow us to study these problems at much larger scales than exact methods would allow. We find that in all cases a quantum phase transition occurs and the minimum gap decreases exponentially with system size, leading to an exponentially large running time for the QAA. Based on these and other results, we briefly discuss potential modifications to the QAA that may improve the scaling of the minimum gap, leading to faster quantum adiabatic algorithms.

Journal of Physics Conference Series•Sep 28, 2015•0 citations

First-Order Phase Transition in the Quantum Adiabatic Algorithm

A. P. Young, Sergey Knysh, Vadim Smelyanskiy

We simulate the quantum adiabatic algorithm (QAA) for the exact cover problem for sizes up to N=256 using quantum Monte Carlo simulations incorporating parallel tempering. At large N, we find that some instances have a discontinuous (first-order) quantum phase transition during the evolution of the QAA. This fraction increases with increasing N and may tend to 1 for N-->infinity.

arXiv:0910.1378•Physical Review Letters•Jan 14, 2010•171 citations

First-Order Transitions and the Performance of Quantum Algorithms in Random Optimization Problems

Thomas Jörg, Florent Krząkała, Guilhem Semerjian +1 more

We present a study of the phase diagram of a random optimization problem in the presence of quantum fluctuations. Our main result is the characterization of the nature of the phase transition, which we find to be a first-order quantum phase transition. We provide evidence that the gap vanishes exponentially with the system size at the transition. This indicates that the quantum adiabatic algorithm requires a time growing exponentially with system size to find the ground state of this problem.

arXiv:0911.3438•Physical Review Letters•May 20, 2010•100 citations

Bounding first-order quantum phase transitions in adiabatic quantum computing

Matthias Werner, Artur García-Sáez, Marta P. Estarellas

In the context of adiabatic quantum computation (AQC), it has been argued that first-order quantum phase transitions (QPTs) due to localization phenomena cause AQC to fail by exponentially decreasing the minimal spectral gap of the Hamiltonian along the annealing path as a function of the qubit number. The vanishing of the spectral gap is often linked to the localization of the ground state in a local minimum, requiring the system to tunnel into the global minimum at a later stage of the annealing. Recent methods have been proposed to avoid this phenomenon by carefully designing the involved Hamiltonians. However, it remains a challenge to formulate a comprehensive theory of the effect of the various parameters and the conditions under which QPTs make the AQC algorithm fail. Equipped with concepts from graph theory, in this work we link graph quantities associated with the Hamiltonians along the annealing path with the occurrence of QPTs. These links allow us to derive bounds on the location of the minimal spectral gap along the annealing path, augmenting the toolbox for the analysis of strategies to improve the runtime of AQC algorithms.

arXiv:2301.13861•Physical Review Research•Dec 13, 2023•7 citations

The quantum adiabatic optimization algorithm and local minima

Ben W. Reichardt

The quantum adiabatic optimization algorithm uses the adiabatic theorem from quantum physics to minimize a function by interpolation between two Hamiltonians. The quantum wave function can sometimes tunnel through significant obstacles. However it can also sometimes get stuck in local minima, even for fairly simple problems. An initial Hamiltonian which insufficiently mixes computational basis states is analogous to a poorly mixing Markov transition rule. We study a physical system -- the Ising quantum chain with alternating sector interaction defects, but constant transverse field -- which is equivalent to applying the quantum adiabatic algorithm to a particular SAT problem. We prove that for a constant range of values for the transverse field, the spectral gap is exponentially small in the sector length. Indeed, we prove that there are exponentially many eigenvalues all exponentially close to the ground state energy. Applying the adiabatic theorem therefore takes exponential time, even for this simple problem.

ACM Symposium on Theory of Computing (STOC)•Jun 13, 2004•110 citations

The role of symmetries in adiabatic quantum algorithms

Gernot Schaller, Ralf Schützhold

Exploiting the similarity between adiabatic quantum algorithms and quantum phase transitions, we argue that second-order transitions -- typically associated with broken or restored symmetries -- should be advantageous in comparison to first-order transitions. Guided by simple examples we construct an alternative adiabatic algorithm for the NP-complete problem {\em Exact Cover 3}. We show numerically that its average performance (for the considered cases up to ${\cal O}\{20\}$ qubits) is better than that of the conventional scheme. The run-time of adiabatic algorithms is not just determined by the minimum value of the fundamental energy gap (between the ground state and the exited states), but also by its curvature at the critical point. The proposed symmetry-restoring adiabatic quantum algorithm only contains contributions linear and quadratic in the Pauli matrices and can be generalized to other problem Hamiltonians which are decomposed of terms involving one and two qubits. We show how the factoring problem can be cast into such a quadratic form. These findings suggest that adiabatic quantum algorithms can solve a large class of NP problems much faster than the Grover search routine (which corresponds to a first-order transition and yields a quadratic enhancement only).

arXiv:0708.1882•Aug 14, 2007•7 citations
Motivated by the quantum adiabatic algorithm (QAA), we consider the scaling of the Hamiltonian gap at quantum first-order transitions, generally expected to be exponentially small in the size of the system. However, we show that a quantum antiferromagnetic Ising chain in a staggered field can exhibit a first-order transition with only an algebraically small gap. In addition, we construct a simple classical translationally invariant one-dimensional Hamiltonian containing nearest-neighbor interactions only, which exhibits an exponential gap at a thermodynamic quantum first-order transition of essentially topological origin. This establishes that (i) the QAA can be successful even across first-order transitions but also that (ii) it can fail on exceedingly simple problems readily solved by inspection, or by classical annealing.
Quantum annealers promise to solve practical optimization problems potentially faster than conventional classical computers. One of the major ongoing debates in this context pertains to their robustness against the decohering effects of finite temperature and interactions with the environment. We argue that even in an ideal setting of very low temperatures and in the absence of a decohering environment, quantum annealers do not necessarily perform better than classical heuristic solvers. Here, we numerically study the performance of the quantum adiabatic algorithm (QAA) on a variety of constraint satisfaction problems and a spin glass problem by studying the size dependence of the minimum energy gap during the evolution of the QAA. We do so by employing Quantum Monte Carlo schemes as these allow us to study these problems at much larger scales than exact methods would allow. We find that in all cases a quantum phase transition occurs and the minimum gap decreases exponentially with system size, leading to an exponentially large running time for the QAA. Based on these and other results, we briefly discuss potential modifications to the QAA that may improve the scaling of the minimum gap, leading to faster quantum adiabatic algorithms.
In the context of adiabatic quantum computation (AQC), it has been argued that first-order quantum phase transitions (QPTs) due to localization phenomena cause AQC to fail by exponentially decreasing the minimal spectral gap of the Hamiltonian along the annealing path as a function of the qubit number. The vanishing of the spectral gap is often linked to the localization of the ground state in a local minimum, requiring the system to tunnel into the global minimum at a later stage of the annealing. Recent methods have been proposed to avoid this phenomenon by carefully designing the involved Hamiltonians. However, it remains a challenge to formulate a comprehensive theory of the effect of the various parameters and the conditions under which QPTs make the AQC algorithm fail. Equipped with concepts from graph theory, in this work we link graph quantities associated with the Hamiltonians along the annealing path with the occurrence of QPTs. These links allow us to derive bounds on the location of the minimal spectral gap along the annealing path, augmenting the toolbox for the analysis of strategies to improve the runtime of AQC algorithms.
The quantum adiabatic optimization algorithm uses the adiabatic theorem from quantum physics to minimize a function by interpolation between two Hamiltonians. The quantum wave function can sometimes tunnel through significant obstacles. However it can also sometimes get stuck in local minima, even for fairly simple problems. An initial Hamiltonian which insufficiently mixes computational basis states is analogous to a poorly mixing Markov transition rule. We study a physical system -- the Ising quantum chain with alternating sector interaction defects, but constant transverse field -- which is equivalent to applying the quantum adiabatic algorithm to a particular SAT problem. We prove that for a constant range of values for the transverse field, the spectral gap is exponentially small in the sector length. Indeed, we prove that there are exponentially many eigenvalues all exponentially close to the ground state energy. Applying the adiabatic theorem therefore takes exponential time, even for this simple problem.
Exploiting the similarity between adiabatic quantum algorithms and quantum phase transitions, we argue that second-order transitions -- typically associated with broken or restored symmetries -- should be advantageous in comparison to first-order transitions. Guided by simple examples we construct an alternative adiabatic algorithm for the NP-complete problem {\em Exact Cover 3}. We show numerically that its average performance (for the considered cases up to O{20}{\cal O}\{20\}O{20} qubits) is better than that of the conventional scheme. The run-time of adiabatic algorithms is not just determined by the minimum value of the fundamental energy gap (between the ground state and the exited states), but also by its curvature at the critical point. The proposed symmetry-restoring adiabatic quantum algorithm only contains contributions linear and quadratic in the Pauli matrices and can be generalized to other problem Hamiltonians which are decomposed of terms involving one and two qubits. We show how the factoring problem can be cast into such a quadratic form. These findings suggest that adiabatic quantum algorithms can solve a large class of NP problems much faster than the Grover search routine (which corresponds to a first-order transition and yields a quadratic enhancement only).