Mathematical foundation of quantum annealing
From MaRDI portal
Quantum computation (81P68) Quantum dynamics and nonequilibrium statistical mechanics (general) (82C10) Dynamics of disordered systems (random Ising systems, etc.) in time-dependent statistical mechanics (82C44) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)
Abstract: Quantum annealing is a generic name of quantum algorithms to use quantum-mechanical fluctuations to search for the solution of optimization problem. It shares the basic idea with quantum adiabatic evolution studied actively in quantum computation. The present paper reviews the mathematical and theoretical foundation of quantum annealing. In particular, theorems are presented for convergence conditions of quantum annealing to the target optimal state after an infinite-time evolution following the Schroedinger or stochastic (Monte Carlo) dynamics. It is proved that the same asymptotic behavior of the control parameter guarantees convergence both for the Schroedinger dynamics and the stochastic dynamics in spite of the essential difference of these two types of dynamics. Also described are the prescriptions to reduce errors in the final approximate solution obtained after a long but finite dynamical evolution of quantum annealing. It is shown there that we can reduce errors significantly by an ingenious choice of annealing schedule (time dependence of the control parameter) without compromising computational complexity qualitatively. A review is given on the derivation of the convergence condition for classical simulated annealing from the view point of quantum adiabaticity using a classical-quantum mapping.
Recommendations
Cites work
- An effective implementation of the Lin-Kernighan traveling salesman heuristic
- Convergence of quantum annealing with real-time Schrödinger dynamics
- Convergence of simulated annealing using the generalized transition probability
- Convergence theorems for quantum annealing
- scientific article; zbMATH DE number 41891 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1528424 (Why is no real title available?)
- Non-adiabatic crossing of energy levels
- Non-negative matrices and Markov chains.
- On the Product of Semi-Groups of Operators
- Optimization by simulated annealing
- Optimization using quantum mechanics: quantum annealing through adiabatic evolution
- Phase Transitions in Combinatorial Optimization Problems
- Quantum approach to classical statistical mechanics
- Quantum Effects in Neural Networks
- Quantum stochastic optimization
- Relationship among exactly soluble models of critical phenomena. I: 2D Ising model, dimer problem and the generalized XY-model.
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
- The influence of hydrodynamic instability on the structure of cellular flames
Cited in
(30)- Quantum annealing with Markov chain Monte Carlo simulations and D-wave quantum computers
- Quantum annealing learning search for solving QUBO problems
- Quantum-inspired algorithm with fitness landscape approximation in reduced dimensional spaces for numerical function optimization
- Spiking neural network dynamic system modeling for computation of quantum annealing and its convergence analysis
- An introduction to quantum annealing
- Dissipative quantum annealing
- Convergence of quantum annealing with real-time Schrödinger dynamics
- Deterministic quantum annealing expectation-maximization algorithm
- Convergence theorems for quantum annealing
- Quantum Annealing via Path-Integral Monte Carlo With Data Augmentation
- A complete restricted Boltzmann machine on an adiabatic quantum computer
- Correlation inequalities for quantum spin systems with quenched centered disorder
- Quantum annealing with Jarzynski equality
- Quantum clock models with infinite-range interactions
- Rigorous convergence condition for quantum annealing
- Convergence condition of simulated quantum annealing with a non-stoquastic catalyst
- Statistical Analysis of Quantum Annealing
- Solving larger maximum clique problems using parallel quantum annealing
- Extracting a function encoded in amplitudes of a quantum state by tensor network and orthogonal function expansion
- Convergence of the quantum dynamics framework for optimization algorithm
- Mathematical aspects of the Digital Annealer's simulated annealing algorithm
- Deep learning optimal quantum annealing schedules for random Ising models
- Adiabatic theorem for classical stochastic processes
- Hidden symmetries, spin and charge of artificial magnetic monopoles
- Quantum Ising chain with time-averaged work in linear response theory
- Quantum computing for discrete optimization: a highlight of three technologies
- Quantum computing and the stable set problem
- 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
- Quantum adiabatic theorem for unbounded Hamiltonians with a cutoff and its application to superconducting circuits
This page was built for publication: Mathematical foundation of quantum annealing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3624670)
