Quantum algorithm for energy matching in hard optimization problems

Abstract

We consider the ability of local quantum dynamics to solve the energy matching problem: given an instance of a classical optimization problem and a low energy state, find another macroscopically distinct low energy state. Energy matching is difficult in rugged optimization landscapes, as the given state provides little information about the distant topography. Here we show that the introduction of quantum dynamics can provide a speed-up over local classical algorithms in a large class of hard optimization problems. The essential intuition is that tunneling allows the system to explore the optimization landscape while approximately conserving the classical energy, even in the presence of large barriers. In particular, we study energy matching in the random p-spin model of spin glass theory. Using perturbation theory and numerical exact diagonalization, we show that introducing a transverse field leads to three sharp dynamical phases, only one of which solves the matching problem: (1) a small-field trapped phase, in which tunneling is too weak for the system to escape the vicinity of the initial state; (2) a large-field excited phase, in which the field excites the system into high energy states, effectively forgetting the initial low energy; and (3) the intermediate tunneling phase, in which the system succeeds at energy matching. We find that in the tunneling phase, the time required to find distant states scales exponentially with system size but is nevertheless exponentially faster than simple classical Monte Carlo.

arXiv comment20 pages (15 main text, 5 appendix), 9 figures

References in corpus (25)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Quantum annealing with more than one hundred qubits
• Schrieffer-Wolff transformation for quantum many-body systems
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Phase Transitions in the Coloring of Random Graphs
• Recipes for metastable states in Spin Glasses
• Anderson localization casts clouds over adiabatic quantum optimization
• Phase diagram of glassy systems in an external field
• Coloring random graphs
• First order phase transition in the Quantum Adiabatic Algorithm
• Many-body mobility edge in a mean-field quantum spin glass
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• A variational description of the ground state structure in random satisfiability problems
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Simple Glass Models and their Quantum Annealing
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
• The forward approximation as a mean field approximation for the Anderson and Many Body Localization transitions
• The many-body localized phase of the quantum random energy model
• Clustering of non-ergodic eigenstates in quantum spin glasses
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Quantum phase transition in spin glasses with multi-spin interactions
• A solvable model of quantum random optimization problems
• Statistical Mechanics of the Quantum K-Satisfiability problem

Cited by in corpus (32)

• Reverse annealing for the fully connected $p$-spin model
• The Many-Body localization transition in the Hilbert space
• Quantum-enhanced Markov chain Monte Carlo
• The Lévy-Rosenzweig-Porter random matrix ensemble
• A perspective on protein structure prediction using quantum computers
• Non-ergodic delocalized states for efficient population transfer within a narrow band of the energy landscape
• Quantum annealing with longitudinal bias fields
• Finding spin-glass ground states using quantum walks
• Non-ergodic extended phase of the Quantum Random Energy model
• Quenched vs Annealed: Glassiness from SK to SYK
• Quantum echo dynamics in the Sherrington-Kirkpatrick model
• Existence of replica-symmetry breaking in quantum glasses
• A Variational Ansatz for the Ground State of the Quantum Sherrington-Kirkpatrick Model
• Out of equilibrium Phase Diagram of the Quantum Random Energy Model
• Spectral Form Factor of a Quantum Spin Glass
• Fully localized and partially delocalized states in the tails of Erdös-Rényi graphs in the critical regime
• Quantum quenches in isolated quantum glasses out of equilibrium
• Multifractal phase in the weighted adjacency matrices of random Erdös-Rényi graphs
• Spectral statistics of a minimal quantum glass model
• Eigenstate localization in a many-body quantum system
• Quantum Jamming: Critical Properties of a Quantum Mechanical Perceptron
• Disordered Lieb-Robinson bounds in one dimension
• Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem
• The quantum annealing gap and quench dynamics in the exact cover problem
• Revisiting the replica trick: Competition between spin glass and conventional order
• Quantum annealing sampling with a bias field
• The anomalously slow dynamics of inhomogeneous quantum annealing
• Time-translation invariance symmetry breaking hidden by finite-scale singularities
• The Wishart--Rosenzweig--Porter random matrix ensemble
• Replica approach to the generalized Rosenzweig-Porter model
• The quantum $p$-spin renormalization group in the large $N$ limit as a benchmark for functional renormalization group
• Anderson Localization on Husimi Trees and its implications for Many-Body localization