Undecidability of the Spectral Gap (short version)

Abstract

The spectral gap - the energy difference between the ground state and first excited state - is central to quantum many-body physics. Many challenging open problems, such as the Haldane conjecture, existence of gapped topological spin liquid phases, or the Yang-Mills gap conjecture, concern spectral gaps. These and other problems are particular cases of the general spectral gap problem: given a quantum many-body Hamiltonian, is it gapped or gapless? Here we prove that this is an undecidable problem. We construct families of quantum spin systems on a 2D lattice with translationally-invariant, nearest-neighbour interactions for which the spectral gap problem is undecidable. This result extends to undecidability of other low energy properties, such as existence of algebraically decaying ground-state correlations. The proof combines Hamiltonian complexity techniques with aperiodic tilings, to construct a Hamiltonian whose ground state encodes the evolution of a quantum phase-estimation algorithm followed by a universal Turing Machine. The spectral gap depends on the outcome of the corresponding Halting Problem. Our result implies that there exists no algorithm to determine whether an arbitrary model is gapped or gapless. It also implies that there exist models for which the presence or absence of a spectral gap is independent of the axioms of mathematics.

v2: published version. 7 pages, 3 figures. See long companion paper arXiv:1502.04573 (same title and authors) for full technical details. v3: Added supplementary material as ancilliary file (previously part of arXiv:1502.04573v2)

References in corpus (10)

• Lieb-Robinson Bounds and the Exponential Clustering Theorem
• The power of quantum systems on a line
• Entropy and Entanglement in Quantum Ground States
• Stochastic Error Cancellation in Analog Quantum Simulation
• Matrix product operators and states: NP-hardness and undecidability
• Size-Driven Quantum Phase Transitions
• Non-signaling deterministic models for non-local correlations have to be uncomputable
• Measurement-based quantum computation and undecidable logic
• On the uncomputability of the spectral gap
• Comment on "On the uncomputability of the spectral gap"

Cited by in corpus (127)

• Matter-wave diffraction from a quasicrystalline optical lattice
• Near-optimal ground state preparation
• Observing localisation in a 2D quasicrystalline optical lattice
• Strongly-Interacting Bosons in a Two-Dimensional Quasicrystal Lattice
• A cross-disciplinary introduction to quantum annealing-based algorithms
• Speed limits and locality in many-body quantum dynamics
• The adiabatic theorem and linear response theory for extended quantum systems
• Evaluating energy differences on a quantum computer with robust phase estimation
• Matrix Model simulations using Quantum Computing, Deep Learning, and Lattice Monte Carlo
• Local gap threshold for frustration-free spin systems
• Stability of fractional Chern insulators in the effective continuum limit of Harper-Hofstadter bands with Chern number $|C|>1$
• Towards a mathematical formalism for classifying phases of matter
• Non-power-law universality in one-dimensional quasicrystals
• Constructing Turing complete Euler flows in dimension $3$
• Spectral gaps of frustration-free spin systems with boundary
• Demonstrating the AKLT spectral gap on 2D degree-3 lattices
• Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Solving the Liouvillian Gap with Artificial Neural Networks
• Thermodynamic costs of Turing Machines
• Undecidability of the Spectral Gap in One Dimension
• The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
• Size-Driven Quantum Phase Transitions
• Locally accurate MPS approximations for ground states of one-dimensional gapped local Hamiltonians
• Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian
• Undecidability in quantum thermalization
• Undecidability of the fate of relaxation in one-dimensional quantum systems
• A class of two-dimensional AKLT models with a gap
• Thermodynamic Phase Diagram of Two-Dimensional Bosons in a Quasicrystal Potential
• Projected Entangled Pair States: Fundamental analytical and numerical limitations
• The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
• Effects of defects in the XY chain with frustrated boundary conditions
• Generic Local Hamiltonians are Gapless
• Improved local spectral gap thresholds for lattices of finite dimension
• Optimal working point in digitized quantum annealing
• Importance of the spectral gap in estimating ground-state energies
• Uncomputability of Phase Diagrams
• Undecidable problems in quantum field theory
• Divide and conquer method for proving gaps of frustration free Hamiltonians
• Certified algorithms for equilibrium states of local quantum Hamiltonians
• Spectral Gap and Edge Excitations of $d$-dimensional PVBS models on half-spaces
• Precision is not limited by the second law of thermodynamics
• Origin of the Curie-von Schweidler law and the fractional capacitor from time-varying capacitance
• Uncomputability and complexity of quantum control
• What the foundations of quantum computer science teach us about chemistry
• Locality at the boundary implies gap in the bulk for 2D PEPS
• Hybrid actor-critic algorithm for quantum reinforcement learning at CERN beam lines
• Algorithmic Shadow Spectroscopy
• Glassy word problems: ultraslow relaxation, Hilbert space jamming, and computational complexity
• On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
• Undecidability of the Spectral Gap (full version)
• Gaplessness is not generic for translation-invariant spin chains
• Some Problems in Density Functional Theory
• Epistemic Horizons and the Foundations of Quantum Mechanics
• Analytic model of thermalization: Quantum emulation of classical cellular automata
• The complexity of simulating local measurements on quantum systems
• Connected components of irreducible maps and 1D quantum phases
• Uncomputably Complex Renormalisation Group Flows
• The pair-flip model: a very entangled translationally invariant spin chain
• A unified diagrammatic approach to topological fixed point models
• Beyond Quantum Annealing: Optimal control solutions to MaxCut problems
• Entanglement Action for the Real-Space Entanglement Spectra of Composite Fermion Wave Functions
• Halos and undecidability of tensor stable positive maps
• Random translation-invariant Hamiltonians and their spectral gaps
• Translationally invariant universal classical Hamiltonians
• Towards a Quantum-Like Cognitive Architecture for Decision-Making
• The Spectroscopy and Form Factors of Nucleon Resonances from Superconformal Quantum Mechanics and Holographic QCD
• Quantum-Assisted Joint Virtual Network Function Deployment and Maximum Flow Routing for Space Information Networks
• Finite-size criteria for spectral gaps in $D$-dimensional quantum spin systems
• Undecidability in Physics: a Review
• Lieb-Schultz-Mattis theorem in higher dimensions from approximate magnetic translation symmetry
• Translationally-Invariant Universal Quantum Hamiltonians in 1D
• Many bounded versions of undecidable problems are NP-hard
• A Quantum Annealing Protocol to Solve the Nuclear Shell Model
• Detailed Analysis of Circuit-to-Hamiltonian Mappings
• Hadron Physics From Superconformal Quantum Mechanics and its Light-Front Holographic Embedding
• Quasi-Locality Bounds for Quantum Lattice Systems. Part II. Perturbations of Frustration-Free Spin Models with Gapped Ground States
• Duality-preserving deformation of 3+1d lattice ${\mathbb{Z}}_2$ gauge theory with exact gapped ground states
• Classifying Data with Local Hamiltonians
• Spectral properties for a family of two-dimensional quantum antiferromagnets
• Entanglement subvolume law for 2D frustration-free spin systems
• Can quantum gravity be both consistent and complete?
• Classical and quantum spin liquids
• On the uncomputability of the spectral gap
• Stability of the spectral gap and ground state indistinguishability for a decorated AKLT model
• Computational Complexity and the Nature of Quantum Mechanics
• Oracle complexity classes and local measurements on physical Hamiltonians
• Infinite-dimensional features of matrices and pseudospectra
• A Note on the Second Spectral Gap Incompleteness Theorem
• Spectral Gap Optimization for Enhanced Adiabatic State Preparation
• Quantum annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy
• Quantum Annealing for Prime Factorization
• Functional Epistemology "Nullifies" Dyson's Rebuttal of Perturbation Theory
• Towards a Fluid computer
• Topological order in symmetric blockade structures
• Quantum circuit complexity and unsupervised machine learning of topological order
• Characterizing the asymmetry in hardness between synthesis and destruction of heteropolymers
• How Real is Incomputability in Physics?
• Gödel's undecidability theorems and the search for a theory of everything
• Simulating the spectral gap with polariton graphs
• Unprovability of First Maxwell's Equation in Light of EPR's Completeness Condition -- A Computational Approach from Logico-linguistic Perspective
• Hidden jerk in universal creep and aftershocks
• Computing local properties in the trivial phase
• Multiobjective Optimization in a Quantum Adiabatic Computer
• Universal Hamiltonians for Exponentially Long Simulation
• Deformations of the Boundary Theory of the Square Lattice AKLT Model
• Intuitionistic interpretation of quantum mechanics
• A Hierarchy of Spectral Gap Certificates for Frustration-Free Spin Systems
• Revisiting thermodynamics in computation and information theory
• Collective Motion of Predictive Swarms
• Undecidability in Spacetime Geometry via the AdS/CFT Correspondence
• The Undecidable Charge Gap and the Oil Drop Experiment
• Sample complexity of matrix product states at finite temperature
• Quantum Image Rotation by an arbitrary angle
• A Minimal Intervention Definition of Reverse Engineering a Neural Circuit
• On the computability properties of topological entropy: a general approach
• Undecidability of the spectral gap in rotationally symmetric Hamiltonians
• Gapped and gapless phases of frustration-free spin-1/2 chains
• Physics and science: the art of taking a stance about undecidable questions
• Spectral statistics and energy-gap scaling in $k-$local spin Hamiltonians
• Universal witnesses of vanishing energy gap
• Variational Quantum Algorithm for Solving the Liouvillian Gap
• Hybrid Quantum-Classical Clustering for Preparing a Prior Distribution of Eigenspectrum
• The equilibrium classical scatter spectrum of waves
• Renormalization method for proving frustration-free local spin chains are gapped
• Asymptotic lower bound for the gap of Hermitian matrices having ergodic ground states and infinitesimal off-diagonal elements
• Bundled matrix product states represent low-energy excitations faithfully