Determining spectral gaps in the thermodynamic limit is a central challenge in quantum many-body physics. When a fixed boundary condition is imposed, this problem is undecidable: no algorithm, even with unlimited resources, can decide for every Hamiltonian whether it is gapped. Yet the thermodynamic limit is meant to capture the intrinsic properties of very large systems, which should not depend on how their boundaries are chosen. Here, we therefore consider the bulk spectral gap problem, which concerns only the intrinsic excitations of the infinite system, independently of any boundary. We first give a general algorithm producing a hierarchy of certified upper bounds on the bulk gap, arbitrarily tight at the cost of more computation. Second, we prove that the spectral gap problem remains undecidable in the bulk: no algorithm can decide whether the bulk gap is positive, already for translationally invariant nearest-neighbour chains of fixed local dimension. The bulk spectral gap is thus certifiable from above but uncomputable from below. More precisely, the bulk-gaplessness promise problem is RE-complete, exactly as hard as the halting problem. The same construction also shows that deciding whether an explicitly given state is a ground state of the infinite system is undecidable. Finally, we apply the upper-bounding algorithm to the spin-1/2 kagome Heisenberg antiferromagnet to produce the first nontrivial certified upper bounds on its bulk gap.
Comments
47 pages, 5 figures, incl. SI (38 pages). Comments welcome! v4: uncomputability of KMS ground states and their expectation values; instability under onsite perturbations; corrected kagome bounds. v3: uncomputability of the bulk gap from below, RE-completeness, title updated (previously: The bulk spectral gap is semi-decidable: a convergent family of certified upper bounds)
Determining spectral gaps in the thermodynamic limit is a central challenge in quantum many-body physics. When a fixed boundary condition is imposed, this problem is undecidable: no algorithm, even with unlimited resources, can decide for every Hamiltonian whether it is gapped. Yet the thermodynamic limit is meant to capture the intrinsic properties of very large systems, which should not depend on how their boundaries are chosen. Here, we therefore consider the bulk spectral gap problem, which concerns only the intrinsic excitations of the infinite system, independently of any boundary. We first give a general algorithm producing a hierarchy of certified upper bounds on the bulk gap, arbitrarily tight at the cost of more computation. Second, we prove that the spectral gap problem remains undecidable in the bulk: no algorithm can decide whether the bulk gap is positive, already for translationally invariant nearest-neighbour chains of fixed local dimension. The bulk spectral gap is thus certifiable from above but uncomputable from below. More precisely, the bulk-gaplessness promise problem is RE-complete, exactly as hard as the halting problem. The same construction also shows that deciding whether an explicitly given state is a ground state of the infinite system is undecidable. Finally, we apply the upper-bounding algorithm to the spin-1/2 kagome Heisenberg antiferromagnet to produce the first nontrivial certified upper bounds on its bulk gap.
This paper provides a self-contained conceptual overview of one of the most striking results in contemporary quantum many-body physics: the undecidability of the spectral gap problem. The spectral gap—the energy difference between a system's ground state and its first excited state—is a fundamental property that distinguishes insulating from conducting behavior and marks quantum phase transitions. In 2015, Cubitt, Pérez-García, and Wolf proved that deciding whether a translationally invariant quantum spin system with finite-range interactions is gapped or gapless is algorithmically undecidable. This result was extended to one-dimensional systems by Bausch and colleagues in 2020, overturning the intuition that lower-dimensional systems are inherently more tractable. The proof architecture rests on two main ingredients: aperiodic tilings and history-state constructions. Aperiodic tilings encode undecidable combinatorial properties into the spatial structure of the Hamiltonian, while history states embed the evolution of a Turing machine into the ground state. By combining these elements, the authors construct explicit Hamiltonians whose spectral gap depends directly on whether a simulated Turing machine halts—a problem known to be undecidable. Thus, no algorithm can classify every instance correctly. The paper also distinguishes two forms of undecidability: algorithmic undecidability, which asserts that no Turing machine can solve the problem for all instances, and axiomatic independence, which shows that for some Hamiltonians, the gap status is not determined by the standard axioms of mathematics. These results impose fundamental limits on numerical simulation and phase classification, but they do not render all systems intractable. They demarcate a boundary between decidable and undecidable behavior, revealing deep connections between physics, computation, and logic.
FINDING: The spectral gap problem — determining whether a quantum Hamiltonian's energy spectrum has a gap above the ground state — is provably undecidable in general, linking quantum many-body physics to the halting problem and Gödelian limits. | MATH: The key construction (Cubitt, Perez-Garcia, Wolf, 2015) reduces the halting problem to a family of 2D spin-lattice Hamiltonians H(n) on a fixed lattice, where the spectral gap (difference between ground state energy E0 and first excited state E1) is either Δ>0 (gapped) or Δ=0 (gapless), depending on whether a Turing machine halts. The Hamiltonian is built from translationally invariant local terms with frustration-free ground states; the gap closes as Δ∼1/poly(n) in the gapless case. No closed-form equation for Δ exists — it is algorithmically uncomputable. | CONNECTION: The construction uses a lattice structure (square lattice, 2D) with local interaction ter Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
FINDING: Undecidability of the spectral gap in quantum many-body systems proves that certain physical properties cannot be algorithmically determined, revealing fundamental limits to computation and knowledge. | MATH: The spectral gap problem is equivalent to the halting problem; no algorithm exists to decide if a Hamiltonian has a gap (Δ > 0) or is gapless (Δ = 0). Key constants: spectral gap Δ, Hamiltonian H, ground state energy E₀, first excited state energy E₁, Δ = E₁ - E₀. | CONNECTION: The spectral gap problem is linked to the geometry of the parameter space of Hamiltonians; the undecidability arises from the ability to encode Turing machines into the lattice structure of quantum spin systems, reflecting a deep symmetry between computation and physical law. The ratio Δ/||H|| is not computable in general. | DEPTH: 9 — This finding bridges computability theory, quantum mechanics, and geometry, showing that the mathematical structure of the universe includes inherently uncomputable Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
Here is the finding. For frustration-free spin-1/2 chains, the spectral gap question is decidable. We can completely classify these systems into gapped and gapless phases. This holds even though the general problem for translationally invariant Hamiltonians is undecidable, as shown by Cubitt, Perez-Garcia, and Wolf in 2015. Here is the context. We are talking about Hamiltonians written as a sum of local terms, each positive semidefinite, with a ground state annihilated by every term. That is the frustration-free condition. The spectral gap is the energy difference between the first excited state and the ground state. For a general quantum many-body system, determining whether that gap closes in the thermodynamic limit is notoriously hard. But for this restricted class, the mathematics gives us a clean answer. Here is the mechanism. The key is the matrix product state representation. The ground state of a gapped phase has finite correlation length. Its MPS transfer matrix is injective Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
Abstract 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. Moreover, this constant can be taken equal to the operator norm of the local operator that generates the Hamiltonian (the local interaction strength). The result still holds true if one restricts to arbitrarily small quantum perturbations of classical Hamiltonians. The proof combines a robustness analysis of Robinson’s aperiodic tiling, together with tools from quantum information theory: the quantum phase estimation algorithm and the history state technique mapping Quantum Turing Machines to Hamiltonians.
FINDING: The spectral gap problem is undecidable in general — no algorithm can determine whether a quantum many-body Hamiltonian has a spectral gap or is gapless, establishing a Gödel/Turing-style limit inside physics itself. | MATH: Given a translation-invariant, nearest-neighbour Hamiltonian H on a 2D spin lattice, the ground-state energy density and the question "is Δ = E₁ − E₀ > 0?" are undecidable (Cubitt, Pérez-García, Wolf, Nature 2015). The construction encodes a universal Turing machine into the low-energy spectrum; the spectral gap's presence/absence maps to halting/non-halting. | CONNECTION: No direct golden-ratio or crystallographic constant appears in the undecidability result itself. The relevant symmetry structure is the 2D lattice translation group ℤ² and the local SU(2)/finite-group gauge structure of the spin Hamiltonian — a lattice/crystallographic setting, but the undecidability is a logical (computability) property, not a geometric-harmony ratio. | DEPTH: 9 FINDIN Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com