Convergence theorems for quantum annealing
arXiv:quant-ph/0608154 · doi:10.1088/0305-4470/39/45/004
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.
19 pages
References in corpus (12)
- Quantum Annealing in the Transverse Ising Model
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Generalized Simulated Annealing
- Quantum annealing of the Traveling Salesman Problem
- Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
- Residual Energies after Slow Quantum Annealing
- Optimization by Quantum Annealing: Lessons from Simple Cases
- Convergence of simulated annealing by the generalized transition probability
- Quantum Annealing in a Kinetically Constrained System
- Monte Carlo studies of quantum and classical annealing on a double-well
- Optimization in random field Ising models by quantum annealing
Cited by in corpus (23)
- Quantum Annealing and Analog Quantum Computation
- Mathematical Foundation of Quantum Annealing
- Adiabatic quantum dynamics of a random Ising chain across its quantum critical point
- Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
- Application of QUBO solver using black-box optimization to structural design for resonance avoidance
- Convergence of Quantum Annealing with Real-Time Schrodinger Dynamics
- Simulated quantum annealing as a simulator of non-equilibrium quantum dynamics
- Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian
- Simulated quantum annealing of double-well and multi-well potentials
- Fast Quantum Methods for Optimization
- Quantum annealing of an Ising spin-glass by Green's function Monte Carlo
- Quantum Annealing - Foundations and Frontiers
- Pattern-recalling processes in quantum Hopfield networks far from saturation
- Noise amplification at spin-glass bottlenecks of quantum annealing: a solvable model
- Quantum annealing approach to Ionic Diffusion in Solid
- A Quantum Annealing Protocol to Solve the Nuclear Shell Model
- Deterministic flows of order-parameters in stochastic processes of quantum Monte Carlo method
- Convergence condition of simulated quantum annealing for closed and open systems
- Quantum response to time-dependent external fields
- Quantum Spinodal Phenomena
- Quantum-thermal annealing with cluster-flip algorithm
- Relation of classical non-equilibrium dynamics and quantum annealing
- A quantum diffusion network