The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective

Abstract

Among various algorithms designed to exploit the specific properties of quantum computers with respect to classical ones, the quantum adiabatic algorithm is a versatile proposition to find the minimal value of an arbitrary cost function (ground state energy). Random optimization problems provide a natural testbed to compare its efficiency with that of classical algorithms. These problems correspond to mean field spin glasses that have been extensively studied in the classical case. This paper reviews recent analytical works that extended these studies to incorporate the effect of quantum fluctuations, and presents also some original results in this direction.

151 pages, 21 figures

References in corpus (149)

• Non-Abelian Anyons and Topological Quantum Computation
• Quantum Mechanics helps in searching for a needle in a haystack
• Elementary gates for quantum computation
• Quantum algorithm for solving linear systems of equations
• Efficient classical simulation of slightly entangled quantum computations
• The Physical Implementation of Quantum Computation
• Quantum Annealing in the Transverse Ising Model
• Theoretical perspective on the glass transition and amorphous materials
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Strengths and Weaknesses of Quantum Computing
• Real time evolution using the density matrix renormalization group
• Quantum random walks - an introductory overview
• Quantum Algorithms Revisited
• Quantum Computation and Decision Trees
• Time-dependent density-matrix renormalization-group using adaptive effective Hilbert spaces
• Two-Bit Gates are Universal for Quantum Computation
• Universal computation by quantum walk
• Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
• Classical simulation of infinite-size quantum lattice systems in one spatial dimension
• The Bethe lattice spin glass revisited
• Supercooled Liquids for Pedestrians
• Theory of Structural Glasses and Supercooled Liquids
• Stochastic series expansion method with operator-loop update
• Theory of Quantum Annealing of an Ising Spin Glass
• Dynamics of a Quantum Phase Transition and Relaxation to a Steady State
• Quantum Annealing and Analog Quantum Computation
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• Quantum Search by Local Adiabatic Evolution
• Classical simulation of quantum many-body systems with a tree tensor network
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Optimal Control at the Quantum Speed Limit
• Models of traps and glass phenomenology
• Robustness of adiabatic quantum computation
• The structural glass transition and the entropy of the metastable states
• Spin-Glass Theory for Pedestrians
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Mathematical Foundation of Quantum Annealing
• Experimental demonstration of Shor's algorithm with quantum entanglement
• Universality in Quantum Computation
• The Thermodynamic Limit in Mean Field Spin Glass Models
• Computing prime factors with a Josephson phase qubit quantum processor
• Phase Transitions in the Coloring of Random Graphs
• Finite-Size Scaling Exponents of the Lipkin-Meshkov-Glick Model
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Continuous unitary transformations and finite-size scaling exponents in the Lipkin-Meshkov-Glick model
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Anderson localization casts clouds over adiabatic quantum optimization
• Ising models on locally tree-like graphs
• A Numerical Study of the Random Transverse-Field Ising Spin Chain
• The power of quantum systems on a line
• Adiabatic Quantum Computation in Open Systems
• Statistical mechanics of the random K-SAT model
• Time-dependent density-matrix renormalization group: A systematic method for the study of quantum many-body systems out-of-equilibrium
• Transition times in the Landau-Zener model
• Experimental implementation of an adiabatic quantum optimization algorithm
• First order phase transition in the Quantum Adiabatic Algorithm
• How Powerful is Adiabatic Quantum Computation?
• A Landscape Analysis of Constraint Satisfaction Problems
• Zero--Temperature Quantum Phase Transition of a Two--Dimensional Ising Spin--Glass
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Geometric Aspects of Quantum Spin States
• Quantum Graphical Models and Belief Propagation
• Adiabatic quantum dynamics of a random Ising chain across its quantum critical point
• Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
• A variational description of the ground state structure in random satisfiability problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Quantum annealing with antiferromagnetic fluctuations
• A ferromagnet with a glass transition
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• First Order Quantum Phase Transition in Adiabatic Quantum Computation
• Infinite-range Ising ferromagnet in a time-dependent transverse field: quench and ac dynamics near the quantum critical point
• Simple Glass Models and their Quantum Annealing
• Quantum fluctuations can promote or inhibit glass formation
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Quantum Belief Propagation
• Exact solutions for diluted spin glasses and optimization problems
• On the freezing of variables in random constraint satisfaction problems
• Noise resistance of adiabatic quantum computation using random matrix theory
• Experimental determination of Ramsey numbers
• On the dynamics of the glass transition on Bethe lattices
• First-order transitions and the performance of quantum algorithms in random optimization problems
• Superconductor-Insulator transition and energy localization
• Distributions of gaps and end-to-end correlations in random transverse-field Ising spin chains
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions
• Efficient simulation of infinite tree tensor network states on the Bethe lattice
• The Quantum Spherical p-Spin-Glass Model
• Energy transport in strongly disordered superconductors and magnets
• Speeding up critical system dynamics through optimized evolution
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
• Cavity method for quantum spin glasses on the Bethe lattice
• Circumspect descent prevails in solving random constraint satisfaction problems
• The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
• Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
• On quantum mean-field models and their quantum annealing
• The Quantum Transverse Field Ising Model on an Infinite Tree from Matrix Product States
• Facilitated spin models of dissipative quantum glasses
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Exponential complexity of an adiabatic algorithm for an NP-complete problem
• Quantum TAP equations
• Locked constraint satisfaction problems
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Markov entropy decomposition: a variational dual for quantum belief propagation
• Pairs of SAT Assignment in Random Boolean Formulae
• Quantum phase transitions in fully connected spin models: an entanglement perspective
• On the structure of typical states of a disordered Richardson model and many-body localization
• Quantum Walks
• Quantum phase transition in spin glasses with multi-spin interactions
• A note on the switching adiabatic theorem
• Potts Glass on Random Graphs
• Chaotic temperature dependence in a model of spin glasses
• Exact solution of the Bose-Hubbard model on the Bethe lattice
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Algorithmic approach to adiabatic quantum optimization
• The Adiabatic Theorem for Quantum Systems with Spectral Degeneracy
• Random Graph Coloring - a Statistical Physics Approach
• Random subcubes as a toy model for constraint satisfaction problems
• Improved Error Bounds for the Adiabatic Approximation
• On product, generic and random generic quantum satisfiability
• The cavity method for quantum disordered systems: from transverse random field ferromagnets to directed polymers in random media
• Bose-Einstein condensation in quantum glasses
• Belief propagation algorithm for computing correlation functions in finite-temperature quantum many-body systems on loopy graphs
• The Phase Diagram of the Quantum Curie-Weiss Model
• Hardness of approximation for quantum problems
• A solvable model of quantum random optimization problems
• The quantum Biroli-Mézard model: glass transition and superfluidity in a quantum lattice glass model
• Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
• Excitation Gap from Optimized Correlation Functions in Quantum Monte Carlo Simulations
• Elimination of Perturbative Crossings in Adiabatic Quantum Optimization
• Complexity transitions in global algorithms for sparse linear systems over finite fields
• Coarse grained belief propagation for simulation of interacting quantum systems at all temperatures
• Exact results for state-to-state transition probabilities in the multistate Landau-Zener model by non-stationary perturbation theory
• On belief propagation guided decimation for random k-SAT
• Simulating quantum systems on the Bethe lattice by translationally invariant infinite-Tree Tensor Network
• Sign problem in the Bethe approximation
• Quantum Annealing of Hard Problems
• Cavity approach to variational quantum mechanics
• Adiabatic Computation - A Toy Model
• Spin Glass: A Bridge between quantum computation and statistical mechanics
• A Quantum Monte Carlo Method at Fixed Energy
• Quantum Annealing: from Viewpoints of Statistical Physics, Condensed Matter Physics, and Computational Physics
• Glauber dynamics for the quantum Ising model in a transverse field on a regular tree

Cited by in corpus (83)

• Quantum information processing with superconducting circuits: a review
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Perspective: The Glass Transition
• What is the Computational Value of Finite Range Tunneling?
• A new class of variance reduction techniques using lattice symmetries
• Challenges and Opportunities in Quantum Optimization
• Shortcuts to Adiabaticity in Digitized Adiabatic Quantum Computing
• Quantum annealing correction for random Ising problems
• Reexamining classical and quantum models for the D-Wave One processor
• Coherent and dissipative dynamics at quantum phase transitions
• Dicke Quantum Spin and Photon Glass in Optical Cavities: Non-equilibrium theory and experimental signatures
• NISQ Computers: A Path to Quantum Supremacy
• Reinforcement Learning assisted Quantum Optimization
• Efficiency of quantum versus classical annealing in non-convex learning problems
• Reverse quantum annealing of the $p$-spin model with relaxation
• Portfolio Optimization with Digitized-Counterdiabatic Quantum Algorithms
• Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
• Quantum annealing: the fastest route to quantum computation?
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• Dicke simulators with emergent collective quantum computational abilities
• Quantum algorithm for energy matching in hard optimization problems
• An entanglement perspective on the quantum approximate optimization algorithm
• Exploring adiabatic quantum trajectories via optimal control
• A dissipative environment may improve the quantum annealing performances of the ferromagnetic p-spin model
• Quasi-adiabatic quantum Monte Carlo algorithm for quantum evolution in imaginary time
• Quenched vs Annealed: Glassiness from SK to SYK
• Dynamic nuclear polarization and the paradox of Quantum Thermalization
• On the optimal working point in dissipative quantum annealing
• Quantum annealing speedup over simulated annealing on random Ising chains
• Open system quantum annealing in mean field models with exponential degeneracy
• Adiabatic Quantum Search in Open Systems
• Existence of replica-symmetry breaking in quantum glasses
• A Variational Ansatz for the Ground State of the Quantum Sherrington-Kirkpatrick Model
• Observation of coherent oscillation in single-passage Landau-Zener transitions
• Out of equilibrium dynamics of classical and quantum complex systems
• Nested Quantum Annealing Correction at Finite Temperature: $p$-spin models
• Spectral Form Factor of a Quantum Spin Glass
• Mean-Field Approximate Optimization Algorithm
• Slow Nonthermalizing Dynamics in a Quantum Spin Glass
• Interface dynamics in the two-dimensional quantum Ising model
• Groups, Information Theory and Einstein's Likelihood Principle
• Anomalous behavior of the energy gap in the one-dimensional quantum XY model
• Phase Diagram of the Quantum Random Energy Model
• Retrieving the ground state of spin glasses using thermal noise: Performance of quantum annealing at finite temperatures
• The characteristic functions of quantum heat with baths at different temperatures
• Optimizing adiabatic quantum pathways via a learning algorithm
• Thermal, quantum and simulated quantum annealing: analytical comparisons for simple models
• Tunneling in projective quantum Monte Carlo simulations with guiding wave functions
• On the quantum spin glass transition on the Bethe lattice
• One-loop diagrams in the Random Euclidean Matching Problem
• Disordered Lieb-Robinson bounds in one dimension
• Finite-size corrections in the random assignment problem
• Enhancing quantum annealing performance by a degenerate two-level system
• Clustering in Hilbert space of a quantum optimization problem
• Optimal exploration of random walks with local bias on networks
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• Generalized Random Energy Models in a Transversal Magnetic Field: Free Energy and Phase Diagrams
• Beyond Quantum Annealing: Optimal control solutions to MaxCut problems
• Role of initial conditions in the dynamics of quantum glassy systems
• Quantum Chaos in Random Ising Networks
• Why adiabatic quantum annealing is unlikely to yield speed-up
• A near-term quantum simulation of the transverse field Ising model hints at Glassy Dynamics
• Hard instance learning for quantum adiabatic prime factorization
• The Quantum Random Energy Model as a Limit of p-Spin Interactions
• Quantum Annealing search of Ising spin glass ground state(s) with tunable transverse & longitudinal fields
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Implementing transferable annealing protocols for combinatorial optimisation on neutral atom quantum processors: a case study on smart-charging of electric vehicles
• First-order quantum phase transitions as condensations in the space of states
• The effect of quantum fluctuations on the coloring of random graphs
• Thermalization of the Lipkin-Meshkov-Glick model in blackbody radiation
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• Large time effective kinetics $\beta$-functions for quantum (2+p)-spin glass
• The Random Fractional Matching Problem
• Bethe free-energy approximations for disordered quantum systems
• Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
• The anomalously slow dynamics of inhomogeneous quantum annealing
• Duality approach to quantum annealing of the 3-XORSAT problem
• Noise tolerance via reinforcement: Learning a reinforced quantum dynamics
• Multilayer wave functions: A recursive coupling of local excitations
• Studying viral populations with tools from quantum spin chains
• Energy gap of quantum spin glasses: a projection quantum Monte Carlo study
• The quantum $p$-spin renormalization group in the large $N$ limit as a benchmark for functional renormalization group
• Solving the Turbine Balancing Problem using Quantum Annealing