Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Uncomputable finite-size gap exponents

Seth Douglas, Nidhal Mghirbi

Published Oct 29, 2026• 0 citations
Publisher

Abstract

We classify the nonnegative finite-size spectral-gap exponents of translation-invariant nearest-neighbour Hamiltonians on the square lattice, with finite local dimension, integer interaction matrices and open boundaries. The gap is measured above the entire ground space on an $L\times L$ box. The existing exponents in $\Delta(L)=L^{-z+o(1)}$ are exactly the nonnegative limit-computable ($\Delta^0_2$) reals. The finite nonnegative lower/upper exponent pairs are exactly the ordered pairs consisting of a left-$\Sigma^0_2$ real and a left-$\Pi^0_2$ real. In particular, one fixed integer-valued model has exponent equal to the halting probability of any chosen prefix-universal machine. A classical boundary preference fixes a size counter and a computation tableau; a reversible mixed-radix counter supplies the small gap. We bound every sector of the full Hilbert space. The closing modes live on a boundary segment of length $O(\log L)$, and the local dimension may depend on the prescribed pair. These are finite-box exponents, with no assertion about bulk dispersion or stability of thermodynamic critical exponents.

DOI
10.5281/zenodo.23753840

Related papers

Uncomputable critical exponents

Seth Douglas, Nidhal Mghirbi

We construct translation-invariant nearest-neighbour quantum Hamiltonian families with rational affine coefficient matrices whose existing finite nonnegative critical gap exponents at coupling zero are exactly the nonnegative Delta^0_3 reals, already in two dimensions. Volume limits along factorial tori precede coupling, and gaps are above the entire ground space. Separate finite registers share an energetic ruler, a framed computation and a final-time broadcast to positive-density quantum readers. The inner gap is eventually exact at fixed positive coupling without a general computable settling bound. Three-dimensional broadcast and wetting films give independent routes; tamed rulers and nested limits retain their classifications. A fixed universal noisy rule, with a computable bottom boundary, program origin and infinite cloning, has exactly Delta^0_3 density and counting laws in [0,1] under prescribed time-then-window limits, robust on an open positive-rate kernel region. At computable kernels no effective inquiry converges with positive probability to a fixed such law outside Delta^0_2; the exceptional learnable kernels are null, meager but dense for external finite-cylinder inquiry. Unique classical states of computable specifications have computable local numbers, while growing readouts and state selection permit noncomputable asymptotic content. Restricted response certificates and an exact calibrated-ruler criterion delimit robustness claims. A computable randomized adaptive inquiry reaches a fixed real with positive probability only at Delta^0_2. The beyond-Delta^0_2 gap exponents have no computably bounded relative gap-settling scale, excluding a specified uniform scaling tail. All-size convergence, unique ground states, locally nondegenerate gap identification and robust intrinsic equilibrium exponents remain unestablished.

•Oct 29, 2026•1 citation

The bulk spectral gap is certifiable from above but uncomputable from below

Xiangling Xu, Matthias Schötz, Jie Wang +4 more

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. We therefore consider the bulk spectral gap, which concerns only the intrinsic excitations of the infinite system, and ask what can and cannot be computed about it. First, we 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, already for translationally invariant nearest-neighbour chains of fixed local dimension. Hence no general algorithm produces convergent lower bounds, and no convergent upper-bounding algorithm, ours included, admits a computable convergence rate. 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 shows that no general algorithm can decide whether a given product state is a ground state, and that convergent bounds on ground-state expectation values admit no computable convergence rate in general. Finally, we obtain the first nontrivial certified upper bounds on the bulk gap of the spin-1/2 kagome Heisenberg antiferromagnet.

quant-pharXiv:2606.03836•Jun 3, 2026•0 citations

Uncomputable critical exponents

Seth Douglas, Nidhal Mghirbi

We construct translation-invariant nearest-neighbour quantum Hamiltonian families with rational coefficient matrices whose critical gap exponents at the computable transition coupling zero fill Delta-2 in the bulk on Z^2 and Delta-3 in the bulk on Z^3. Volume limits use cubic tori of side L=n! and precede the coupling limit; gaps are above the entire ground space. A classical energetic ruler selects pitch proportional to inverse coupling. In three dimensions a self-created frame supports an unbounded computation, whose final-time output is broadcast by nearest-neighbour classical constraints to positive-density bulk counters. Their full gaps give an extensive flat band and nonzero local spectral weight per volume at each fixed positive coupling. The inner limit is eventually exact, with no general computable settling bound. The two-dimensional ruler also realizes ordered left-Sigma-2 and left-Pi-2 endpoint pairs, including a halting probability. Surface-anchored wetting films independently attain Delta-3; fixed-thickness films and dependent nested box limits yield the stated arithmetic hierarchy. We give full-sector counter bounds, conditional ceilings for effectively controlled limits, and an explicit onsite instability of the earlier rulers. Finite analytic systems have integer exponents. No all-integer-size limit, robustness, unique-ground-state realization, correlation-length classification, or identification with locally nondegenerate or KMS-extremized gaps is established.

•Oct 29, 2026•1 citation

Uncomputable critical exponents

Seth Douglas, Nidhal Mghirbi

We construct translation-invariant nearest-neighbour quantum Hamiltonian families with rational affine coefficient matrices whose existing finite nonnegative critical gap exponents at coupling zero are exactly the nonnegative Delta^0_3 reals, already in two dimensions. Volume limits along factorial tori precede coupling, and gaps are above the entire ground space. Separate finite registers share an energetic ruler, a framed computation and a final-time broadcast to positive-density quantum readers. The inner gap is eventually exact at fixed positive coupling without a general computable settling bound. Three-dimensional broadcast and wetting films give independent routes; tamed rulers and nested limits retain their classifications. A fixed universal noisy rule, with a computable bottom boundary, program origin and infinite cloning, has exactly Delta^0_3 density and counting laws in [0,1] under prescribed time-then-window limits, robust on an open positive-rate kernel region. At computable kernels no effective inquiry converges with positive probability to a fixed such law outside Delta^0_2; the exceptional learnable kernels are null, meager but dense for external finite-cylinder inquiry. Unique classical states of computable specifications have computable local numbers, while growing readouts and state selection permit noncomputable asymptotic content. Restricted response certificates and an exact calibrated-ruler criterion delimit robustness claims. A computable randomized adaptive inquiry reaches a fixed real with positive probability only at Delta^0_2. The beyond-Delta^0_2 gap exponents have no computably bounded relative gap-settling scale, excluding a specified uniform scaling tail. All-size convergence, unique ground states, locally nondegenerate gap identification and robust intrinsic equilibrium exponents remain unestablished.

•Oct 29, 2026•0 citations

Undecidability of the Spectral Gap

Toby S. Cubitt, David Pérez-Garcı́a, Michael M. Wolf

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.

arXiv:1502.04573•Forum of Mathematics Pi•Jan 1, 2022•14 citations

Quantum Spectral Gap Provably Undecidable, Linking Physics to Halting Problem — E8 Intelligence Research

Andrew Stewart Caldin

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 \( E_0 \) and first excited state \( E_1 \)) is either \( \Delta > 0 \) (gapped) or \( \Delta = 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 \( \Delta \sim 1/\text{poly}(n) \) in the gapless case. No closed-form equation for \( \Delta \) 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

•Oct 26, 2026•0 citations
We classify the nonnegative finite-size spectral-gap exponents of translation-invariant nearest-neighbour Hamiltonians on the square lattice, with finite local dimension, integer interaction matrices and open boundaries. The gap is measured above the entire ground space on an L×LL\times LL×L box. The existing exponents in Δ(L)=L−z+o(1)\Delta(L)=L^{-z+o(1)}Δ(L)=L−z+o(1) are exactly the nonnegative limit-computable (Δ20\Delta^0_2Δ20​) reals. The finite nonnegative lower/upper exponent pairs are exactly the ordered pairs consisting of a left-Σ20\Sigma^0_2Σ20​ real and a left-Π20\Pi^0_2Π20​ real. In particular, one fixed integer-valued model has exponent equal to the halting probability of any chosen prefix-universal machine. A classical boundary preference fixes a size counter and a computation tableau; a reversible mixed-radix counter supplies the small gap. We bound every sector of the full Hilbert space. The closing modes live on a boundary segment of length O(log⁡L)O(\log L)O(logL), and the local dimension may depend on the prescribed pair. These are finite-box exponents, with no assertion about bulk dispersion or stability of thermodynamic critical exponents.
We construct translation-invariant nearest-neighbour quantum Hamiltonian families with rational affine coefficient matrices whose existing finite nonnegative critical gap exponents at coupling zero are exactly the nonnegative Delta^0_3 reals, already in two dimensions. Volume limits along factorial tori precede coupling, and gaps are above the entire ground space. Separate finite registers share an energetic ruler, a framed computation and a final-time broadcast to positive-density quantum readers. The inner gap is eventually exact at fixed positive coupling without a general computable settling bound. Three-dimensional broadcast and wetting films give independent routes; tamed rulers and nested limits retain their classifications. A fixed universal noisy rule, with a computable bottom boundary, program origin and infinite cloning, has exactly Delta^0_3 density and counting laws in [0,1] under prescribed time-then-window limits, robust on an open positive-rate kernel region. At computable kernels no effective inquiry converges with positive probability to a fixed such law outside Delta^0_2; the exceptional learnable kernels are null, meager but dense for external finite-cylinder inquiry. Unique classical states of computable specifications have computable local numbers, while growing readouts and state selection permit noncomputable asymptotic content. Restricted response certificates and an exact calibrated-ruler criterion delimit robustness claims. A computable randomized adaptive inquiry reaches a fixed real with positive probability only at Delta^0_2. The beyond-Delta^0_2 gap exponents have no computably bounded relative gap-settling scale, excluding a specified uniform scaling tail. All-size convergence, unique ground states, locally nondegenerate gap identification and robust intrinsic equilibrium exponents remain unestablished.
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. We therefore consider the bulk spectral gap, which concerns only the intrinsic excitations of the infinite system, and ask what can and cannot be computed about it. First, we 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, already for translationally invariant nearest-neighbour chains of fixed local dimension. Hence no general algorithm produces convergent lower bounds, and no convergent upper-bounding algorithm, ours included, admits a computable convergence rate. 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 shows that no general algorithm can decide whether a given product state is a ground state, and that convergent bounds on ground-state expectation values admit no computable convergence rate in general. Finally, we obtain the first nontrivial certified upper bounds on the bulk gap of the spin-1/2 kagome Heisenberg antiferromagnet.
We construct translation-invariant nearest-neighbour quantum Hamiltonian families with rational coefficient matrices whose critical gap exponents at the computable transition coupling zero fill Delta-2 in the bulk on Z^2 and Delta-3 in the bulk on Z^3. Volume limits use cubic tori of side L=n! and precede the coupling limit; gaps are above the entire ground space. A classical energetic ruler selects pitch proportional to inverse coupling. In three dimensions a self-created frame supports an unbounded computation, whose final-time output is broadcast by nearest-neighbour classical constraints to positive-density bulk counters. Their full gaps give an extensive flat band and nonzero local spectral weight per volume at each fixed positive coupling. The inner limit is eventually exact, with no general computable settling bound. The two-dimensional ruler also realizes ordered left-Sigma-2 and left-Pi-2 endpoint pairs, including a halting probability. Surface-anchored wetting films independently attain Delta-3; fixed-thickness films and dependent nested box limits yield the stated arithmetic hierarchy. We give full-sector counter bounds, conditional ceilings for effectively controlled limits, and an explicit onsite instability of the earlier rulers. Finite analytic systems have integer exponents. No all-integer-size limit, robustness, unique-ground-state realization, correlation-length classification, or identification with locally nondegenerate or KMS-extremized gaps is established.
We construct translation-invariant nearest-neighbour quantum Hamiltonian families with rational affine coefficient matrices whose existing finite nonnegative critical gap exponents at coupling zero are exactly the nonnegative Delta^0_3 reals, already in two dimensions. Volume limits along factorial tori precede coupling, and gaps are above the entire ground space. Separate finite registers share an energetic ruler, a framed computation and a final-time broadcast to positive-density quantum readers. The inner gap is eventually exact at fixed positive coupling without a general computable settling bound. Three-dimensional broadcast and wetting films give independent routes; tamed rulers and nested limits retain their classifications. A fixed universal noisy rule, with a computable bottom boundary, program origin and infinite cloning, has exactly Delta^0_3 density and counting laws in [0,1] under prescribed time-then-window limits, robust on an open positive-rate kernel region. At computable kernels no effective inquiry converges with positive probability to a fixed such law outside Delta^0_2; the exceptional learnable kernels are null, meager but dense for external finite-cylinder inquiry. Unique classical states of computable specifications have computable local numbers, while growing readouts and state selection permit noncomputable asymptotic content. Restricted response certificates and an exact calibrated-ruler criterion delimit robustness claims. A computable randomized adaptive inquiry reaches a fixed real with positive probability only at Delta^0_2. The beyond-Delta^0_2 gap exponents have no computably bounded relative gap-settling scale, excluding a specified uniform scaling tail. All-size convergence, unique ground states, locally nondegenerate gap identification and robust intrinsic equilibrium exponents remain unestablished.
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 — 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) H(n) H(n) on a fixed lattice, where the spectral gap (difference between ground state energy E0 E_0 E0​ and first excited state E1 E_1 E1​) is either Δ>0 \Delta > 0 Δ>0 (gapped) or Δ=0 \Delta = 0 Δ=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) \Delta \sim 1/\text{poly}(n) Δ∼1/poly(n) in the gapless case. No closed-form equation for Δ \Delta Δ 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