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

Journal of Physics Conference Series

Mathematical aspects of quantum annealing

Hidetoshi Nishimori, Satoshi Morita

Published Jan 1, 2008• 0 citations
Publisher

Abstract

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.

DOI
10.1088/1742-6596/95/1/012021

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 theorems for quantum annealing

Satoshi Morita, Hidetoshi Nishimori

We prove several theorems to give sufficient conditions for convergence of quantum annealing, which is a protocol to solve generic optimization problems by quantum dynamics. In particular the property of strong ergodicity is proved for the path-integral Monte Carlo implementation of quantum annealing for the transverse Ising model under a power decay of the transverse field. This result is to be compared with the much slower inverse-log decay of temperature in the conventional simulated annealing. Similar results are proved for the Green's function Monte Carlo approach. Optimization problems in continuous space of particle configurations are also discussed.

arXiv:quant-ph/0608154•Journal of Physics A Mathematical and General•Oct 24, 2006•51 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

Study of Optimization Problems by Quantum Annealing

Tadashi Kadowaki

We introduce quantum fluctuations into the simulated annealing process of optimization problems, aiming at faster convergence to the optimal state. The idea is tested by the two models, the transverse Ising model and the traveling salesman problem (TSP). Adding the transverse field to the Ising model is a simple way to introduce quantum fluctuations. The strength of the transverse field is controlled as a function of time similarly to the temperature in the conventional method. TSP can be described by the Ising spin, so that we also apply the same technique to TSP. We directory solve the time-dependent Schrödinger equation for small-size systems and perform the quantum Monte Carlo simulation for large-size systems. Comparison with the results of the corresponding classical (thermal) method reveals that the quantum method leads to the ground state with much larger probability in almost all cases if we use the same annealing schedule of the control parameters. We also find that the relaxation time is quite short for quantum systems by numerical simulations. We consider this is one of the reasons why the annealing in quantum systems have a better performance of finding the optimal state in comparison with classical systems.

arXiv:quant-ph/0205020•May 5, 2002•39 citations

Optimization using quantum mechanics: quantum annealing through adiabatic evolution

Giuseppe E. Santoro, Erio Tosatti

We review here some recent work in the field of quantum annealing, alias adiabatic quantum computation. The idea of quantum annealing is to perform optimization by a quantum adiabatic evolution which tracks the ground state of a suitable time-dependent Hamiltonian, where 'ℏ' is slowly switched off. We illustrate several applications of quantum annealing strategies, starting from textbook toy-models—double-well potentials and other one-dimensional examples, with and without disorder. These examples display in a clear way the crucial differences between classical and quantum annealing. We then discuss applications of quantum annealing to challenging hard optimization problems, such as the random Ising model, the travelling salesman problem and Boolean satisfiability problems. The techniques used to implement quantum annealing are either deterministic Schrödinger's evolutions, for the toy models, or path-integral Monte Carlo and Green's function Monte Carlo approaches, for the hard optimization problems. The crucial role played by disorder and the associated non-trivial Landau–Zener tunnelling phenomena is discussed and emphasized.

Journal of Physics A Mathematical and General•Aug 18, 2006•354 citations
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.
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 prove several theorems to give sufficient conditions for convergence of quantum annealing, which is a protocol to solve generic optimization problems by quantum dynamics. In particular the property of strong ergodicity is proved for the path-integral Monte Carlo implementation of quantum annealing for the transverse Ising model under a power decay of the transverse field. This result is to be compared with the much slower inverse-log decay of temperature in the conventional simulated annealing. Similar results are proved for the Green's function Monte Carlo approach. Optimization problems in continuous space of particle configurations are also discussed.
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 introduce quantum fluctuations into the simulated annealing process of optimization problems, aiming at faster convergence to the optimal state. The idea is tested by the two models, the transverse Ising model and the traveling salesman problem (TSP). Adding the transverse field to the Ising model is a simple way to introduce quantum fluctuations. The strength of the transverse field is controlled as a function of time similarly to the temperature in the conventional method. TSP can be described by the Ising spin, so that we also apply the same technique to TSP. We directory solve the time-dependent Schrödinger equation for small-size systems and perform the quantum Monte Carlo simulation for large-size systems. Comparison with the results of the corresponding classical (thermal) method reveals that the quantum method leads to the ground state with much larger probability in almost all cases if we use the same annealing schedule of the control parameters. We also find that the relaxation time is quite short for quantum systems by numerical simulations. We consider this is one of the reasons why the annealing in quantum systems have a better performance of finding the optimal state in comparison with classical systems.
We review here some recent work in the field of quantum annealing, alias adiabatic quantum computation. The idea of quantum annealing is to perform optimization by a quantum adiabatic evolution which tracks the ground state of a suitable time-dependent Hamiltonian, where 'ℏ' is slowly switched off. We illustrate several applications of quantum annealing strategies, starting from textbook toy-models—double-well potentials and other one-dimensional examples, with and without disorder. These examples display in a clear way the crucial differences between classical and quantum annealing. We then discuss applications of quantum annealing to challenging hard optimization problems, such as the random Ising model, the travelling salesman problem and Boolean satisfiability problems. The techniques used to implement quantum annealing are either deterministic Schrödinger's evolutions, for the toy models, or path-integral Monte Carlo and Green's function Monte Carlo approaches, for the hard optimization problems. The crucial role played by disorder and the associated non-trivial Landau–Zener tunnelling phenomena is discussed and emphasized.