Convergence theorems for quantum annealing

悟史 森田, Satoshi Morita, 秀稔 西森 +1 more

Alexander Rumyantsev, Davide Pastorello, Enrico Blanzieri +1 more

Satoshi Morita, Hidetoshi Nishimori

悟史 森田, Satoshi Morita, 秀稔 西森 +1 more

Yusuke Kimura, Hidetoshi Nishimori

Abstract We derive a generic bound on the rate of decrease of transverse field for quantum annealing to converge to the ground state of a generic Ising model when quantum annealing is formulated as an infinite-time process. Our theorem is based on a rigorous upper bound on the excitation probability in the infinite-time limit and is a mathematically rigorous counterpart of a previously known result derived only from the leading-order term of the asymptotic expansion of adiabatic condition. Since our theorem gives a sufficient condition of convergence for a generic transverse-field Ising model, any specific problem may allow a better, faster, control of the coefficient.

Satoshi Morita, Hidetoshi Nishimori

We prove several theorems to give sufficient conditions for convergence of quantum annealing, which is a protocol to solve generic optimization problems by quantum dynamics. In particular the property of strong ergodicity is proved for the path-integral Monte Carlo implementation of quantum annealing for the transverse Ising model under a power decay of the transverse field. This result is to be compared with the much slower inverse-log decay of temperature in the conventional simulated annealing. Similar results are proved for the Green's function Monte Carlo approach. Optimization problems in continuous space of particle configurations are also discussed.