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:1909.00322 · Physical Review A

Noise amplification at spin-glass bottlenecks of quantum annealing: A solvable model

David Roberts, Łukasz Cincio, Avadh Saxena, A. G. Petukhov, Sergey Knysh

Published Apr 16, 2020• 11 citations
arXivHTMLPDF

Abstract

To gain better insight into the complexity theory of quantum annealing, we propose and solve a class of spin systems which contain bottlenecks of the kind expected to dominate the runtime of quantum annealing as it tries to solve difficult optimization problems. We uncover a noise amplification effect at these bottlenecks, whereby tunneling rates caused by flux-qubit noise scale in proportion to the number of qubits $\mathcal{N}$ in the limit that $\mathcal{N}\ensuremath{\rightarrow}\ensuremath{\infty}$. By solving the incoherent annealing dynamics exactly, we find a wide range of regimes where the probability that a quantum annealer remains in the ground state upon exiting the bottleneck is close to one-half. We corroborate our analysis with detailed simulations of the performance of the D-Wave 2X quantum annealer on our class of computational problems.

DOI
10.1103/physreva.101.042317

Related papers

Computational Bottlenecks of Quantum Annealing

Sergey Knysh

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.

arXiv:1506.08608•Jun 29, 2015•3 citations

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

Reaching states below the threshold energy in spin glasses via quantum annealing

Christopher L. Baldwin

Although quantum annealing is usually considered as a method for locating the ground states of difficult spin-glass and optimization problems, its use in approximate optimization -- finding low- but not zero-energy states in a reasonably short amount of time -- is no less important. Here we investigate the behavior of quantum annealing at approximate optimization in the canonical mean-field spin-glass models, the spherical $p$-spin models, and find that it performs surprisingly well. Whereas it had long been assumed that infinite-range spin glasses have a unique ``threshold'' energy at which all quench and annealing dynamics become trapped until exponential timescales, recent work has shown that two-stage quenches can in fact reach states below the naive threshold in more generic situations. We demonstrate that quantum annealing is also capable of exploiting this effect to locate sub-threshold states in $O(1)$ time. Not only can it attain energies as far below the threshold as classical annealing algorithms, but it can do so significantly faster: for an annealing schedule taking time $τ$, the residual energy under quantum annealing decays as $τ^{-α}$ with an exponent up to twice as large as that of simulated annealing in the cases considered. Importantly, by deriving and numerically solving closed integro-differential equations that hold in the thermodynamic limit, our results are free from finite-size effects and hold for annealing times that are unambiguously independent of system size.

quant-pharXiv:2603.23602•Mar 26, 2026•0 citations

Adiabatic bottlenecks in quantum annealing and nonequilibrium dynamics of paramagnons

Tim Bode, Frank K. Wilhelm

The correspondence between long-range interacting quantum spin glasses and combinatorial optimization problems underpins the physical motivation for adiabatic quantum computing. On one hand, in disordered (quantum) spin systems, the focus is on exact methods such as the replica trick that allow the calculation of system quantities in the limit of infinite system and ensemble size. On the other hand, when solving a given instance of an optimization problem, disorder-averaged quantities are of no relevance, as one is solely interested in instance-specific, finite-size properties, in particular the optimal solution. Here, we apply the nonequilibrium Green's function formalism to the spin coherent-state path integral to obtain the statistical fluctuations and the collective-excitation spectrum along the annealing path. For the example of the quantum Sherrington-Kirkpatrick spin glass, by comparing to extensive numerically exact results, we show that this method provides access to the instance-specific bottlenecks of the annealing protocol.

arXiv:2403.11548•Physical Review A•Jul 12, 2024•4 citations

Nonstoquastic Hamiltonians and quantum annealing of an Ising spin glass

Layla Hormozi, Ethan Brown, Giuseppe Carleo +1 more

Quantum annealers are computing machines that utilize quantum effects to solve hard optimization problems. Understanding the circumstances under which quantum annealers are more efficient than other optimization methods is a challenging open problem. A clue to this conundrum comes from studying the complexity of quantum annealers. In general, the complexity of a physical system relates to how efficiently the system can be simulated by classical algorithms. One then asks: if some class of quantum annealers are hard to simulate classically, are they also more powerful optimization machines? Here, the authors study quantum annealers belonging to two different complexity classes: the so-called ``stoquastic'' systems, which can be efficiently simulated with classical algorithms, and ``nonstoquastic'' systems, currently with no efficient classical treatment. Applied to a prototypical optimization problem, the authors observe that, on average, the stoquastic systems perform better on easier instances of the problem, while the more complex nonstoquastic annealers show significant advantage when applied to the hardest instances. The authors conjecture that the performance of the nonstoquastic Hamiltonians is closely related to their internal structure during the annealing process and elucidate how properties such as magnetic frustration can play a key role in devising more powerful quantum annealers.

arXiv:1609.06558•Physical review. B./Physical review. B•May 15, 2017•97 citations

Finite-size scaling in quantum annealing with decoherence

Phillip Weinberg

Quantum annealing represents an essential milestone towards the goal of adiabatic quantum computing. In quantum annealing, the computation involves finding the ground state of a classical Ising-like Hamiltonian realized as interactions between qubits. Quantum fluctuations are introduced to allow the wavefunction of the qubits to explore the energy landscape, the hope being that the wavefunction finds a minimum energy configuration and possibly giving the result of the computation. While quantum annealing likely may not be as powerful as adiabatic quantum computing, it is possible that it may be better at optimization compared to analogous classical algorithms. In physical realizations of quantum annealing, there are still questions as to the role of quantum fluctuations in the operation of a device given the short coherence times of the individual qubits. These questions have consistently posed a serious theoretical challenge making it difficult to verify experimental results. Here we simplify the problem by considering a system of qubits with ferromagnetic interactions, modeling the decoherence effects as classical noise in the transverse-field of each qubit. We compare the calculations to data collected from a system of manufactured qubits produced by D-wave Systems by performing a finite-size scaling analysis that captures the competition between quantum fluctuations of the transverse-field and bit-flip errors from the noise. We argue that on time-scales larger than the single-qubit decoherence time, the device produces the expected quantum fluctuations for the many-body system. Using this finite-size scaling, one can diagnose sources of noise in the system. Hopefully, in the near future, these devices will not only be realizing coherent quantum annealing but will likely be useful as another example of synthetic quantum matter.

•Jan 1, 2020•0 citations
To gain better insight into the complexity theory of quantum annealing, we propose and solve a class of spin systems which contain bottlenecks of the kind expected to dominate the runtime of quantum annealing as it tries to solve difficult optimization problems. We uncover a noise amplification effect at these bottlenecks, whereby tunneling rates caused by flux-qubit noise scale in proportion to the number of qubits N\mathcal{N}N in the limit that N\ensuremath→\ensuremath∞\mathcal{N}\ensuremath{\rightarrow}\ensuremath{\infty}N\ensuremath→\ensuremath∞. By solving the incoherent annealing dynamics exactly, we find a wide range of regimes where the probability that a quantum annealer remains in the ground state upon exiting the bottleneck is close to one-half. We corroborate our analysis with detailed simulations of the performance of the D-Wave 2X quantum annealer on our class of computational problems.
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.
Although quantum annealing is usually considered as a method for locating the ground states of difficult spin-glass and optimization problems, its use in approximate optimization -- finding low- but not zero-energy states in a reasonably short amount of time -- is no less important. Here we investigate the behavior of quantum annealing at approximate optimization in the canonical mean-field spin-glass models, the spherical ppp-spin models, and find that it performs surprisingly well. Whereas it had long been assumed that infinite-range spin glasses have a unique ``threshold'' energy at which all quench and annealing dynamics become trapped until exponential timescales, recent work has shown that two-stage quenches can in fact reach states below the naive threshold in more generic situations. We demonstrate that quantum annealing is also capable of exploiting this effect to locate sub-threshold states in O(1)O(1)O(1) time. Not only can it attain energies as far below the threshold as classical annealing algorithms, but it can do so significantly faster: for an annealing schedule taking time τττ, the residual energy under quantum annealing decays as τ−ατ^{-α}τ−α with an exponent up to twice as large as that of simulated annealing in the cases considered. Importantly, by deriving and numerically solving closed integro-differential equations that hold in the thermodynamic limit, our results are free from finite-size effects and hold for annealing times that are unambiguously independent of system size.
The correspondence between long-range interacting quantum spin glasses and combinatorial optimization problems underpins the physical motivation for adiabatic quantum computing. On one hand, in disordered (quantum) spin systems, the focus is on exact methods such as the replica trick that allow the calculation of system quantities in the limit of infinite system and ensemble size. On the other hand, when solving a given instance of an optimization problem, disorder-averaged quantities are of no relevance, as one is solely interested in instance-specific, finite-size properties, in particular the optimal solution. Here, we apply the nonequilibrium Green's function formalism to the spin coherent-state path integral to obtain the statistical fluctuations and the collective-excitation spectrum along the annealing path. For the example of the quantum Sherrington-Kirkpatrick spin glass, by comparing to extensive numerically exact results, we show that this method provides access to the instance-specific bottlenecks of the annealing protocol.
Quantum annealers are computing machines that utilize quantum effects to solve hard optimization problems. Understanding the circumstances under which quantum annealers are more efficient than other optimization methods is a challenging open problem. A clue to this conundrum comes from studying the complexity of quantum annealers. In general, the complexity of a physical system relates to how efficiently the system can be simulated by classical algorithms. One then asks: if some class of quantum annealers are hard to simulate classically, are they also more powerful optimization machines? Here, the authors study quantum annealers belonging to two different complexity classes: the so-called ``stoquastic'' systems, which can be efficiently simulated with classical algorithms, and ``nonstoquastic'' systems, currently with no efficient classical treatment. Applied to a prototypical optimization problem, the authors observe that, on average, the stoquastic systems perform better on easier instances of the problem, while the more complex nonstoquastic annealers show significant advantage when applied to the hardest instances. The authors conjecture that the performance of the nonstoquastic Hamiltonians is closely related to their internal structure during the annealing process and elucidate how properties such as magnetic frustration can play a key role in devising more powerful quantum annealers.
Quantum annealing represents an essential milestone towards the goal of adiabatic quantum computing. In quantum annealing, the computation involves finding the ground state of a classical Ising-like Hamiltonian realized as interactions between qubits. Quantum fluctuations are introduced to allow the wavefunction of the qubits to explore the energy landscape, the hope being that the wavefunction finds a minimum energy configuration and possibly giving the result of the computation. While quantum annealing likely may not be as powerful as adiabatic quantum computing, it is possible that it may be better at optimization compared to analogous classical algorithms. In physical realizations of quantum annealing, there are still questions as to the role of quantum fluctuations in the operation of a device given the short coherence times of the individual qubits. These questions have consistently posed a serious theoretical challenge making it difficult to verify experimental results. Here we simplify the problem by considering a system of qubits with ferromagnetic interactions, modeling the decoherence effects as classical noise in the transverse-field of each qubit. We compare the calculations to data collected from a system of manufactured qubits produced by D-wave Systems by performing a finite-size scaling analysis that captures the competition between quantum fluctuations of the transverse-field and bit-flip errors from the noise. We argue that on time-scales larger than the single-qubit decoherence time, the device produces the expected quantum fluctuations for the many-body system. Using this finite-size scaling, one can diagnose sources of noise in the system. Hopefully, in the near future, these devices will not only be realizing coherent quantum annealing but will likely be useful as another example of synthetic quantum matter.