PIRSA:18100004

Undecidability of the spectral gap in one dimension

APA

Lucia, A. (2018). Undecidability of the spectral gap in one dimension. Perimeter Institute for Theoretical Physics. https://pirsa.org/18100004

MLA

Lucia, Angelo. Undecidability of the spectral gap in one dimension. Perimeter Institute for Theoretical Physics, Oct. 24, 2018, https://pirsa.org/18100004

BibTex

          @misc{ scivideos_PIRSA:18100004,
            doi = {10.48660/18100004},
            url = {https://pirsa.org/18100004},
            author = {Lucia, Angelo},
            keywords = {Quantum Information},
            language = {en},
            title = {Undecidability of the spectral gap in one dimension},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2018},
            month = {oct},
            note = {PIRSA:18100004 see, \url{https://scivideos.org/index.php/pirsa/18100004}}
          }
          

Angelo Lucia California Institute of Technology

Talk numberPIRSA:18100004
Source RepositoryPIRSA

Abstract

The spectral gap problem consist in deciding, given a local interaction, whether the corresponding translationally invariant Hamiltonian on a lattice has a spectral gap independent of the system size or not. In the simplest case of nearest-neighbour frustration-free qubit interactions, there is a complete classification. On the other extreme, for two (or higher) dimensional models with nearest-neighbour interactions this problem can be reduced to the Halting Problem, and it is therefore undecidable.

There are a lot of indications that one dimensional spin chain are relatively simpler than their counterparts in higher dimensions. Nonetheless, I will present a construction of a family of nearest-neighbour, translationally invariant Hamiltonians on a spin chain, for which the spectral gap problem is undecidable.