Mathematical Foundation of Quantum Annealing

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.

51pages, 8 figures

References in corpus (22)

• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum Annealing in the Transverse Ising Model
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Annealing and Analog Quantum Computation
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• Quantum Search by Local Adiabatic Evolution
• Generalized Simulated Annealing
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• Quantum annealing of the Traveling Salesman Problem
• A Quantum Approach to Classical Statistical Mechanics
• Residual Energies after Slow Quantum Annealing
• Optimization by Quantum Annealing: Lessons from Simple Cases
• Convergence theorems for quantum annealing
• Convergence of simulated annealing by the generalized transition probability
• Study of Optimization Problems by Quantum Annealing
• Quantum Effects in Neural Networks
• Convergence of Quantum Annealing with Real-Time Schrodinger Dynamics
• Quantum annealing of the random-field Ising model by transverse ferromagnetic interactions
• Quantum Annealing in a Kinetically Constrained System
• Quantum annealing of an Ising spin-glass by Green's function Monte Carlo
• Monte Carlo studies of quantum and classical annealing on a double-well
• Faster annealing schedules for quantum annealing

Cited by in corpus (191)

• Programmable Quantum Simulations of Spin Systems with Trapped Ions
• Quantum Annealing for Industry Applications: Introduction and Review
• Experimental signature of programmable quantum annealing
• Quantum Optimization of Fully-Connected Spin Glasses
• Error corrected quantum annealing with hundreds of qubits
• Efficient partition of integer optimization problems with one-hot encoding
• Quantum Annealing: An Overview
• Exotic Freezing of Response in Quantum Many-Body System
• Decoherence in adiabatic quantum computation
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• Quantum annealing with antiferromagnetic fluctuations
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Reverse annealing for the fully connected $p$-spin model
• Quantum annealing correction for random Ising problems
• Reexamining classical and quantum models for the D-Wave One processor
• Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Scaling and diabatic effects in quantum annealing with a D-Wave device
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Benchmarking Quantum Annealing Controls with Portfolio Optimization
• Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
• Multivariable Optimization: Quantum Annealing & Computation
• Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
• A deceptive step towards quantum speedup detection
• Quantum Volume in Practice: What Users Can Expect from NISQ Devices
• MAX 2-SAT with up to 108 qubits
• Feature Selection on Quantum Computers
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
• Nested Quantum Annealing Correction
• Quantum pattern recognition with liquid-state nuclear magnetic resonance
• An introduction to quantum annealing
• Uncertain fate of fair sampling in quantum annealing
• Travel time optimization on multi-AGV routing by reverse annealing
• Scaling overhead of embedding optimization problems in quantum annealing
• Benchmark test of Black-box optimization using D-Wave quantum annealer
• Two-parameter counter-diabatic driving in quantum annealing
• Constant-adiabaticity RF-pulses for generating long-lived singlet spin states in NMR
• Quantum Computing for Fusion Energy Science Applications
• Quantum annealing with Jarzynski equality
• Quantum annealing via environment-mediated quantum diffusion
• Comparative Study of the Performance of Quantum Annealing and Simulated Annealing
• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• Relation between quantum fluctuations and the performance enhancement of quantum annealing in a nonstoquastic Hamiltonian
• Simulated quantum annealing as a simulator of non-equilibrium quantum dynamics
• Fair Sampling by Simulated Annealing on Quantum Annealer
• Variational optimization of the quantum annealing schedule for the Lechner-Hauke-Zoller scheme
• Hybrid Quantum Annealing via Molecular Dynamics
• Quantum Annealing Learning Search for solving QUBO problems
• Solving Larger Maximum Clique Problems Using Parallel Quantum Annealing
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Constant-adiabaticity ultralow magnetic field manipulations of parahydrogen-induced polarization: application to an AA'X spin system
• Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics
• Quantum annealing speedup over simulated annealing on random Ising chains
• Optimal Control for Closed and Open System Quantum Optimization
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian
• Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
• Variational counterdiabatic driving of the Hubbard model for ground-state preparation
• Energy gap at first-order quantum phase transitions: An anomalous case
• Complex semiclassical analysis of the Loschmidt amplitude and dynamical quantum phase transitions
• Simulated quantum annealing of double-well and multi-well potentials
• A symbolic approach to discrete structural optimization using quantum annealing
• Fast Quantum Methods for Optimization
• Greedy parameter optimization for diabatic quantum annealing
• Understanding Quantum Tunneling using Diffusion Monte Carlo Simulations
• Experimental and Theoretical Study of Thermodynamic Effects in a Quantum Annealer
• Breakdown of the weak coupling limit in quantum annealing
• Detecting many-body Bell non-locality by solving Ising models
• Anomalous behavior of the energy gap in the one-dimensional quantum XY model
• Discretized quantum adiabatic process for free fermions and comparison with the imaginary-time evolution
• The three phases of quantum annealing: fast, slow, and very slow
• Fair sampling of ground-state configurations of binary optimization problems
• Quantum and classical annealing in a continuous space with multiple local minima
• Counterdiabatic Reverse Annealing
• Retrieving the ground state of spin glasses using thermal noise: Performance of quantum annealing at finite temperatures
• Statistical-mechanical analysis of compressed sensing for Hamiltonian estimation of Ising spin glass
• Noise Dynamics of Quantum Annealers: Estimating the Effective Noise Using Idle Qubits
• Dynamical Singularities of Glassy Systems in a Quantum Quench
• Correlation Inequalities for Quantum Spin Systems with Quenched Centered Disorder
• Exponential capacity of associative memories under quantum annealing recall
• Thermal, quantum and simulated quantum annealing: analytical comparisons for simple models
• Initial State Encoding via Reverse Quantum Annealing and h-gain Features
• Elementary Proof of QAOA Convergence
• Nonequilibrium work on spin glasses in longitudinal and transverse fields
• Mean-Field Solution of the Weak-Strong Cluster Problem for Quantum Annealing with Stoquastic and Non-Stoquastic Catalysts
• Deep learning optimal quantum annealing schedules for random Ising models
• Effectiveness of quantum annealing for continuous-variable optimization
• Quantum accelerated approach to the thermal state of classical spin systems with applications to pattern-retrieval in the Hopfield neural network
• Cyclic Quantum Annealing: Searching for Deep Low-Energy States in 5000-Qubit Spin Glass
• Quantum annealing with twisted fields
• Performance enhancement of quantum annealing under the Lechner-Hauke-Zoller scheme by non-linear driving of the constraint term
• Exploration of new chemical materials using black-box optimization with the D-wave quantum annealer
• Advantage of pausing: parameter setting for quantum annealers
• Test Case Minimization with Quantum Annealers
• A small-world search for quantum speedup: How small-world interactions can lead to improved quantum annealer designs
• 4-clique Network Minor Embedding for Quantum Annealers
• Deterministic Quantum Annealing Expectation-Maximization Algorithm
• On the Question of Ergodicity in Quantum Spin Glass Phase and its role in Quantum Annealing
• Feeding the multitude: A polynomial-time algorithm to improve sampling
• Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts
• Finding Optimal Pathways in Chemical Reaction Networks Using Ising Machines
• A Logarithmic Bayesian Approach to Quantum Error Detection
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Nonequilibrium work performed in quantum annealing
• Efficient quantum and simulated annealing of Potts models using a half-hot constraint
• Message-passing algorithm of quantum annealing with nonstoquastic Hamiltonian
• Petri Net Modeling for Ising Model Formulation in Quantum Annealing
• Failure of the geometric approach prediction of excess work scaling for open and isolated quantum systems
• Shortcuts to thermodynamic quasistaticity
• Dynamics of open quantum systems by interpolation of von Neumann and classical master equations, and its application to quantum annealing
• Quantum Annealing search of Ising spin glass ground state(s) with tunable transverse & longitudinal fields
• Adiabatic approximation for the imaginary-time Schroedinger equation and its application to simulated annealing
• Quantum annealing with a nonvanishing final value of the transverse field
• Rigorous convergence condition for quantum annealing
• Eigenvalue-invariant transformation of Ising problem for anti-crossing mitigation in quantum annealing
• A Quantum Annealing Protocol to Solve the Nuclear Shell Model
• Convergence condition of simulated quantum annealing for closed and open systems
• Exact expression of the energy gap at first-order quantum phase transitions of a non-stoquastic Hamiltonian
• Effects of low-lying excitations on ground-state energy and energy gap of Sherrington-Kirkpatrick model in transverse field
• Reusability Report: Comparing gradient descent and monte carlo tree search optimization of quantum annealing schedules
• How to experimentally evaluate the adiabatic condition for quantum annealing
• Analysis of the shortest vector problems with the quantum annealing to search the excited states
• Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems
• Difference between quantum annealing by imaginary-time and real-time Schrödinger equation of Grover's search
• Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer
• The effect of quantum fluctuations on the coloring of random graphs
• Quantum adiabatic theorem for unbounded Hamiltonians with a cutoff and its application to superconducting circuits
• Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
• Quantum Ising chain with time-averaged work in linear response theory
• Analysis of a Programmable Quantum Annealer as a Random Number Generator
• Nonstoquastic catalyst for bifurcation-based quantum annealing of ferromagnetic $p$-spin model
• Spectroscopic estimation of the photon number for superconducting Kerr parametric oscillators
• Analyzing the Effectiveness of Quantum Annealing with Meta-Learning
• Cost of Emulating a Small Quantum Annealing Problem in the Circuit-Model
• Quantum Phase Transition in Fully-Connected Quantum Wajnflasz-Pick Model
• Quantum clock models with infinite-range interactions
• Enhancing Quantum Annealing in Digital-Analog Quantum Computing
• Quantum annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy
• Mapping State Transition Susceptibility in Quantum Annealing
• Reformulating Regression Test Suite Optimization using Quantum Annealing -- an Empirical Study
• Posiform Planting: Generating QUBO Instances for Benchmarking
• Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
• Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
• Quantum computing and the stable set problem
• Absence of small-world effects at the quantum level and stability of the quantum critical point
• Quantum Annealing and Computation: A Brief Documentary Note
• Development of research network on Quantum Annealing Computation and Information using Google Scholar data
• Reduction of the energy-gap scaling by coherent catalysis in models of quantum annealing
• Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA
• Assessing the performance of quantum annealing with nonlinear driving
• Effect of Quantum Statistics on Computational Power of Atomic Quantum Annealers
• Analytical shortcuts to adiabaticity of weakly driven processes
• Population annealing with topological defect driven nonlocal updates for spin systems with quenched disorder
• Adiabatic theorem for classical stochastic processes
• Comparing Quantum Annealing and Spiking Neuromorphic Computing for Sampling Binary Sparse Coding QUBO Problems
• A Variable Neighbourhood Descent Heuristic for Conformational Search Using a Quantum Annealer
• Optimization of neural networks via finite-value quantum fluctuations
• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
• Transfer Learning for Deep-Unfolded Combinatorial Optimization Solver with Quantum Annealer
• The anomalously slow dynamics of inhomogeneous quantum annealing
• Noise Effects on Diabatic Quantum Annealing Protocols
• A Statistical Analysis for Per-Instance Evaluation of Stochastic Optimizers: Avoiding Unreliable Conclusions
• Hardware-efficient quantum annealing with error mitigation via classical shadow
• Optimal Quantum Likelihood Estimation
• Convergence condition of simulated quantum annealing with a non-stoquastic catalyst
• Relation of classical non-equilibrium dynamics and quantum annealing
• Relaxation of the EM Algorithm via Quantum Annealing for Gaussian Mixture Models
• Multi-tasking through quantum annealing
• Lack of a thermodynamic finite-temperature spin-glass phase in the two-dimensional randomly-coupled ferromagnet
• Magnetic Hysteresis Experiments Performed on Quantum Annealers
• Statistical mechanical models of integer factorization problem
• Re`class'ification of `quant'ified classical simulated annealing
• Standardization of Multi-Objective QUBOs
• Robust phase estimation of the ground-state energy without controlled time evolution on a quantum device
• Statistical Analysis of Quantum Annealing
• A useful fundamental speed limit for the imaginary-time Schrodinger equation
• Hidden local adiabatic ramp in the modulated time evolution and the quantum approximate optimization algorithm
• Optimization of conveyance of quantum particles by moving potential well
• Formulation and evaluation of ocean dynamics problems as optimization problems for quantum annealing machines
• Upper bound inequality for calculation time in simulated annealing analogous to adiabatic theorem in quantum systems
• Q-CHOP: Quantum constrained Hamiltonian optimization
• Assessing the quantumness of the annealing dynamics via Leggett Gargs inequalities: a weak measurement approach
• Quantum-inspired search method for low-energy states of classical Ising Hamiltonians
• Generation of all-to-all connections in a two-dimensional qubit array with two-body interactions
• Quantum speed-up for solving the one-dimensional Hubbard model using quantum annealing
• Boltzmann Sampling of Frustrated J1 - J2 Ising Models with Programmable Quantum Annealers
• Structural Comparison of Error Mitigation Methods for Ising Machines: Penalty-Spin Model versus Stacked Model