Simple Glass Models and their Quantum Annealing

Abstract

We study first order quantum phase transitions in mean-field spin glasses. We solve the quantum Random Energy Model using elementary methods and show that at the transition the eigenstate suddenly projects onto the unperturbed ground state and that the gap between the lowest states is exponentially small in the system size. We argue that this is a generic feature of all `Random First Order' models, which includes benchmarks such as random satisfiability. We introduce a two-time instanton to calculate this gap in general, and discuss the consequences for quantum annealing.

4 pages, 3 figures, minor typos corrected

References in corpus (11)

• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Tunable Quantum Tunneling of Magnetic Domain Walls
• An Accelerated Conjugate Gradient Algorithm to Compute Low-Lying Eigenvalues --- a Study for the Dirac Operator in SU(2) Lattice QCD
• Quantum TAP equations
• Quantum phase transition in spin glasses with multi-spin interactions
• From second to first order transitions in a disordered quantum magnet
• Phase diagram of the $p$-spin-interacting spin glass with ferromagnetic bias and a transverse field in the infinite-$p$ limit

Cited by in corpus (76)

• Adiabatic Quantum Computing
• Perspectives of quantum annealing: Methods and implementations
• Anderson localization casts clouds over adiabatic quantum optimization
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• First order phase transition in the Quantum Adiabatic Algorithm
• Many-body mobility edge in a mean-field quantum spin glass
• Quantum annealing with antiferromagnetic fluctuations
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• First-order transitions and the performance of quantum algorithms in random optimization problems
• Coherent and dissipative dynamics at quantum phase transitions
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• Two-component Structure in the Entanglement Spectrum of Highly Excited States
• On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
• 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 many-body localized phase of the quantum random energy model
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Clustering of non-ergodic eigenstates in quantum spin glasses
• Quantum annealing: the fastest route to quantum computation?
• Finite temperature quantum annealing solving exponentially small gap problem with non-monotonic success probability
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Programmable Quantum Annealing Architectures with Ising Quantum Wires
• Quantum annealing with longitudinal bias fields
• Quantum algorithm for energy matching in hard optimization problems
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Ground-state fidelity at first-order quantum transitions
• Quantum annealing with Jarzynski equality
• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• A solvable model of quantum random optimization problems
• The quantum Biroli-Mézard model: glass transition and superfluidity in a quantum lattice glass model
• Out of equilibrium Phase Diagram of the Quantum Random Energy Model
• Dissipative dynamics at first-order quantum transitions
• Greedy parameter optimization for diabatic quantum annealing
• Many-body localization enables iterative quantum optimization
• Quantum quenches in isolated quantum glasses out of equilibrium
• Phase Diagram of the Quantum Random Energy Model
• The characteristic functions of quantum heat with baths at different temperatures
• Quantum state engineering by steering in the presence of errors
• Dynamical Singularities of Glassy Systems in a Quantum Quench
• Thermal, quantum and simulated quantum annealing: analytical comparisons for simple models
• Nonequilibrium work on spin glasses in longitudinal and transverse fields
• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies
• Hybrid annealing using a quantum simulator coupled to a classical computer
• Quantum search using non-Hermitian adiabatic evolution
• Non-Hermitian Quantum Annealing in the Ferromagnetic Ising Model
• Efficient quantum and simulated annealing of Potts models using a half-hot constraint
• Nonequilibrium work performed in quantum annealing
• Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing
• Non-Hermitian Quantum Annealing in the Antiferromagnetic Ising Chain
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Higher-order tensor renormalization group approach to lattice glass model
• The quantum annealing gap and quench dynamics in the exact cover problem
• Effect of random fluctuations on quantum spin-glass transitions at zero temperature
• The Quantum Random Energy Model as a Limit of p-Spin Interactions
• Effects of low-lying excitations on ground-state energy and energy gap of Sherrington-Kirkpatrick model in transverse field
• First-order quantum phase transitions as condensations in the space of states
• Quantum annealing sampling with a bias field
• Revisiting the replica trick: Competition between spin glass and conventional order
• The effect of quantum fluctuations on the coloring of random graphs
• Phase transitions and gaps in quantum random energy models
• Computational Bottlenecks of Quantum Annealing
• Non-Hermitian Adiabatic Quantum Optimization
• Absence of small-world effects at the quantum level and stability of the quantum critical point
• Fighting Exponentially Small Gaps by Counterdiabatic Driving
• Finite temperature quantum condensations in the space of states: General Proof
• The anomalously slow dynamics of inhomogeneous quantum annealing
• Studying viral populations with tools from quantum spin chains
• Effects of dynamical paths on the energy gap and the corrections to free energy in path integrals of mean-field quantum spin systems
• Effect of Quantum Statistics on Computational Power of Atomic Quantum Annealers
• Steady state distributions of network of degenerate optical parametric oscillators in solving combinatorial optimization problems
• Finite temperature quantum condensations in the space of states: a new perspective for quantum annealing
• Identifying mobility edge from finite temperature spectral form factor
• Statistical mechanical models of integer factorization problem