[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

  • Article
  • Published:

Undecidability of the spectral gap

Nature volume 528, pages 207–211 (2015)Cite this article

Subjects

Abstract

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.

Access through your institution
Buy or subscribe

This is a preview of subscription content, access via your institution

Access options

Access through your institution

Buy this article

  • Purchase on SpringerLink
  • Instant access to full article PDF
Buy now

Prices may be subject to local taxes which are calculated during checkout

Figure 1: Gapped and gapless systems.
Figure 2: Relating ground state energy density to spectral gap.
Figure 3: Complete Hamiltonian construction.

Similar content being viewed by others

References

  1. Schultz, T. D., Mattis, D. C. & Lieb, E. H. Two-dimensional Ising model as a soluble problem of many fermions. Rev. Mod. Phys. 36, 856–871 (1964)

    Article  ADS  MathSciNet  Google Scholar 

  2. Hastings, M. B. Lieb-Schultz-Mattis in higher dimensions. Phys. Rev. B 69, 104431 (2004)

    Article  ADS  Google Scholar 

  3. Affleck, I., Kennedy, T., Lieb, E. H. & Tasaki, H. Valence bond ground states in isotropic quantum antiferromagnets. Commun. Math. Phys. 115, 477–528 (1988)

    Article  ADS  MathSciNet  Google Scholar 

  4. Haldane, F. D. M. Nonlinear field theory of large-spin Heisenberg antiferromagnets: semiclassically quantized solitons of the one-dimensional easy-axis Neel state. Phys. Rev. Lett. 50, 1153–1156 (1983)

    Article  ADS  MathSciNet  Google Scholar 

  5. Golinelli, O., Jolicoeur, Th. & Lacaze, R. Finite-lattice extrapolations for a Haldane-gap antiferromagnet. Phys. Rev. B 50, 3037–3044 (1994)

    Article  ADS  CAS  Google Scholar 

  6. Anderson, P. W. Resonating valence bonds: a new kind of insulator? Mater. Res. Bull. 8, 153–160 (1973)

    Article  CAS  Google Scholar 

  7. Yan, S., Huse, D. A. & White, S. R. Spin-liquid ground state of the S = 1/2 kagome Heisenberg antiferromagnet. Science 332, 1173–1176 (2011)

    Article  ADS  CAS  Google Scholar 

  8. Balents, L. Spin liquids in frustrated magnets. Nature 464, 199–208 (2010)

    Article  ADS  CAS  Google Scholar 

  9. Han, T.-H. et al. Fractionalized excitations in the spin-liquid state of a kagome-lattice antiferromagnet. Nature 492, 406–410 (2012)

    Article  ADS  CAS  Google Scholar 

  10. Jaffe, A. & Witten, E. in The Millennium Prize Problems (eds Carlson, J. A., Jaffe, A. & Wiles, A. ) 129–152, http://www.claymath.org/sites/default/files/yangmills.pdf (Clay Mathematics Institute, American Mathematical Society, 2006)

  11. Rebbi, C. Lattice Gauge Theories and Monte Carlo Simulations (World scientific, 1983)

  12. Turing, A. M. On computable numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. 42, 230–265 (1936)

    MathSciNet  MATH  Google Scholar 

  13. Gödel, K. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatsh. Math. Phys. 38, 173–198 (1931)

    Article  MathSciNet  Google Scholar 

  14. Poonen, B. in Interpreting Gödel: Critical Essays (ed. Kennedy, J. ) 211–241 (Cambridge Univ. Press, 2014)

  15. Feynman, R. P. Quantum mechanical computers. Optics News 11, 11–20 (1985)

    Article  Google Scholar 

  16. Kitaev, A.Y., Shen, A.H. & Vyalyi M.N. Classical and Quantum Computation Vol. 47 of Graduate Studies in Mathematics Ch. 14.4 (American Mathematical Society, 2002)

  17. Kempe, J., Kitaev, A. & Regev, O. The complexity of the local Hamiltonian problem. SIAM J. Comput. 35, 1070–1097 (2006)

    Article  MathSciNet  Google Scholar 

  18. Oliveira, R. & Terhal, B. M. The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Inf. Comput. 8, 900–924 (2008)

    MathSciNet  MATH  Google Scholar 

  19. Aharonov, D., Gottesman, D., Irani, S. & Kempe, J. The power of quantum systems on a line. Commun. Math. Phys. 287, 41–65 (2009)

    Article  ADS  MathSciNet  Google Scholar 

  20. Gottesman, D. & Irani, S. The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. In Proc. 50th Annu. Symp. Found. Comput. Sci. 95–104 (IEEE, 2009)

  21. Bernstein, E. & Vazirani, U. Quantum complexity theory. SIAM J. Comput. 26, 1411–1473 (1997)

    Article  MathSciNet  Google Scholar 

  22. Nielsen, M. A. & Chuang, I. L. Quantum Computation and Quantum Information Ch. 5.2 (Cambridge Univ. Press, 2000)

  23. Wang, H. Proving theorems by pattern recognition. Bell Syst. Tech. J. 40, 1–41 (1961)

    Article  Google Scholar 

  24. Robinson, R. M. Undecidability and nonperiodicity for tilings of the plane. Invent. Math. 12, 177–209 (1971)

    Article  ADS  MathSciNet  Google Scholar 

  25. Cardy, J. (ed.) Finite-size Scaling (Elsevier, 2012)

  26. Cardy, J. Scaling and Renormalization in Statistical Physics (Cambridge Univ. Press, 1996)

  27. Cubitt, T. S., Perez-Garcia, D. & Wolf, M. M. Undecidability of the spectral gap. Preprint at http://arXiv.org/abs/1502.04573 (2015)

  28. Bravyi, S., Hastings, M. & Michalakis, S. Topological quantum order: stability under local perturbations. J. Math. Phys. 51, 093512 (2010)

    Article  ADS  MathSciNet  Google Scholar 

  29. Michalakis, S. & Zwolak, J. P. Stability of frustration-free Hamiltonians. Commun. Math. Phys. 322, 277–302 (2013)

    Article  ADS  MathSciNet  Google Scholar 

Download references

Acknowledgements

T.S.C. thanks IBM. T. J. Watson Laboratory for their hospitality, and C. Bennett in particular for discussions about this work. T.S.C., D.P.-G. and M.M.W. thank the Isaac Newton Institute for Mathematical Sciences, Cambridge for their hospitality during the programme “Mathematical Challenges in Quantum Information”, where part of this work was carried out. T.S.C. is supported by the Royal Society. D.P.G. acknowledges support from MINECO (grant MTM2011-26912 and PRI-PIMCHI-2011-1071), Comunidad de Madrid (grant QUITEMAD+-CM, ref. S2013/ICE-2801) and the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no. 648913). This work was made possible through the support of grant no. 48322 from the John Templeton Foundation. The opinions expressed in this publication are those of the authors and do not necessarily reflect the views of the John Templeton Foundation.

Author information

Authors and Affiliations

  1. Department of Computer Science, University College London, Gower Street, London, WC1E 6BT, UK

    Toby S. Cubitt

  2. DAMTP, University of Cambridge, Centre for Mathematical Sciences, Wilberforce Road, Cambridge, CB3 0WA, UK

    Toby S. Cubitt

  3. Departamento de Análisis Matemático and IMI, Facultad de CC Matemáticas, Universidad Complutense de Madrid, Plaza de Ciencias 3, Madrid, 28040, Spain

    David Perez-Garcia

  4. ICMAT, C/Nicolás Cabrera, Campus de Cantoblanco, Madrid, 28049, Spain

    David Perez-Garcia

  5. Department of Mathematics, Technische Universität München, Garching, 85748, Germany

    Michael M. Wolf

Authors
  1. Toby S. Cubitt
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David Perez-Garcia
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michael M. Wolf
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors contributed extensively to the paper.

Corresponding author

Correspondence to Toby S. Cubitt.

Ethics declarations

Competing interests

The authors declare no competing financial interests.

Supplementary information

Supplementary Information

This file contains Supplementary Text and Data 1-7, Supplementary Figures 1-5 and additional references. (PDF 750 kb)

PowerPoint slides

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cubitt, T., Perez-Garcia, D. & Wolf, M. Undecidability of the spectral gap. Nature 528, 207–211 (2015). https://doi.org/10.1038/nature16059

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1038/nature16059

Search

Advanced search

Quick links

Nature Briefing

Sign up for the Nature Briefing newsletter — what matters in science, free to your inbox daily.

Get the most important science stories of the day, free in your inbox. Sign up for Nature Briefing