Upper bound inequality for calculation time in simulated annealing analogous to adiabatic theorem in quantum systems
arXiv:2107.01792
Abstract
It has been recently reported that classical systems have speed limit for state evolution, although such a concept of speed limit had been considered to be unique to quantum systems. Owing to the speed limit for classical system, the lower bound for calculation time of simulated annealing with desired calculation accuracy can be derived. However, such a lower bound does not work as a criterion for completion of calculation in a practical time. In this paper, we derive an inequality for classical system analogous to the quantum adiabatic theorem that gives calculation time for an accuracy-guaranteed fluctuation-exploiting computation. The trade-off relation between calculation time and accuracy is given in the form tolerable in practical use.
References in corpus (15)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Ultimate physical limits to computation
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing and Analog Quantum Computation
- Quantum speed limit for non-Markovian dynamics
- Mathematical Foundation of Quantum Annealing
- Quantum limits to dynamical evolution
- Energy-time uncertainty relation for driven quantum systems
- Quantum Speed Limit is Not Quantum
- Markov Chain Monte Carlo Method without Detailed Balance
- Irreversible Monte Carlo Algorithms for Efficient Sampling
- Violation of detailed balance accelerates relaxation
- Mathematical understanding of detailed balance condition violation and its application to Langevin dynamics