Undecidability of the Spectral Gap (full version)
arXiv:1502.04573 · doi:10.1017/fmp.2021.15
Abstract
We show that the spectral gap problem is undecidable. Specifically, we construct families of translationally-invariant, nearest-neighbour Hamiltonians on a 2D square lattice of d-level quantum systems (d constant), for which determining whether the system is gapped or gapless is an undecidable problem. This is true even with the promise that each Hamiltonian is either gapped or gapless in the strongest sense: it is promised to either have continuous spectrum above the ground state in the thermodynamic limit, or its spectral gap is lower-bounded by a constant in the thermodynamic limit. Moreover, this constant can be taken equal to the local interaction strength of the Hamiltonian.
arXiv commentv1: 146 pages, 56 theorems etc, 15 figs. See shorter companion paper arXiv:1502.04135 for version omitting technical details. v2: Small fix to abstract wording. v3: Simplified and shortened parts of proof. 127p, 55 thms, 10 figs. v4: Minor intro edits. v5: Published version. Adds explanatory pseudo-code for all Turing Machines, and other presentational improvements. 150 pages, 55 thms, 13 figs
References in corpus (40)
- Area laws for the entanglement entropy - a review
- A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
- 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
- Spectral Gap and Exponential Decay of Correlations
- Lieb-Robinson Bounds and the Exponential Clustering Theorem
- Topological quantum order: stability under local perturbations
- Undecidability of the Spectral Gap (short version)
- The power of quantum systems on a line
- Entropy and Entanglement in Quantum Ground States
- Stability of Frustration-Free Hamiltonians
- 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
- Rigorous RG algorithms and area laws for low energy eigenstates in 1D
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- More Really is Different
- Quantum measurement occurrence is undecidable
- Persistence of exponential decay and spectral gaps for interacting fermions
- Frustration free gapless Hamiltonians for Matrix Product States
- Fundamental limitations in the purifications of tensor networks
- Demonstrating the AKLT spectral gap on 2D degree-3 lattices
- Existence of a Spectral Gap in the Affleck-Kennedy-Lieb-Tasaki Model on the Hexagonal Lattice
- Undecidability of the Spectral Gap in One Dimension
- Size-Driven Quantum Phase Transitions
- Memory effects can make the transmission capability of a communication channel uncomputable
- The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
- Non-signaling deterministic models for non-local correlations have to be uncomputable
- Stable quasicrystalline ground states
- Uncomputability of Phase Diagrams
- Are problems in Quantum Information Theory (un)decidable?
- Measurement-based quantum computation and undecidable logic
- Undecidability in Tensor Network States
- The Stability of Free Fermi Hamiltonians
- Open problems in mathematical physics
- On the uncomputability of the spectral gap
Cited by in corpus (7)
- Some Problems in Density Functional Theory
- Uncomputably Complex Renormalisation Group Flows
- Undecidability in Physics: a Review
- Duality-preserving deformation of 3+1d lattice gauge theory with exact gapped ground states
- Stability of the spectral gap and ground state indistinguishability for a decorated AKLT model
- On the set of reduced states of translation invariant, infinite quantum systems
- A Hierarchy of Spectral Gap Certificates for Frustration-Free Spin Systems