Convergence of Quantum Annealing with Real-Time Schrödinger Dynamics
- Full text:
- PDF (eReader) / PDF (Download) (76 kB)
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 Schrödinger 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.
References
- 1 T.Kadowaki and H.Nishimori:Phys. Rev. E 58 (1998) 5355. Crossref, Google Scholar
- 2 A.Das and B. K.Chakrabarti:Quantum Annealing and Related Optimization Methods. (Springer, Berlin, Heidelberg, 2005) Lecture Notes in Physics, Vol. 679. Google Scholar
- 3 G. E.Santoro and E.Tosatti:J. Phys. A 39 (2006) R393. Crossref, Google Scholar
- 4 A. B.Finnila, M. A.Gomez, D.Sebenik, C.Stenson, and J. D.Doll:Chem. Phys. Lett. 219 (1994) 343. Crossref, Google Scholar
- 5 E.Farhi, J.Goldstone, S.Gutmann, and M.Sipser: quant-ph/0001106. Google Scholar
- 6 G. E.Santoro, R.Martoňák, E.Tosatti, and R.Car:Science 295 (2002) 2427. Crossref, Google Scholar
- 7 R.Martoňák, G. E.Santoro, and E.Tosatti:Phys. Rev. B 66 (2002) 094203. Crossref, Google Scholar
- 8 S.Suzuki and M.Okada:J. Phys. Soc. Jpn. 74 (2005) 1649. Link, Google Scholar
- 9 M.Sarjala, V.Petäjä, and M.Alava: J. Stat. Mech. (2006) P01008. Crossref, Google Scholar
- 10 Y.-H.Lee and B. J.Berne:J. Phys. Chem. A 104 (2000) 86. Crossref, Google Scholar
- 11 P.Liu and B. J.Berne:J. Chem. Phys. 118 (2003) 2999. Crossref, Google Scholar
- 12 R.Martoňák, G. E.Santoro, and E.Tosatti:Phys. Rev. E 70 (2004) 057701. Crossref, Google Scholar
- 13 L.Stella, G. E.Santoro, and E.Tosatti:Phys. Rev. B 72 (2005) 014303. Crossref, Google Scholar
- 14 L.Stella, G. E.Santoro, and E.Tosatti:Phys. Rev. B 73 (2006) 144302. Crossref, Google Scholar
- 15 A.Das, B. K.Chakrabarti, and R. B.Stinchcombe:Phys. Rev. E 72 (2005) 026701. Crossref, Google Scholar
- 16 S.Kirkpatrick, S. D.Gelett, and M. P.Vecchi:Science 220 (1983) 671 Crossref, Google Scholar
- 17 E.Aarts and J.Korst:Simulated Annealing and Boltzmann Machines: a Stochastic Approach to Combinatorial Optimization and Neural Computing (Wiley, New York, 1989) Chap. 3, p. 33. Google Scholar
- 18 S.Morita and H.Nishimori:J. Phys. A 39 (2006) 13903. Crossref, Google Scholar
- 19 S.Geman and D.Geman: IEEE Trans. Pattern Anal. Mach. Intell. 6 (1984) 721. Crossref, Google Scholar
- 20 R. D.Somma, C. D.Batista, and G.Ortiz: quant-ph/0609216. Google Scholar
- 21 A.Messiah:Quantum Mechanics (Wiley, New York, 1976). Google Scholar
- 22 E.Hopf: J. Math. Mech. 12 (1963) 683. Google Scholar
- 23 S.Suzuki, H.Nishimori, and M.Suzuki: to be published in Phys. Rev. E; quant-ph/0702214. Google Scholar