Undecidability of the Spectral Gap (short version)
arXiv:1502.04135 · doi:10.1038/nature16059
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.
arXiv commentv2: 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 (29)
- Area laws for the entanglement entropy - a review
- Spin Liquid Ground State of the Kagome Heisenberg Model
- Fractionalized excitations in the spin liquid state of a kagomé lattice antiferromagnet
- An Area Law for One Dimensional Quantum Systems
- Lieb-Schultz-Mattis in Higher Dimensions
- Lieb-Robinson Bounds and the Exponential Clustering Theorem
- Topological quantum order: stability under local perturbations
- The power of quantum systems on a line
- Entropy and Entanglement in Quantum Ground States
- Stability of Frustration-Free Hamiltonians
- Finite-lattice extrapolations for a Haldane gap antiferromagnet
- Vanishing spin gap in a competing spin-liquid phase in the kagome Heisenberg antiferromagnet
- Elementary excitations in gapped quantum spin systems
- Stochastic Error Cancellation in Analog Quantum Simulation
- Hofstadter butterfly as Quantum phase diagram
- Matrix product operators and states: NP-hardness and undecidability
- Quantum measurement occurrence is undecidable
- More Really is Different
- Frustration free gapless Hamiltonians for Matrix Product States
- Size-Driven Quantum Phase Transitions
- The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
- A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
- Non-signaling deterministic models for non-local correlations have to be uncomputable
- Are problems in Quantum Information Theory (un)decidable?
- Stable quasicrystalline ground states
- Undecidability in Tensor Network States
- 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 (128)
- 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
- Towards a mathematical formalism for classifying phases of matter
- Non-power-law universality in one-dimensional quasicrystals
- Constructing Turing complete Euler flows in dimension
- Spectral gaps of frustration-free spin systems with boundary
- Demonstrating the AKLT spectral gap on 2D degree-3 lattices
- Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
- Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
- 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 of the fate of relaxation in one-dimensional quantum systems
- Undecidability in quantum thermalization
- 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
- The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
- Optimal working point in digitized quantum annealing
- Improved local spectral gap thresholds for lattices of finite dimension
- Importance of the spectral gap in estimating ground-state energies
- Uncomputability of Phase Diagrams
- Spectral Gap and Edge Excitations of -dimensional PVBS models on half-spaces
- Divide and conquer method for proving gaps of frustration free Hamiltonians
- Undecidable problems in quantum field theory
- Certified algorithms for equilibrium states of local quantum Hamiltonians
- Precision is not limited by the second law of thermodynamics
- What the foundations of quantum computer science teach us about chemistry
- Uncomputability and complexity of quantum control
- Origin of the Curie-von Schweidler law and the fractional capacitor from time-varying capacitance
- 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
- On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
- Glassy word problems: ultraslow relaxation, Hilbert space jamming, and computational complexity
- Gaplessness is not generic for translation-invariant spin chains
- Some Problems in Density Functional Theory
- Undecidability of the Spectral Gap (full version)
- Analytic model of thermalization: Quantum emulation of classical cellular automata
- Epistemic Horizons and the Foundations of Quantum Mechanics
- 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
- Entanglement Action for the Real-Space Entanglement Spectra of Composite Fermion Wave Functions
- Translationally invariant universal classical Hamiltonians
- Halos and undecidability of tensor stable positive maps
- Beyond Quantum Annealing: Optimal control solutions to MaxCut problems
- Towards a Quantum-Like Cognitive Architecture for Decision-Making
- Random translation-invariant Hamiltonians and their spectral gaps
- Finite-size criteria for spectral gaps in -dimensional quantum spin systems
- Quantum-Assisted Joint Virtual Network Function Deployment and Maximum Flow Routing for Space Information Networks
- The Spectroscopy and Form Factors of Nucleon Resonances from Superconformal Quantum Mechanics and Holographic QCD
- Undecidability in Physics: a Review
- Lieb-Schultz-Mattis theorem in higher dimensions from approximate magnetic translation symmetry
- A Quantum Annealing Protocol to Solve the Nuclear Shell Model
- Detailed Analysis of Circuit-to-Hamiltonian Mappings
- Many bounded versions of undecidable problems are NP-hard
- Translationally-Invariant Universal Quantum Hamiltonians in 1D
- Hadron Physics From Superconformal Quantum Mechanics and its Light-Front Holographic Embedding
- Classifying Data with Local Hamiltonians
- 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 gauge theory with exact gapped ground states
- Spectral properties for a family of two-dimensional quantum antiferromagnets
- On the uncomputability of the spectral gap
- Can quantum gravity be both consistent and complete?
- Classical and quantum spin liquids
- Entanglement subvolume law for 2D frustration-free spin systems
- Infinite-dimensional features of matrices and pseudospectra
- Spectral Gap Optimization for Enhanced Adiabatic State Preparation
- Stability of the spectral gap and ground state indistinguishability for a decorated AKLT model
- A Note on the Second Spectral Gap Incompleteness Theorem
- Oracle complexity classes and local measurements on physical Hamiltonians
- Quantum annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy
- Computational Complexity and the Nature of Quantum Mechanics
- Quantum Annealing for Prime Factorization
- Topological order in symmetric blockade structures
- Towards a Fluid computer
- Gödel's undecidability theorems and the search for a theory of everything
- Quantum circuit complexity and unsupervised machine learning of topological order
- Universal Hamiltonians for Exponentially Long Simulation
- Unprovability of First Maxwell's Equation in Light of EPR's Completeness Condition -- A Computational Approach from Logico-linguistic Perspective
- Simulating the spectral gap with polariton graphs
- Characterizing the asymmetry in hardness between synthesis and destruction of heteropolymers
- Computing local properties in the trivial phase
- Functional Epistemology "Nullifies" Dyson's Rebuttal of Perturbation Theory
- Hidden jerk in universal creep and aftershocks
- Multiobjective Optimization in a Quantum Adiabatic Computer
- How Real is Incomputability in Physics?
- 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
- A Minimal Intervention Definition of Reverse Engineering a Neural Circuit
- Revisiting thermodynamics in computation and information theory
- The Undecidable Charge Gap and the Oil Drop Experiment
- Undecidability in Spacetime Geometry via the AdS/CFT Correspondence
- Collective Motion of Predictive Swarms
- Quantum Image Rotation by an arbitrary angle
- Sample complexity of matrix product states at finite temperature
- Bundled matrix product states represent low-energy excitations faithfully
- Hybrid Quantum-Classical Clustering for Preparing a Prior Distribution of Eigenspectrum
- Renormalization method for proving frustration-free local spin chains are gapped
- Gapped and gapless phases of frustration-free spin-1/2 chains
- Universal witnesses of vanishing energy gap
- Spectral statistics and energy-gap scaling in local spin Hamiltonians
- Variational Quantum Algorithm for Solving the Liouvillian Gap
- The equilibrium classical scatter spectrum of waves
- Asymptotic lower bound for the gap of Hermitian matrices having ergodic ground states and infinitesimal off-diagonal elements
- Physics and science: the art of taking a stance about undecidable questions
- On the computability properties of topological entropy: a general approach
- Undecidability of the spectral gap in rotationally symmetric Hamiltonians