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

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

Chengwei Liu, Anatoli Polkovnikov, Anders W. Sandvik

Published Apr 7, 2015• 54 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.114.147203

Related papers

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•225 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

Universal dynamic scaling in three-dimensional Ising spin glasses

Cheng-Wei Liu, Anatoli Polkovnikov, Anders W. Sandvik +1 more

We use a nonequilibrium Monte Carlo simulation method and dynamical scaling to study the phase transition in three-dimensional Ising spin glasses. The transition point is repeatedly approached at finite velocity v (temperature change versus time) in Monte Carlo simulations starting at a high temperature. This approach has the advantage that the equilibrium limit does not have to be strictly reached for a scaling analysis to yield critical exponents. For the dynamic exponent we obtain z=5.85(9) for bimodal couplings distribution and z=6.00(10) for the Gaussian case. Assuming universal dynamic scaling, we combine the two results and obtain z=5.93±0.07 for generic 3D Ising spin glasses.

arXiv:1411.6745•Physical Review E•Aug 19, 2015•27 citations

Comparative study of the performance of quantum annealing and simulated annealing

Hidetoshi Nishimori, Junichi Tsuda, Sergey Knysh

Relations of simulated annealing and quantum annealing are studied by a mapping from the transition matrix of classical Markovian dynamics of the Ising model to a quantum Hamiltonian and vice versa. It is shown that these two operators, the transition matrix and the Hamiltonian, share the eigenvalue spectrum. Thus, if simulated annealing with slow temperature change does not encounter a difficulty caused by an exponentially long relaxation time at a first-order phase transition, the same is true for the corresponding process of quantum annealing in the adiabatic limit. One of the important differences between the classical-to-quantum mapping and the converse quantum-to-classical mapping is that the Markovian dynamics of a short-range Ising model is mapped to a short-range quantum system, but the converse mapping from a short-range quantum system to a classical one results in long-range interactions. This leads to a difference in efficiencies that simulated annealing can be efficiently simulated by quantum annealing but the converse is not necessarily true. We conclude that quantum annealing is easier to implement and is more flexible than simulated annealing. We also point out that the present mapping can be extended to accommodate explicit time dependence of temperature, which is used to justify the quantum-mechanical analysis of simulated annealing by Somma, Batista, and Ortiz. Additionally, an alternative method to solve the nonequilibrium dynamics of the one-dimensional Ising model is provided through the classical-to-quantum mapping.

arXiv:1409.6386•Physical Review E•Jan 6, 2015•32 citations

Computational studies of thermal and quantum phase transitions approached through non-equilibrium quenching

Chengwei Liu

Phase transitions and their associated critical phenomena are of fundamental importance and play a crucial role in the development of statistical physics for both classical and quantum systems. Phase transitions embody diverse aspects of physics and also have numerous applications outside physics, e.g., in chemistry, biology, and combinatorial optimization problems in computer science. Many problems can be reduced to a system consisting of a large number of interacting agents, which under some circumstances (e.g., changes of external parameters) exhibit collective behavior; this type of scenario also underlies phase transitions. The theoretical understanding of equilibrium phase transitions was put on a solid footing with the establishment of the renormalization group. In contrast, non-equilibrium phase transition are relatively less understood and currently a very active research topic. One important milestone here is the Kibble-Zurek (KZ) mechanism, which provides a useful framework for describing a system with a transition point approached through a non-equilibrium quench process. I developed two efficient Monte Carlo techniques for studying phase transitions, one is for classical phase transition and the other is for quantum phase transitions, both are under the framework of KZ scaling. For classical phase transition, I develop a non-equilibrium quench (NEQ) simulation that can completely avoid the critical slowing down problem. For quantum phase transitions, I develop a new algorithm, named quasi-adiabatic quantum Monte Carlo (QAQMC) algorithm for studying quantum quenches. I demonstrate the utility of QAQMC quantum Ising model and obtain high-precision results at the transition point, in particular showing generalized dynamic scaling in the quantum system. To further extend the methods, I study more complex systems such as spin-glasses and random graphs. The techniques allow us to investigate the problems efficiently. From the classical perspective, using the NEQ approach I verify the universality class of the 3D Ising spin-glasses. I also investigate the random 3-regular graphs in terms of both classical and quantum phase transitions. I demonstrate that under this simulation scheme, one can extract information associated with the classical and quantum spin-glass transitions without any knowledge prior to the simulation.

•Jan 1, 2015•0 citations

Quantum annealing of an Ising spin-glass by Green’s function Monte Carlo

Lorenzo Stella, Giuseppe E. Santoro

We present an implementation of quantum annealing (QA) via lattice Green's function Monte Carlo (GFMC), focusing on its application to the Ising spin glass in transverse field. In particular, we study whether or not such a method is more effective than the path-integral Monte Carlo- (PIMC) based QA, as well as classical simulated annealing (CA), previously tested on the same optimization problem. We identify the issue of importance sampling, i.e., the necessity of possessing reasonably good (variational) trial wave functions, as the key point of the algorithm. We performed GFMC-QA runs using such a Boltzmann-type trial wave function, finding results for the residual energies that are qualitatively similar to those of CA (but at a much larger computational cost), and definitely worse than PIMC-QA. We conclude that, at present, without a serious effort in constructing reliable importance sampling variational wave functions for a quantum glass, GFMC-QA is not a true competitor of PIMC-QA.

arXiv:cond-mat/0608420•Physical Review E•Mar 13, 2007•19 citations
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.
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.
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 use a nonequilibrium Monte Carlo simulation method and dynamical scaling to study the phase transition in three-dimensional Ising spin glasses. The transition point is repeatedly approached at finite velocity v (temperature change versus time) in Monte Carlo simulations starting at a high temperature. This approach has the advantage that the equilibrium limit does not have to be strictly reached for a scaling analysis to yield critical exponents. For the dynamic exponent we obtain z=5.85(9) for bimodal couplings distribution and z=6.00(10) for the Gaussian case. Assuming universal dynamic scaling, we combine the two results and obtain z=5.93±0.07 for generic 3D Ising spin glasses.
Relations of simulated annealing and quantum annealing are studied by a mapping from the transition matrix of classical Markovian dynamics of the Ising model to a quantum Hamiltonian and vice versa. It is shown that these two operators, the transition matrix and the Hamiltonian, share the eigenvalue spectrum. Thus, if simulated annealing with slow temperature change does not encounter a difficulty caused by an exponentially long relaxation time at a first-order phase transition, the same is true for the corresponding process of quantum annealing in the adiabatic limit. One of the important differences between the classical-to-quantum mapping and the converse quantum-to-classical mapping is that the Markovian dynamics of a short-range Ising model is mapped to a short-range quantum system, but the converse mapping from a short-range quantum system to a classical one results in long-range interactions. This leads to a difference in efficiencies that simulated annealing can be efficiently simulated by quantum annealing but the converse is not necessarily true. We conclude that quantum annealing is easier to implement and is more flexible than simulated annealing. We also point out that the present mapping can be extended to accommodate explicit time dependence of temperature, which is used to justify the quantum-mechanical analysis of simulated annealing by Somma, Batista, and Ortiz. Additionally, an alternative method to solve the nonequilibrium dynamics of the one-dimensional Ising model is provided through the classical-to-quantum mapping.
Phase transitions and their associated critical phenomena are of fundamental importance and play a crucial role in the development of statistical physics for both classical and quantum systems. Phase transitions embody diverse aspects of physics and also have numerous applications outside physics, e.g., in chemistry, biology, and combinatorial optimization problems in computer science. Many problems can be reduced to a system consisting of a large number of interacting agents, which under some circumstances (e.g., changes of external parameters) exhibit collective behavior; this type of scenario also underlies phase transitions. The theoretical understanding of equilibrium phase transitions was put on a solid footing with the establishment of the renormalization group. In contrast, non-equilibrium phase transition are relatively less understood and currently a very active research topic. One important milestone here is the Kibble-Zurek (KZ) mechanism, which provides a useful framework for describing a system with a transition point approached through a non-equilibrium quench process. I developed two efficient Monte Carlo techniques for studying phase transitions, one is for classical phase transition and the other is for quantum phase transitions, both are under the framework of KZ scaling. For classical phase transition, I develop a non-equilibrium quench (NEQ) simulation that can completely avoid the critical slowing down problem. For quantum phase transitions, I develop a new algorithm, named quasi-adiabatic quantum Monte Carlo (QAQMC) algorithm for studying quantum quenches. I demonstrate the utility of QAQMC quantum Ising model and obtain high-precision results at the transition point, in particular showing generalized dynamic scaling in the quantum system. To further extend the methods, I study more complex systems such as spin-glasses and random graphs. The techniques allow us to investigate the problems efficiently. From the classical perspective, using the NEQ approach I verify the universality class of the 3D Ising spin-glasses. I also investigate the random 3-regular graphs in terms of both classical and quantum phase transitions. I demonstrate that under this simulation scheme, one can extract information associated with the classical and quantum spin-glass transitions without any knowledge prior to the simulation.
We present an implementation of quantum annealing (QA) via lattice Green's function Monte Carlo (GFMC), focusing on its application to the Ising spin glass in transverse field. In particular, we study whether or not such a method is more effective than the path-integral Monte Carlo- (PIMC) based QA, as well as classical simulated annealing (CA), previously tested on the same optimization problem. We identify the issue of importance sampling, i.e., the necessity of possessing reasonably good (variational) trial wave functions, as the key point of the algorithm. We performed GFMC-QA runs using such a Boltzmann-type trial wave function, finding results for the residual energies that are qualitatively similar to those of CA (but at a much larger computational cost), and definitely worse than PIMC-QA. We conclude that, at present, without a serious effort in constructing reliable importance sampling variational wave functions for a quantum glass, GFMC-QA is not a true competitor of PIMC-QA.