UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Undecidability of the Spectral Gap

Cubitt, T; Perez-Garcia, D; Wolf, M; (2022) Undecidability of the Spectral Gap. Forum of Mathematics Pi (In press).

[thumbnail of spectral-gap.pdf] Text
spectral-gap.pdf - Accepted Version
Access restricted to UCL open access staff until 4 November 2022.

Download (3MB)


We construct families of translationally-invariant, nearest-neighbour Hamiltonians on a 2D square lattice of d-level quantum systems (d constant), for which determining whether the system is gapped or gapless is an undecidable problem. This is true even with the promise that each Hamiltonian is either gapped or gapless in the strongest sense: it is promised to either have continuous spectrum above the ground state in the thermodynamic limit, or its spectral gap is lower-bounded by a constant. Moreover, this constant can be taken equal to the operator norm of the local operator that generates the Hamiltonian (the local interaction strength). The result still holds true if one restricts to arbitrarily small quantum perturbations of classical Hamiltonians. The proof combines a robustness analysis of Robinson’s aperiodic tiling, together with tools from quantum information theory: the quantum phase estimation algorithm and the history state technique mapping Quantum Turing Machines to Hamiltonians.

Type: Article
Title: Undecidability of the Spectral Gap
Publisher version: https://www.cambridge.org/core/journals/forum-of-m...
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10140175
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item