The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions

Abstract

Motivated by the quantum adiabatic algorithm (QAA), we consider the scaling of the Hamiltonian gap at quantum first order transitions, generally expected to be exponentially small in the size of the system. However, we show that a quantum antiferromagnetic Ising chain in a staggered field can exhibit a first order transition with only an algebraically small gap. In addition, we construct a simple classical translationally invariant one-dimensional Hamiltonian containing nearest-neighbour interactions only, which exhibits an exponential gap at a thermodynamic quantum first-order transition of essentially topological origin. This establishes that (i) the QAA can be successful even across first order transitions but also that (ii) it can fail on exceedingly simple problems readily solved by inspection, or by classical annealing.

6 pages, 3 figures

References in corpus (14)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Ising models of quantum frustration
• Anderson localization casts clouds over adiabatic quantum optimization
• Two-dimensional periodic frustrated Ising models in a transverse field
• First order phase transition in the Quantum Adiabatic Algorithm
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• The antiferromagnetic Ising chain in a mixed transverse and longitudinal magnetic field
• 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
• Simple Glass Models and their Quantum Annealing
• First-order transitions and the performance of quantum algorithms in random optimization problems
• Adiabatic quantum algorithms as quantum phase transitions: first versus second order
• Cavity method for quantum spin glasses on the Bethe lattice
• A solvable model of quantum random optimization problems

Cited by in corpus (56)

• Adiabatic Quantum Computing
• Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
• Perspectives of quantum annealing: Methods and implementations
• Quantum Many-Body Scars and Hilbert Space Fragmentation: A Review of Exact Results
• Quantum Many-Body Scars: A Quasiparticle Perspective
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Coherent and dissipative dynamics at quantum phase transitions
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Exact results for fidelity susceptibility of the quantum Ising model: The interplay between parity, system size, and magnetic field
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Quantum transitions driven by one-bond defects in quantum Ising rings
• From ergodic to non-ergodic chaos in Rosenzweig-Porter model
• Quantum annealing: the fastest route to quantum computation?
• Quantum Ising chains with boundary fields
• How does a locally constrained quantum system localize?
• Finite temperature quantum annealing solving exponentially small gap problem with non-monotonic success probability
• Continuous Preparation of a Fractional Chern Insulator
• The eigenstate thermalization hypothesis in constrained Hilbert spaces: a case study in non-Abelian anyon chains
• The Power of Adiabatic Quantum Computation with No Sign Problem
• Finite-size scaling at the first-order quantum transitions of quantum Potts chains
• A quantum-walk-inspired adiabatic algorithm for graph isomorphism
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Scaling properties of the dynamics at first-order quantum transitions when boundary conditions favor one of the two phases
• Finite-size scaling at first-order quantum transitions when boundary conditions favor one of the two phases
• Energy gap at first-order quantum phase transitions: An anomalous case
• Intrinsic Jump Character of the First-Order Quantum Phase Transitions
• Emergent symmetries and slow quantum dynamics in a Rydberg-atom chain with confinement
• Nested Quantum Annealing Correction at Finite Temperature: $p$-spin models
• Off-equilibrium scaling behaviors across first-order transitions
• Many-body localization enables iterative quantum optimization
• Anomalous behavior of the energy gap in the one-dimensional quantum XY model
• Odd thermodynamic limit for the Loschmidt echo
• Magic phase transition and non-local complexity in generalized $W$ State
• Simulating continuous symmetry models with discrete ones
• Quantum many-body scars in spin-1 Kitaev chain with uniaxial single-ion anisotropy
• Quantum annealing in spin-boson model: from a perturbative to a ultrastrong mediated coupling
• Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem
• Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts
• Diagnosing First and Second Order Phase Transitions with Probes of Quantum Chaos
• Obstacles to quantum annealing in a planar embedding of XORSAT
• Noise-tolerant quantum speedups in quantum annealing without fine tuning
• Out-of-equilibrium dynamics across the first-order quantum transitions of one-dimensional quantum Ising models
• Quantum discontinuity fixed point and renormalization group flow of the SYK model
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Adiabatic Bottlenecks in Quantum Annealing and Nonequilibrium Dynamics of Paramagnons
• Kibble-Zurek mechanism in quantum link model
• Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
• Quantum annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy
• Computational Bottlenecks of Quantum Annealing
• Quantum quenches across continuous and first-order quantum transitions in one-dimensional quantum Ising models
• Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array
• The fate of local order in topologically frustrated spin chains
• The anomalously slow dynamics of inhomogeneous quantum annealing
• Analog Errors in Quantum Annealing: Doom and Hope
• Steady state distributions of network of degenerate optical parametric oscillators in solving combinatorial optimization problems