Convergence of Quantum Annealing with Real-Time Schrodinger Dynamics

Abstract

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.

6 pages, minor corrections

References in corpus (9)

• 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
• Quantum annealing of the Traveling Salesman Problem
• Residual Energies after Slow Quantum Annealing
• Optimization by Quantum Annealing: Lessons from Simple Cases
• Convergence theorems for quantum annealing
• Quantum Annealing in a Kinetically Constrained System
• Monte Carlo studies of quantum and classical annealing on a double-well

Cited by in corpus (18)

• Quantum Annealing and Analog Quantum Computation
• Mathematical Foundation of Quantum Annealing
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian
• Discretized quantum adiabatic process for free fermions and comparison with the imaginary-time evolution
• Lossy compression of matrices by black-box optimisation of mixed integer nonlinear programming
• Mechanism of Slow Relaxation due to Screening Effect in a Frustrated System
• Finding Optimal Pathways in Chemical Reaction Networks Using Ising Machines
• Post-processing variationally scheduled quantum algorithm for constrained combinatorial optimization problems
• Eigenvalue-invariant transformation of Ising problem for anti-crossing mitigation in quantum annealing
• Convergence condition of simulated quantum annealing for closed and open systems
• Quantum Spinodal Phenomena
• Quantum response to time-dependent external fields
• Quantum-thermal annealing with cluster-flip algorithm
• Quantum Phase Transition in Fully-Connected Quantum Wajnflasz-Pick Model
• Relation of classical non-equilibrium dynamics and quantum annealing
• Convergence condition of simulated quantum annealing with a non-stoquastic catalyst
• Structural Comparison of Error Mitigation Methods for Ising Machines: Penalty-Spin Model versus Stacked Model