PIRSA:18100004

Undecidability of the spectral gap in one dimension

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

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

          @misc{ pirsa_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},
            year = {2018},
            month = {oct},
            note = {PIRSA:18100004 see, \url{https://pirsa.org}}
          }

Angelo Lucia

California Institute of Technology

Talk number
PIRSA:18100004
Collection
Talk Type
Subject
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.