Undecidability of the Spectral Gap in One Dimension

Abstract

The spectral gap problem - determining whether the energy spectrum of a system has an energy gap above ground state, or if there is a continuous range of low-energy excitations - pervades quantum many-body physics. Recently, this important problem was shown to be undecidable for quantum spin systems in two (or more) spatial dimensions: there exists no algorithm that determines in general whether a system is gapped or gapless, a result which has many unexpected consequences for the physics of such systems. However, there are many indications that one dimensional spin systems are simpler than their higher-dimensional counterparts: for example, they cannot have thermal phase transitions or topological order, and there exist highly-effective numerical algorithms such as DMRG - and even provably polynomial-time ones - for gapped 1D systems, exploiting the fact that such systems obey an entropy area-law. Furthermore, the spectral gap undecidability construction crucially relied on aperiodic tilings, which are not possible in 1D. So does the spectral gap problem become decidable in 1D? In this paper we prove this is not the case, by constructing a family of 1D spin chains with translationally-invariant nearest neighbour interactions for which no algorithm can determine the presence of a spectral gap. This not only proves that the spectral gap of 1D systems is just as intractable as in higher dimensions, but also predicts the existence of qualitatively new types of complex physics in 1D spin chains. In particular, it implies there are 1D systems with constant spectral gap and non-degenerate classical ground state for all systems sizes up to an uncomputably large size, whereupon they switch to a gapless behaviour with dense spectrum.

arXiv comment7 figures

References in corpus (30)

• An Area Law for One Dimensional Quantum Systems
• Experimental realization of a long-range antiferromagnet in the Hubbard model with ultracold atoms
• Spectral Gap and Exponential Decay of Correlations
• Topological quantum order: stability under local perturbations
• Undecidability of the Spectral Gap (short version)
• An introduction to integrable techniques for one-dimensional quantum systems
• The power of quantum systems on a line
• Renormalization group transformations on quantum states
• Stability of Frustration-Free Hamiltonians
• Quantum phase transitions in matrix product systems
• Power law violation of the area law in quantum spin chains
• Matrix product operators and states: NP-hardness and undecidability
• More Really is Different
• Quantum measurement occurrence is undecidable
• Ground states in relatively bounded quantum perturbations of classical lattice systems
• Frustration free gapless Hamiltonians for Matrix Product States
• Fundamental limitations in the purifications of tensor networks
• DCA${}^{+}$: Dynamical Cluster Approximation with continuous lattice self-energy
• Unfrustrated Qudit Chains and their Ground States
• Space-Time Circuit-to-Hamiltonian Construction and Its Applications
• 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
• Generic Local Hamiltonians are Gapless
• Non-signaling deterministic models for non-local correlations have to be uncomputable
• Analysis and limitations of modified circuit-to-Hamiltonian constructions
• Undecidability in Tensor Network States
• Measurement-based quantum computation and undecidable logic
• The Complexity of Translationally-Invariant Low-Dimensional Spin Lattices in 3D
• Gaplessness is not generic for translation-invariant spin chains

Cited by in corpus (21)

• Near-optimal ground state preparation
• Speed limits and locality in many-body quantum dynamics
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Solving the Liouvillian Gap with Artificial Neural Networks
• The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
• Effects of defects in the XY chain with frustrated boundary conditions
• Undecidable problems in quantum field theory
• What the foundations of quantum computer science teach us about chemistry
• Glassy word problems: ultraslow relaxation, Hilbert space jamming, and computational complexity
• Undecidability of the Spectral Gap (full version)
• Random translation-invariant Hamiltonians and their spectral gaps
• Many bounded versions of undecidable problems are NP-hard
• Identification of gapless phases by a twisting operator
• Unprovability of First Maxwell's Equation in Light of EPR's Completeness Condition -- A Computational Approach from Logico-linguistic Perspective
• A Hierarchy of Spectral Gap Certificates for Frustration-Free Spin Systems
• Sample complexity of matrix product states at finite temperature
• The membership problem for constant-sized quantum correlations is undecidable
• The Undecidable Charge Gap and the Oil Drop Experiment
• Spectral statistics and energy-gap scaling in $k-$local spin Hamiltonians
• Undecidability of the spectral gap in rotationally symmetric Hamiltonians
• Variational Quantum Algorithm for Solving the Liouvillian Gap