The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
arXiv:1210.0811 · doi:10.1016/j.physrep.2012.10.002
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 (43)
- Non-Abelian Anyons and Topological Quantum Computation
- Quantum algorithm for solving linear systems of equations
- Theoretical perspective on the glass transition and amorphous materials
- Real time evolution using the density matrix renormalization group
- Universal computation by quantum walk
- Classical simulation of infinite-size quantum lattice systems in one spatial dimension
- Supercooled Liquids for Pedestrians
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Mathematical Foundation of Quantum Annealing
- Experimental demonstration of Shor's algorithm with quantum entanglement
- Demonstration of Shor's quantum factoring algorithm using photonic qubits
- Finite-Size Scaling Exponents of the Lipkin-Meshkov-Glick Model
- Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
- Rigorous Inequalities between Length and Time Scales in Glassy Systems
- The power of quantum systems on a line
- Experimental implementation of an adiabatic quantum optimization algorithm
- How Powerful is Adiabatic Quantum Computation?
- A Landscape Analysis of Constraint Satisfaction Problems
- Quantum Graphical Models and Belief Propagation
- Adiabatic quantum dynamics of a random Ising chain across its quantum critical point
- Clusters of solutions and replica symmetry breaking in random k-satisfiability
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
- 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 Belief Propagation
- On the freezing of variables in random constraint satisfaction problems
- Noise resistance of adiabatic quantum computation using random matrix theory
- Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions
- 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 Transverse Field Ising Model on an Infinite Tree from Matrix Product States
- Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
- Locked constraint satisfaction problems
- Quantum phase transitions in fully connected spin models: an entanglement perspective
- Potts Glass on Random Graphs
- Random subcubes as a toy model for constraint satisfaction problems
- The Phase Diagram of the Quantum Curie-Weiss Model
- Belief propagation algorithm for computing correlation functions in finite-temperature quantum many-body systems on loopy graphs
- A solvable model of quantum random optimization problems
- Adiabatic Computation - A Toy Model