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:1506.08608

Computational Bottlenecks of Quantum Annealing

Sergey Knysh

Published Jun 29, 2015• 3 citations
arXivHTMLPDF

Abstract

A promising approach to solving hard binary optimisation problems is quantum adiabatic annealing (QA) in a transverse magnetic field. An instantaneous ground state --- initially a symmetric superposition of all possible assignments of $N$ qubits --- is closely tracked as it becomes more and more localised near the global minimum of the classical energy. Regions where the energy gap to excited states is small (e.g. at the phase transition) are the algorithm's bottlenecks. Here I show how for large problems the complexity becomes dominated by $O(\log N)$ bottlenecks inside the spin glass phase, where the gap scales as a stretched exponential. For smaller $N$, only the gap at the critical point is relevant, where it scales polynomially, as long as the phase transition is second order. This phenomenon is demonstrated rigorously for the two-pattern Gaussian Hopfield Model. Qualitative comparison with the Sherrington-Kirkpatrick Model leads to similar conclusions.

DOI
10.48550/arxiv.1506.08608

Related papers

Zero-temperature quantum annealing bottlenecks in the spin-glass phase

Sergey Knysh

A promising approach to solving hard binary optimization problems is quantum adiabatic annealing in a transverse magnetic field. An instantaneous ground state-initially a symmetric superposition of all possible assignments of N qubits-is closely tracked as it becomes more and more localized near the global minimum of the classical energy. Regions where the energy gap to excited states is small (for instance at the phase transition) are the algorithm's bottlenecks. Here I show how for large problems the complexity becomes dominated by O(log N) bottlenecks inside the spin-glass phase, where the gap scales as a stretched exponential. For smaller N, only the gap at the critical point is relevant, where it scales polynomially, as long as the phase transition is second order. This phenomenon is demonstrated rigorously for the two-pattern Gaussian Hopfield model. Qualitative comparison with the Sherrington-Kirkpatrick model leads to similar conclusions.

Nature Communications•Aug 5, 2016•79 citations

Energy gap of quantum spin glasses: a projection quantum Monte Carlo study

L. Brodoloni, G. E. Astrakharchik, S. Giorgini +1 more

The performance of quantum annealing for combinatorial optimization is fundamentally limited by the minimum energy gap $Δ$ encountered at quantum phase transitions. We investigate the scaling of $Δ$ with system size $N$ for two paradigmatic quantum spin-glass models: the two-dimensional Edwards-Anderson (2D-EA) and the all-to-all Sherrington-Kirkpatrick (SK) models. Utilizing a newly proposed unbiased energy-gap estimator for continuous-time projection quantum Monte Carlo simulations, complemented by high-performance sparse eigenvalue solvers, we characterize the gap distributions across disorder realizations. It is found that, in the 2D-EA case, the inverse-gap distribution develops a fat tail with infinite variance as $N$ increases. This indicates that the unfavorable super-algebraic scaling of $Δ$, recently reported for binary couplings [Nature 631, 749 (2024)], persists for the Gaussian disorder considered here, pointing to a universal feature of 2D spin glasses. Conversely, the SK model retains a finite-variance distribution, with the disorder-averaged gap following a rather slow power law, close to $Δ\propto N^{-1/3}$. This finding provides a promising outlook for the potential efficiency of quantum annealers for optimization problems with dense connectivity.

cond-mat.dis-nnCross-listedarXiv:2602.20108•Physical Review Letters•Feb 24, 2026•0 citations

Quantum annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy

Hiroshi Hayasaka, Takashi Imoto, Yuichiro Matsuzaki +1 more

Quantum annealing (QA) is a method for solving combinatorial optimization problems. We can estimate the computational time for QA using what is referred to as the adiabatic condition derived from the adiabatic theorem. The adiabatic condition consists of two parts: an energy gap and a transition matrix. Most past studies have focused on the relationship between the energy gap and computational time. The success probability of QA is considered to decrease exponentially owing to the exponentially decreasing energy gap at the first-order phase-transition point. In this study, through a detailed analysis of the relationship between the energy gap, transition matrix, and computational cost during QA, we propose a general method for constructing counterintuitive models wherein QA with a constant annealing time fails despite a constant energy gap, based on polynomial energy. We assume that the energy of the total Hamiltonian is at most $\mathrm{\ensuremath{\Theta}}(L)$, where $L$ is the number of qubits. In our formalism, we choose a known model that exhibits an exponentially small energy gap during QA, and modify the model by adding a specific penalty term to the Hamiltonian. In the modified model, the transition matrix in the adiabatic condition becomes exponentially large as the number of qubits increases, while the energy gap remains constant. Moreover, we achieve a quadratic speedup, for which the upper bound for improvement in the adiabatic condition is determined by the polynomial energy. For concrete examples, we consider the adiabatic Grover search and the ferromagnetic $p$-spin model. In these cases, with the addition of the penalty term, although the success probability of QA on the modified models becomes exponentially small despite a constant energy gap, we are able to achieve a success probability considerably higher than that of conventional QA. Moreover, in concrete examples, we numerically show the scaling of the computational cost is quadratically improved compared to the conventional QA. Our findings pave the way for a better understanding of QA performance.

arXiv:2212.09995•Physical Review A•Aug 26, 2024•4 citations

The quantum transition of the two-dimensional Ising spin glass

Massimo Bernaschi, I. González-Adalid Pemartín, Víctor Martín-Mayor +1 more

Abstract Quantum annealers are commercial devices that aim to solve very hard computational problems1, typically those involving spin glasses2,3. Just as in metallurgic annealing, in which a ferrous metal is slowly cooled4, quantum annealers seek good solutions by slowly removing the transverse magnetic field at the lowest possible temperature. Removing the field diminishes the quantum fluctuations but forces the system to traverse the critical point that separates the disordered phase (at large fields) from the spin-glass phase (at small fields). A full understanding of this phase transition is still missing. A debated, crucial question regards the closing of the energy gap separating the ground state from the first excited state. All hopes of achieving an exponential speed-up, compared to classical computers, rest on the assumption that the gap will close algebraically with the number of spins5–9. However, renormalization group calculations predict instead that there is an infinite-randomness fixed point10. Here we solve this debate through extreme-scale numerical simulations, finding that both parties have grasped parts of the truth. Although the closing of the gap at the critical point is indeed super-algebraic, it remains algebraic if one restricts the symmetry of possible excitations. As this symmetry restriction is experimentally achievable (at least nominally), there is still hope for the quantum annealing paradigm11–13.

arXiv:2310.07486•Nature•Jul 10, 2024•35 citations

Stretched Exponential Scaling of Parity-Restricted Energy Gaps in a Random Transverse-Field Ising Model

G. -X. Tang, J. -Z. Zhuang, L. -M. Duan +1 more

The success of a quantum annealing algorithm requires a polynomial scaling of the energy gap. Recently it was shown that a two-dimensional transverse-field Ising model on a square lattice with nearest-neighbor $\pm J$ random coupling has a polynomial energy gap in the symmetric subspace of the parity operator [Nature 631, 749-754 (2024)], indicating the efficient preparation of its ground states by quantum annealing. However, it is not clear if this result can be generalized to other spin glass models with continuous or biased randomness. Here we prove that under general independent and identical distributions (i.i.d.) of the exchange energies, the energy gap of a one-dimensional random transverse-field Ising model follows a stretched exponential scaling even in the parity-restricted subspace. We discuss the implication of this result to quantum annealing problems.

cond-mat.dis-nnCross-listedarXiv:2512.03526•Dec 4, 2025•0 citations

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
A promising approach to solving hard binary optimisation problems is quantum adiabatic annealing (QA) in a transverse magnetic field. An instantaneous ground state --- initially a symmetric superposition of all possible assignments of NNN qubits --- is closely tracked as it becomes more and more localised near the global minimum of the classical energy. Regions where the energy gap to excited states is small (e.g. at the phase transition) are the algorithm's bottlenecks. Here I show how for large problems the complexity becomes dominated by O(log⁡N)O(\log N)O(logN) bottlenecks inside the spin glass phase, where the gap scales as a stretched exponential. For smaller NNN, only the gap at the critical point is relevant, where it scales polynomially, as long as the phase transition is second order. This phenomenon is demonstrated rigorously for the two-pattern Gaussian Hopfield Model. Qualitative comparison with the Sherrington-Kirkpatrick Model leads to similar conclusions.
A promising approach to solving hard binary optimization problems is quantum adiabatic annealing in a transverse magnetic field. An instantaneous ground state-initially a symmetric superposition of all possible assignments of N qubits-is closely tracked as it becomes more and more localized near the global minimum of the classical energy. Regions where the energy gap to excited states is small (for instance at the phase transition) are the algorithm's bottlenecks. Here I show how for large problems the complexity becomes dominated by O(log N) bottlenecks inside the spin-glass phase, where the gap scales as a stretched exponential. For smaller N, only the gap at the critical point is relevant, where it scales polynomially, as long as the phase transition is second order. This phenomenon is demonstrated rigorously for the two-pattern Gaussian Hopfield model. Qualitative comparison with the Sherrington-Kirkpatrick model leads to similar conclusions.
The performance of quantum annealing for combinatorial optimization is fundamentally limited by the minimum energy gap ΔΔΔ encountered at quantum phase transitions. We investigate the scaling of ΔΔΔ with system size NNN for two paradigmatic quantum spin-glass models: the two-dimensional Edwards-Anderson (2D-EA) and the all-to-all Sherrington-Kirkpatrick (SK) models. Utilizing a newly proposed unbiased energy-gap estimator for continuous-time projection quantum Monte Carlo simulations, complemented by high-performance sparse eigenvalue solvers, we characterize the gap distributions across disorder realizations. It is found that, in the 2D-EA case, the inverse-gap distribution develops a fat tail with infinite variance as NNN increases. This indicates that the unfavorable super-algebraic scaling of ΔΔΔ, recently reported for binary couplings [Nature 631, 749 (2024)], persists for the Gaussian disorder considered here, pointing to a universal feature of 2D spin glasses. Conversely, the SK model retains a finite-variance distribution, with the disorder-averaged gap following a rather slow power law, close to Δ∝N−1/3Δ\propto N^{-1/3}Δ∝N−1/3. This finding provides a promising outlook for the potential efficiency of quantum annealers for optimization problems with dense connectivity.
Quantum annealing (QA) is a method for solving combinatorial optimization problems. We can estimate the computational time for QA using what is referred to as the adiabatic condition derived from the adiabatic theorem. The adiabatic condition consists of two parts: an energy gap and a transition matrix. Most past studies have focused on the relationship between the energy gap and computational time. The success probability of QA is considered to decrease exponentially owing to the exponentially decreasing energy gap at the first-order phase-transition point. In this study, through a detailed analysis of the relationship between the energy gap, transition matrix, and computational cost during QA, we propose a general method for constructing counterintuitive models wherein QA with a constant annealing time fails despite a constant energy gap, based on polynomial energy. We assume that the energy of the total Hamiltonian is at most $\mathrm{\ensuremath{\Theta}}(L)$, where LLL is the number of qubits. In our formalism, we choose a known model that exhibits an exponentially small energy gap during QA, and modify the model by adding a specific penalty term to the Hamiltonian. In the modified model, the transition matrix in the adiabatic condition becomes exponentially large as the number of qubits increases, while the energy gap remains constant. Moreover, we achieve a quadratic speedup, for which the upper bound for improvement in the adiabatic condition is determined by the polynomial energy. For concrete examples, we consider the adiabatic Grover search and the ferromagnetic ppp-spin model. In these cases, with the addition of the penalty term, although the success probability of QA on the modified models becomes exponentially small despite a constant energy gap, we are able to achieve a success probability considerably higher than that of conventional QA. Moreover, in concrete examples, we numerically show the scaling of the computational cost is quadratically improved compared to the conventional QA. Our findings pave the way for a better understanding of QA performance.
Abstract Quantum annealers are commercial devices that aim to solve very hard computational problems1, typically those involving spin glasses2,3. Just as in metallurgic annealing, in which a ferrous metal is slowly cooled4, quantum annealers seek good solutions by slowly removing the transverse magnetic field at the lowest possible temperature. Removing the field diminishes the quantum fluctuations but forces the system to traverse the critical point that separates the disordered phase (at large fields) from the spin-glass phase (at small fields). A full understanding of this phase transition is still missing. A debated, crucial question regards the closing of the energy gap separating the ground state from the first excited state. All hopes of achieving an exponential speed-up, compared to classical computers, rest on the assumption that the gap will close algebraically with the number of spins5–9. However, renormalization group calculations predict instead that there is an infinite-randomness fixed point10. Here we solve this debate through extreme-scale numerical simulations, finding that both parties have grasped parts of the truth. Although the closing of the gap at the critical point is indeed super-algebraic, it remains algebraic if one restricts the symmetry of possible excitations. As this symmetry restriction is experimentally achievable (at least nominally), there is still hope for the quantum annealing paradigm11–13.
The success of a quantum annealing algorithm requires a polynomial scaling of the energy gap. Recently it was shown that a two-dimensional transverse-field Ising model on a square lattice with nearest-neighbor ±J\pm J±J random coupling has a polynomial energy gap in the symmetric subspace of the parity operator [Nature 631, 749-754 (2024)], indicating the efficient preparation of its ground states by quantum annealing. However, it is not clear if this result can be generalized to other spin glass models with continuous or biased randomness. Here we prove that under general independent and identical distributions (i.i.d.) of the exchange energies, the energy gap of a one-dimensional random transverse-field Ising model follows a stretched exponential scaling even in the parity-restricted subspace. We discuss the implication of this result to quantum annealing problems.
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.