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

Direct comparison of quantum and simulated annealing on a fully connected Ising ferromagnet

Matteo M. Wauters, Rosario Fazio, Hidetoshi Nishimori, Giuseppe E. Santoro

Published Aug 29, 2017• 28 citations
arXivHTMLPDF

Abstract

We compare the performance of quantum annealing (QA, through Schr\"odinger dynamics) and simulated annealing (SA, through a classical master equation) on the $p$-spin infinite range ferromagnetic Ising model, by slowly driving the system across its equilibrium, quantum or classical, phase transition. When the phase transition is second order ($p=2$, the familiar two-spin Ising interaction) SA shows a remarkable exponential speed-up over QA. For a first-order phase transition ($p\ensuremath{\ge}3$, i.e., with multispin Ising interactions), in contrast, the classical annealing dynamics appears to remain stuck in the disordered phase, while we have clear evidence that QA shows a residual energy which decreases towards zero when the total annealing time $\ensuremath{\tau}$ increases, albeit in a rather slow (logarithmic) fashion. This is one of the rare examples where a limited quantum speedup, a speedup by QA over SA, has been shown to exist by direct solutions of the Schr\"odinger and master equations in combination with a nonequilibrium Landau-Zener analysis. We also analyze the imaginary-time QA dynamics of the model, finding a $1/{\ensuremath{\tau}}^{2}$ behavior for all finite values of $p$, as predicted by the adiabatic theorem of quantum mechanics. The Grover-search limit $p(\mathrm{odd})=\ensuremath{\infty}$ is also discussed.

DOI
10.1103/physreva.96.022326

Related papers

Quantum annealing speedup over simulated annealing on random Ising chains

Tommaso Zanca, Giuseppe E. Santoro

We show clear evidence of a quadratic speedup of a quantum annealing (QA) Schr\"odinger dynamics over a Glauber master equation simulated annealing (SA) for a random Ising model in one dimension, via an equal-footing exact deterministic dynamics of the Jordan-Wigner fermionized problems. This is remarkable, in view of the arguments of H. G. Katzgraber et al. [Phys. Rev. X 4, 021008 (2014)], since SA does not encounter any phase transition, while QA does. We also find a second remarkable result: that a ``quantum-inspired'' imaginary-time Schr\"odinger QA provides a further exponential speedup, i.e., an asymptotic residual error decreasing as a power law ${\ensuremath{\tau}}^{\ensuremath{-}\ensuremath{\mu}}$ of the annealing time $\ensuremath{\tau}$.

arXiv:1511.01906•Physical review. B./Physical review. B•Jun 28, 2016•26 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•30 citations

Convergence of Quantum Annealing with Real-Time Schrödinger Dynamics

Satoshi Morita, Hidetoshi Nishimori

Convergence conditions for quantum annealing are derived for optimization problems represented by the Ising model of a general form. Quantum fluctuations are introduced as a transverse field and/or transverse ferromagnetic interactions, and the time evolution follows the real-time Schrodinger equation. It is shown that the system stays arbitrarily close to the instantaneous ground state, finally reaching the target optimal state, if the strength of quantum fluctuations decreases sufficiently slowly, in particular inversely proportionally to the power of time in the asymptotic region. This is the same condition as the other implementations of quantum annealing, quantum Monte Carlo and Green's function Monte Carlo simulations, in spite of the essential difference in the type of dynamics. The method of analysis is an application of the adiabatic theorem in conjunction with an estimate of a lower bound of the energy gap based on the recently proposed idea of Somma et. al. for the analysis of classical simulated annealing using a classical-quantum correspondence.

arXiv:quant-ph/0702252•Journal of the Physical Society of Japan•May 25, 2007•41 citations

Efficient Quantum and Simulated Annealing of Potts Models Using a Half-hot Constraint

Shuntaro Okada, Masayuki Ohzeki, Kazuyuki Tanaka

The Potts model is a generalization of the Ising model with $Q>2$ components. In the fully connected ferromagnetic Potts model, a first-order phase transition is induced by varying thermal fluctuations. Therefore, the computational time required to obtain the ground states by simulated annealing exponentially increases with the system size. This study analytically confirms that the transverse magnetic-field quantum annealing induces a first-order phase transition. This result implies that quantum annealing does not exponentially accelerate the ground-state search of the ferromagnetic Potts model. To avoid the first-order phase transition, we propose an iterative optimization method using a half-hot constraint that is applicable to both quantum and simulated annealing. In the limit of $Q \to \infty$, a saddle point equation under the half-hot constraint is identical to the equation describing the behavior of the fully connected ferromagnetic Ising model, thus confirming a second-order phase transition. Furthermore, we verify the same relation between the fully connected Potts glass model and the Sherrington--Kirkpatrick model under assumptions of static approximation and replica symmetric solution. The proposed method is expected to obtain low-energy states of the Potts models with high efficiency using Ising-type computers such as the D-Wave quantum annealer and the Fujitsu Digital Annealer.

arXiv:1904.01522•Journal of the Physical Society of Japan•Jul 28, 2020•8 citations

On quantum mean-field models and their quantum annealing

Victor Bapst, Guilhem Semerjian

This paper deals with fully-connected mean-field models of quantum spins with p-body ferromagnetic interactions and a transverse field. For p=2 this corresponds to the quantum Curie-Weiss model (a special case of the Lipkin-Meshkov-Glick model) which exhibits a second-order phase transition, while for p>2 the transition is first order. We provide a refined analytical description both of the static and of the dynamic properties of these models. In particular we obtain analytically the exponential rate of decay of the gap at the first-order transition. We also study the slow annealing from the pure transverse field to the pure ferromagnet (and vice versa) and discuss the effect of the first-order transition and of the spinodal limit of metastability on the residual excitation energy, both for finite and exponentially divergent annealing times. In the quantum computation perspective this quantity would assess the efficiency of the quantum adiabatic procedure as an approximation algorithm.

•Mar 27, 2012•67 citations

On quantum mean-field models and their quantum annealing

Victor Bapst, Guilhem Semerjian

This paper deals with fully-connected mean-field models of quantum spins with p-body ferromagnetic interactions and a transverse field. For p=2 this corresponds to the quantum Curie-Weiss model (a special case of the Lipkin-Meshkov-Glick model) which exhibits a second-order phase transition, while for p>2 the transition is first order. We provide a refined analytical description both of the static and of the dynamic properties of these models. In particular we obtain analytically the exponential rate of decay of the gap at the first-order transition. We also study the slow annealing from the pure transverse field to the pure ferromagnet (and vice versa) and discuss the effect of the first-order transition and of the spinodal limit of metastability on the residual excitation energy, both for finite and exponentially divergent annealing times. In the quantum computation perspective this quantity would assess the efficiency of the quantum adiabatic procedure as an approximation algorithm.

arXiv:1203.6003•Journal of Statistical Mechanics Theory and Experiment•Jun 19, 2012•73 citations
We compare the performance of quantum annealing (QA, through Schr"odinger dynamics) and simulated annealing (SA, through a classical master equation) on the ppp-spin infinite range ferromagnetic Ising model, by slowly driving the system across its equilibrium, quantum or classical, phase transition. When the phase transition is second order (p=2p=2p=2, the familiar two-spin Ising interaction) SA shows a remarkable exponential speed-up over QA. For a first-order phase transition (p\ensuremath≥3p\ensuremath{\ge}3p\ensuremath≥3, i.e., with multispin Ising interactions), in contrast, the classical annealing dynamics appears to remain stuck in the disordered phase, while we have clear evidence that QA shows a residual energy which decreases towards zero when the total annealing time \ensuremathτ\ensuremath{\tau}\ensuremathτ increases, albeit in a rather slow (logarithmic) fashion. This is one of the rare examples where a limited quantum speedup, a speedup by QA over SA, has been shown to exist by direct solutions of the Schr"odinger and master equations in combination with a nonequilibrium Landau-Zener analysis. We also analyze the imaginary-time QA dynamics of the model, finding a 1/\ensuremathτ21/{\ensuremath{\tau}}^{2}1/\ensuremathτ2 behavior for all finite values of ppp, as predicted by the adiabatic theorem of quantum mechanics. The Grover-search limit p(odd)=\ensuremath∞p(\mathrm{odd})=\ensuremath{\infty}p(odd)=\ensuremath∞ is also discussed.
We show clear evidence of a quadratic speedup of a quantum annealing (QA) Schr\"odinger dynamics over a Glauber master equation simulated annealing (SA) for a random Ising model in one dimension, via an equal-footing exact deterministic dynamics of the Jordan-Wigner fermionized problems. This is remarkable, in view of the arguments of H. G. Katzgraber et al. [Phys. Rev. X 4, 021008 (2014)], since SA does not encounter any phase transition, while QA does. We also find a second remarkable result: that a ``quantum-inspired'' imaginary-time Schr\"odinger QA provides a further exponential speedup, i.e., an asymptotic residual error decreasing as a power law ${\ensuremath{\tau}}^{\ensuremath{-}\ensuremath{\mu}}$ of the annealing time $\ensuremath{\tau}$.
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.
Convergence conditions for quantum annealing are derived for optimization problems represented by the Ising model of a general form. Quantum fluctuations are introduced as a transverse field and/or transverse ferromagnetic interactions, and the time evolution follows the real-time Schrodinger equation. It is shown that the system stays arbitrarily close to the instantaneous ground state, finally reaching the target optimal state, if the strength of quantum fluctuations decreases sufficiently slowly, in particular inversely proportionally to the power of time in the asymptotic region. This is the same condition as the other implementations of quantum annealing, quantum Monte Carlo and Green's function Monte Carlo simulations, in spite of the essential difference in the type of dynamics. The method of analysis is an application of the adiabatic theorem in conjunction with an estimate of a lower bound of the energy gap based on the recently proposed idea of Somma et. al. for the analysis of classical simulated annealing using a classical-quantum correspondence.
The Potts model is a generalization of the Ising model with Q>2Q>2Q>2 components. In the fully connected ferromagnetic Potts model, a first-order phase transition is induced by varying thermal fluctuations. Therefore, the computational time required to obtain the ground states by simulated annealing exponentially increases with the system size. This study analytically confirms that the transverse magnetic-field quantum annealing induces a first-order phase transition. This result implies that quantum annealing does not exponentially accelerate the ground-state search of the ferromagnetic Potts model. To avoid the first-order phase transition, we propose an iterative optimization method using a half-hot constraint that is applicable to both quantum and simulated annealing. In the limit of Q→∞Q \to \inftyQ→∞, a saddle point equation under the half-hot constraint is identical to the equation describing the behavior of the fully connected ferromagnetic Ising model, thus confirming a second-order phase transition. Furthermore, we verify the same relation between the fully connected Potts glass model and the Sherrington--Kirkpatrick model under assumptions of static approximation and replica symmetric solution. The proposed method is expected to obtain low-energy states of the Potts models with high efficiency using Ising-type computers such as the D-Wave quantum annealer and the Fujitsu Digital Annealer.
This paper deals with fully-connected mean-field models of quantum spins with p-body ferromagnetic interactions and a transverse field. For p=2 this corresponds to the quantum Curie-Weiss model (a special case of the Lipkin-Meshkov-Glick model) which exhibits a second-order phase transition, while for p>2 the transition is first order. We provide a refined analytical description both of the static and of the dynamic properties of these models. In particular we obtain analytically the exponential rate of decay of the gap at the first-order transition. We also study the slow annealing from the pure transverse field to the pure ferromagnet (and vice versa) and discuss the effect of the first-order transition and of the spinodal limit of metastability on the residual excitation energy, both for finite and exponentially divergent annealing times. In the quantum computation perspective this quantity would assess the efficiency of the quantum adiabatic procedure as an approximation algorithm.
This paper deals with fully-connected mean-field models of quantum spins with p-body ferromagnetic interactions and a transverse field. For p=2 this corresponds to the quantum Curie-Weiss model (a special case of the Lipkin-Meshkov-Glick model) which exhibits a second-order phase transition, while for p>2 the transition is first order. We provide a refined analytical description both of the static and of the dynamic properties of these models. In particular we obtain analytically the exponential rate of decay of the gap at the first-order transition. We also study the slow annealing from the pure transverse field to the pure ferromagnet (and vice versa) and discuss the effect of the first-order transition and of the spinodal limit of metastability on the residual excitation energy, both for finite and exponentially divergent annealing times. In the quantum computation perspective this quantity would assess the efficiency of the quantum adiabatic procedure as an approximation algorithm.