Mathematical foundation of quantum annealing
By Satoshi Morita, Hidetoshi Nishimori. 2008
370 citations recorded by the source corpus.
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 Schrodinger or stochastic (Monte Carlo) dynamics. It is proved that the same asymptotic behavior of the control parameter guarantees convergence for both the Schrodinger 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.
Subfields: Artificial Intelligence
View Paper: https://www.semanticscholar.org/paper/32053071882c8ec7ee89adb5d06b19ca7d13ab84
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Tameem Albash
- Daniel A. Lidar
- Göran Wendin
- Vadim N. Smelyanskiy
- Matthias Troyer
- Dave Wecker
- Zhihui Wang
- Troels F. Rønnow
Citations in the corpus
- Quantum annealing for industry applications: introduction and review (2021, neutral): “An approach closely related to AQC is QA [44, 81, 122, 126, 172], proposed in 1988 by Apolloni et al [10].”
- Decoherence in adiabatic quantum computation (2015, background): “(57) In this setting adiabatic quantum computing is also known as quantum annealing [41, 73].”
- Evidence for quantum annealing with more than one hundred qubits (2013, background): “[7, 9], “Quantum Monte Carlo Annealing” versus “QA with real time adiabatic evolution” in Ref.”
- Quantum Optimization of Fully-Connected Spin Glasses (2014, background): “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”