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.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
Gödel, K. (2006) · Monatshefte für Mathematik · doi:10.1007/s00605-006-0423-7 · Cited by 2,077
Scaling and Renormalization in Statistical Physics
Cardy, J. (1996) · Cambridge University Press eBooks · doi:10.1017/cbo9781316036440 · Cited by 1,902
Feynman, R. P. (1986) · Foundations of Physics · doi:10.1007/bf01886518 · Cited by 1,770
Bernstein, E., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300921 · Cited by 1,503
Valence bond ground states in isotropic quantum antiferromagnets
Affleck, I., Kennedy, T., Lieb, E. H., & Tasaki, H. (1988) · Communications in Mathematical Physics · doi:10.1007/bf01218021 · Cited by 1,477
Classical and Quantum Computation
Kitaev, A., Shen, A., & Vyalyi, M. (2002) · Graduate Studies in Mathematics · doi:10.1090/gsm/047 · Cited by 1,387
Fredkin, E., & Toffoli, T. (2001) · Cited by 1,302
Bernstein, E., & Vazirani, U. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167097 · Cited by 1,284
Spin-Liquid Ground State of the S = 1/2 Kagome Heisenberg Antiferromagnet
Yan, S., Huse, D. A., & White, S. R. (2011) · Science · doi:10.1126/science.1201080 · Cited by 1,241
Fractionalized excitations in the spin-liquid state of a kagome-lattice antiferromagnet
Han, T.-H., Helton, J. S., Chu, S., Nocera, D. G., Rodriguez-Rivera, J. A., Broholm, C., & Lee, Y. S. (2012) · Nature · doi:10.1038/nature11659 · Cited by 1,179
An area law for one-dimensional quantum systems
Hastings, M. B. (2007) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2007/08/p08024 · Cited by 1,131
Feynman, R. P. (1985) · Optics News · doi:10.1364/on.11.2.000011 · Cited by 1,023
Two-Dimensional Ising Model as a Soluble Problem of Many Fermions
SCHULTZ, T. D., MATTIS, D. C., & LIEB, E. H. (1964) · Reviews of Modern Physics · doi:10.1103/revmodphys.36.856 · Cited by 936
Computability in Analysis and Physics
Pour-El, M. B., & Richards, J. I. (1989) · Perspectives in Mathematical Logic · doi:10.1007/978-3-662-21717-7 · Cited by 920
Proving Theorems by Pattern Recognition - II
Wang, H. (1961) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1961.tb03975.x · Cited by 862
Undecidability and nonperiodicity for tilings of the plane
Robinson, R. M. (1971) · Inventiones mathematicae · doi:10.1007/bf01418780 · Cited by 826
Lieb-Schultz-Mattis in higher dimensions
Hastings, M. B. (2004) · Physical Review B · doi:10.1103/physrevb.69.104431 · Cited by 685
The Complexity of the Local Hamiltonian Problem
Kempe, J., Kitaev, A., & Regev, O. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704445226 · Cited by 648
Quantum Computation by Adiabatic Evolution
Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2000) · arXiv · doi:10.48550/arxiv.quant-ph/0001106 · Cited by 536
Equivalence of Cellular Automata to Ising Models and Directed Percolation
Domany, E., & Kinzel, W. (1984) · Physical Review Letters · doi:10.1103/physrevlett.53.311 · Cited by 497
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447323 · Cited by 457
Unpredictability and undecidability in dynamical systems
Moore, C. (1990) · Physical Review Letters · doi:10.1103/physrevlett.64.2354 · Cited by 414
Lieb-Robinson Bounds and the Exponential Clustering Theorem
Nachtergaele, B., & Sims, R. (2006) · Communications in Mathematical Physics · doi:10.1007/s00220-006-1556-1 · Cited by 406
Spectral gap and exponential decay of correlationsPreprint
Hastings, M. B., & Koma, T. (2013) · Cited by 393
Topological quantum order: Stability under local perturbations
Bravyi, S., Hastings, M. B., & Michalakis, S. (2010) · Journal of Mathematical Physics · doi:10.1063/1.3490195 · Cited by 374
Rado, T. (1962) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1962.tb00480.x · Cited by 297
The wave equation with computable initial data such that its unique solution is not computable
Pour-El, M. B., & Richards, I. (1981) · Advances in Mathematics · doi:10.1016/0001-8708(81)90001-3 · Cited by 243
A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians
Landau, Z. A., Vazirani, U. V., & Vidick, T. (2015) · Nature Physics · doi:10.1038/nphys3345 · Cited by 216
The Power of Quantum Systems on a Line
Aharonov, D., Gottesman, D., Irani, S., & Kempe, J. (2009) · Communications in Mathematical Physics · doi:10.1007/s00220-008-0710-3 · Cited by 210
Entropy and entanglement in quantum ground states
Hastings, M. B. (2007) · Physical Review B · doi:10.1103/physrevb.76.035114 · Cited by 178
Stability of Frustration-Free Hamiltonians
Michalakis, S., & Zwolak, J. P. (2013) · Communications in Mathematical Physics · doi:10.1007/s00220-013-1762-6 · Cited by 176
Lattice Gauge Theories and Monte Carlo Simulations
Claudio Rebbi, B. (1983) · WORLD SCIENTIFIC eBooks · doi:10.1142/0043 · Cited by 156
The complexity of quantum spin systems on a two-dimensional square lattice
Oliveira, R. I., & Terhal, B. M. (2008) · CERN Document Server (European Organization for Nuclear Research) · doi:10.5555/2016985.2016987 · Cited by 145
Finite-lattice extrapolations for a Haldane-gap antiferromagnet
Golinelli, O., Jolicœur, T., & Lacaze, R. (1994) · Physical review. B, Condensed matter · doi:10.1103/physrevb.50.3037 · Cited by 144
Vanishing spin gap in a competing spin-liquid phase in the kagome Heisenberg antiferromagnet
Iqbal, Y., Poilblanc, D., & Becca, F. (2014) · Physical Review B · doi:10.1103/physrevb.89.020407 · Cited by 131
Elementary Excitations in Gapped Quantum Spin Systems
Haegeman, J., Michalakis, S., Nachtergaele, B., Osborne, T. J., Schuch, N., & Verstraete, F. (2013) · Physical Review Letters · doi:10.1103/physrevlett.111.080401 · Cited by 128
Schwartz, M. D. (2013) · Cambridge University Press eBooks · doi:10.1017/9781139540940.027 · Cited by 102
Matrix-Product Operators and States: NP-Hardness and Undecidability
Kliesch, M., Gross, D., & Eisert, J. (2014) · Physical Review Letters · doi:10.1103/physrevlett.113.160503 · Cited by 93
Hofstadter butterfly as quantum phase diagram
Osadchy, D., & Avron, J. E. (2001) · Journal of Mathematical Physics · doi:10.1063/1.1412464 · Cited by 86
Nishimura, H., & Ozawa, M. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(01)00111-6 · Cited by 81
The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
Gottesman, D., & Irani, S. (2009) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2009.22 · Cited by 76
Frustration Free Gapless Hamiltonians for Matrix Product States
Fernández-González, C., Schuch, N., Wolf, M. M., Cirac, J. I., & Pérez-García, D. (2014) · Communications in Mathematical Physics · doi:10.1007/s00220-014-2173-z · Cited by 64
Self-citationUndecidable problems: a sampler
Poonen, B. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9780511756306.015 · Cited by 63
Gu, M., Weedbrook, C., Perales, Á., & Nielsen, M. A. (2009) · Physica D Nonlinear Phenomena · doi:10.1016/j.physd.2008.12.016 · Cited by 59
Undecidability of Macroscopically Distinguishable States in Quantum Field Theory
Komar, A. B. (1964) · Physical Review · doi:10.1103/physrev.133.b542 · Cited by 56
Quantum measurement occurrence is undecidable
Eisert, J., Müller, M. P., & Gogolin, C. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.260501 · Cited by 53
Are problems in Quantum Information Theory (un)decidable?Preprint
Wolf, M. M., Cubitt, T. S., & Pérez-García, D. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1111.5425 · Cited by 48
Self-citationUndecidability principle and the uncertainty principle even for classical systems
Kanter, I. (1990) · Physical Review Letters · doi:10.1103/physrevlett.64.332 · Cited by 32
Quantum-mechanical computers and uncomputability
Lloyd, S. (1993) · Physical Review Letters · doi:10.1103/physrevlett.71.943 · Cited by 31
The Complexity of Translationally Invariant Spin Chains with Low Local Dimension
Bausch, J., Cubitt, T. S., & Ozols, M. (2017) · UCL Discovery (University College London) · doi:10.17863/cam.15638 · Cited by 29
Self-citationA polynomial-time algorithm for the ground state of 1D gapped local HamiltoniansPreprint
Landau, Z. A., Vazirani, U. V., & Vidick, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1307.5143 · Cited by 25
Nonsignaling Deterministic Models for Nonlocal Correlations have to be Uncomputable
Bendersky, A., Senno, G., de la Torre, G., Figueira, S. D., & Acín, A. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.130401 · Cited by 19
Measurement-Based Quantum Computation and Undecidable Logic
Van den Nest, M., & Briegel, H. J. (2008) · Foundations of Physics · doi:10.1007/s10701-008-9212-6 · Cited by 17
Undecidability in tensor network states
Morton, J., & Biamonte, J. (2012) · Physical Review A · doi:10.1103/physreva.86.030301 · Cited by 17
The Gödel Incompleteness Theorem and Decidability over a Ring
Blum, L., & Smale, S. (1993) · Springer eBooks · doi:10.1007/978-1-4612-2740-3_32 · Cited by 16
Stochastic Error Cancellation in Analog Quantum Simulation
Cai, Y., Tong, Y., & Preskill, J. P. (2023) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.tqc.2024.2 · Cited by 14
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
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.