Mathematical foundation of quantum annealing
Open accessThe DOI matches its Crossref record; 49 of the 50 references it cites were found in a registry or an index.
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“The adiabatic theorem of quantum mechanics ensures that QA identi fi es the optimal solution regardless of the size and landscape of the combinatorial parametric space, highlighting QA as a powerful and practical solver 11 -14 .”
From Quantum annealing for combinatorial optimization: a benchmarking study (2025) · cites this paper as [14]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
(1979) · Cited by 43,841
Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.
Geman, S., & Geman, D. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767596 · Cited by 17,949
Messiah, A. (1961) · Cited by 16,012
Press, W. H., Teukolsky, S. A., Vetterling, W. T., & Flannery, B. P. (1994) · Cited by 15,411
Ground State of the Electron Gas by a Stochastic Method
Ceperley, D. M., & Alder, B. J. (1980) · Physical Review Letters · doi:10.1103/physrevlett.45.566 · Cited by 14,384
Doob, J. L., & Doob, J. L. (1953) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,053
Non-adiabatic crossing of energy levels
Zener, C. (1932) · Proceedings of the Royal Society of London Series A Containing Papers of a Mathematical and Physical Character · doi:10.1098/rspa.1932.0165 · Cited by 4,572
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306
Non-negative Matrices and Markov Chains
Seneta, E. (1981) · Springer Series in Statistics · doi:10.1007/0-387-32792-4 · Cited by 2,807 · cited 1×
“The condition Γ(t) < Γ0 (t > t0) is unnecessary here because the off-diagonal element χ can always be chosen smaller than the diagonal elements by adding a positive constant to the diagonal.”
BackgroundQuantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339
Self-citationOn the product of semi-groups of operators
Trotter, H. F. (1959) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1959-0108732-6 · Cited by 2,282
A Guide to Monte Carlo Simulations in Statistical Physics
Landau, D. P., & Binder, K. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139696463 · Cited by 2,257
An effective implementation of the Lin–Kernighan traveling salesman heuristic
Helsgaun, K. (2000) · European Journal of Operational Research · doi:10.1016/s0377-2217(99)00284-2 · Cited by 1,630
(1990) · Discrete Applied Mathematics · doi:10.1016/0166-218x(90)90039-f · Cited by 1,440
Theory of Quantum Annealing of an Ising Spin Glass
Santoro, G. E., Martoňák, R., Tosatti, E., & Car, R. (2002) · Science · doi:10.1126/science.1068774 · Cited by 734
Colloquium : Quantum annealing and analog quantum computation
Das, A., & Chakrabarti, B. K. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1061 · Cited by 700
Quantum annealing: A new method for minimizing multidimensional functions
Finnila, A. B., Gomez, M. A., Sebenik, C., Stenson, C., & Doll, J. D. (1994) · Chemical Physics Letters · doi:10.1016/0009-2614(94)00117-0 · Cited by 644
Quantum search by local adiabatic evolution
Roland, J., & Cerf, N. J. (2002) · Physical Review A · doi:10.1103/physreva.65.042308 · Cited by 629
Generalized simulated annealing
Tsallis, C., & Stariolo, D. A. (1996) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(96)00271-3 · Cited by 503
Optimization using quantum mechanics: quantum annealing through adiabatic evolution
Santoro, G. E., & Tosatti, E. (2006) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/39/36/r01 · Cited by 354
On the Product of Semi-Groups of Operators
Trotter, H. F. (1959) · Proceedings of the American Mathematical Society · doi:10.2307/2033649 · Cited by 322
Quantum Annealing and Other Optimization Methods
(2005) · Lecture Notes in Physics · doi:10.1007/11526216 · Cited by 296
Suzuki, M. (1971) · Progress of Theoretical Physics · doi:10.1143/ptp.46.1337 · Cited by 277
Hartmann, A. K., & Weigt, M. (2005) · Wiley eBooks · doi:10.1002/3527606734 · Cited by 267
Ground-state correlations of quantum antiferromagnets: A Green-function Monte Carlo study
Trivedi, N., & Ceperley, D. M. (1990) · Physical Review B · doi:10.1103/physrevb.41.4552 · Cited by 238
Simple Proof of Equivalence between Adiabatic Quantum Computation and the Circuit Model
Mizel, A., Lidar, D. A., & Mitchell, M. (2007) · Physical Review Letters · doi:10.1103/physrevlett.99.070502 · Cited by 217
Quantum stochastic optimization
Apolloni, B., Carvalho, C., & de Falco, D. (1989) · Stochastic Processes and their Applications · doi:10.1016/0304-4149(89)90040-9 · Cited by 207
Quantum annealing of the traveling-salesman problem
Martoňák, R., Santoro, G. E., & Tosatti, E. (2004) · Physical Review E · doi:10.1103/physreve.70.057701 · Cited by 195
Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising model
Martoňák, R., Santoro, G. E., & Tosatti, E. (2002) · Physical review. B, Condensed matter · doi:10.1103/physrevb.66.094203 · Cited by 171
Quantum Annealing and Related Optimization Methods
Das, A., & Chakrabarti, B. K. (2008) · Cited by 142
Quantum Approach to Classical Statistical Mechanics
Somma, R. D., Batista, C. D., & Ortiz, G. (2007) · Physical Review Letters · doi:10.1103/physrevlett.99.030603 · Cited by 87
Study of Optimization Problems by Quantum AnnealingPreprint
Kadowaki, T. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0205020 · Cited by 69 · cited 1×
“Let us now turn our attention to quantum annealing [6, 7, 8 , 9, 10, 11] 1 . In SA, we make use of thermal (classical) fluctuations to let the system hop from state to state over intermediate energy barriers to search for the desired lowest-energy state.”
Optimization by quantum annealing: Lessons from simple cases
Stella, L., Santoro, G. E., & Tosatti, E. (2005) · Physical Review B · doi:10.1103/physrevb.72.014303 · Cited by 67
Residual Energies after Slow Quantum Annealing
Suzuki, S., & Okada, M. (2005) · Journal of the Physical Society of Japan · doi:10.1143/jpsj.74.1649 · Cited by 64
Convergence theorems for quantum annealing
Morita, S., & Nishimori, H. (2006) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/39/45/004 · Cited by 59
Self-citationStochastic Processes, Physics and Geometry II
Albeverio, S. A., Cattaneo, U., & Merlini, D. (1995) · doi:10.1142/9789814533195 · Cited by 54
Convergence of Quantum Annealing with Real-Time Schrödinger Dynamics
Morita, S., & Nishimori, H. (2007) · Journal of the Physical Society of Japan · doi:10.1143/jpsj.76.064002 · Cited by 51
Self-citationConvergence of simulated annealing using the generalized transition probability
Nishimori, H., & Inoue, J.-I. (1998) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/31/26/007 · Cited by 50
Self-citationQuantum annealing in a kinetically constrained system
Das, A., Chakrabarti, B. K., & Stinchcombe, R. B. (2005) · Physical Review E · doi:10.1103/physreve.72.026701 · Cited by 46
Quantum Effects in Neural Networks
Nishimori, H., & Nonomura, Y. (1996) · Journal of the Physical Society of Japan · doi:10.1143/jpsj.65.3780 · Cited by 41
Self-citationQuantum annealing of the random-field Ising model by transverse ferromagnetic interactions
Suzuki, S., Nishimori, H., & Suzuki, M. (2007) · Physical Review E · doi:10.1103/physreve.75.051112 · Cited by 37
Self-citationQuantum annealing of an Ising spin-glass by Green’s function Monte Carlo
Stella, L., & Santoro, G. E. (2007) · Physical Review E · doi:10.1103/physreve.75.036703 · Cited by 22
Faster Annealing Schedules for Quantum Annealing
Morita, S. (2007) · Journal of the Physical Society of Japan · doi:10.1143/jpsj.76.104001 · Cited by 20
Self-citationMonte Carlo studies of quantum and classical annealing on a double well
Stella, L., Santoro, G. E., & Tosatti, E. (2006) · Physical Review B · doi:10.1103/physrevb.73.144302 · Cited by 19
Stochastic Processes, Physics and Geometry
(1990) · doi:10.1142/0932 · Cited by 19
Optimization in random field Ising models by quantum annealing
Sarjala, M., Petäjä, V., & Alava, M. J. (2006) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2006/01/p01008 · Cited by 19
Faster annealing schedules for quantum annealing
Morita, S. (2007) · CERN Document Server (European Organization for Nuclear Research) · Cited by 7
Self-citationAnalytic study of quantum annealing
森田, 悟. (2008) · Medical Entomology and Zoology · Cited by 1
Research works printed but not linked: 7
- T. Kadowaki , “Study of optimization problems by quantum annealing,” PhD thesis, Tokyo Institute of Technology, 1999;
- A. Das and B. K.Chakrabarti , e-print arXiv:0801.2193; · arXiv
- Quantum Annealing and Analog Quantum Computation
- 2006, J. Stat. Mech.: Theory Exp., P01008
- E. Farhi, J. Goldstone, S. Gutomann, and M. Sipser, e-print arXiv:quant-ph/0001106. · arXiv
- 1976, Quantum Mechanics
- 1963, J. Math. Mech., 12, 683
Cited by
Programmable Quantum Simulations of Spin Systems with Trapped Ions
Monroe, C., Campbell, W. C., Duan, L. M., Gong, Z. X., Gorshkov, A. V., Hess, P., Islam, R., Kim, K., Linke, N., Pagano, G., et al. (2019) · arXiv · doi:10.48550/arxiv.1912.07845 · Cited by 806
Programmable quantum simulations of spin systems with trapped ions
Monroe, C., Campbell, W. C., Duan, L.-M., Gong, Z.-X., Gorshkov, A. V., Hess, P. W., Islam, R., Kim, K., Linke, N. M., Pagano, G., et al. (2021) · Reviews of Modern Physics · doi:10.1103/revmodphys.93.025001 · Cited by 802
Quantum annealing for industry applications: introduction and review
Yarkoni, S., Raponi, E., Bäck, T., & Schmitt, S. (2022) · Reports on Progress in Physics · doi:10.1088/1361-6633/ac8c54 · Cited by 341
“An approach closely related to AQC is QA [44, 81, 122, 126, 172], proposed in 1988 by Apolloni et al [10].”
Experimental signature of programmable quantum annealing
Boixo, S., Albash, T., Spedalieri, F. M., Chancellor, N., & Lidar, D. A. (2013) · Nature Communications · doi:10.1038/ncomms3067 · Cited by 293
Quantum Optimization of Fully Connected Spin Glasses
Venturelli, D., Mandrà, S., Knysh, S., O’Gorman, B., Biswas, R., & Smelyanskiy, V. (2015) · Physical Review X · doi:10.1103/physrevx.5.031040 · Cited by 209
“While the founding principles of the technique have been investigated numerically [3], analytically [4,5], and experimentally [6] in the past decade, the disordered, interacting, time-dependent, and open nature of the many-body problem makes it very hard to draw universal conclusions about the power of the technique […”
Background
Metadata
- Authors
- Morita, S., & Nishimori, H.
- Affiliations
- Scuola Internazionale Superiore di Studi Avanzati (IT)
- Tokyo Institute of Technology (JP)
- Venue
- Journal of Mathematical Physics
- Publisher
- AIP Publishing
- Published
- 2008-12-01
- Volume
- 49
- Issue
- 12
- ISSN
- 0022-2488 (ISSN-L)
- 1089-7658
- OpenAlex
- W2019013791
- Semantic Scholar
- 32053071882c8ec7ee89adb5d06b19ca7d13ab84
- Cited by
- 381
- References
- 50
- Citations by year
- 2026: 24 · 2025: 61 · 2024: 55 · 2023: 43 · 2022: 36 · 2021: 32 · 2020: 18 · 2019: 22 · 2018: 15 · 2017: 14 · 2016: 11 · 2015: 17 · 2014: 6 · 2013: 5 · 2012: 8
- FWCI
- 7.39
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Journal of Mathematical Physics (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- quantum annealing, quantum adiabatic evolution, optimization problems, convergence conditions, Schrödinger dynamics, stochastic dynamics, Monte Carlo dynamics, annealing schedule, error reduction, simulated annealing
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.