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

Convergence condition of simulated quantum annealing for closed and open systems

Yusuke Kimura, Hidetoshi Nishimori

Published Dec 19, 2022• 5 citations
arXivHTMLPDF

Abstract

Simulated quantum annealing is a generic classical protocol to simulate some aspects of quantum annealing and is sometimes regarded as a classical alternative to quantum annealing in finding the ground state of a classical Ising model. We derive a generic condition for simulated quantum annealing to converge to thermal equilibrium at a given, typically low, temperature. Both closed and open systems are treated. We rewrite the classical master equation for simulated quantum annealing into an imaginary-time Schr\"odinger equation, to which we apply the imaginary-time variant of the asymptotic adiabatic condition to deduce the convergence condition. The result agrees qualitatively with a rigorous convergence condition of simulated quantum annealing for closed systems, which was derived from the theory of inhomogeneous Markov processes. Also observed is qualitative agreement with a rigorous convergence condition of quantum annealing for closed systems under the real-time Schr\"odinger dynamics. This coincidence of convergence conditions for classical stochastic processes for simulated quantum annealing and the real-time quantum dynamics for quantum annealing is highly nontrivial and calls for further scrutiny.

DOI
10.1103/physreva.106.062614

Related papers

Adiabatic Approximation for the Imaginary-Time Schrödinger Equation and Its Application to Simulated Annealing

Kazuya Kaneko, Hidetoshi Nishimori

We formulate an adiabatic approximation for the imaginary-time Schroedinger equation. The obtained adiabatic condition consists of two inequalities, one of which coincides with the conventional adiabatic condition for the real-time Schroedinger equation, but the other does not. We apply this adiabatic approximation to the analysis of Markovian dynamics of the classical Ising model, which can be formulated as the imaginary-time Schrödinger equation, to obtain an asymptotic formula for the probability that the system reaches the ground state in the limit of a long annealing time in simulated annealing. Using this form, we amend the theory of Somma, Batista, and Ortiz for a convergence condition for simulated annealing.

arXiv:1504.00425•Journal of the Physical Society of Japan•Aug 5, 2015•7 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

Mathematical foundation of quantum annealing

Satoshi Morita, Hidetoshi Nishimori

Quantum annealing is a generic name of quantum algorithms that use quantum-mechanical fluctuations to search for the solution of an optimization problem. It shares the basic idea with quantum adiabatic evolution studied actively in quantum computation. The present paper reviews the mathematical and theoretical foundations of quantum annealing. In particular, theorems are presented for convergence conditions of quantum annealing to the target optimal state after an infinite-time evolution following the Schrödinger or stochastic (Monte Carlo) dynamics. It is proved that the same asymptotic behavior of the control parameter guarantees convergence for both the Schrödinger dynamics and the stochastic dynamics in spite of the essential difference of these two types of dynamics. Also described are the prescriptions to reduce errors in the final approximate solution obtained after a long but finite dynamical evolution of quantum annealing. It is shown there that we can reduce errors significantly by an ingenious choice of annealing schedule (time dependence of the control parameter) without compromising computational complexity qualitatively. A review is given on the derivation of the convergence condition for classical simulated annealing from the view point of quantum adiabaticity using a classical-quantum mapping.

arXiv:0806.1859•Journal of Mathematical Physics•Dec 1, 2008•380 citations

Rigorous convergence condition for quantum annealing

Yusuke Kimura, Hidetoshi Nishimori

Abstract We derive a generic bound on the rate of decrease of transverse field for quantum annealing to converge to the ground state of a generic Ising model when quantum annealing is formulated as an infinite-time process. Our theorem is based on a rigorous upper bound on the excitation probability in the infinite-time limit and is a mathematically rigorous counterpart of a previously known result derived only from the leading-order term of the asymptotic expansion of adiabatic condition. Since our theorem gives a sufficient condition of convergence for a generic transverse-field Ising model, any specific problem may allow a better, faster, control of the coefficient.

arXiv:2207.12096•Journal of Physics A Mathematical and Theoretical•Oct 27, 2022•6 citations

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

Matteo M. Wauters, Rosario Fazio, Hidetoshi Nishimori +1 more

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.

arXiv:1707.02621•Physical Review A•Aug 29, 2017•28 citations

Convergence condition of simulated quantum annealing with a non-stoquastic catalyst

Yusuke Kimura, Hidetoshi Nishimori

Abstract The Ising model with a transverse field and an antiferromagnetic transverse interaction is represented as a matrix in the computational basis with non-zero off-diagonal elements with both positive and negative signs and thus may be regarded to be non-stoquastic. We show that the local Boltzmann factors of such a system under an appropriate Suzuki–Trotter representation can be chosen non-negative and thus may potentially be simulated classically without a sign problem if the parameter values are limited to a subspace of the whole parameter space. We then derive conditions for parameters to satisfy asymptotically in order that simulated quantum annealing of this system converges to thermal equilibrium in the long-time limit.

arXiv:2302.00998•Journal of Physics A Mathematical and Theoretical•Mar 17, 2023•1 citation
Simulated quantum annealing is a generic classical protocol to simulate some aspects of quantum annealing and is sometimes regarded as a classical alternative to quantum annealing in finding the ground state of a classical Ising model. We derive a generic condition for simulated quantum annealing to converge to thermal equilibrium at a given, typically low, temperature. Both closed and open systems are treated. We rewrite the classical master equation for simulated quantum annealing into an imaginary-time Schr"odinger equation, to which we apply the imaginary-time variant of the asymptotic adiabatic condition to deduce the convergence condition. The result agrees qualitatively with a rigorous convergence condition of simulated quantum annealing for closed systems, which was derived from the theory of inhomogeneous Markov processes. Also observed is qualitative agreement with a rigorous convergence condition of quantum annealing for closed systems under the real-time Schr"odinger dynamics. This coincidence of convergence conditions for classical stochastic processes for simulated quantum annealing and the real-time quantum dynamics for quantum annealing is highly nontrivial and calls for further scrutiny.
We formulate an adiabatic approximation for the imaginary-time Schroedinger equation. The obtained adiabatic condition consists of two inequalities, one of which coincides with the conventional adiabatic condition for the real-time Schroedinger equation, but the other does not. We apply this adiabatic approximation to the analysis of Markovian dynamics of the classical Ising model, which can be formulated as the imaginary-time Schrödinger equation, to obtain an asymptotic formula for the probability that the system reaches the ground state in the limit of a long annealing time in simulated annealing. Using this form, we amend the theory of Somma, Batista, and Ortiz for a convergence condition for simulated annealing.
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.
Quantum annealing is a generic name of quantum algorithms that use quantum-mechanical fluctuations to search for the solution of an optimization problem. It shares the basic idea with quantum adiabatic evolution studied actively in quantum computation. The present paper reviews the mathematical and theoretical foundations of quantum annealing. In particular, theorems are presented for convergence conditions of quantum annealing to the target optimal state after an infinite-time evolution following the Schrödinger or stochastic (Monte Carlo) dynamics. It is proved that the same asymptotic behavior of the control parameter guarantees convergence for both the Schrödinger dynamics and the stochastic dynamics in spite of the essential difference of these two types of dynamics. Also described are the prescriptions to reduce errors in the final approximate solution obtained after a long but finite dynamical evolution of quantum annealing. It is shown there that we can reduce errors significantly by an ingenious choice of annealing schedule (time dependence of the control parameter) without compromising computational complexity qualitatively. A review is given on the derivation of the convergence condition for classical simulated annealing from the view point of quantum adiabaticity using a classical-quantum mapping.
Abstract We derive a generic bound on the rate of decrease of transverse field for quantum annealing to converge to the ground state of a generic Ising model when quantum annealing is formulated as an infinite-time process. Our theorem is based on a rigorous upper bound on the excitation probability in the infinite-time limit and is a mathematically rigorous counterpart of a previously known result derived only from the leading-order term of the asymptotic expansion of adiabatic condition. Since our theorem gives a sufficient condition of convergence for a generic transverse-field Ising model, any specific problem may allow a better, faster, control of the coefficient.
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{\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 ppp, as predicted by the adiabatic theorem of quantum mechanics. The Grover-search limit $p(\mathrm{odd})=\ensuremath{\infty}$ is also discussed.
Abstract The Ising model with a transverse field and an antiferromagnetic transverse interaction is represented as a matrix in the computational basis with non-zero off-diagonal elements with both positive and negative signs and thus may be regarded to be non-stoquastic. We show that the local Boltzmann factors of such a system under an appropriate Suzuki–Trotter representation can be chosen non-negative and thus may potentially be simulated classically without a sign problem if the parameter values are limited to a subspace of the whole parameter space. We then derive conditions for parameters to satisfy asymptotically in order that simulated quantum annealing of this system converges to thermal equilibrium in the long-time limit.