IDEAS home Printed from https://ideas.repec.org/a/nat/nature/v528y2015i7581d10.1038_nature16059.html
   My bibliography  Save this article

Undecidability of the spectral gap

Author

Listed:
  • Toby S. Cubitt

    (University College London
    DAMTP, University of Cambridge, Centre for Mathematical Sciences)

  • David Perez-Garcia

    (Facultad de CC Matemáticas, Universidad Complutense de Madrid
    ICMAT, C/Nicolás Cabrera, Campus de Cantoblanco)

  • Michael M. Wolf

    (Technische Universität München)

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.

Suggested Citation

  • Toby S. Cubitt & David Perez-Garcia & Michael M. Wolf, 2015. "Undecidability of the spectral gap," Nature, Nature, vol. 528(7581), pages 207-211, December.
  • Handle: RePEc:nat:nature:v:528:y:2015:i:7581:d:10.1038_nature16059
    DOI: 10.1038/nature16059
    as

    Download full text from publisher

    File URL: https://www.nature.com/articles/nature16059
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1038/nature16059?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. James D. Watson & Emilio Onorati & Toby S. Cubitt, 2022. "Uncomputably complex renormalisation group flows," Nature Communications, Nature, vol. 13(1), pages 1-8, December.
    2. Hamza Fawzi & Omar Fawzi & Samuel O. Scalet, 2024. "Certified algorithms for equilibrium states of local quantum Hamiltonians," Nature Communications, Nature, vol. 15(1), pages 1-6, December.
    3. Heinz Langhals, 2017. "Interaction of Components in Molecular Optoelectronics for the Next Generation of IT Devices," Scientific Review, Academic Research Publishing Group, vol. 3(3), pages 17-28, 03-2017.
    4. Bin Yan & Nikolai A. Sinitsyn, 2022. "Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian," Nature Communications, Nature, vol. 13(1), pages 1-12, December.
    5. Schmidhuber, Christof, 2022. "Chaitin’s Omega and an algorithmic phase transition," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 586(C).

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:nat:nature:v:528:y:2015:i:7581:d:10.1038_nature16059. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.nature.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.