Convergence theorems for quantum annealing

DOI10.1088/0305-4470/39/45/004MaRDI QIDQ3419343zbMATH OpenOpenAlexFDO

Authors Satoshi Morita, Hidetoshi Nishimori

Publication date 6 February 2007

Published in Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0608154

Mathematics Subject Classification ID

Variational principles of physics (49S05) Monte Carlo methods (65C05) Quantum computation (81P68) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: 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.

Recommendations

• Convergence of quantum annealing with real-time Schrödinger dynamics
• Mathematical foundation of quantum annealing
• Rigorous convergence condition for quantum annealing
• Quantum annealing of hard problems
• An introduction to quantum annealing

Cited in

(12)

• Embedding equality constraints of optimization problems into a quantum annealer
• Colloquium: Quantum annealing and analog quantum computation
• Convergence of quantum annealing with real-time Schrödinger dynamics
• Mathematical foundation of quantum annealing
• On the treatment of thermal and quantum annealing by stochastic variational means
• Efficiency of quantum vs. classical annealing in nonconvex learning problems
• Rigorous convergence condition for quantum annealing
• Convergence condition of simulated quantum annealing with a non-stoquastic catalyst
• Convergence of the quantum dynamics framework for optimization algorithm
• Evaluating the convergence of tabu enhanced hybrid quantum optimization
• Mean-field behavior of the quantum Ising susceptibility and a new lace expansion for the classical Ising model
• A quantum annealing protocol to solve the nuclear shell model

This page was built for publication: Convergence theorems for quantum annealing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3419343)