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

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

Kazuya Kaneko, Hidetoshi Nishimori

Published Aug 5, 2015• 7 citations
arXivHTMLPDF

Abstract

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.

DOI
10.7566/jpsj.84.094001

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

Convergence condition of simulated quantum annealing for closed and open systems

Yusuke Kimura, Hidetoshi Nishimori

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.

arXiv:2209.15523•Physical Review A•Dec 19, 2022•5 citations

Difference between Quantum Annealing by Imaginary-Time and Real-Time Schrödinger Equations of Grover’s Search

Shuntaro Okada, Masayuki Ohzeki, Kazuyuki Tanaka

We confirmed the annealing time of Grover's search which is required to obtain desired success probability for quantum annealing by the imaginary-time and the real-time Schrödinger equation with two kinds of schedulings; one linearly decreases the quantum fluctuation and the other tunes the evolution rate of the Hamiltonian based on the adiabatic condition. With linear scheduling, the required annealing time for quantum annealing by the imaginary-time Schrödinger equation is of order $\log N$, which is very different from $O(N)$ required for the quantum annealing by the real-time Schrödinger equation. With the scheduling based on the adiabatic condition, the required annealing time is of order $\sqrt{N}$, which is identical to the annealing time for quantum annealing by the real-time Schrödinger equation. Although the scheduling based on the adiabatic condition is optimal for the quantum annealing by the real-time Schrödinger equation, it is inefficient for the quantum annealing by the imaginary-time Schrödinger equation. This result implies that the optimal scheduling for the quantum annealing by the imaginary-time and the real-time Schrödinger equation is very different, and the efficient scheduling considered with the quantum Monte Carlo methods, which is based on imaginary-time Schrödinger equation, is not necessarily effective to improve the performance of quantum annealing by the real-time Schrödinger equation. We discuss the efficient scheduling for quantum annealing by the imaginary-time Schrödinger equation with respect to the exponential decay of excited states.

arXiv:1801.06297•Journal of the Physical Society of Japan•Jan 16, 2019•5 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

Mathematical aspects of quantum annealing

Hidetoshi Nishimori, Satoshi Morita

Sufficient conditions for convergence of quantum annealing are derived for optimization problems represented by the Ising model. Three different types of time evolution are considered; the real-time Schrödinger equation, the path-integral Monte Carlo method and the Green's function Monte Carlo method. It is proved that the system under each dynamics reaches the target solution in the limit of infinite time if the transverse field, representing the strength of quantum fluctuations, decreases inversely proportionally to the power of time in the asymptotic region.

Journal of Physics Conference Series•Jan 1, 2008•0 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
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.
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 confirmed the annealing time of Grover's search which is required to obtain desired success probability for quantum annealing by the imaginary-time and the real-time Schrödinger equation with two kinds of schedulings; one linearly decreases the quantum fluctuation and the other tunes the evolution rate of the Hamiltonian based on the adiabatic condition. With linear scheduling, the required annealing time for quantum annealing by the imaginary-time Schrödinger equation is of order log⁡N\log NlogN, which is very different from O(N)O(N)O(N) required for the quantum annealing by the real-time Schrödinger equation. With the scheduling based on the adiabatic condition, the required annealing time is of order N\sqrt{N}N​, which is identical to the annealing time for quantum annealing by the real-time Schrödinger equation. Although the scheduling based on the adiabatic condition is optimal for the quantum annealing by the real-time Schrödinger equation, it is inefficient for the quantum annealing by the imaginary-time Schrödinger equation. This result implies that the optimal scheduling for the quantum annealing by the imaginary-time and the real-time Schrödinger equation is very different, and the efficient scheduling considered with the quantum Monte Carlo methods, which is based on imaginary-time Schrödinger equation, is not necessarily effective to improve the performance of quantum annealing by the real-time Schrödinger equation. We discuss the efficient scheduling for quantum annealing by the imaginary-time Schrödinger equation with respect to the exponential decay of excited states.
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.
Sufficient conditions for convergence of quantum annealing are derived for optimization problems represented by the Ising model. Three different types of time evolution are considered; the real-time Schrödinger equation, the path-integral Monte Carlo method and the Green's function Monte Carlo method. It is proved that the system under each dynamics reaches the target solution in the limit of infinite time if the transverse field, representing the strength of quantum fluctuations, decreases inversely proportionally to the power of time in the asymptotic region.
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.