Simulated annealing and quantum detailed balance

Matthias Troyer

Toshiyuki Tanaka

We discuss a classical reinterpretation of quantum-mechanics-based analysis of classical Markov chains with detailed balance, that is based on the quantum-classical correspondence. The classical reinterpretation is then used to demonstrate that it successfully reproduces a sufficient condition for cooling schedule in classical simulated annealing, which has the inverse-logarithmic scaling.

Abstract. We discuss a classical reinterpretation of quantum-mechanics-based analysis of classical Markov chains with detailed balance, that is based on the quantum-classical correspondence. The classical reinterpretation is then used to demonstrate that it successfully reproduces a sufficient condition for cooling schedule in classical simulated annealing, which has the inverse-logarithm scaling. 1.

G. Aeppli, T. F. Rosenbaum

Tameem Albash

Akihisa Ichiki, Masayuki Ohzeki

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.