The DOI matches its Crossref record; 66 of the 66 references it cites were found in a registry or an index.
Undecidability of the spectral gap
Open accessAbstract
The spectral gap—the energy difference between the ground state and first excited state of a system—is central to quantum many-body physics. Many challenging open problems, such as the Haldane conjecture, the question of the existence of gapped topological spin liquid phases, and the Yang–Mills gap conjecture, concern spectral gaps. These and other problems are particular cases of the general spectral gap problem: given the Hamiltonian of a quantum many-body system, is it gapped or gapless? Here we prove that this is an undecidable problem. Specifically, we construct families of quantum spin systems on a two-dimensional lattice with translationally invariant, nearest-neighbour interactions, for which the spectral gap problem is undecidable. This result extends to undecidability of other low-energy properties, such as the existence of algebraically decaying ground-state correlations. The proof combines Hamiltonian complexity techniques with aperiodic tilings, to construct a Hamiltonian whose ground state encodes the evolution of a quantum phase-estimation algorithm followed by a universal Turing machine. The spectral gap depends on the outcome of the corresponding ‘halting problem’. Our result implies that there exists no algorithm to determine whether an arbitrary model is gapped or gapless, and that there exist models for which the presence or absence of a spectral gap is independent of the axioms of mathematics.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Quantum Computation and Quantum Information
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
On computable numbers, with an application to the entscheidungsproblem
Turing, A. M. (1937) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s2-42.1.230 · Cited by 8,283
Spin liquids in frustrated magnets
Balents, L. (2010) · Nature · doi:10.1038/nature08917 · Cited by 4,316
Two soluble models of an antiferromagnetic chain
Lieb, E., Schultz, T., & Mattis, D. (1961) · Annals of Physics · doi:10.1016/0003-4916(61)90115-4 · Cited by 4,280
Haldane, F. D. M. (1983) · Physical Review Letters · doi:10.1103/physrevlett.50.1153 · Cited by 3,695
Logical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679
Energy levels and wave functions of Bloch electrons in rational and irrational magnetic fields
Hofstadter, D. R. (1976) · Physical Review B · doi:10.1103/physrevb.14.2239 · Cited by 3,495
Colloquium : Area laws for the entanglement entropy
Eisert, J., Cramer, M., & Plenio, M. B. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.277 · Cited by 2,873
Resonating valence bonds: A new kind of insulator?
Anderson, P. W. (1973) · Materials Research Bulletin · doi:10.1016/0025-5408(73)90167-0 · Cited by 2,823
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
Gödel, K. (1931) · Monatshefte für Mathematik und Physik · doi:10.1007/bf01700692 · Cited by 2,395
Cited by
A cross-disciplinary introduction to quantum annealing-based algorithms
Venegas-Andraca, S. E., Cruz-Santos, W., McGeoch, C., & Lanzagorta, M. (2018) · Contemporary Physics · doi:10.1080/00107514.2018.1450720 · Cited by 83
Metadata
- Authors
- Cubitt, T. S., Perez-Garcia, D., & Wolf, M. M.
- Venue
- Nature
- Published
- 2015-12
- Volume
- 528
- Issue
- 7581
- Pages
- 207-211
- ISSN
- 0028-0836 (ISSN-L)
- 1476-4687
- OpenAlex
- W2192149141
- Cited by
- 262
- References
- 66
- FWCI
- 13.08
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Undecidability of the spectral gap. https://app.cochat.ai/papers/10.1038/nature16059
- The paper
- Cubitt, T. S., Perez-Garcia, D., & Wolf, M. M. (2015). Undecidability of the spectral gap. Nature. https://doi.org/10.1038/nature16059
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.