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

Size Dependence of the Minimum Excitation Gap in the Quantum Adiabatic Algorithm

A. P. Young, Sergey Knysh, Vadim Smelyanskiy

Published Oct 23, 2008• 127 citations
arXivHTMLPDF

Abstract

We study the typical (median) value of the minimum gap in the quantum version of the exact cover problem using quantum Monte Carlo simulations, in order to understand the complexity of the quantum adiabatic algorithm for much larger sizes than before. For a range of sizes N< or =128, where the classical Davis-Putnam algorithm shows exponential median complexity, the quantum adiabatic algorithm shows polynomial median complexity. The bottleneck of the algorithm is an isolated avoided-crossing point of a Landau-Zener type (collision between the two lowest energy levels only).

DOI
10.1103/physrevlett.101.170503

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

On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm

Sergey Knysh, Vadim Smelyanskiy

Two recent preprints [B. Altshuler, H. Krovi, and J. Roland, "Quantum adiabatic optimization fails for random instances of NP-complete problems", arXiv:0908.2782 and "Anderson localization casts clouds over adiabatic quantum optimization", arXiv:0912.0746] argue that random 4th order perturbative corrections to the energies of local minima of random instances of NP-complete problem lead to avoided crossings that cause the failure of quantum adiabatic algorithm (due to exponentially small gap) close to the end, for very small transverse field that scales as an inverse power of instance size N. The theoretical portion of this work does not to take into account the exponential degeneracy of the ground and excited states at zero field. A corrected analysis shows that unlike those in the middle of the spectrum, avoided crossings at the edge would require high [O(1)] transverse fields, at which point the perturbation theory may become divergent due to quantum phase transition. This effect manifests itself only in large instances [exp(0.02 N) >> 1], which might be the reason it had not been observed in the authors' numerical work. While we dispute the proposed mechanism of failure of quantum adiabatic algorithm, we cannot draw any conclusions on its ultimate complexity.

arXiv:1005.3011•May 17, 2010•21 citations

Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems

Itay Hen, A. P. Young

We determine the complexity of several constraint satisfaction problems using the quantum adiabatic algorithm in its simplest implementation. We do so by studying the size dependence of the gap to the first excited state of "typical" instances. We find that, at large sizes N, the complexity increases exponentially for all models that we study. We also compare our results against the complexity of the analogous classical algorithm WalkSAT and show that the harder the problem is for the classical algorithm, the harder it is also for the quantum adiabatic algorithm.

arXiv:1109.6872•Physical Review E•Dec 29, 2011•89 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

The performance of the quantum adiabatic algorithm on spike Hamiltonians

Linghang Kong, Elizabeth Crosson

Spike Hamiltonians arise from optimization instances for which the adiabatic algorithm provably out performs classical simulated annealing. In this work, we study the efficiency of the adiabatic algorithm for solving the “the Hamming weight with a spike” problem by analyzing the scaling of the spectral gap at the critical point for various sizes of the barrier. Our main result is a rigorous lower bound on the minimum spectral gap for the adiabatic evolution when the bit-symmetric cost function has a thin but polynomially high barrier, which is based on a comparison argument and an improved variational ansatz for the ground state. We also adapt the discrete WKB method for the case of abruptly changing potentials and compare it with the predictions of the spin coherent instanton method which was previously used by Farhi, Goldstone and Gutmann. Finally, our improved ansatz for the ground state leads to a method for predicting the location of avoided crossings in the excited energy states of the thin spike Hamiltonian, and we use a recursion relation to understand the ordering of some of these avoided crossings as a step towards analyzing the previously observed diabatic cascade phenomenon.

arXiv:1511.06991•International Journal of Quantum Information•Feb 7, 2017•17 citations

On the Critical Behaviour, Crossover Point and Complexity of the Exact Cover Problem

Robin D. Morris, Vadim Smelyanskiy, Daniel Shumow +1 more

Research into quantum algorithms for NP-complete problems has rekindled interest in the detailed study a broad class of combinatorial problems. A recent paper applied the quantum adiabatic evolution algorithm to the Exact Cover problem for 3-sets (EC3), and provided an empirical evidence that the algorithm was polynomial. In this paper we provide a detailed study of the characteristics of the exact cover problem. We present the annealing approximation applied to EC3, which gives an over-estimate of the phase transition point. We also identify empirically the phase transition point. We also study the complexity of two classical algorithms on this problem: Davis-Putnam and Simulated Annealing. For these algorithms, EC3 is significantly easier than 3-SAT.

•Apr 10, 2003•0 citations
We study the typical (median) value of the minimum gap in the quantum version of the exact cover problem using quantum Monte Carlo simulations, in order to understand the complexity of the quantum adiabatic algorithm for much larger sizes than before. For a range of sizes N< or =128, where the classical Davis-Putnam algorithm shows exponential median complexity, the quantum adiabatic algorithm shows polynomial median complexity. The bottleneck of the algorithm is an isolated avoided-crossing point of a Landau-Zener type (collision between the two lowest energy levels only).
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.
Two recent preprints [B. Altshuler, H. Krovi, and J. Roland, "Quantum adiabatic optimization fails for random instances of NP-complete problems", arXiv:0908.2782 and "Anderson localization casts clouds over adiabatic quantum optimization", arXiv:0912.0746] argue that random 4th order perturbative corrections to the energies of local minima of random instances of NP-complete problem lead to avoided crossings that cause the failure of quantum adiabatic algorithm (due to exponentially small gap) close to the end, for very small transverse field that scales as an inverse power of instance size N. The theoretical portion of this work does not to take into account the exponential degeneracy of the ground and excited states at zero field. A corrected analysis shows that unlike those in the middle of the spectrum, avoided crossings at the edge would require high [O(1)] transverse fields, at which point the perturbation theory may become divergent due to quantum phase transition. This effect manifests itself only in large instances [exp(0.02 N) >> 1], which might be the reason it had not been observed in the authors' numerical work. While we dispute the proposed mechanism of failure of quantum adiabatic algorithm, we cannot draw any conclusions on its ultimate complexity.
We determine the complexity of several constraint satisfaction problems using the quantum adiabatic algorithm in its simplest implementation. We do so by studying the size dependence of the gap to the first excited state of "typical" instances. We find that, at large sizes N, the complexity increases exponentially for all models that we study. We also compare our results against the complexity of the analogous classical algorithm WalkSAT and show that the harder the problem is for the classical algorithm, the harder it is also for the quantum adiabatic algorithm.
Spike Hamiltonians arise from optimization instances for which the adiabatic algorithm provably out performs classical simulated annealing. In this work, we study the efficiency of the adiabatic algorithm for solving the “the Hamming weight with a spike” problem by analyzing the scaling of the spectral gap at the critical point for various sizes of the barrier. Our main result is a rigorous lower bound on the minimum spectral gap for the adiabatic evolution when the bit-symmetric cost function has a thin but polynomially high barrier, which is based on a comparison argument and an improved variational ansatz for the ground state. We also adapt the discrete WKB method for the case of abruptly changing potentials and compare it with the predictions of the spin coherent instanton method which was previously used by Farhi, Goldstone and Gutmann. Finally, our improved ansatz for the ground state leads to a method for predicting the location of avoided crossings in the excited energy states of the thin spike Hamiltonian, and we use a recursion relation to understand the ordering of some of these avoided crossings as a step towards analyzing the previously observed diabatic cascade phenomenon.
Research into quantum algorithms for NP-complete problems has rekindled interest in the detailed study a broad class of combinatorial problems. A recent paper applied the quantum adiabatic evolution algorithm to the Exact Cover problem for 3-sets (EC3), and provided an empirical evidence that the algorithm was polynomial. In this paper we provide a detailed study of the characteristics of the exact cover problem. We present the annealing approximation applied to EC3, which gives an over-estimate of the phase transition point. We also identify empirically the phase transition point. We also study the complexity of two classical algorithms on this problem: Davis-Putnam and Simulated Annealing. For these algorithms, EC3 is significantly easier than 3-SAT.