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:cond-mat/0205280 · Science

Theory of Quantum Annealing of an Ising Spin Glass

Giuseppe E. Santoro, Roman Martoňák, Erio Tosatti, Roberto Car

Published Mar 29, 2002• 728 citations
arXivHTMLPDF

Abstract

Probing the lowest energy configuration of a complex system by quantum annealing was recently found to be more effective than its classical, thermal counterpart. By comparing classical and quantum Monte Carlo annealing protocols on the two-dimensional random Ising model (a prototype spin glass), we confirm the superiority of quantum annealing relative to classical annealing. We also propose a theory of quantum annealing based on a cascade of Landau-Zener tunneling events. For both classical and quantum annealing, the residual energy after annealing is inversely proportional to a power of the logarithm of the annealing time, but the quantum case has a larger power that makes it faster.

DOI
10.1126/science.1068774

Related papers

Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising model

Roman Martoňák, Giuseppe E. Santoro, Erio Tosatti

Quantum annealing was recently found experimentally in a disordered spin-$\frac{1}{2}$ magnet to be more effective than its classical, thermal counterpart. We use the random two-dimensional Ising model as a test example and perform on it both classical and quantum (path-integral) Monte Carlo annealing. A systematic study of the dependence of the final residual energy on the annealing Monte Carlo time quantitatively demonstrates the superiority of quantum relative to classical annealing in this system. In order to determine the parameter regime for optimal efficiency of the quantum annealing procedure we explore a range of values of Trotter slice number P and temperature T. This identifies two different regimes of freezing with respect to efficiency of the algorithm, and leads to useful guidelines for the optimal choice of quantum annealing parameters.

Physical review. B, Condensed matter•Sep 13, 2002•144 citations

Quantum versus classical annealing of Ising spin glasses

Bettina Heim, Troels F. Rønnow, Sergei V. Isakov +1 more

Quantum annealers use quantum fluctuations to escape local minima and find low-energy configurations of a physical system. Strong evidence for superiority of quantum annealing (QA) has come from comparing QA implemented through quantum Monte Carlo (QMC) simulations to classical annealing. Motivated by recent experiments, we revisit the question of when quantum speedup may be expected. Although a better scaling is seen for QA in two-dimensional Ising spin glasses, this advantage is due to time discretization artifacts and measurements that are not possible on a physical quantum annealer. Simulations in the physically relevant continuous time limit, on the other hand, do not show superiority. Our results imply that care must be taken when using QMC simulations to assess the potential for quantum speedup.

arXiv:1411.5693•Science•Mar 12, 2015•218 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

Proposal of a new quantum annealing schedule for studying transverse-field-based quantum versus classical annealing of the Ising model: a case study of the Ising spin glass model on the square lattice by the Monte Carlo simulation

Chiaki Yamaguchi

Recently, Heim, R\o nnow, Isakov and Troyer [{\it Science} \textbf{348} (2015) 215] have reported that Monte Carlo simulations for the Ising spin glass model on the square lattice in the physically relevant continuous-imaginary-time limit do not show superiority of quantum annealing (QA) using transverse field against classical annealing (CA). Although the QA schedule that they had used has been using conventionally, however the QA schedule mathematically has no guarantee that the used schedule is the best QA schedule for performance of optimization. We propose a new QA schedule for studying transverse-field-based quantum versus classical annealing of the Ising model. The present QA schedule is made based on the concept of perturbation theory. This QA schedule utilizes a smallest effective transverse field derived in this article. As a case study, we study QA of the Ising spin glass model on the square lattice at low but finite temperature. A new Monte Carlo algorithm using the physically relevant continuous-imaginary-time limit is performed. As the simulation results, we show superiority of QA against CA when the annealing time is spent enough.

arXiv:1706.06416•Jun 20, 2017•0 citations

Tranverse Ising Model, Glass and Quantum Annealing

Bikas K. Chakrabarti, Arnab Das

We introduce the transverse Ising model as a prototype for discussing quantum phase transition. Next we introduce Suzuki-Trotter formalism to show the correspondence between $d$-dimensional quantum system with a $(d+1)$-dimensional classical system. We then discuss transverse Ising spin glass models, namely S-K model, E-A model, and the $\pm J$ model with Ising spin in transverse field. We briefly discuss the mean field, exact diagonalization, and quantum Monte Carlo results for their phase diagrams. Next we discuss the question of replica symmetry restoration in quantum spin glasses (due to tunnelling possibility through the barriers). Then we discuss the quantum annealing technique and indicate its relationship with replica symmetry restoration in quantum spin glasses. We have also breifly discussed the possibility of Quantum Annealing in context of kinetically constrained systems. Mean-field calculation for BCS superconductivity, Real-space RG calculation for one dimensional transverse Ising system, scattering amplitude calculation for tunneling through asymmetric barrier (useful for quantum kinetically constrained system) are given in the appendices.

arXiv:cond-mat/0312611•Dec 23, 2003•2 citations

Quantum versus Classical Annealing: Insights from Scaling Theory and Results for Spin Glasses on 3-Regular Graphs

Chengwei Liu, Anatoli Polkovnikov, Anders W. Sandvik

We discuss an Ising spin glass where each S=1/2 spin is coupled antiferromagnetically to three other spins (3-regular graphs). Inducing quantum fluctuations by a time-dependent transverse field, we use out-of-equilibrium quantum Monte Carlo simulations to study dynamic scaling at the quantum glass transition. Comparing the dynamic exponent and other critical exponents with those of the classical (temperature-driven) transition, we conclude that quantum annealing is less efficient than classical simulated annealing in bringing the system into the glass phase. Quantum computing based on the quantum annealing paradigm is therefore inferior to classical simulated annealing for this class of problems. We also comment on previous simulations where a parameter is changed with the simulation time, which is very different from the true Hamiltonian dynamics simulated here.

arXiv:1409.7192•Physical Review Letters•Apr 7, 2015•55 citations
Probing the lowest energy configuration of a complex system by quantum annealing was recently found to be more effective than its classical, thermal counterpart. By comparing classical and quantum Monte Carlo annealing protocols on the two-dimensional random Ising model (a prototype spin glass), we confirm the superiority of quantum annealing relative to classical annealing. We also propose a theory of quantum annealing based on a cascade of Landau-Zener tunneling events. For both classical and quantum annealing, the residual energy after annealing is inversely proportional to a power of the logarithm of the annealing time, but the quantum case has a larger power that makes it faster.
Quantum annealing was recently found experimentally in a disordered spin-12\frac{1}{2}21​ magnet to be more effective than its classical, thermal counterpart. We use the random two-dimensional Ising model as a test example and perform on it both classical and quantum (path-integral) Monte Carlo annealing. A systematic study of the dependence of the final residual energy on the annealing Monte Carlo time quantitatively demonstrates the superiority of quantum relative to classical annealing in this system. In order to determine the parameter regime for optimal efficiency of the quantum annealing procedure we explore a range of values of Trotter slice number P and temperature T. This identifies two different regimes of freezing with respect to efficiency of the algorithm, and leads to useful guidelines for the optimal choice of quantum annealing parameters.
Quantum annealers use quantum fluctuations to escape local minima and find low-energy configurations of a physical system. Strong evidence for superiority of quantum annealing (QA) has come from comparing QA implemented through quantum Monte Carlo (QMC) simulations to classical annealing. Motivated by recent experiments, we revisit the question of when quantum speedup may be expected. Although a better scaling is seen for QA in two-dimensional Ising spin glasses, this advantage is due to time discretization artifacts and measurements that are not possible on a physical quantum annealer. Simulations in the physically relevant continuous time limit, on the other hand, do not show superiority. Our results imply that care must be taken when using QMC simulations to assess the potential for quantum speedup.
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.
Recently, Heim, R\o nnow, Isakov and Troyer [{\it Science} \textbf{348} (2015) 215] have reported that Monte Carlo simulations for the Ising spin glass model on the square lattice in the physically relevant continuous-imaginary-time limit do not show superiority of quantum annealing (QA) using transverse field against classical annealing (CA). Although the QA schedule that they had used has been using conventionally, however the QA schedule mathematically has no guarantee that the used schedule is the best QA schedule for performance of optimization. We propose a new QA schedule for studying transverse-field-based quantum versus classical annealing of the Ising model. The present QA schedule is made based on the concept of perturbation theory. This QA schedule utilizes a smallest effective transverse field derived in this article. As a case study, we study QA of the Ising spin glass model on the square lattice at low but finite temperature. A new Monte Carlo algorithm using the physically relevant continuous-imaginary-time limit is performed. As the simulation results, we show superiority of QA against CA when the annealing time is spent enough.
We introduce the transverse Ising model as a prototype for discussing quantum phase transition. Next we introduce Suzuki-Trotter formalism to show the correspondence between ddd-dimensional quantum system with a (d+1)(d+1)(d+1)-dimensional classical system. We then discuss transverse Ising spin glass models, namely S-K model, E-A model, and the ±J\pm J±J model with Ising spin in transverse field. We briefly discuss the mean field, exact diagonalization, and quantum Monte Carlo results for their phase diagrams. Next we discuss the question of replica symmetry restoration in quantum spin glasses (due to tunnelling possibility through the barriers). Then we discuss the quantum annealing technique and indicate its relationship with replica symmetry restoration in quantum spin glasses. We have also breifly discussed the possibility of Quantum Annealing in context of kinetically constrained systems. Mean-field calculation for BCS superconductivity, Real-space RG calculation for one dimensional transverse Ising system, scattering amplitude calculation for tunneling through asymmetric barrier (useful for quantum kinetically constrained system) are given in the appendices.
We discuss an Ising spin glass where each S=1/2 spin is coupled antiferromagnetically to three other spins (3-regular graphs). Inducing quantum fluctuations by a time-dependent transverse field, we use out-of-equilibrium quantum Monte Carlo simulations to study dynamic scaling at the quantum glass transition. Comparing the dynamic exponent and other critical exponents with those of the classical (temperature-driven) transition, we conclude that quantum annealing is less efficient than classical simulated annealing in bringing the system into the glass phase. Quantum computing based on the quantum annealing paradigm is therefore inferior to classical simulated annealing for this class of problems. We also comment on previous simulations where a parameter is changed with the simulation time, which is very different from the true Hamiltonian dynamics simulated here.