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:2107.01792 · Journal of the Physical Society of Japan

An Upper-Bound Inequality for the Calculation Time in Simulated Annealing: A Classical Analogue of the Adiabatic Theorem

Akihisa Ichiki, Masayuki Ohzeki

Published Oct 30, 2026• 0 citations
arXivHTMLPDF

Abstract

It has recently been reported that classical systems have a speed limit for state evolution, although the concept of a speed limit had previously been considered to be unique to quantum systems. Owing to the speed limit for classical systems, a lower bound on the calculation time of simulated annealing for a desired calculation accuracy can be derived. However, such a lower bound does not provide a practical criterion for determining whether a calculation can be completed within a reasonable time. In this paper, we derive an inequality for classical systems analogous to the quantum adiabatic theorem, which provides a calculation time that guarantees a specified accuracy for fluctuation-exploiting computation. For a Fokker–Planck evolution with a spectral gap, the error is bounded by a relaxation term and, for a genuinely driven annealing protocol, by an additional driving term proportional to the speed of the instantaneous stationary distribution. The trade-off relation between calculation time and accuracy is given in a form that is tolerable for practical use. The result clarifies the roles of the relaxation gap and annealing speed, as well as the possible acceleration caused by detailed-balance-violating dynamics.

DOI
10.7566/jpsj.95.114006

Related papers

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

Adiabaticity in open quantum systems

Lorenzo Campos Venuti, Tameem Albash, Daniel A. Lidar +1 more

We provide a rigorous generalization of the quantum adiabatic theorem for open systems described by a Markovian master equation with time-dependent Liouvillian $\mathcal{L}(t)$. We focus on the finite system case relevant for adiabatic quantum computing and quantum annealing. Adiabaticity is defined in terms of closeness to the instantaneous steady state. While the general result is conceptually similar to the closed-system case, there are important differences. Namely, a system initialized in the zero-eigenvalue eigenspace of $\mathcal{L}(t)$ will remain in this eigenspace with a deviation that is inversely proportional to the total evolution time $T$. In the case of a finite number of level crossings, the scaling becomes ${T}^{\ensuremath{-}\ensuremath{\eta}}$ with an exponent $\ensuremath{\eta}$ that we relate to the rate of the gap closing. For master equations that describe relaxation to thermal equilibrium, we show that the evolution time $T$ should be long compared to the corresponding minimum inverse gap squared of $\mathcal{L}(t)$. Our results are illustrated with several examples.

arXiv:1508.05558•Physical Review A•Mar 14, 2016•98 citations

ON THE GAP OF HAMILTONIANS FOR THE ADIABATIC SIMULATION OF QUANTUM CIRCUITS

Anand Ganti, Rolando D. Somma

The time or cost of simulating a quantum circuit by adiabatic evolution is determined by the spectral gap of the Hamiltonians involved in the simulation. In "standard" constructions based on Feynman's Hamiltonian, such a gap decreases polynomially with the number of gates in the circuit, L. Because a larger gap implies a smaller cost, we study the limits of spectral gap amplification in this context. We show that, under some assumptions on the ground states and the cost of evolving with the Hamiltonians (which apply to the standard constructions), an upper bound on the gap of the order 1/L follows. In addition, if the Hamiltonians satisfy a frustration-free property, the upper bound is of the order 1/L2. Our proofs use recent results on adiabatic state transformations, spectral gap amplification, and the simulation of continuous-time quantum query algorithms. They also consider a reduction from the unstructured search problem, whose lower bound in the oracle cost translates into the upper bounds in the gaps. The impact of our results is that improving the gap beyond that of standard constructions (i.e. 1/L2), if possible, is challenging.

arXiv:1307.4993•International Journal of Quantum Information•Oct 1, 2013•5 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

On the Speed Limit for Imaginary-Time Schrödinger Equation with Application to Quantum Searches

Jie Sun, Songfeng Lu

Recently, Okuyama and Ohzek [1] derived a speed limit for the imaginary-time Schrödinger equation, which is inspired by the prior work of Kieu, who had shown a new class of time–energy uncertainty relations suitable for actually evaluating the speed limit of quantum dynamics. In this paper, we apply the result of Okuyama and Ohzek to obtain a generalized speed limit for Grover’s search in imaginary-time quantum annealing. An estimate of the lower bound on the computational time is shown, from which the role of the coefficient function corresponding to the final Hamiltonian played in the quantum dynamics for the problem is sticking out. However, when trying to apply the speed limit to the analogue of Grover’s problem, we find that not only the coefficient of the target Hamiltonian is related to the time complexity of the algorithm, but also the coefficient of the initial Hamiltonian is crucial for determining the time complexity. This is new and generalizes one of the results in our previous work.

Open Systems & Information Dynamics•Jun 1, 2021•0 citations

Faster annealing schedules for quantum annealing

Morita, S

New annealing schedules for quantum annealing are proposed based on the adiabatic theorem. These schedules exhibit faster decrease of the excitation probability than a linear schedule. To derive this conclusion, the asymptotic form of the excitation probability for quantum annealing is explicitly obtained in the limit of long annealing time. Its first-order term, which is inversely proportional to the square of the annealing time, is shown to be determined only by the information at the initial and final times. Our annealing schedules make it possible to drop this term, thus leading to a higher order (smaller) excitation probability. We verify these results by solving numerically the time-dependent Schrodinger equation for small size systems

•Mar 7, 2007•7 citations
It has recently been reported that classical systems have a speed limit for state evolution, although the concept of a speed limit had previously been considered to be unique to quantum systems. Owing to the speed limit for classical systems, a lower bound on the calculation time of simulated annealing for a desired calculation accuracy can be derived. However, such a lower bound does not provide a practical criterion for determining whether a calculation can be completed within a reasonable time. In this paper, we derive an inequality for classical systems analogous to the quantum adiabatic theorem, which provides a calculation time that guarantees a specified accuracy for fluctuation-exploiting computation. For a Fokker–Planck evolution with a spectral gap, the error is bounded by a relaxation term and, for a genuinely driven annealing protocol, by an additional driving term proportional to the speed of the instantaneous stationary distribution. The trade-off relation between calculation time and accuracy is given in a form that is tolerable for practical use. The result clarifies the roles of the relaxation gap and annealing speed, as well as the possible acceleration caused by detailed-balance-violating dynamics.
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.
We provide a rigorous generalization of the quantum adiabatic theorem for open systems described by a Markovian master equation with time-dependent Liouvillian L(t)\mathcal{L}(t)L(t). We focus on the finite system case relevant for adiabatic quantum computing and quantum annealing. Adiabaticity is defined in terms of closeness to the instantaneous steady state. While the general result is conceptually similar to the closed-system case, there are important differences. Namely, a system initialized in the zero-eigenvalue eigenspace of L(t)\mathcal{L}(t)L(t) will remain in this eigenspace with a deviation that is inversely proportional to the total evolution time TTT. In the case of a finite number of level crossings, the scaling becomes ${T}^{\ensuremath{-}\ensuremath{\eta}}$ with an exponent $\ensuremath{\eta}$ that we relate to the rate of the gap closing. For master equations that describe relaxation to thermal equilibrium, we show that the evolution time TTT should be long compared to the corresponding minimum inverse gap squared of L(t)\mathcal{L}(t)L(t). Our results are illustrated with several examples.
The time or cost of simulating a quantum circuit by adiabatic evolution is determined by the spectral gap of the Hamiltonians involved in the simulation. In "standard" constructions based on Feynman's Hamiltonian, such a gap decreases polynomially with the number of gates in the circuit, L. Because a larger gap implies a smaller cost, we study the limits of spectral gap amplification in this context. We show that, under some assumptions on the ground states and the cost of evolving with the Hamiltonians (which apply to the standard constructions), an upper bound on the gap of the order 1/L follows. In addition, if the Hamiltonians satisfy a frustration-free property, the upper bound is of the order 1/L2. Our proofs use recent results on adiabatic state transformations, spectral gap amplification, and the simulation of continuous-time quantum query algorithms. They also consider a reduction from the unstructured search problem, whose lower bound in the oracle cost translates into the upper bounds in the gaps. The impact of our results is that improving the gap beyond that of standard constructions (i.e. 1/L2), if possible, is challenging.
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.
Recently, Okuyama and Ohzek [1] derived a speed limit for the imaginary-time Schrödinger equation, which is inspired by the prior work of Kieu, who had shown a new class of time–energy uncertainty relations suitable for actually evaluating the speed limit of quantum dynamics. In this paper, we apply the result of Okuyama and Ohzek to obtain a generalized speed limit for Grover’s search in imaginary-time quantum annealing. An estimate of the lower bound on the computational time is shown, from which the role of the coefficient function corresponding to the final Hamiltonian played in the quantum dynamics for the problem is sticking out. However, when trying to apply the speed limit to the analogue of Grover’s problem, we find that not only the coefficient of the target Hamiltonian is related to the time complexity of the algorithm, but also the coefficient of the initial Hamiltonian is crucial for determining the time complexity. This is new and generalizes one of the results in our previous work.
New annealing schedules for quantum annealing are proposed based on the adiabatic theorem. These schedules exhibit faster decrease of the excitation probability than a linear schedule. To derive this conclusion, the asymptotic form of the excitation probability for quantum annealing is explicitly obtained in the limit of long annealing time. Its first-order term, which is inversely proportional to the square of the annealing time, is shown to be determined only by the information at the initial and final times. Our annealing schedules make it possible to drop this term, thus leading to a higher order (smaller) excitation probability. We verify these results by solving numerically the time-dependent Schrodinger equation for small size systems