The bulk spectral gap is certifiable from above but uncomputable from below
Abstract
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.
Related
- Smooth approximation of the minimum function from below (and above)
- Bulk-surface spectral homogenization with indefinite mass in periodic perforated domains
- Bulk gap stability and spectral flow for fermions with weak long-range interactions
- Trisection invariants of 4-manifolds are uncomputable
- PnP*: A certifiable solver for Perspective-n-Point
BibTeX
@misc{xu2026bulk,
title = {{The bulk spectral gap is certifiable from above but uncomputable from below}},
author = {Xiangling Xu and Matthias Schötz and Jie Wang and Victor Magron and Igor Klep and Omar Fawzi and Marc-Olivier Renou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.03836},
eprint = {2606.03836},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.03836},
}
RIS
TY - UNPB
TI - The bulk spectral gap is certifiable from above but uncomputable from below
AU - Xiangling Xu
AU - Matthias Schötz
AU - Jie Wang
AU - Victor Magron
AU - Igor Klep
AU - Omar Fawzi
AU - Marc-Olivier Renou
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2606.03836
UR - https://arxiv.org/abs/2606.03836
AB - 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.
ER -