Simulated Quantum Annealing by the Real-time Evolution

Yusuke Kimura, Hidetoshi Nishimori

Simulated quantum annealing is a generic classical protocol to simulate some aspects of quantum annealing and is sometimes regarded as a classical alternative to quantum annealing in finding the ground state of a classical Ising model. We derive a generic condition for simulated quantum annealing to converge to thermal equilibrium at a given, typically low, temperature. Both closed and open systems are treated. We rewrite the classical master equation for simulated quantum annealing into an imaginary-time Schr\"odinger equation, to which we apply the imaginary-time variant of the asymptotic adiabatic condition to deduce the convergence condition. The result agrees qualitatively with a rigorous convergence condition of simulated quantum annealing for closed systems, which was derived from the theory of inhomogeneous Markov processes. Also observed is qualitative agreement with a rigorous convergence condition of quantum annealing for closed systems under the real-time Schr\"odinger dynamics. This coincidence of convergence conditions for classical stochastic processes for simulated quantum annealing and the real-time quantum dynamics for quantum annealing is highly nontrivial and calls for further scrutiny.

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

Du Weilin, Li Bin, Yu Peng Tian

Lorenzo Stella, Giuseppe E. Santoro, Erio Tosatti

We investigate the basic behavior and performance of simulated quantum annealing (QA) in comparison with classical annealing (CA). Three simple one-dimensional case study systems are considered: namely, a parabolic well, a double well, and a curved washboard. The time-dependent Schr\"odinger evolution in either real or imaginary time describing QA is contrasted with the Fokker-Planck evolution of CA. The asymptotic decrease of excess energy with annealing time is studied in each case, and the reasons for differences are examined and discussed. The Huse-Fisher classical power law of double-well CA is replaced with a different power law in QA. The multiwell washboard problem studied in CA by Shinomoto and Kabashima and leading classically to a logarithmic annealing even in the absence of disorder turns to a power-law behavior when annealed with QA. The crucial role of disorder and localization is briefly discussed.

Matthias Troyer

Satoshi Morita, Hidetoshi Nishimori

Convergence conditions for quantum annealing are derived for optimization problems represented by the Ising model of a general form. Quantum fluctuations are introduced as a transverse field and/or transverse ferromagnetic interactions, and the time evolution follows the real-time Schrodinger equation. It is shown that the system stays arbitrarily close to the instantaneous ground state, finally reaching the target optimal state, if the strength of quantum fluctuations decreases sufficiently slowly, in particular inversely proportionally to the power of time in the asymptotic region. This is the same condition as the other implementations of quantum annealing, quantum Monte Carlo and Green's function Monte Carlo simulations, in spite of the essential difference in the type of dynamics. The method of analysis is an application of the adiabatic theorem in conjunction with an estimate of a lower bound of the energy gap based on the recently proposed idea of Somma et. al. for the analysis of classical simulated annealing using a classical-quantum correspondence.