Cubitt, T;
Perez-Garcia, D;
Wolf, M;
(2022)
Undecidability of the Spectral Gap.
Forum of Mathematics Pi
, 10
, Article e14. 10.1017/fmp.2021.15.
Preview |
Text
Cubitt_undecidability-of-the-spectral-gap.pdf Download (10MB) | Preview |
Abstract
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 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1017/fmp.2021.15 |
| Publisher version: | https://doi.org/10.1017/fmp.2021.15 |
| Language: | English |
| Additional information: | This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited. |
| Keywords: | Quantum many-body physics, quantum computation, undecidability, spectral theory |
| 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 |
Archive Staff Only
 |
View Item |
