An Upper-Bound Inequality for the Calculation Time in Simulated Annealing: A Classical Analogue of the Adiabatic Theorem

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.