Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T01:48:16.050Z Has data issue: false hasContentIssue false

Undecidability of the Spectral Gap

Published online by Cambridge University Press:  10 June 2022

Toby Cubitt*
Affiliation:
Department of Computer Science, University College London, Gower Street, London WC1E 6EA, United Kingdom
David Perez-Garcia
Affiliation:
Department of Applied Mathematics and Mathematical Analysis, Facultad de CC Matemáticas, Universidad Complutense de Madrid, Plaza de Ciencias 3, 28040 Madrid, SpainICMAT, C/Nicolás Cabrera, Campus de Cantoblanco, 28049 Madrid, Spain; E-mail: dperezga@ucm.es
Michael M. Wolf
Affiliation:
Department of Mathematics, Technische Universität München, 85748 Garching, GermanyMunich Center for Quantum Science and Technology (MCQST), Germany; E-mail: m.wolf@tum.de

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.

Information

Type
Mathematical Physics
Creative Commons
Creative Common License - CCCreative Common License - BY
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.
Copyright
© The Author(s), 2022. Published by Cambridge University Press
Figure 0

Figure 1Tiles for encoding a Turing machine with half-infinite tape into a completion problem. The tile in the bottom-left corner is fixed and, together with the second tile in the third row, starts the Turing machines running on the blank half-infinite tape. The tiles in the second row are the ‘action tiles’ that are able to change the state of the Turing machine and correspond to a left or right moving head. For each pair $(q,s)$ there is at most one action tile.

Figure 1

Figure 2The preparation and control-$U_\varphi $ stages of the quantum phase estimation circuit for $\varphi $ (cf. Fig. 5.2 in [62]).

Figure 2

Figure 3The inverse QFT stage of the quantum phase estimation circuit (cf. Fig. 5.1 in [62]).

Figure 3

Figure 4Example of a clock oscillation cycle.

Figure 4

Figure 5Cartoon illustration of the role of the different tracks. Track 1 acts as the clock’s “second hand”, repeating one full cycle for every clock increment. Track 3 acts as the “minute hand”, getting incremented by one for every cycle of Track 1. Track 2 stores the counter Turing Machine head and internal state machinery needed to implement this incrementing. These clock tracks drive the Quantum Turing Machine in Tracks 4 and 5, Track 4 storing the QTM head and internal state, Track 5 storing the QTM tape qudits. If the QTM ever halts or runs out of space on Track 5, it switches to writing garbage on the “time-wasting” trap stored on Track 6 to use up the remaining time on the clock.

Figure 5

Table 1Single-site illegal states enforcing that end-marker states must appear across all tracks simultaneously.

Figure 6

Table 2All transition rules for Tracks 1 to 3.

Figure 7

Table 3All illegal pairs and regular expressions enforced by illegal pairs for Tracks 1 to 3.

Figure 8

Table 4All transition rules for Tracks 4, 5 and 6.

Figure 9

Table 5Initialisation illegal pairs for Tracks 4–6.

Figure 10

Figure 6The five basic tiles of Robinson’s tiling (top), and a simplified schematic representation of these used in Figure 9 (bottom).

Figure 11

Figure 7(a) Facing crosses, and (b) back-to-back crosses in Robinson’s tiling.

Figure 12

Figure 8Parity markings to force the position of the crosses.

Figure 13

Figure 9A possible Robinson tiling of the plane.

Figure 14

Figure 10Left: A $3\times 3$ square of the Robinson tiling, with the choice of a right/up facing cross in the middle tile. Right: A $7\times 7$ square of the Robinson tiling, with the choice of a right/down facing cross in the middle tile. (To avoid confusion, we have only drawn the coloured lines of the tiles in this second figure.)

Figure 15

Figure 11Left: an example of a fault line, in which the patterns are shifted. Right: a schematic way, with the fault line in grey, to complete the figure on the right to a $7\times 7$ square (compare with the example of the $7\times 7$ square in Figure 10).

Figure 16

Figure 12The basic tiles of the modified Robinson tiling.

Figure 17

Figure 13Starting with the Hamiltonian $H_u$ constructed in Proposition 53, we consider two additional Hamiltonians, $H_d$ and $H_0$, with dense and trivial spectrum respectively. These are combined into a final Hamiltonian H such that the different spectra get combined as indicated by the arrows in the figure. This results in an overall Hamiltonian H with gapped or gapless behaviour, as shown in the bottom figure, depending on whether the TM encoded in Hamiltonian $H_u$ halts or not.

Figure 18

Figure 14Boundary tiles for periodic boundary condition construction.