Undecidability of the Spectral Gap

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.

1 Introduction

1.1 Definitions and notation

Let us start by defining the setup we will be considering, which is the standard framework in mathematical physics for describing (finite) spin lattice models. We denote by $\Lambda (L):=\{1,\ldots ,L\}^2$ the set of vertices (referred to as sites) of a square lattice of side $L\in \mathbb {N}$ , with $L\ge 2$ . ${{\mathcal {E}}}\subset \Lambda (L)\times \Lambda (L)$ will denote the set of directed edges of the square lattice, oriented so that $(i,j)\in \mathcal{E}$ implies that j lies north or east of i. We will consider both periodic and open boundary conditions. In the first case, the outer rows and columns are also connected along the same direction, so that $\Lambda (L)$ becomes a square lattice on a torus. In the second case, these connections are not present.

We associate to each site $i\in \Lambda (L)$ a Hilbert space , and to any subset $S\subseteq \Lambda (L)$ the tensor product $\bigotimes _{i\in S} {\mathcal {H}}^{(i)}$ . The interactions between neighbouring pairs $(i,j)\in \mathcal{E}$ are given by Hermitian operators $h^{(i,j)}\in {\mathcal {B}}({\mathcal {H}}^{(i)}\otimes {\mathcal {H}}^{(j)})$ . In addition, we may assign an on-site interaction given by a Hermitian matrix $h_1^{(k)}\in {\mathcal {B}}({\mathcal {H}}^{(k)})$ to each site $k\in \Lambda (L)$ .

We will restrict in this paper to models that are built up from such nearest-neighbour and possibly on-site terms in a translationally invariant way. That is, when identifying the isomorphic Hilbert spaces on which they act, $h_1^{(k)}=h_1^{(l)}$ for all $k,l\in \Lambda (L)$ , and $h^{(i',j')}=h^{(i,j)}$ whenever there is a $v\in \mathbb {Z}^2$ such that $(i',j')=(i+v,j+v)$ . The total Hamiltonian for the system is then defined as

(1.1) $$ \begin{align} H^{\Lambda(L)}:=\sum_{(i,j)\in\mathcal{E}} h^{(i,j)}+\sum_{k\in\Lambda(L)} h_1^{(k)}. \end{align} $$

It is fully described for any system size L by three Hermitian matrices: a $d\times d$ matrix $h_1$ and two $d^2\times d^2$ matrices $h_{\text {row}}$ and $h_{\text {col}}$ , which define the interactions between neighbouring sites within any row and column respectively. Hence, it may alternatively be written as

(1.2) $$ \begin{align} H^{\Lambda(L)} = \sum_{\text{rows}}\sum_{c} h_{\text{row}}^{(c,c+1)} + \sum_{\text{columns}}\sum_{r} h_{\text{col}}^{(r,r+1)} + \sum_{i\in\Lambda(L)} h_1^{(i)}. \end{align} $$

$\max \{\|h_{\text {row}}\|, \|h_{\text {col}}\|, \|h_1\|\}$ is called the local interaction strength of the Hamiltonian and can be normalised to be $1$ .

The set of eigenvalues, or energy levels, of the Hamiltonian $H^{\Lambda (L)}$ will be denoted by . When the Hamiltonian is clear from context, we will sometimes omit it and just write $\{\lambda _0,\lambda _1,\dots \}$ . They are always assumed to be listed in non-decreasing order $\lambda _0\leq \lambda _1\leq \ldots $ . The smallest eigenvalue $\lambda _0(H^{\Lambda (L)})$ is called the ground state energy and the corresponding eigenvectors ground states. The ground state energy density is defined as

(1.3) $$ \begin{align} E_{\rho}:=\lim_{L\rightarrow \infty} E_\rho(L), \quad \text{where } \; E_\rho(L):=\frac{\lambda_0(H^{\Lambda(L)})}{L^2}. \end{align} $$

It is not difficult to show [22] that this limit is well defined.

$H^{\Lambda (L)}$ is called frustration-free if its ground state energy is zero while all $h^{(i,j)},h_1^{(k)}$ are positive semi-definite. That is, a ground state of a frustration-free Hamiltonian minimises the energy of each interaction term individually. $H^{\Lambda (L)}$ is called classical if its defining interactions $h^{(i,j)},h_1^{(k)}$ are diagonal in a given product basis (e.g. the canonical one).

We can define now the main quantity under study: the spectral gap

(1.4) $$ \begin{align} \Delta(H^{\Lambda(L)}):= \lambda_1(H^{\Lambda(L)})-\lambda_0(H^{\Lambda(L)}). \end{align} $$

In this paper we are considering the behaviour of $\Delta (H^{\Lambda (L)})$ in the thermodynamic limit, that is, when $L\rightarrow \infty $ . For that, we introduce the following definitions:

Definition 1 (Gapped)

We say that a family $\{H^{\Lambda (L)}\}$ of Hamiltonians, as described above, characterises a gapped system if there is a constant $\gamma>0$ and a system size $L_0$ such that for all $L>L_0$ , $\lambda _0(H^{\Lambda (L)})$ is non-degenerate and $\Delta (H^{\Lambda (L)})\geq \gamma $ . In this case, we say that the spectral gap is at least $\gamma $ .

Definition 2 (Gapless)

We say that a family $\{H^{\Lambda (L)}\}$ of Hamiltonians, as described above, characterises a gapless system if there is a constant $c>0$ such that for all $\varepsilon>0$ there is an $L_0\in \mathbb {N}$ so that for all $L>L_0$ any point in $[\lambda _0(H^{\Lambda (L)}),\lambda _0(H^{\Lambda (L)})+c]$ is within distance $\varepsilon $ from .

Note that gapped is not defined as the negation of gapless; there are systems that fall into neither class. The reason for choosing such strong definitions is to deliberately avoid ambiguous cases (such as systems with degenerate ground states). Our constructions will allow us to use these strong definitions, because we are able to guarantee that each instance falls into one of the two classes. Indeed, we could further strengthen the definition of gapless without changing our undecidability results or their proofs, below, by demanding that $c=c(L)$ grows with L so that $\lim _{L\rightarrow \infty }c(L)=\infty $ .

The ideas and techniques for the proof will mainly come from quantum information theory. We therefore use notation standard to that field, such as Dirac’s notation for linear algebra operations. A summary of all the relevant standard notation can be found, for example, in Chapter 2 of the classic book of Nielsen and Chuang [62].

1.2 Main results

For each natural number n, we define $\varphi =\varphi (n)$ to be the rational number whose binary fraction expansion consists of the digits of n in reverse order after the decimal point. We also fix throughout a specific Universal Turing Machine, denoted by UTM.

Theorem 3 (Main theorem)

For any given universal Turing Machine UTM, we can construct explicitly a dimension d, $d^2\times d^2$ matrices $A,A',B,C,D,D'$ a $d\times d$ diagonal projector $\Pi $ and a rational number $\beta $ which can be as small as desired, with the following properties:

1. (i) A is diagonal with entries in .

2. (ii) $A'$ is Hermitian with entries in ,

3. (iii) $B,C$ have integer entries,

4. (iv) D is diagonal with entries in ,

5. (v) $D'$ is hermitian with entries in .

For each natural number n, define:

$$ \begin{align*} \begin{aligned} h_1(n)&=\alpha(n)\Pi, \qquad \\ h_{\text{col}}(n)&=D +\beta D',\qquad\quad \text{independent of } n \\ h_{\text{row}}(n)&=A + \beta\left(A'+e^{i\pi\varphi} B + e^{-i\pi\varphi} B^{\dagger} + e^{i\pi2^{-{\lvert{\varphi}\rvert}}} C + e^{-i\pi2^{-{\lvert{\varphi}\rvert}}} C^{\dagger}\right),\end{aligned} \end{align*} $$

where $\alpha (n)\le \beta $ is an algebraic number computable from n. Then:

1. (i) The local interaction strength is bounded by 1, i.e. $\max ({\lVert {h_1(n)}\rVert }, {\lVert {h_{\text {row}}(n)}\rVert }, {\lVert {h_{\text {col}}(n)}\rVert }) \leq 1$ .

2. (ii) If UTM halts on input n, then the associated family of Hamiltonians $\{H^{\Lambda (L)}(n)\}$ is gapped in the strong sense of Definition 1 and, moreover, the gap $\gamma \ge 1$ .

3. (iii) If UTM does not halt on input n, then the associated family of Hamiltonians $\{H^{\Lambda (L)}(n)\}$ is gapless in the strong sense of Definition 2.

Some comments are in order:

• • Using the classic result of Turing [72] that the Halting Problem for UTM on input n is undecidable, we can conclude that the spectral gap problem is also undecidable.

• • The interaction terms in the Hamiltonians given in the Theorem are $\beta $ -perturbations of the classical Hamiltonian given by $h_{\text {row}}=A,h_{\text {col}}=D$ . Since $\beta $ can be taken as small as desired, all interactions appearing in the Theorem are arbitrarily small quantum perturbations of a classical system.

• • The only dependency on n in the interactions appears in some prefactors to a set of fixed interactions.

• • In the gapped case, the size of the gap is larger than or equal to the local interaction strength, hence is as large as possible.

• • It is straightforward (if tedious) to extract an explicit value for d in Theorem 3 and Corollary 4 from the construction described in this paper.

• • By exploiting the well known connection between (algorithmic) undecidability and (axiomatic) independence (see e.g. [68]) one immediately obtains the following corollary:

Corollary 4 (Axiomatic independence of the spectral gap)

Let $d\in \mathbb {N}$ be a sufficiently large constant. For any consistent formal system with a recursive set of axioms, there exists a translationally invariant nearest-neighbour Hamiltonian on a 2D lattice with local dimension d and algebraic entries for which neither the presence nor the absence of a spectral gap is provable from the axioms.

Moreover, as a key intermediate step in the proof of Theorem 3, we will prove that the ground state energy density problem is also undecidable, a result clearly interesting on its own.

Theorem 5 (Undecidability of g.s. energy density)

Let $d\in \mathbb {N}$ be sufficiently large but fixed. We can explicitly construct a one-parameter family of translationally invariant nearest-neighbour Hamiltonians on a 2D square lattice with open boundary conditions, local Hilbert space dimension d, algebraic matrix entries, and local interaction strengths bounded by 1 for which determining whether $E_\rho =0$ or $E_\rho>0$ is an undecidable problem.

A short version of this paper – including a statement of the main result, discussion of its implications, an outline of the main ideas behind the proof, together with a sketch of the argument – was published recently in Nature [22]. We encourage the reader to consult it in order to gain some high-level intuition about the full, rigorous proof given in this work.

1.3 Relation to physics

As already discussed in [22], this result has a number of implications for condensed matter and mathematical physics, that we briefly recall here.

Quantum spin lattice models are ubiquitous in mathematical physics. They play a central role in condensed matter physics, in quantum computation and even in high energy physics, where one route to formalising the continuum is to consider quantum many body systems on a lattice and later sending the lattice spacing to zero. In all these contexts, one often starts from a description of the microscopic interactions that govern the system. The question is then how to infer the relevant observable macroscopic properties that emerge as the lattice size (number of particles) tends to infinity.

The spectral gap is amongst the most important properties of a quantum many-body Hamiltonian. It is intimately related to the physics of a quantum many-body system. Quantum phase transitions can only occur at critical points where the gap vanishes. The intuitive reason is that the spectral gap “protects” the ground state properties of the system against small perturbations, since an energy of the order of the gap must be pumped into the system to transition to a different state. Formalising this intuition is a major open question. Recently Bravyi, Hastings and Michalakis [19] and Michalakis and Pytel [57] proved this for the particular case of frustration-free systems satisfying certain additional conditions, by proving that the spectral gap of these systems is stable under arbitrary local perturbations throughout the system.

The low-temperature behaviour of a system is also governed by the spectral gap: gapped systems exhibit “non-critical” behaviour, with low-energy excitations that behave as massive particles [35], preventing long-range correlations [42, 61]; gapless systems exhibit “critical” behaviour, with low-energy excitations that behave as massless particles, allowing long-range correlations. This implies that ground states of gapped systems are somehow less complex. That intuition has been formalised in the area law conjecture [26], which has been proven for 1D spin systems [39], and in 2D if certain additional hypothesis on the spectrum are satisfied [40]. This in turn translates into better algorithms for computing properties of such systems [65]. A paradigmatic example of this line of research is the recent proof [51, 7], based on an improved version of the 1D area law theorem [6], that the ground state energy density problem for gapped quantum spin systems in 1D is in the complexity class P (i.e. the run-time of the algorithm scales polynomially in the system size).

Because of its central importance to many-body quantum systems, many seminal results in mathematical physics concern the spectral gap of specific systems. Examples include the Lieb-Schultz-Mattis theorem showing that the Heisenberg chain for half-integer spins is gapless [53], extended to higher dimensional bipartite lattices by Hastings [38], and the proof of a spectral gap for the 1D AKLT model [1]. More recently, shortly after this work first appeared on preprint servers, Bravyi and Gosset gave a complete characterisation of the spectral gap for the simplest non-trivial case of 1D chains of spin- $\tfrac {1}{2}$ particles (qubits) with frustration-free, nearest-neighbour interactions [18]. (The frustrated case remains open.)

The same is true of some of the most important open questions in the field. For instance, the Haldane conjecture [36], first formulated in 1983, states that the integer-spin antiferromagnetic Heisenberg model in 1D has a non-vanishing spectral gap. Despite strong supporting evidence from numerical simulations, a proof remains elusive. The analogous question in 2D for non-bipartite lattices can be traced back to the work of Anderson in 1973 [5], where he suggested the existence of new types of materials, nowadays called topological quantum spin liquids. The existence of minerals in nature, such as herbertsmithite, whose interactions can be well approximated by the spin- $\frac {1}{2}$ antiferromagnetic Heisenberg model on the Kagome lattice – hence are compelling candidates for systems with a topological quantum spin liquid phase [37] – brought the problem of its spectral gap to the forefront of physics. The existence of a spectral gap in these systems is an active area of research, with techniques reducing the spectral gap problem to finite-volume criteria very recently being applied successfully (partially numerically) to certain cases such as the honeycomb lattice [52, 67], whilst other cases remain disputed even at the level of numerical evidence (see e.g. [76, 44]).

Undecidability of the spectral gap has a number of immediate corollaries relevant to physics. It implies that one can write down models whose phase diagrams are so complex they are in fact uncomputable. It implies the standard approach of trying to gain insight into physics models by solving numerically for larger and larger lattice sizes necessarily fails for some systems; the system can display all the features of a gapless model, with the gap of the finite system decreasing monotonically with increasing size. Then, at some threshold size, it may suddenly switch to having a large gap. (In Section 2 we also construct models exhibiting the opposite transition, from gapped to gapless.) Not only can the threshold size be arbitrarily large; the threshold size itself is an uncomputable number. In a recent paper [11], we constructed very simple models with small local dimensions which exhibit this type of “size-driven phase transition” (without, however, the undecidability properties proven here). Our findings also imply that a result showing robustness of the spectral gap under perturbations, as for the case of frustration-free Hamiltonians [57] and for free-fermion systems [24, 41], cannot hold for general gapped systems.

Phase diagrams with infinitely many phases are known in quantum systems in connection with the quantum Hall effect, where fractal diagrams like the Hofstadter butterfly can be obtained [66, 43]. Since membership in many fractal sets is not decidable (when formulated in the framework of real computation; see [17]), it would be interesting to see whether quantum Hall systems could provide a real-world manifestation of our findings.

Conjectures about the spectral gap, such as the Haldane conjecture, the 2D AKLT conjecture, or the Yang-Mills mass gap conjecture in quantum field theory, implicitly assume that these questions can be answered one way or the other. Our results prove that the answer to the general spectral gap question is not determined by the axioms of mathematics. Whilst our results are still a long way from proving that any of these specific conjectures are axiomatically undecidable, they at least open the door to the possibility that these – or similar – questions about physical models may be provably unanswerable.

The idea that some of the most difficult open problems in physics could be mathematically proven to be impossible to solve is not new. Indeed, proving the impossibility of obtaining exact formulae for certain physical quantities in natural physical models is highlighted as one of the main open problems in mathematical physics in the list published by the International Association of Mathematical Physics in the late 90’s, edited by Aizenman [3]. Apart from the pioneering work of Komar in this direction in 1964 [49], stating undecidable properties in Quantum Field Theories, and the influential paper of Anderson entitled “More is different” [4] in 1972, most of the initial connections between physical problems and undecidability arose in the 80s and 90s. In 1981, [69] studied non-computable solutions to the wave equation. One year later, [31] found undecidable questions in models of hard frictionless balls. In 1984, Wolfram wrote the paper “Undecidability and Intractability in Theoretical Physics” where, motivated by the emergent complexity of very simple cellular automata, he conjectured that many natural problems in physics, and in particular in classical statistical physics, should be undecidable. Many results in this direction – using cellular automata to prove undecidability results in physical problems – have been shown since then (e.g [25] or [64]). The work of Gu, Weedbrook, Perales and Nielsen [34] in 2009 found undecidable properties in the 2D classical Ising model. Besides cellular automata, another natural connection between undecidability and physics, that we will exploit in this paper, came from tiling problems, shown to be undecidable by the works of Wang and Berger in the 60s [74, 15]. This idea has been exploited for instance in 1990 by Kanter [45], finding undecidable properties in anisotropic 1D Potts Hamiltonians. That same year, in a completely different direction, Moore wrote one of the most influential papers on undecidability in physics [59], proving undecidability of the long-term behaviour of a particle-in-a-box problem. (See also [14] for a nice commentary on that paper.)

In recent years, mainly motivated by quantum information theory and the link it established between physics and computer science, there has been a revival of interest in undecidability in quantum physics. Results in this direction have appeared in several contexts, such as measurement and control [27, 75], tensor networks [60, 48, 21], measurement-based quantum computation [73], channel capacities [28], or Bell inequalities [12, 71].

A precursor of those results, due to Lloyd, appeared already in 1993 [54, 55] in the early days of quantum information theory. There, it is argued that quantum computing implies certain spectral properties of quantum mechanical operators are undecidable. More precisely, the unitary evolution U associated to the evolution of a computer (classical or quantum) capable of universal computation has invariant subspaces with discrete spectrum (roots of unity) and other invariant subspaces with continuous spectrum (the whole unit sphere), corresponding respectively to computations that halt and do not halt. Then, since the halting problem is undecidable, Lloyd concludes that given a quantum state associated with a program in the infinite dimensional space in which U is defined, it is undecidable to know whether it has overlap with an invariant subspace having discrete spectrum or, conversely, it is supported on an invariant subspace in which the spectrum is the full unit circle. See [56, 23] for a recent discussion between the relation between Lloyd’s result and the result of this paper.

In subsequent follow-up work, we have extended the undecidability results described here to 1D systems [8] and to uncomputability of phase diagrams [9], and have used insights from our undecidability results to construct simple, explicit examples of the new type of “size-driven” phase transition implied by undecidability of the spectral gap [11].

We refer to a forthcoming review paper in collaboration with Gu and Perales [20] for an extensive analysis and discussion of all results mentioned above, and many more, related to undecidability in physics.

1.4 Brief overview of the proof

An extended overview and discussion of the ideas behind our proof can be found in the Supplementary Material of [22]. We will simply sketch here the four main steps of the proof, whose rigorous statements and proofs are given, respectively, in Sections 3 to 6.

Step 1: write n on the tape.

In order to feed an arbitrary input to the UTM, and at the same time keep a uniform upper bound on the local dimension of the Hilbert space of each site in the final Hamiltonian, we need to construct a Quantum Turing Machine (QTM) with a fixed number of internal states such that, when fed with an input given by any sequence of 1’s larger than the size of n, writes n deterministically on the tape and halts. We need also to keep strict control on the time and space required for this computation. The precise result we prove along these lines is given in Theorem 10, and Section 3 is devoted to proving it. The idea is to construct explicitly the QTM associated to the quantum phase estimation algorithm. To do this, we rely heavily on results and ideas from [16].

Step 2: construct, for each , a 1D Hamiltonian whose ground state energy on a finite chain depends on the behaviour of the UTM on input n.

For this, we heavily rely on the remarkable paper of Gottesman and Irani [32] (see also [10]), which can be seen as a milestone in a long history of papers [47, 46, 63, 2], dating back to Feynman [30], relating the ground state energy of a Hamiltonian with the time-evolution of a quantum computation. In order to achieve the desired properties of our construction, we have to modify the original construction of Gottesman and Irani, but most of the essential ideas of this step appear already in [32].

After these two steps, we have for each a 1D translationally invariant Hamiltonian whose ground state energy for a chain of size L and open boundary conditions is $0$ if the UTM does not halt on n in space less than $O(L)$ and time less than $O(c^L)$ (for any desired constant c). Otherwise, it has energy larger than $c^{-L}$ . So there the difference in ground state energy depending on the halting behaviour of the UTM on n vanishes exponentially fast with chain length, and is zero in the thermodynamic limit. Theorem 32 states the precise result we obtain, and Section 4 is devoted to its proof.

Step 3: amplify the ground state energy difference.

For this, we turn to 2D lattices, and exploit the properties of an aperiodic tiling of the 2D plane due to Robinson. The idea is to construct a Hamiltonian whose ground state mimics the tiling pattern of Robinson’s tiling shown in Figure 9 and, at the same time, places the ground state of the 1D Hamiltonian constructed in Step 2 on top of each of the 1D borders appearing in this pattern. Using the fact that there is a constant density of squares of size $4^r$ for all , and making a shift in energies, we manage to show for the resulting Hamiltonian that, if the UTM halts on n, the ground state energy diverges to $+\infty $ , whereas in the non-halting case it diverges to $-\infty $ . From there, we conclude undecidability of the ground state energy density. Section 5 takes care of proving all the new results we require for Robinson’s tiling. The rest of the proof, together with the final step, appears in Section 6.

Step 4: from ground state energy difference to spectral gap.

The final step combines the Hamiltonian $H_u$ constructed in Step 3 with two others: a trivial Hamiltonian having ground state energy $0$ and a constant spectral gap, and a critical Hamiltonian $H_d$ having ground state energy $0$ and a spectrum that becomes dense in $[0,\infty )$ as the system size goes to infinity. We couple these Hamiltonians in such a way that the spectrum of the resulting Hamiltonian on $\Lambda (L)$ is

with $S_L\ge \min \left \{1, 1+\lambda _0(H_u^{\Lambda (L)})\right \}$ . This, together with the spectral properties of $H_u$ shown in Step 3, completes the proof.

2 Unconstrained local Hilbert space dimension

Before starting in Section 3 on the proof of the main theorem, in this section we will describe two approaches that exploit known undecidability results for tiling and completion problems. Based on these, we can derive simpler but weaker undecidability results for the spectral gap and for other low energy properties of translationally invariant, nearest-neighbour Hamiltonians on a 2D square lattice, defined by their local interactions $\{(h_{\text {row}}(n),h_{\text {col}}(n))\}_{n\in \mathbb {N}}$ . In contrast to the main theorem of this paper, however, the families of Hamiltonians that we construct here have local Hilbert space dimension $d_n$ that differs for different elements n of the family, with no upper bound on $\{d_n\}_{n\in \mathbb {N}}$ .

2.1 Undecidability of the spectral gap via tiling

As in the more sophisticated constructions that will appear later, the idea is to reduce an undecidable ground state energy problem to the spectral gap problem. If we do not constrain the local Hilbert space dimension, then this reduction can be chosen such that it directly exploits the undecidability of a tiling problem. To this end, we need two ingredients:

2.1.1 Ingredient 1: a tiling Hamiltonian

We start by recalling the notion of Wang tilings and tiling problems. A unit square whose edges are coloured with colours chosen from a finite set is called a Wang tile. A finite set $\mathcal {K}$ of Wang tiles is said to tile the plane $\mathbb {Z}^2$ if there is an assignment $\mathbb {Z}^2\rightarrow \mathcal {K}$ such that abutting edges of adjacent tiles have the same colour. (Rotations or reflections of the tiles are not allowed here.) It is a classic result of Berger [15] that, given any set of tiles as input, determining whether or not this set can tile the plane is undecidable.

There is an easy way to rewrite any tiling problem as a ground state energy problem for a classical Hamiltonian. If $\mathcal {K}=\{1,\ldots ,K\}$ we assign a Hilbert space to each site i of a square lattice, and define the local interactions via

(2.1)

where the set of constraints $C^{(i,j)}\subseteq \mathcal {K}\times \mathcal {K}$ includes all pairs of tiles $(m,n)$ which are incompatible when placed on adjacent sites i and j. The overall Hamiltonian on the lattice $\Lambda (L)$ is then simply

(2.2) $$ \begin{align} H_c^{\Lambda(L)} := \sum_{(i,j)\in{\mathcal{E}}} h_c^{(i,j)}. \end{align} $$

By construction, we have $h_c^{(i,j)}\geq 0$ , $H_c^{\Lambda (L)}$ is translationally invariant and its spectrum is contained in $\mathbb {N}_0$ . If there exists a tiling of the plane, then for open boundary conditions . Similarly, in the case of periodic boundary conditions, the existence of a periodic tiling implies that holds for an unbounded sequence of L’s. On the other hand, if there is no tiling, then there is an $L_0$ such that

(2.3)

This is due to Wang’s extension theorem (see e.g. [33]).

2.1.2 Ingredient 2: a gapless frustration-free Hamiltonian

As a second ingredient we will use that there are frustration-free two-body Hamiltonians

(2.4) $$ \begin{align} H_q^{\Lambda(L)}:=\sum_{(i,j)\in{\mathcal{E}}} h_q^{(i,j)}, \end{align} $$

such that for $L\rightarrow \infty $ we get in the sense that the spectrum of the finite system approaches a dense subset of [29]. We will denote the corresponding single site Hilbert space by and we can in fact choose $D=2$ for instance by assigning to each row of the lattice the XY-model with transversal field taken at a gapless point with product ground state. Note that in this case the entries of the matrices $h_q^{(i,j)}$ are rational.

2.1.3 Reducing tiling to spectral gap

In order to fruitfully merge the ingredients, we assign a Hilbert space to each site $i\in \Lambda (L)$ . A corresponding orthonormal set of basis vectors will be denoted by and , respectively. The Hamiltonian is then defined in terms of the two-body interactions

(2.5)

(2.6)

(2.7)

Here and denote the identity operators on ${\mathcal {H}}_c,{\mathcal {H}}_q$ and ${\mathcal {H}}_c{\otimes }{\mathcal {H}}_q$ , respectively. As before, we define the Hamiltonian on the square lattice $\Lambda (L)$ as

(2.8) $$ \begin{align} H^{\Lambda(L)}:=\sum_{(i,j)\in{\mathcal{E}}}H^{(i,j)}. \end{align} $$

Theorem 6 (Reducing tiling to spectral gap)

Consider any set $\mathcal {K}$ of Wang tiles, and the corresponding family of two-body Hamiltonians $\{H^{\Lambda (L)}\}_{L}$ on square lattices $\Lambda (L)$ either with open or with periodic boundary conditions.

1. (i) The family of Hamiltonians is frustration-free.

2. (ii) If $\mathcal {K}$ tiles the plane $\mathbb {Z}^2$ , then in the case of open boundary conditions, we have that for $L\rightarrow \infty $ , i.e., there is no gap and the excitation spectrum becomes dense in . Similarly, if $\mathcal {K}$ tiles any torus, then in the case of periodic boundary conditions for a subsequence $L_i\rightarrow \infty $ .

3. (iii) If $\mathcal {K}$ does not tile the plane, then there is an $L_0$ such that for all $L>L_0 \ H^{\Lambda (L)}$ has a unique ground state and a spectral gap of size at least one, i.e.

   (2.9)

   

Proof. Frustration-freeness is evident since $H^{(i,j)}\geq 0$ and . In order to arrive at the other assertions, we decompose the Hamiltonian as $ H^{\Lambda (L)}=:H_0+H_c+H_q$ , where the three terms on the right are defined by taking the sum over edges separately for the expressions in (2.5), (2.6) and (2.7), respectively. Let us now assign a signature $\sigma \in \{0,\ldots ,K\}^{L^2}$ to every state of our computational product basis, in the following way: is assigned the signature $\sigma _i=0$ , and is assigned the signature $\sigma _i=k$ irrespective of $\alpha $ . By collecting computational basis states with the same signature we can then decompose the Hilbert space as

(2.10) $$ \begin{align} \bigotimes_{i\in\Lambda}{\mathcal{H}}^{(i)}\simeq\bigoplus_{\sigma}{\mathcal{H}}_\sigma. \end{align} $$

The Hamiltonian is block-diagonal w.r.t. this decomposition, i.e. it can be written as

(2.11)

In order to identify the spectra coming from different signatures we will distinguish three cases:

1. (i) $\sigma =(0,\ldots ,0)$ : this yields an eigenvalue $0$ as already mentioned.

2. (ii) $\sigma \neq (0,\ldots ,0)$ but $\sigma _i=0$ for some i: for any unit vector with such a signature we have . We will denote the part of the spectrum which corresponds to these signatures by $S\subset \mathbb {R}$ . The only property we will use is that $S\geq 1$ .

3. (iii) $\sigma \in \{1,\ldots ,K\}^{L^2}$ : In the subspace spanned by all states whose signature does not contain $0$ we have that $H_0=0$ and . Consequently, the spectrum stemming from this subspace equals .

Putting things together, we obtain

(2.12)

The equivalence between the impossibility of tiling with $\mathcal {K}$ and the existence of a spectral gap of size at least 1 now follows immediately from the properties of the ingredients $h_c$ and $h_q$ . Uniqueness of the ground state in cases where no tiling exists follows from the above argument when considering the spectra as multisets rather than sets.

From the undecidability of the tiling problem we now obtain the following corollary. Recall from Section 1.1 that a pair of Hermitian matrices $(h_{\text {row}},h_{\text {col}})$ defines a Hamiltonian $H^{\Lambda (L)}$ for each square $\Lambda (L)$ via (1.2), where we are now choosing open boundary conditions. ¹

Corollary 7 (Undecidability of the spectral gap for unconstrained dimension)

Let $\epsilon>0$ . There is no algorithm that, on input $(h_{\text {row}},h_{\text {col}})$ with rational entries and operator norm smaller than $1+\epsilon $ , decides whether the associated family of Hamiltonians $\{H^{\Lambda (L)}\}$ describe a gapped or a gapless system (according to the definitions given in Section 1.1). This holds even under the promise that one of these is true, that $H^{\Lambda (L)}$ is frustration free for all $\Lambda $ , and that in the gapped case the spectral gap is at least 1.

Here, the norm bound follows from the observation that where $h_q^{(i,j)}$ can be rescaled to arbitrarily small norm.

For the case of periodic boundary conditions we obtain the same statement if we replace our strong definition of ‘gapless’ by the weaker requirement that $\exists c>0\; \forall \epsilon >0 \; \forall L_0 \; \exists L>L_0$ so that every point in $[\lambda _0(H^{\Lambda (L)}),\lambda _0(H^{\Lambda (L)})+c]$ is within distance $\epsilon $ from . The reason for this is, that if the period of the torus does not match the required one, then a gap can be generated that, however, disappears again if we enlarge the size of the system.

We emphasise that, so far, there is no constraint on the local Hilbert space dimension. Since every instance in the above construction has a finite local Hilbert space we can, however, at least conclude axiomatic undecidability for finite local Hilbert spaces. That is, for any given consistent formal system with a recursive set of axioms, one can construct a specific instance of a Hamiltonian with properties as in the corollary and finite-dimensional local Hilbert space, such that neither the presence nor the absence of a spectral gap can be proven from the axioms. ² . However, the local dimension, whilst finite, depends on the choice of axiomatic system and there is no upper-bound on the values it can take. The main aim of this paper is to prove the much stronger Theorem 3, which shows that the spectral gap problem remains undecidable even for a fixed value of the local Hilbert space dimension. This in turn implies that for any consistent, recursive formal system, axiomatic independence holds for Hamiltonians with this fixed local dimension; the local dimension is now independent of the choice of axioms.

In the above construction, gapped cases are related to the impossibility of tiling. Since the latter always admits a proof, the axiomatically undecidable cases coming from this construction have to be gapless. The following section will provide a construction where this asymmetry is reversed.

2.2 Undecidability of low energy properties

2.2.1 Reducing tile completion to a ground state energy problem

We now modify the above construction in order to show that not only the spectral gap but many other low energy properties are undecidable as well. The idea is to invert the relation between gap and existence of tiling. In the previous construction, the existence of a gap was associated with the impossibility of a tiling. Now we want to associate it with the existence of a tiling. A drawback is that we loose the frustration-free property. On the other hand, we do not have to rely on the undecidability of tiling (which is a rather non-trivial result [15, 70]), but can exploit the simpler undecidability of the completion problem, already proven by Wang [74]. In the tiling completion problem, one fixes a tile at the left-bottom corner and asks whether the first quadrant can be tiled.

Undecidability of the completion problem is relatively simple by reduction from the Halting Problem for Turing Machines (TM), and explained in full detail in Robinson [70, Section 4]. There are many different, computationally equivalent definitions of Turing Machines. (The Halting Problem is undecidable for any of these variants.) For the completion problem, the most convenient is to take a Turing Machine to be specified by a finite number of states $Q=\{q_0, q_1,\ldots \}$ with $q_0$ the initial state, a finite alphabet of tape symbols $S=\{s_0,s_1,\ldots \}$ with $s_0$ the blank symbol, together with a finite set of transition rules specified by quintuples of the form

$$ \begin{align*} (q,s,s',D,q')\in Q\times S\times S\times \{\text{left, right}\}\times Q. \end{align*} $$

The TM has a half-infinite tape of cells indexed by , and a single read/write tape head that moves along the tape. The machine starts in state $q_0$ with the head in tape cell 0. If the TM is currently in state q and reads the symbol s from the current tape cell, then it writes $s'$ into the current tape cell, transitions to state $q'$ , and moves in the direction D. For each $q,s$ , there must be at most one valid quintuplet. If there is none, then the machine halts. ³

Following Robinson [70], we use the Wang tiles shown in Figure 1. For clarity, edges here are marked with labelled arrows rather than colours, and adjacent edges match if arrow heads abut arrow tails with the same label; clearly these tile markings can be identified with different colours to recover a set of standard Wang tiles. We denote the set of tiles by $\mathcal {K}$ , which contains at most $K:=|\mathcal {K}|\leq 2+ (3|Q|+1)|S|$ elements.

Figure 1 Tiles 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.

If the tile that appears in the bottom-left corner in Figure 1, which we denote by , is fixed in the bottom-left corner of an $L\times L$ lattice, then any valid tiling corresponds to the evolution of the Turing Machine on the blank tape up to time L, where time goes up in the vertical direction and each row of tiles corresponds to the total configuration (including the tape) of the Turing machine in two consecutive instants of time (represented by the bottom and upper edges of that row of tiles). Hence,

1. (1) There exists a valid tile completion for all $L\times L$ squares if and only if the Turing Machine, when running on an initially blank tape, does not halt.

2. (2) If such a tiling exists, then it is unique.

Now, the completion problem can be represented as a ground state energy problem in the following straightforward way. Consider a square lattice $\Lambda (L)$ with open boundary conditions and corresponding edge set ${\mathcal {E}}$ .

Assign a weight $w_{(i,j)}(m,n)\in \mathbb {Z}$ to edge $(i,j)\in {\mathcal {E}}$ on which a pair of tiles $(m,n)\subseteq \mathcal {K}\times \mathcal {K}$ is placed. The choice of weights is summarised in the following table. Here stands for any tile different from , the unbracketed numbers define the weights for non-matching adjacent tiles, and the numbers in brackets define the weights for cases where the tiles match (i.e. all abutting labels and arrows match).

(2.13)

Assign a Hilbert space ${\mathcal {H}}_u^{(i)}\simeq \mathbb {C}^{K}$ to each site $i\in \Lambda (L)$ whose computational basis states are labelled by tiles. We define a Hamiltonian $H_u^{\Lambda (L)}:=\sum _{(i,j)\in {\mathcal {E}}}h_u^{(i,j)},$ with

(2.14)

so that positive and negative weights become energy “penalties” or “bonuses” in the Hamiltonian. By construction, the Hamiltonian is diagonal in computational basis, its eigenvectors correspond to tile configurations $\Lambda (L)\rightarrow \mathcal {K}$ and, since all weights are integers, its spectrum lies in $\mathbb {Z}$ . In order to determine the ground state energy note that the tile is the only one that can lead to negative weights. Assume first that a tile is placed on a site different from the bottom-left corner. Then this tile will have at least one neighbour below with an arrow pointing upwards or one neighbour to the left with an arrow pointing to the right. In either case there will be an energy penalty $+4$ so that the weights involving this tile will sum up to at least $2$ . If, however, is placed in the bottom-left corner, then no such energy penalty is picked up and the tile can contribute $-2$ to the energy.

If the tiling is then completed following the evolution of the encoded Turing machine on a blank tape, then no additional penalty will occur on $\Lambda (L)$ if the Turing machine does not halt within L time-steps. Hence $\lambda _0(H_u^{\Lambda (L)})=-2$ , the ground state will be unique, and will be given by a product state. If the Turing machine halts, then the completion problem has no solution beyond some $L_0$ and every configuration with at its bottom-left corner will get an additional penalty of at least $2$ , leading to non-negative energy. Since there is always a configuration that achieves zero energy (e.g. one using only the tile types at the top-left of Figure 1), we obtain:

Lemma 8 (Relating ground state energy to the halting problem)

Consider any Turing machine with state set Q and tape alphabet S running on an initially blank tape such that its head never moves left of the starting cell. There is a family of translationally invariant nearest neighbour Hamiltonians $\{H_u^{\Lambda (L)}\}_L$ (specified above) on the 2D square lattice with open boundary conditions and local Hilbert space dimension at most $|S|(3|Q|+1)+2$ such that

1. (i) If the Turing Machine does not halt within L time-steps, then $\lambda _0(H_u^{\Lambda (L)})=-2$ . In this case the corresponding ground state is a product state, and is the unique eigenstate with negative energy.

2. (ii) If the Turing machine halts, then $\exists L_0$ (given by the halting time) such that $ \forall L>L_0:\lambda _0(H_u^{\Lambda (L)})= 0$ .

Since every Turing machine can be simulated by one with a half-infinite tape, which automatically satisfies the constraint that its head never moves to the left of the origin, the above construction leads to an undecidable ground state energy problem, which we will exploit in the following.

2.2.2 Reduction of the halting problem to arbitrary low energy properties

Consider translationally invariant Hamiltonians on square lattices with open boundary conditions. Let $H_q^{\Lambda (L)}$ describe such a family of Hamiltonians on $L\times L$ lattices. Our aim is to prove the undecidability of essentially any low energy property displayed by this Hamiltonian in the thermodynamic limit that distinguishes it from a gapped system with unique product ground state, e.g. the existence of topological order, or non-vanishing correlation functions. This is implied by the following theorem:

Theorem 9 (Relating low energy properties to the halting problem)

Let TM be a Turing machine with state set Q and alphabet S running on an initially blank tape. Consider the class of translationally invariant Hamiltonians on square lattices with open boundary conditions. Let $H_q^{\Lambda (L)}$ with nearest-neighbour interaction $h_q^{(i,j)}\in {\mathcal {B}}({\mathcal {H}}_q^{(i)}{\otimes }{\mathcal {H}}_q^{(j)})$ , ${\mathcal {H}}_q^{(i)}\simeq \mathbb {C}^q$ , and on-site term $h_{q1}^{(k)}\in {\mathcal {B}}({\mathcal {H}}_q^{(k)})$ describe such a Hamiltonian. Assume that there is a $c\in \mathbb {R}$ such that $\lambda _0\big(H_q^{\Lambda (L)}\big)-cL^2\in [-\frac 12,\frac 12]$ for all lattice sizes L. Then we can construct a family of Hamiltonians $H^{\Lambda (L)}$ with the following properties:

1. (i) $H^{\Lambda (L)}$ is translationally invariant on the square lattice with open boundary conditions and local Hilbert spaces ${\mathcal {H}}^{(i)}\simeq \mathbb {C}^d$ of dimension $d\leq 2(q+1)+|S|(3|Q|+1)$ .

2. (ii) The interactions of $H^{\Lambda (L)}$ are nearest-neighbour (possibly with on-site terms), computable and independent of L.

3. (iii) If the TM does not halt within L time-steps, then $H^{\Lambda (L)}$ has a non-degenerate product ground state and a spectral gap $\Delta (H^{\Lambda (L)})\geq \frac 12$ .

4. (iv) If TM halts, then $\exists L_0$ (determined by the halting time) such that $\forall L>L_0$ the following identity between multisets holds in the interval $[0,\frac 12)$ :

   (2.15)

   
   In this case there exist isometries $V^{(i)}:{\mathcal {H}}_q^{(i)}\rightarrow {\mathcal {H}}^{(i)}$ , $V:=\bigotimes _i V^{(i)}$ such that, for this part of the spectrum, any eigenstate of $H_q^{\Lambda (L)}$ is mapped to the corresponding eigenstate of $H^{\Lambda (L)}$ via .

Some remarks before the proof. Since, on the Turing machine level, (ii) and (iii) cannot be told apart by any effective algorithm, the same has to hold for any property that distinguishes a gapped system with product ground state from the low energy sector of some frustration-free Hamiltonian. With small modifications in the proof, the nearest neighbour assumption for $h_q$ could be replaced by any fixed local interaction geometry. In this case, $H^{\Lambda (L)}$ will of course inherit this interaction geometry.

Proof. W.l.o.g. $c=0$ since we can always compensate for it by adding a multiple of the identity to the on-site part of the Hamiltonian.

We first embed the Hamiltonian given in the Theorem in a larger system, such that its ground state energy is shifted by $-1$ . Define a translationally invariant, nearest-neighbour Hamiltonian on an auxiliary system with local Hilbert space ${\mathcal {H}}_a^{(i)}\simeq \mathbb {C}^2$ , via

(2.16)

Note that this is nothing but $\frac 12 \times $ the Hamiltonian defined by (2.13) (with the number in brackets), where equals and is the blank tile. Hence $\lambda _0(\eta )=-1$ and $\Delta (\eta )=1$ .

Now introduce ${\mathcal {H}}_Q^{(i)}:={\mathcal {H}}_a^{(i)}{\otimes }{\mathcal {H}}_q^{(i)}$ and set

acting on ${\mathcal {H}}_Q^{(i)}{\otimes }{\mathcal {H}}_Q^{(j)}$ . Then

has the property that in the interval $(-\infty ,\lambda _0(H_q^{\Lambda (L)}))$ we have that

holds as an identity between multisets (i.e. including multiplicities) and the corresponding eigenstates are related via a local isometric embedding.

We now combine this with the Hamiltonian from the previous subsection by enlarging the local Hilbert space to ${\mathcal {H}}^{(i)}:={\mathcal {H}}_u^{(i)}\oplus {\mathcal {H}}_Q^{(i)}$ and defining

(2.17)

where $h_Q^{(i,j)}$ and $h_u^{(i,j)}$ act nontrivially on ${\mathcal {H}}^{(i)}_Q{\otimes } {\mathcal {H}}_Q^{(j)}$ and ${\mathcal {H}}_u^{(i)}{\otimes } {\mathcal {H}}_u^{(j)}$ respectively and and denote the projectors onto the respective subspaces. The Hamiltonian on the square $\Lambda (L)$ is now

(2.18)

To analyse the ground state of $H^{\Lambda (L)}$ , notice that all the terms in the Hamiltonian commute with each other. Let $\tilde {H}_q = \sum _{(i,j)\in {\mathcal {E}}} h_q^{(i,j)} + h_{q1}^{(i,j)}$ , , and . We can then decompose $H^{\Lambda (L)}=\tilde {H}_q + \tilde {H}_u + \tilde {H}_\eta $ where the three Hamiltonians commute with each other.

We now assign a signature $\sigma \in \{0,1,2\}^{L^2}$ to every state of our computational product basis, so that is identified with $\sigma _j\in \{0,1\}$ for all of the form and $\sigma _j=2$ for all . By collecting computational basis states with the same signature, we can then decompose the Hilbert space as

(2.19) $$ \begin{align} \bigotimes_{i\in\Lambda}{\mathcal{H}}^{(i)}\simeq\bigoplus_{\sigma}{\mathcal{H}}_\sigma. \end{align} $$

The Hamiltonian is block diagonal w.r.t. this decomposition, i.e. it can be written as

(2.20)

In order to identify the spectra and eigenstates coming from different signatures we will distinguish three cases:

Case 1:

$\sigma =(2,\ldots ,2)$ . Restricted to this sector (i.e. the ${\mathcal {H}}_\sigma $ component of the direct sum), the Hamiltonian acts as $H_u^{\Lambda (L)}=\sum _{(i,j)\in {\mathcal {E}}} h^{(i,j)}_u$ . But according to Lemma 8, if up to time L the TM did not halt, then $H_u^{\Lambda (L)}$ has one negative eigenvalue $-2$ whose associated eigenstate is a product. However, if $L\ge L_0$ where $L_0$ is related to the halting time, then .

Case 2:

$\sigma _j=1$ for all $j\in \Lambda (L)$ , except in the lowest left corner, where $\sigma _j=0$ . In this sector we have the following identity between multisets:

(2.21)

Case 3:

Any other signature $\sigma $ . It is easy to see that the energy given by $\tilde {H}_\eta $ in the sector ${\mathcal {H}}_\sigma $ is exactly the energy given to the configuration $\sigma $ by the tiling Hamiltonian (2.14) with colours $\{0,1,2\}$ and weights given by the following tables from (2.13), hence the energy is $\ge 0$ .

(2.22)

Similarly, one can show that $\tilde {H}_u\ge 0$ . Therefore, in this Case 3, the energy of $H^{\Lambda (L)}$ in the sector ${\mathcal {H}}_\sigma $ is $\ge \lambda _0(H_q^{\Lambda (L)})$ . Theorem 9 now follows straightforwardly.

3 Quantum Phase Estimation Turing Machine

We will see in Section 4 how to encode an arbitrary Quantum Turing Machine (QTM) into a translationally invariant nearest-neighbour Hamiltonian, in such a way that the local Hilbert space dimension is a function only of the alphabet size and number of internal states. This will allow us to encode any specific universal (reversible) Turing Machine in a Hamiltonian with fixed local dimension. However, to prove undecidability by reduction from the Halting Problem, we will need a way to feed any desired input to this universal TM.

To this end, the main result of this section is to construct a family of quantum Turing Machines, all of which have the same alphabet size and number of internal states, but whose transition rules vary. For any given $n\in \mathbb {N}$ , we can choose the transition rules such that the QTM, when started from a sequence of N ones (N any number larger than the number of bits $|n|$ in the binary representation of n) writes out the binary representation of n to its tape and then halts deterministically.

Given n, we recall from Section 1.2 that $\varphi =\varphi (n)$ is defined as the rational number whose binary fraction expansion contains the digits of n in reverse order after the decimal. ⁴

The QTM that we construct will be based on the quantum phase estimation algorithm [78, 62], applied to the single qubit unitary $U_\varphi =\left (\begin {smallmatrix}1&0\\0&e^{i\pi \varphi }\end {smallmatrix}\right )$ , to obtain the phase $\varphi $ . The input N can be any upper bound on the number of binary digits in the output of the quantum phase estimation algorithm, such that $\varphi $ can be represented exactly as a binary fraction, with no approximation error. Note that the transition rules of the QTM are not allowed to depend on N, though they can depend on $\varphi $ (and hence on n).

The important role played by N can be sketched as follows. Firstly, N fixes the number of output qubits to be used in the quantum phase estimation algorithm, such that an exact binary fraction representation of $\varphi $ is possible. But N has a more subtle use in the last step of the quantum phase estimation algorithm, where one needs to implement an inverse quantum Fourier transform (QFT). To implement such a QFT in the standard way on the full set of output qubits, one would require quantum gates implementing phase rotations by angles that depend on N. But this would require N-dependent QTM transition rule amplitudes, which is not allowed. The solution is to use N as a way to locate the least significant bit of $\varphi $ , which will in turn allow the QFT to be implemented using gates that depend only on $\varphi $ . (This is explained in more detail when we give the precise description and analysis of the QTM, later in this section.)

This way of carrying out the QFT on a QTM comes at a cost of exponential run-time, so would not be useful if using the QFT to solve some computational problem. But for our peculiar use of the phase-estimation algorithm to generate an input string for a universal TM, which may anyway run indefinitely, this exponential run-time is not an issue. (Though it will entail a new clock construction when we come to encode the evolution of this QTM in a Hamiltonian, see Section 4.)

More precisely, we will prove the following result (see below for the necessary basic definitions, notations, and facts about QTMs).

Theorem 10 (Phase-estimation QTM)

There exists a family of well-formed, normal form, unidirectional QTMs $P_n$ indexed by with the following properties:

1. (i) Both the alphabet and the set of internal states are identical for all $P_n$ ; only the transition rules differ.

2. (ii) On input $N\geq {\lvert {n}\rvert }$ written in unary, $P_n$ behaves properly, halts deterministically after steps, uses $N+3$ space, and outputs the binary expansion of n (padded to N digits with leading 0’s). (Here, ${\lvert {n}\rvert }$ denotes length of the binary expansion of n.)

3. (iii) For any n, and for each choice of states $p,q$ , alphabet symbols $ \sigma , \tau $ and directions D, the transition amplitude $\delta (p,\sigma ,\tau ,q,D)$ is one of the elements of the set

   (3.1) $$ \begin{align} \left\{0,1,\pm \frac{1}{\sqrt{2}},e^{i\pi\varphi}, e^{i\pi 2^{-{\lvert{\varphi}\rvert}}}\right\} \end{align} $$
   where .

We emphasise again that the input N does not determine the output string that gets written to the tape; it only determines the number of binary digits in the output. The number represented by that output is determined (up to padding with leading zeros) by the choice of the parameter n for the QTM $P_n$ .

Theorem 10 is essentially the only inherently quantum ingredient in our result, and the precise properties asserted there will be absolutely crucial to the proof. For example, if instead of writing out the string and halting deterministically, the QTM did this only with arbitrarily high probability, our proof would not go through.

It is therefore not at all clear a priori whether QTMs fulfilling these strict requirements exist. Since our proof depends so delicately on the precise properties of these QTMs, we cannot appeal to previous results. Instead, in this section we give a detailed and explicit construction of a QTM based on the quantum phase estimation algorithm, that fulfils all the requirements of Theorem 10.

3.1 Quantum Turing Machinery

For completeness we quote the basic definitions of Turing Machines and Quantum Turing Machines verbatim from [16].

Definition 11 (Turing Machine – Definition 3.2 in [16])

A (deterministic) Turing Machine (TM) is defined by a triplet $(\Sigma , Q, \delta )$ where $\Sigma $ is a finite alphabet with an identified blank symbol $\#$ , Q is a finite set of states with an identified initial state $q_0$ and final state $q_f\not = q_0$ , and $\delta $ is a transition function

(3.2) $$ \begin{align} \delta: Q\times \Sigma \rightarrow \Sigma\times Q\times \{L,R\}. \end{align} $$

The TM has a two-way infinite tape of cells indexed by and a single read/write tape head that moves along the tape. A configuration of the TM is a complete description of the contents of the tape, the location of the tape head and the state $q\in Q$ of the finite control. At any time, only a finite number of the tape cells may contain non-blank symbols.

For any configuration c of the TM, the successor configuration $c'$ is defined by applying the transition function to the current state and the symbol scanned by the head, replacing them by those specified in the transition function and moving the head left (L) or right (R) according to $\delta $ .

By convention, the initial configuration satisfies the following conditions: the head is in cell $0$ , called the starting cell, and the machine is in state $q_0$ . We say that an initial configuration has input $x\in (\Sigma \setminus \#)^*$ if x is written on the tape in positions $0,1,2,\cdots $ and all other tape cells are blank. The TM halts on input x if it eventually enters the final state $q_f$ . The number of steps a TM takes to halt on input x is its running time on input x. If a TM halts, then its output is the string in $\Sigma ^*$ consisting of those tape contents from the leftmost non-blank symbol to the rightmost non-blank symbol, or the empty string if the entire tape is blank. A TM is called reversible if each configuration has at most one predecessor.

As amplitudes in quantum mechanics can take arbitrary complex values, one has to be careful when defining quantum Turing Machines to ensure the transition amplitudes are themselves computable. Following [16, Definition 3.2], we restrict the transition function to computable numbers in the standard way. Let be the set consisting of $\alpha $ such that there is a deterministic classical Turing Machine $M_\alpha $ that, given input , outputs the real and imaginary parts of $\alpha $ to within $2^{-n}$ in time polynomial in n. ⁵

Definition 12 (Quantum Turing Machine – Definition 3.2 in [16])

A quantum Turing Machine (QTM) is defined by a triplet $(\Sigma , Q, \delta )$ where $\Sigma $ is a finite alphabet with an identified blank symbol $\#$ , Q is a finite set of states with an identified initial state $q_0$ and final state $q_f\neq q_0$ , and $\delta $ – the quantum transition function – is a function

(3.3)

The QTM has a two-way infinite tape of cells indexed by and a single read/write tape head that moves along the tape. We define configurations, initial configurations and final configurations exactly as for deterministic TMs.

Let $\mathcal {S}$ be the inner-product space of finite complex linear combinations of configurations of M with the Euclidean norm. We call each element $\phi \in \mathcal {S}$ a superposition of M. The QTM M defines a linear operator $U_M: \mathcal {S}\rightarrow \mathcal {S}$ , called the time evolution operator of M, as follows: if M starts in configuration c with current state p and scanned symbol $\sigma $ , then after one step M will be in a superposition of configurations $\psi =\sum _i\alpha _ic_i$ , where each nonzero $\alpha _i$ corresponds to the amplitude $\delta (p,\sigma ,\tau ,q,d)$ of in the transition $\delta (p,\sigma )$ and $c_i$ is the new configuration obtained by writing $\tau $ , changing the internal state to q and moving the head in the direction of d. Extending this map to the entire $\mathcal {S}$ through linearity gives the linear time evolution operator $U_M$ .

Here, for convenience of programming, we will consider generalised TMs and QTMs in which the head can also stay still (No-movement), as well as move Left or Right.

Definition 13 (Generalised TM and QTM)

A generalised TM or generalised QTM is defined exactly as a standard TM (Definition 11) or standard QTM (Definition 12) except that the set of head movement directions is $\{L,R,N\}$ instead of just $\{L,R\}$ .

Following Bernstein and Vazirani [16], we define various classes of deterministic and quantum Turing Machines:

Definition 14 (Well-formed – Definition 3.3 in [16])

We say that a QTM is well-formed if its time evolution operator is an isometry, that is, it preserves the Euclidean norm.

It is easy to see (Theorem 4.2 in [16]) that any reversible TM is also a well-formed QTM where the quantum transition function $\delta (p,\sigma , q,\tau , d)=1$ if $\delta (p,\sigma )=(q,\tau ,d)$ for the reversible TM and $0$ otherwise.

Definition 15 (Normal form – Definition 3.13 in [16])

A well-formed QTM or reversible TM $M = (\Sigma ,Q,\delta )$ is in normal form if

(3.4)

In [16] the normal-form condition is . However, the choice of final direction is just an arbitrary convention, since the machine already halted and never carries out those transitions. We replace R with N in the definition for technical reasons (see the Reversal Lemma 22, below).

There is a specific class of QTMs, called unidirectional, that play an important role in the general theory developed by Bernstein and Vazirani [16].

Definition 16 (Unidirectional – Definition 3.14 in [16])

A QTM $M = (\Sigma ,Q,\delta ))$ is unidirectional if each state can be entered from only one direction. In other words, if $\delta (p_1, \sigma _1, \tau _1, q, d_1)$ and $\delta (p_2, \sigma _2, \tau _2, q, d_2)$ are both non-zero, then $d_1$ = $d_2$ .

Note that in a unidirectional QTM, the direction component in any transition rule triple is fully determined by the state . Thus we can recover the complete transition rules from the components alone, without the direction component. We call these the reduced transition rules, . (Equivalently, there exists an isometry that maps the reduced transition rules to the original transition rules: $V\delta _r(p,\tau ) = \delta (p,\tau )$ .)

The following theorem gives necessary and sufficient conditions for a (partial) transition function to define a reversible Turing Machine.

Theorem 17 (Local well-formedness – Thm. B.1 and Cor. B.3 in [16])

A TM M is reversible iff its transition function satisfies the following conditions:

• Unidirection Each state of M can be entered while moving in only one direction. In other words, if $\delta (p_1,\sigma _1) = (\tau _1, q, d_1)$ and $\delta (p_2,\sigma _2) = (\tau _2, q, d_2)$ then $d_1 = d_2$ .

• One-to-one The transition function is one-to-one when direction is ignored.

Furthermore, a partial transition function satisfying these conditions can always be completed to the transition function of a reversible TM.

Bernstein and Vazirani [16] proved that one can w.l.o.g. restrict to unidirectional QTMs. We therefore restrict the following quantum analogue of Theorem 17 to the unidirectional case:

Theorem 18 (Quantum local well-formedness)

A unidirectional QTM $M=(\Sigma ,Q,\delta )$ is well-formed iff its quantum transition function $\delta $ satisfies the following conditions:

• Normalisation

  (3.5a) $$ \begin{align} \forall p,\sigma \in Q\times\Sigma \quad {\lVert{\delta(p,\sigma)}\rVert} = 1. \end{align} $$

• Orthogonality

  (3.5b) $$ \begin{align} \forall (p_1,\sigma_1) \neq (p_2,\sigma_2) \in Q\times\Sigma \quad \left\langle\delta_r(p_1,\sigma_1),\delta_r(p_2,\sigma_2)\right\rangle = 0. \end{align} $$

Furthermore, a partial quantum transition function satisfying these conditions can always be completed to a well-formed transition function.

Bernstein and Vazirani [16] proved this result for standard QTMs, that is, where the head must move left or right in each time step. (In fact, they prove it without the restriction to unidirectional QTMs; see Theorem 5.2.2 and Lemma 5.3.4 in [16].) We therefore extend the proof of Theorem 18 to generalised QTMs, which is not difficult – indeed, it is made particularly straightforward by our restriction to unidirectional machines.

Proof of Theorem 18. Let U be the time evolution operator of the QTM M. By definition M is well-formed iff U is an isometry, or equivalently iff the columns of U have unit length and are mutually orthogonal. Clearly, the normalisation condition specifies exactly that each column has unit length.

Pairs of configurations whose tapes differ in a cell not under either of the heads, or whose tape heads are more than two cells apart, cannot yield the same configuration in a single time step. Therefore, all such pairs of columns are guaranteed to be orthogonal. The orthogonality condition imposes orthogonality of pairs of columns for configurations that differ only in that one is in state $p_1$ reading $\sigma _1$ while the other is in state $p_2$ reading $\sigma _2$ .

It remains to consider pairs of configurations whose heads are one or two cells apart, differing at most in the symbol written in these cells and in their states. However, unidirectionality implies that any update triples that share the same state must share the same direction. Thus either the state or the head location necessarily differs for all such pairs of columns, hence these too are orthogonal.

The final claim follows straightforwardly from the fact that the normalisation and orthogonality conditions imply that a partial unidirectional reduced transition function $\delta _r$ is well-formed iff it defines an isometry on the space of states and tape symbols, and this can always be extended to a unitary. This fills in the undefined entries of $\delta _r$ by extending $\delta _r(q,\sigma )$ to an orthonormal basis for the space of states and symbols.

We will often only be interested in the behaviour of a QTM (or reversible TM) on a particular subset of inputs, since the machine will only be run on those. A proper machine is guaranteed to behave appropriately on some subset of inputs, but not necessarily on all possible inputs.

Definition 19 (Proper QTM)

A QTM behaves properly (or is proper) on a subset $\mathcal {X}$ of initial superpositions if whenever initialised in $\phi \in \mathcal {X}$ , the QTM halts in a final superposition where each configuration has the tape head in the start cell ⁶ , the head never moved to the left of the starting cell, and the QTM never enters a configuration in which the head is in a superposition of different locations. We will refer to this latter property as deterministic head movement.

Similarly, we say that a deterministic TM behaves properly (or is proper) on $\mathcal {X}\subset (\Sigma \backslash \{\#\})^*$ if the head never moves to the left of the starting cell, and it halts on every input $x\in \mathcal {X}$ with its tape head back in the starting cell.

When the set $\mathcal {X}$ is clear from the context, we will omit it.

Note that, for a QTM to have deterministic head movement, it is not sufficient that none of its transition rules $\delta (\sigma ,\tau )$ produce a superposition of head directions. The head can also end up in a superposition of different locations because the tape state is in a superposition, so that two transition rules with different deterministic head movements apply in superposition.

Behaving properly is not a severe restriction on classical Turing Machines. ⁷ In fact, given any TM, there is always an equivalent proper TM that computes the same function. One way to see this is to recall that all computable functions are computable by Turing Machines restricted to one-way infinite tapes (see any standard text book on the theory of computation, e.g. Kozen [50]), and these clearly behave properly if the tape is extended to be two-way infinite. (Returning the head to the starting cell at the end of the computation poses no great difficulty.) In particular, this means that there exist proper universal Turing Machines.

Quantum Turing Machines were originally defined in Bernstein and Vazirani [16] to have two-way infinite tapes. Indeed, those authors point out that there are trivial well-formed machines (such as the always-move-right machine) whose evolution would not be unitary on a one-way infinite tape, since the starting configuration would have no predecessor. However, when we come to encode our QTMs into local Hamiltonians, we will only be able to simulate tapes with a boundary. ⁸ To avoid technical issues, we follow Bernstein and Vazirani [16] in defining QTMs on two-way infinite tapes, but we will ensure that none of the QTMs (or reversible TMs) that we construct ever move their head before the starting cell. Thus, when encoding the QTM in a Hamiltonian, we can ignore all of the tape to the left of the starting cell.

In fact, the local Hamiltonians encoding the QTMs will only be able to simulate the evolution on a finite (but arbitrarily large) section of tape. We will therefore be interested in keeping very tight control on the space requirements of all the reversible and quantum TMs that we construct. By carefully controlling the space overhead, it will then be sufficient for our purposes to simulate the evolution of the QTM on a finite portion of tape that is essentially no longer than the input.

3.1.1 Turing Machine Programming

For a multi-track Turing machine with k tracks and alphabet $\Sigma _i$ on track i, we will denote the contents of a tape cell by a tuple of symbols $[\sigma _1,\sigma _2,\ldots ,\sigma _k] \in \Sigma _1\times \Sigma _2\times \dots \times \Sigma _k$ specifying the symbol written on each track. Similarly, the configuration of the tape will be specified by a tuple $[c_1,c_2,\dots ,c_n] \in \Sigma _1^*\times \Sigma _2^*\times \dots \times \Sigma _k^*$ , where by convention all $c_i$ are aligned to start in the same cell (which will be the starting cell unless otherwise specified). We will use ${}\cdot {}$ to stand for an arbitrary track symbol. We will often describe Turing machines that act only on a subset of tracks, and leave the contents of all other tracks alone. In this case, we will only write out the states of the acted-upon tracks in the transition function; this transition function should be understood to be extended to the remaining tracks in the obvious way.

As a shorthand, a transition rule on a tuple containing a ${}\cdot {}$ on one or more tracks should be understood to stand for the set of transition rules that leave the tracks marked ${}\cdot {}$ unchanged, and act as indicated on the remaining tracks. We will often only specify some of the elements of a transition function when defining a reversible or quantum TM. We will call such partial transition functions “well-formed” if the elements that are defined satisfy the conditions of Theorem 17 or Theorem 18, since by those theorems this is sufficient to guarantee that the partial transition functions can be completed to well-formed transition functions. QTM (or reversible TM) will sometimes use a finite number of auxiliary tracks. These are assumed always to start and finish in the all blank configuration.

We will have frequent recourse to the following basic TM and QTM programming primitives from Bernstein and Vazirani [16], which we slightly generalise here to account for additional properties of the resulting QTMs that will be important to us later. These primitives allow different QTMs to be combined in various ways to build up a more complex QTM.

Lemma 20 (Subroutine Lemma)

Let $M_1$ be a two-track, normal form, reversible TM and $M_2$ a two-track normal form reversible TM (or well-formed, normal form, unidirectional QTM) with the same alphabet and the following properties:

1. (i) $M_1$ is proper on initial configurations in $\mathcal {X}_1$ and $M_2$ is proper on $\mathcal {X}_2$ .

2. (ii) When started on $\mathcal {X}_1$ , $M_1$ leaves the second track untouched; when started on $\mathcal {X}_2$ , $M_2$ leaves the first track untouched.

3. (iii) There is a state q on $M_1$ that, when started on $\mathcal {X}_1$ , can only be entered with the head in the starting cell.

4. (iv) $\mathcal {X}_2$ contains all the output superpositions (with $q_f$ replaced by $q_0$ ) of k consecutive executions of $M_2$ started from an initial configuration in $\mathcal {X}_2$ for all $0\le k\le r$ , where is the maximum number of times that q is entered when $M_1$ runs on input in $\mathcal {X}_1$ .

Then there is a normal form, reversible TM (or well-formed, normal form, unidirectional QTM) M which behaves properly on $\mathcal {X}_1$ and acts as $M_1$ except that each time it would enter state q, it instead runs machine $M_2$ .

Proof. Exactly as Lemma 4.8 in [16].

Lemma 21 (Dovetailing Lemma)

Let $M_1$ and $M_2$ be well-formed normal form unidirectional QTMs (resp. normal form reversible TMs) with the same alphabet, so that $M_1$ is proper on $\mathcal {X}_1$ , $M_2$ is proper on $\mathcal {X}_2$ and $\mathcal {X}_2$ contains all final superpositions (resp. configurations) of $M_1$ started on $\mathcal {X}_1$ . Then, there is a well-formed normal form unidirectional QTM (resp. normal form reversible TM) M which carries out the computation of $M_1$ followed by the computation of $M_2$ and that is also proper on $\mathcal {X}_1$ .

Proof. Exactly as Lemma 4.9 in [16].

Lemma 22 (Reversal Lemma)

If M is a well-formed, normal form, unidirectional QTM (resp. normal form reversible TM) then there is a well formed, normal form, unidirectional QTM (resp. normal form reversible TM) $M^{\dagger }$ that reverses the computation of M while taking two extra time steps and using the same amount of space. Moreover, if M is proper on $\mathcal {X}$ , then $M^{\dagger }$ is proper on the set of final superpositions (resp. configurations) of M started on $\mathcal {X}$ .

Proof. The proof is very similar to that of Lemma 4.12 in [16]. We will prove it for QTMs, since reversible TMs are a special case of these. Consider an initial superposition , and let be the evolved sequence obtained by , where is a final superposition. Since M is normal form, do not have support on $q_0$ .

Let be the superposition obtained by replacing the state $q_f$ in with the initial state of the new machine $q_0'$ . Let be the superposition obtained by replacing the state $q_f$ in with the new final state $q_f'$ . We want to construct a QTM $M^{\dagger }$ that, when started from , halts on in $n+2$ steps. $M^\dagger $ will have the same alphabet and set of states as M, together with the new initial and final states $q_0',q_f'$ . We define the transition function $\delta '$ in the following way:

1. (i) .

2. (ii) For each $q\in Q\backslash \{q_0\}$ and each $\tau \in \Sigma $ ,

   (3.6)

   

3. (iii) .

4. (iv) .

Here, for any state q, $d_q$ is the unique direction in which that state can be entered, and $\bar {d_q}$ is the opposite direction. Since M is unidirectional, Theorem 18 implies that $M^{\dagger }$ is a well-formed, normal form, unidirectional QTM. Given a configuration c in state q, $\pi (c)$ is defined as the configuration derived from c by moving the head one step in the direction $\bar {d_q}$ . $\pi $ can be extended by linearity to $\mathcal {S}$ .

Let us now analyse the behaviour of $M^{\dagger }$ started from . By (i), $M^{\dagger }$ maps in one step to . Now consider (ii). Since M is normal form, it maps superposition to superposition with no support on state $q_0$ if and only if has no support on state $q_f$ . Denote $Q_0 = Q\backslash \{q_0\}$ , $Q_f = Q\backslash \{q_f\}$ . If M takes a configuration $c_1$ with a state from $Q_f$ with amplitude $\alpha $ to a configuration $c_2$ (necessarily with a state in $Q_0$ ), then (ii) ensures that $M^{\dagger }$ takes configuration $\pi (c_2)$ to configuration $\pi (c_1)$ with amplitude $\alpha ^*$ . Let $S_0$ (resp. $S_f$ ) be the space of superpositions using only states in $Q_0$ (resp. $Q_f$ ). Since M is well-formed, the restriction of the evolution operator $U_M$ to $S_f$ is an isometry into $S_0$ . Hence $M^{\dagger }$ implements, up to conjugation by $\pi $ , the inverse of $U_M$ restricted to $U_M(S_f)$ .

As an aside, note that this implies that the evolution operator of M is indeed a unitary and not just an isometry. Indeed, by (i) to (iv) above, the evolution operator of $M^{\dagger }$ is also an isometry from $S_0$ into $S_f$ . Since $\pi $ is trivially a unitary on $\mathcal {S}$ , this implies that $U_M$ restricted to $S_f$ is a unitary onto $S_0$ . Now, since M is normal form, $U_M$ achieves any possible configuration with state $q_0$ by starting from the same configuration but with $q_0$ replaced by $q_f$ . These two facts together show that $U_M$ is indeed surjective and hence a unitary.

Returning to the proof of the lemma, we have seen how (ii) implies that $M^{\dagger }$ executes the sequence of n steps . Finally, by (iv), in the $(n+2)$ ’th step, $M^{\dagger }$ maps to as desired.

Moreover, it is trivial to see that $M^{\dagger }$ uses exactly the same space as M, and behaves properly.

Note that our way of defining normal form (Definition 15 as opposed to that in [16]) is crucial to guarantee that the reversal machine is proper. As a corollary of the proof, we have also shown that the evolution of a well-formed, normal form unidirectional QTM is a unitary operator. (The proof of this fact for non-unidirectional QTMs is much more involved, and can be found in [16]).

In the following sections, we give explicit constructions of the reversible and quantum Turing Machines that, when combined appropriately using Lemmas 20 to 22 as described below, implement a phase-estimation QTM with the properties required to prove Theorem 10. The formal definitions of all these Turing Machines are given by their transition rule tables, which can directly be verified to satisfy the well-formedness conditions of Theorems 17 and 18.

Since understanding how a TM works just from a table of transition rules is not always straightforward, we additionally give an informal pseudocode description of how each machine operates on suitable input. These pseudocode descriptions also help in verifying that the machines specified in the transition rule tables behave properly and satisfy the claimed space and run-time bounds.

Each pseudocode listing describes how the Turing Machine moves its head and reads and writes tape symbols as the algorithm proceeds, in order to implement the claimed operation. The internal state that the TM transitions into after carrying out the corresponding line of pseudocode is indicated in the margin. ⁹ The internal state that the TM is in at the beginning of an algorithm or subroutine is also indicated in the margin. Where no internal state is indicated in the margin, this means the internal state is left unchanged. Conditional branches in the pseudocode (i.e. if, else if and else statements) are structured to reflect how the different computational paths that can be followed by the TM during the computation branch off and are then re-merged to ensure reversibility.

However, it should be emphasised that these pseudocode listings are not rigorous specifications of the corresponding Turing Machines; the formal, mathematically rigorous specifications are the transition rule tables.

3.1.2 Reversible Turing Machine Toolbox

It will be helpful to have a toolbox of reversible TMs which carry out various elementary computations. In order to satisfy the space constraints of Theorem 10, we will be interested in keeping tight control of the space requirements of all our constructions.

Lemma 23 (Copying machine)

There is a two-track, normal form, reversible TM with alphabet $\Sigma \times \Sigma $ that, on input s written on the first track, behaves properly, copies the input to the second track and runs for time $2{\lvert {s}\rvert }+1$ , using ${\lvert {s}\rvert }+1$ space.

Proof. We simply step the head right, copying the symbol from the first track to the second. However, we defer copying the starting cell until the end of the computation, so that we can locate the starting cell again. In pseudocode:

It is straightforward to verify that the following normal form transition function implements :

(3.7)

This partial transition function verifies the two conditions of Theorem 17, so it is well-formed and can be completed to give a reversible TM.

Lemma 24 (Shift-right machine)

There exists a normal form, reversible TM with alphabet $\Sigma $ that, on input s behaves properly, shifts s one cell to the right and runs for time $2{\lvert {s}\rvert }+2$ , using space ${\lvert {s}\rvert }+2$ .

Proof. The Turing Machine has a separate internal state $q^\sigma $ corresponding to each tape symbol $\sigma $ . It reads the symbol into this internal state, overwrites it with the preceding symbol, and steps right. In pseudocode:

The reason for including two different states $q_2$ and $q_3$ is to guarantee the unidirectionality requirement of Theorem 17. The state $q_2$ is entered from the right and the state $q_3$ from the left. The effect of this is that, if the input is the empty string, this Turing Machine program still steps right and then left before halting.

It is straightforward to verify that the following normal-form transition function implements :

(3.8)

As this partial transition function verifies the two conditions of Theorem 17, it is well-formed and can be completed to give a reversible TM.

Lemma 25 (Equality machine)

There is a three-track, normal form, reversible TM with alphabet $\Sigma \times \Sigma \times \{\#,0,1\}$ that, on input $s;t;b$ , where s and t are arbitrary input strings and b is a single bit, behaves properly and outputs $s;t;b'$ , where $b'=\neg b$ if $s=t$ and $b'=b$ otherwise. Furthermore, runs for time $4{\lvert {s}\rvert }+1$ and uses ${\lvert {s}\rvert }+1$ space.

Implementing a non-reversible equality-testing machine is trivial: just scan the head right checking if the symbols on the two input tracks match. If we reach the end of the input without encountering a non-matching pair, return to the starting cell and flip the output bit. If we encounter a non-matching pair, return to the starting cell and leave the output bit unchanged.

Doing this reversibly requires more care. The problem is that the computation splits into two possible paths, depending on whether a non-match was encountered or not, and we must merge these two divergent computations back together again reversibly. For example, we cannot simply halt after either flipping the output bit or leaving it unchanged, as that would give multiple transitions into the final state that write the same symbol to the starting cell. The trick is to return to the point at which the computational paths diverged (either the first non-matching pair of symbols, or the end of the input) after setting the output bit, in order to merge the two computational paths back together, before returning to the starting cell again to halt.

To accomplish this, we use a state $q_4$ that is the only state that can transition to $q_f$ (except for the special case in which the first symbols in both input strings already differ, which is handled immediately). The state $q_1$ searches along the strings, until it either finds the end of both strings (first computational path), or it finds a point where the symbols in the two inputs differ (second computational path).

In the first path, state $q_2$ will return to the starting cell, switch the output bit and transition to $q_3$ . State $q_3$ will move right again doing the same as $q_1$ did and, at the end of both strings, will transition to $q_4$ . Note that we need two different states for this, due to unidirectionality: $q_2$ will be entered from the left and $q_3$ from the right.

In the second path, states $q_2'$ and $q_3'$ play the corresponding roles of $q_2$ and $q_3$ , respectively. In both paths, $q_4$ will return to the starting cell and halt. Within each path there is no issue with reversibility. The key to this is that, when both computational paths are merged into state $q_4$ , they do so on exactly the same input states as when the paths diverged (with $q_1$ replaced by $q_3$ or $q_3'$ depending on the path). Thus these transitions fulfil the properties required for a well-formed (partial) transition function by Theorem 17.

This implementation requires being able to identify the starting cell, so that we can return to it again. This is also important since we want to avoid ever moving the head before the starting cell, to ensure the TM is proper, see Definition 19.) If the symbols in the first cell differ, we can set the output bit immediately and halt. If they are identical, we temporarily change the symbol on the second input track to a $\#$ to mark the starting cell. We can recover the original second-track input at the end of the computation in this case, by copying over the symbol from the first track. (This is not the only way one could handle this.)

Proof of Lemma 25. In pseudocode, the Turing Machine program for

does the following:

The following normal-form transition function carries out this procedure:

(3.9)

One can verify that this partial transition function satisfies the two conditions of Theorem 17, so it is well-formed and can be completed to give a reversible TM, as required.

It is somewhat easier to construct reversible implementations of basic arithmetic operations if the numbers are written on the tape in little-endian order (i.e. least-significant bit first), as it avoids any need to shift the entire number to the right to accommodate additional digits. We adopt this convention for all the following basic arithmetic machines. We do not allow numbers to be padded with leading 0’s as that would allow multiple binary representations of the same number, which is inconvenient when constructing reversible machines. Note that this means the number zero is represented by the blank string, not the string “0”.

Lemma 26 (Increment and decrement machines)

There exist normal form, reversible TMs and with alphabet $\{\#,0,1\}$ that, on little-endian binary input n (with $n>1$ for ), behave properly and output $n+1$ or $n-1$ respectively. Both machines run for time $O(\log n)$ and use at most ${\lvert {n}\rvert }+2$ space.

Incrementing a binary number on a non-reversible TM is straightforward: simply step the head along the number starting from the least significant bit, flipping 1’s to 0’s to propagate the carry until the first 0 or #, then flip that 0 or # to 1 and halt. (Little-endian order avoids any need to shift the whole input to the right to accommodate an additional digit, should one be required.) However, making this procedure reversible is more fiddly. One option of course is to use the general procedure for reversible simulation and uncomputation of a non-reversible TM due to Bennett [13], but this comes at a cost of polynomial space overhead. A more careful construction allows us to implement directly, using just two additional tape cells.

Proof of Lemma 26. We first use the machine from Lemma 24 to shift the entire input one cell to the right, as a convenient way of getting a $\#$ in the starting cell so that we can return to it later. We then reversibly increment the binary number written on the tape, and finish by running (the reversal of the machine, constructed using Lemma 22) to shift the output back one cell to the left.

To implement reversibly the incrementing part of this procedure, we assign states as follows. State $q_1$ will search along the input for the first $0$ to change it to a $1$ , and along the way will change all $1$ s to $0$ s. In this way, the carry from incrementing the first (least significant) bit is propagated along the binary string to the appropriate bit. If no such $0$ exists, a $1$ will be appended to the end of the input string by changing the blank symbol $\#$ there to a $1$ .

These two possible computation paths have to be merged back into a state $q_4$ , which will then return the TM head to the starting cell and halt. To merge these two paths, which end up in states $q_2$ and $q_2'$ respectively, we add an extra state $q_3$ together with transition rules from $q_2$ and $q^{\prime }_2$ into $q_3$ , such that both computational paths arrive at a configuration in which the TM is in state $q_3$ and reading a $1$ . Thereupon, the TM can transition into $q_4$ and complete the computation.

In pseudocode:

The following normal-form transition function implements this:

(3.10) $$ \begin{align} \begin{array}{l|ccc} & \# & 0 & 1 \\ \hline q_0 & (\#,q_1,R) \\ q_1 & (1,q_2',R) & (1,q_2,R) & (0,q_1,R) \\ q_2 & & (0,q_3,L) & (1,q_3,L) \\ q_2' & (\#,q_3,L) \\ q_3 & & & (1,q_4,L) \\ q_4 & (\#,q_f,N) & (0,q_4,L) \\ q_f & (\#,q_0,N) & (0,q_0,N) & (1,q_0,N) \\ \end{array} \end{align} $$

This partial transition function verifies the two conditions of Theorem 17, so it is well-formed and can be completed to give a reversible TM.

This completes the construction of . To implement , simply construct the reversal of using Lemma 22.

We can use the construction to construct a looping primitive. (This gives a slightly more general version of the Looping Lemma from [16, Lemma 4.13], which also has tighter control on the space requirements.)

Lemma 27 (Looping Lemma)

There is a two-track, normal form, reversible TM with alphabet $\{\#,0,1\}$ , which has the following properties. On input $n;m$ , with $n< m$ both little-endian binary numbers, behaves properly, runs for time $O((m-n)\log m)$ , uses space ${\lvert {m}\rvert }+2$ and halts with its tape unchanged. Moreover, has a special state q such that on input $n;m$ , it visits state q exactly $m-n$ times, each time with its tape head back in the starting cell.

There is also a one-track, normal form, proper, reversible TM which, on input $m\ge 1$ , behaves as on input $0;m$ .

Proof. Our construction closely follows the proof of Bernstein and Vazirani [16, Lemma 4.2.10]. We will use two auxiliary tracks in addition to the two input tracks, both with alphabet $\{\#,0,1\}$ and both initially blank.

The core of the machine is a reversible TM $M'$ constructed out of two proper, normal form, reversible TMs $M_1$ and $M_2$ .

$M_1$ has initial and final states $q_0,q_f$ , and transforms input $n;m;x;b$ into $n;m;x+1;b'$ , where b is a bit and $b'=\neg b$ if $x=n$ or $x=m-1$ but not both, otherwise $b'=b$ . $M_1$ can be constructed by dovetailing together the machine from Lemma 25 (with the first and third tracks as its input tracks and the fourth track as its output), then the machine from Lemma 26 (acting only on the third track), and finally another machine (this time with the second and third tracks as its input tracks and the fourth track as its output). By Lemma 21 and the fact that all the constituent machines are proper, normal form and reversible, $M_1$ is proper, normal form and reversible. From Lemmas 25 and 26, $M_1$ runs for time $O(\log m)$ and takes at most ${\lvert {m}\rvert }+2$ space.

$M_2$ has new initial and final states $q_\alpha ,q_\omega $ , with $q_0$ and $q_f$ as its only other normal (i.e. not initial or final) internal states. $M_2$ behaves as follows:

1. (i) If it is in state $q_\alpha $ with $b=0$ , it flips b to 1 and enters state $q_0$ .

2. (ii) If it is in state $q_f$ with $b=0$ , it enters state $q_0$ .

3. (iii) If it is in state $q_f$ with $b=1$ , it flips b to 0 and halts.

The following normal form, partial transition function for $M_2$ is essentially the same as the corresponding construction in Lemma 4.2.6 of Bernstein and Vazirani [16], but we can simplify slightly by exploiting the fact that we are allowing generalised TMs. It acts only on the fourth track, and implements a machine $M_2$ that clearly satisfies the requirements (i) to (iii), above:

(3.11) $$ \begin{align} \begin{array}{l|ccc} & \# & 0 & 1 \\ \hline q_\alpha & & (1,q_0,N) \\ q_f & & (0,q_0,N) & (0,q_\omega,N) \\ q_\omega & (\#,q_\alpha,N) & (0,q_\alpha,N) & (1,q_\alpha,N) \end{array} \end{align} $$

$M_2$ is clearly normal form, and satisfies the two conditions of Theorem 17.

The transition rules for $M'$ are constructed by deleting the $q_f$ to $q_0$ transition rules from $M_1$ , and adding all the remaining $M_1$ rules to those of $M_2$ . The initial and final states of $M'$ are $q_\alpha ,q_\omega $ . On input $\mbox {n;m;n;0}$ , $M'$ will therefore run $M_2$ until it enters the $q_0$ state, then run $M_1$ until it halts and re-enters $M_2$ . It will continue to alternate in this way between $M_2$ and $M_1$ until the former halts. Thus $M'$ goes through the following sequence of configurations:

(3.12) $$ \begin{align} \mbox{n;m;n;0} \overset{(i)}{\longrightarrow} \mbox{n;m;n;1} \overset{M_1}{\longrightarrow} \mbox{n;m;n+1;0} \overset{(ii)}{\longrightarrow} & \mbox{n;m;n+1;0} \overset{M_1}{\longrightarrow} \mbox{n;m;n+2;0} \overset{(ii)}{\longrightarrow}\cdots \notag \\ &\cdots\overset{(ii)}{\longrightarrow} \mbox{n;m;m-1;0} \overset{M_1}{\longrightarrow} \mbox{n;m;m;1} \overset{(iii)}{\longrightarrow} \mbox{n;m;m;0} \end{align} $$

It therefore runs exactly $m-n$ times and enters the state $q_f$ once in each run, so we can take $q_f$ as the special state q.

To initialise the tracks, we dovetail a proper, reversible TM before $M'$ which transforms the input $n;m;\#;\#$ into the configuration $n;m;n;0$ . This is easily constructed by dovetailing the machine from Lemma 23 (acting on the first and third tracks) with a simple reversible TM which changes the first cell of the fourth track from $\#$ to 0 and halts. (Implementing the latter is trivial.) To return all tracks to their initial configuration at the end, we dovetail another proper, reversible TM after $M'$ which transforms the configuration $n;m;m;0$ into the final output $n;m;\#;\#$ . This is easily constructed by dovetailing the reversal of the copying machine from Lemma 23 (acting on the second and third tracks) with a simple reversible TM which changes the first cell of the fourth track from 0 back to $\#$ . From Lemma 28, these initialisation and reset machines run for time $O(\log n)$ and $O((m-n)\log m)$ , respectively, and use ${\lvert {n}\rvert }+1$ and ${\lvert {m}\rvert }+1$ space.

It remains to show that combining $M_1$ and $M_2$ as described above to form $M'$ gives a proper, normal form, reversible TM. Since $M_1$ is normal form, it has no transitions into $q_0$ or out of $q_f$ other than the ones we deleted before combining it with $M_2$ to construct $M'$ . All remaining internal states of $M_1$ and $M_2$ are distinct. Thus, since $M_1$ is reversible, the transition rules for $M'$ also satisfy the two conditions of Theorem 17. $M'$ can therefore be completed to a normal form, reversible TM. Since $M_1$ is proper, it is easy to see that $M'$ is also proper.

$M'$ loops on $M_1 \ m-n$ times (with constant time overhead and no additional space overhead coming from $M_2$ ). Each run of $M_1$ takes time $O(\log m)$ , so the complete implementation takes time $O(\log m)$ . None of the constituent TMs use more than ${\lvert {m}\rvert }+2$ space, so neither does . This completes the construction of .

To construct , we simply remove the second input track from the machine, and replace the machine that acts on that track with a trivial machine that checks whether the starting cell of the third track contains the $\#$ symbol.

The reversible incrementing, decrementing, and looping machines constructed above are sufficient to implement all arithmetic operations. The only ones we will need are addition and subtraction. These are now easy to construct.

Lemma 28 (Binary adder)

There exist two-track, normal form, reversible TMs and with alphabet $\{\#,0,1\}^{\times 3}$ , which have the following properties. On input $n;m$ with n and m both little-endian binary numbers and $m\ge 1$ , behaves properly and outputs $n+m;m$ . On input $n;m$ with $n> m$ , behaves properly and outputs $n-m;m$ . Both TMs run for time $O(m\log m\log n)$ and use $\max ({\lvert {n}\rvert },{\lvert {m}\rvert })+2$ space.

Proof. To construct , we simply run the TM of Lemma 27 on the second track, inserting for its special state the machine of Lemma 26 acting on the first track. Since both and are proper and normal form, the resulting machine is also proper and normal form. is simply the reversal of , constructed using Lemma 22.

We will also need a reversible TM to convert input from unary representation to binary. Again, it is not difficult to construct this using our reversible incrementing TM.

Lemma 29 (Unary to binary converter)

There exists a two-track, normal form, reversible TM with alphabet $\{\#,1\}\times \{\#,0,1\}$ with the following properties. On input $1^n;\#$ (n written in unary on the first track), behaves properly and outputs $1^n;n$ (n written in little-endian binary on the second track). Furthermore, runs for $O(n^2 \log n)$ steps and uses $n+1$ space.

Proof. The basic idea is to step the head right along the unary track until we reach the end of the unary input string, running the machine of Lemma 26 once each time we step right. However, needs to be started with its head in the starting cell. So each time we run it, we need to temporarily mark the current head location, move the head back to the starting cell in order to run , then return the head to its previous location and continue stepping right.

Consider the following normal form transition function, acting only on the unary track:

(3.13) $$ \begin{align} \begin{array}{l|ccc} & \# & 1 \\ \hline q_0 & (\#,q_f,N) & (1,q,N) \\ q_1 & (\#,q_4,L) & (\#,q_2,L) \\ q_2 & (\#,q,N) & (1,q_2,L) \\ q & (\#,q_2',R) & (\#,q_1,R) \\ q_2' & (1,q_1,R) & (1,q_2',R) \\ q_4 & (1,q_f,N) & (1,q_4,L) \\ q_f & (\#,q_0,N) & (1,q_0,N) \end{array} \end{align} $$

This verifies the two conditions of Theorem 17, so it is well-formed and defines a reversible TM. It is also easy to see that this TM is proper.

The transition function implements a machine M that steps right over the 1’s on the unary track until it reaches the end of the input, at which point it moves its head back to the starting cell and halts. However, each time it steps right, it temporarily marks the current head location by overwriting the 1 on the unary track with a $\#$ , returns the head to the starting cell, enters an apparently useless internal state q for one time step, then returns the head back to where it was before, restores the 1 on the unary track, and continues stepping right from where it left off.

In pseudocode:

The purpose of this apparently pointless procedure is that, by Lemma 20, we can substitute the machine from Lemma 26 for the state q, with acting on the (initially blank) binary track.

The above TM enters the q state precisely n times. Thus, when we substitute for q, will be run precisely n times, leaving the number n written on the binary track as required. Each iteration of takes time $O(\log n)$ and at most ${\lvert {n}\rvert }+2$ space. The step-right TM constructed above adds time overhead $O(n^2)$ and uses $n+1$ space. Neither machine ever moves its head before the starting cell. Thus the overall machine satisfies the time and space claims of the Lemma.

3.2 Quantum phase estimation overview

The qubits used in the quantum phase estimation circuit can be divided into two sets: the “output” qubits which will ultimately contain the binary fraction expansion of the phase in the black-box unitary, and the “ancilla” qubits on which the black-box unitary is applied. In our case, the black-box unitary will be the single-qubit unitary $U_\varphi =\left (\begin {smallmatrix}1&0\\0&e^{i\pi \varphi }\end {smallmatrix}\right )$ , so the ancilla set will be a single qubit. As stated above, $\varphi $ will refer to the number whose binary decimal expansion contains the digits of n in reverse order after the decimal.

The quantum phase estimation algorithm proceeds in five stages:

1. (i) A preparation stage, in which the qubits are first initialised in the state, then Hadamard gates are applied to all the output qubits and the ancilla qubit is prepared in an eigenstate of $U_\varphi $ (in our case  );

2. (ii) The controlled-unitary stage, during which control- $U_\varphi $ operations are applied between the output qubits and the ancilla qubit;

3. (iii) A stage in which we locate the least significant bit of the output;

4. (iv) The quantum Fourier transform stage, in which the inverse quantum Fourier transform is applied to the output qubits;

5. (v) A reset stage, which resets all the auxiliary systems used during the computation to their initial configuration.

We will construct QTMs for each of these stages separately, and use the Dovetailing Lemma 21 to chain them together. It will be useful to divide the tape into multiple tracks. A “quantum track” with alphabet $\Sigma _q=\{\#,0,1\}$ will store the qubits involved in the phase estimation algorithm. The input $1^N$ (the unitary representation of N) will be supplied as a string of N 1’s on the quantum track. All the other tracks will essentially be classical; after each stage they will be left in a single standard basis state (i.e. neither entangled with other tracks, nor in a superposition of basis states). These classical tracks will be used to implement the classical processing needed to control the quantum operations applied to the quantum track.

3.3 Preparation stage

We will use the first cell of the quantum track as the ancilla qubit, and the following N cells as the output qubits of the quantum phase estimation algorithm.

It will be convenient to first store a copy of the input given in unary on the quantum track on an auxiliary “input track”, but written in binary, i.e. to transform the configuration $1^N;\#$ of the quantum and input tracks into $1^N;N$ . Running the unary-to-binary converter from Lemma 29 on the quantum and input tracks carries out the desired transformation.

We want to initialise the $N+1$ qubits that will be used in the phase estimation, by preparing the ancilla qubit in the state and the output qubits in the state. The first N qubits are already in the state thanks to the input string. We therefore prepare the desired state by first temporarily flipping the state of the first qubit on the quantum track to to mark the starting cell, then stepping the QTM head right rotating each qubit into the state, until we reach the first state which we again rotate to to initialise the $N+1$ ’th qubit. We then move the head back to the start location, flip the state of the first cell of the quantum track from to , and halt. (The contents of all other tracks are ignored.)

In pseudocode:

It is straightforward to verify that the following partial transition function satisfies the conditions of Theorem 18, so is well-formed, and implements a proper, well-formed, normal form, unidirectional QTM that does exactly what we want.

(3.14)

3.4 Control- $U_\varphi $ stage

The second stage of the phase estimation procedure is to apply control- $U_\varphi ^{2^{n-1}}$ operations between the n’th output qubit and the ancilla qubit (see Figure 2). Constructing a QTM that implements this is more complex. The basic idea is to supply the QTM with an internal state q that causes the $U_\varphi $ rotation to be applied to the quantum track at the current head location. We then construct classical control machinery which iterates over the output qubits, and loops on q to apply $U_\varphi $ for a total of $2^{n-1}$ times.

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

We will use three auxiliary tracks. A “mark track”, with alphabet $\Sigma _m=\{t,c,m_0,m_1,\#\}$ , will be used to mark the position of the current control and target qubits. (The $m_{0,1}$ states will be used to temporarily store an auxiliary qubit on the mark track of the starting cell.) The other two auxiliary tracks, with alphabet $\Sigma _l=\{0,1,\#\}$ , will constitute the work tapes of two different reversible looping TMs from Lemma 27.

3.4.1 $cU^k$ machine

We will need a QTM which applies the control- $U_\varphi $ operation k times. We give a construction for an arbitrary controlled single-qubit unitary U, as this will be useful later.

Lemma 30 (Controlled-U QTM)

For any single-qubit unitary U, there exists a well-formed normal form unidirectional QTM $cU^k$ with the following properties. The QTM has three tracks: a looping track with alphabet $\Sigma _l=\{0,1,\#\}$ , a mark track with alphabet $\Sigma _m=\{t,c,m_0,m_1,\#\}$ , and a quantum track with alphabet $\Sigma _q=\{0,1,\#\}$ . The input consists of a number $k\ge 1$ written in binary on the looping track in little-endian order, a configuration containing a single t and a single c within the first n tape cells on the mark track (and all other cells blank), and an arbitrary n-qubit state on the quantum track.

On such input, the QTM applies the control-U operation k times between the control and target qubits on the quantum track marked by c and t, and then halts, having run for time $O(k n + k\log k)$ , used at most $\max (n,{\lvert {k}\rvert }) + 2$ space, behaving properly and leaving the configurations of the looping and mark tracks unchanged.

Proof. It will be convenient to first run the machine from Lemma 24 acting only on the mark and quantum tracks, to shift this part of the input one cell to the right. This produces a $\#$ on the mark and quantum tracks of the start cell, which we can use later to return to this cell. The remainder of the construction returns the quantum and mark tracks of the start cell to the $\#$ state, so we can run the corresponding machine at the very end (where is the reversal of $M_1$ constructed using Lemma 22) to shift these tracks back one cell to the left, so that the final output is correctly aligned. These shift operations take $O(n)$ time and use $n + 2$ space.

We construct the core of the $cU^k$ QTM out of two simpler machines, $M_1$ and $M_2$ , dovetailed together in the sequence $M_1,M_2,M_1^\dagger $ (where $M_1^{\dagger }$ is the reversal of $M_1$ ). Machine $M_1$ effectively applies a CNOT gate between the qubits on the quantum track marked by c and t on the mark track, with c as the control and t as the target. However, as these qubits are not necessarily adjacent on the tape, $M_1$ must temporarily make use of an auxiliary qubit stored in the internal states of the QTM, which gets “carried” along with the QTM head. As we cannot leave a qubit in the internal state at the end of the computation, however, $M_1$ must reversibly erase this internal qubit after it has served its purpose, by applying a second CNOT between it and the control qubit. (See below for further details and quantum circuit diagrams.)

$M_1$ implements this in stages: first, it scans right until it encounters a c on the mark track, at which point it applies a CNOT between the quantum track and a qubit stored in its internal state. It then returns the head to the starting cell, and applies a CNOT between this internal qubit and an auxiliary qubit m on the mark track (defined by the two orthogonal states and , which are identified with and respectively). Finally, it returns to the location of the c on the mark track, applies a second CNOT between the quantum track and the internal qubit, returns to the starting cell, and halts.

In pseudocode:

Clearly, $M_1$ is proper, runs for time at most $O(n)$ and uses at most $n+1$ space.

The following well-formed, normal form, partial quantum transition function implements $M_1$ (which acts only on the mark and quantum tracks). Note that two of the internal states of $M_1$ comes in two varieties, indicated by a superscript $j=\{0,1\}$ and identified with , respectively, which are used to temporarily store a qubit in the internal state of the machine:

(3.15)

Machine $M_2$ loops k times, where k is specified by the number written in binary on the looping track, applying a control-U operation between the auxiliary qubit stored on the mark track of the start cell and the target qubit, and then halts. We construct $M_2$ using the reversible looping TM from Lemma 27, and inserting for its special state a QTM $M'$ that is very similar to $M_1$ . The $M'$ machine first applies a CNOT between the auxiliary qubit stored in the mark track of the starting cell and an internal qubit. It then scans right until it finds the t, and applies a single control-U operation between the internal qubit and the target qubit. Finally, it moves the head back to the starting cell, and applies another CNOT between the internal qubit and the auxiliary qubit, before halting.

In pseudocode:

If $u_{ij}$ denotes the $i,j$ ’th matrix element of U, then the following well-formed, normal form, partial quantum transition function (which acts only on the mark and quantum tracks) implements $M'$ :

(3.16)

$M'$ is proper, never alters the mark track and, for given mark track configuration, always runs for the same number of time steps. So substituting $M'$ in the looping machine Loop of Lemma 27 produces a proper QTM $M_2$ . Furthermore, since $M'$ takes $O(n)$ time and at most $n+1$ space, $M_2$ runs for time $O(k n + k \log k)$ , uses at most $\max (n,{\lvert {k}\rvert })+2$ space, and never moves the head before the starting cell.

The only qubits on which the overall QTM acts are the two qubits in the quantum tracks of the cells marked by t and c, the auxiliary qubit stored on the mark track (which we label m), and the two internal qubits stored in the internal states $q_2^j$ of $M_1$ and $q_{1,2}^j$ of $M_2$ (let’s label these $j_{1,2}$ , respectively). Qubits m, $j_1$ and $j_2$ are all initially in the

state. Apart from classical processing to move the head into the correct location, $M_1$ just applies a CNOT between the c and $j_1$ qubits, followed by a CNOT between the $j_1$ and m qubits, and finally another CNOT between the c and $j_1$ qubits:

Similarly, $M'$ applies a CNOT between the k and $j_2$ qubits, a control-U operation between the $j_2$ and t qubits, and a final CNOT between the k and $j_2$ qubits. Letting $cU$ denote the control-U gate, and recalling that the $j_2$ qubit starts off in the

state, the overall effect of this is:

(3.17)

or, as a quantum circuit diagram:

i.e. $M'$ effectively applies a single control-U operation between the m and t qubits. $M_2$ repeats the $M'$ operations k times, so the overall action of $M_2$ is to apply a control-U operation k times between the m and t qubits:

(3.18)

or, in quantum circuit diagrams:

Since the CNOT gate is self-inverse, the time-reversal $M_1^{\dagger }$ in fact applies the same sequence of CNOTs as $M_1$ . So, on the control, target, mark and internal qubits, dovetailing $M_1,M_2,M_1^{\dagger }$ carries out the operation:

(3.19)

or, in quantum circuit diagrams:

Thus the overall action of the entire QTM is to apply a $cU^k$ operation between the control and target qubits, as required, leaving the looping and mark tracks back in the configuration they started in. Furthermore, the QTM runs for time $O(k n + k \log k)$ , uses at most $\max (n,{\lvert {k}\rvert })+2$ space, and is well-formed, normal form, unidirectional and proper, as claimed.

3.4.2 Iterating over the control qubits

We want to apply a $cU_\varphi ^{2^{n-1}}$ operation between the n’th output qubit and the ancilla qubit, for each of the N output qubits. (Note that the output qubits are stored in reverse order on the quantum track starting from the 2nd cell, so the 1st output qubit is stored in the $N+1$ ’th cell of the quantum track and the N’th output qubit is stored in the 2nd cell; recall that the 1st cell holds the target qubit.) As we will need to use a second looping machine to iterate over the qubits, we refer to the looping track for the $cU^k$ machine as the “ $cU$ looping track”, and the track for the second looping machine used here as the “outer looping track”.

We will need a reversible TM which, on suitable mark and $cU$ looping track configurations (cf. Lemma 30), moves the c marker on the mark track one cell to the left, and doubles the value k written on the $cU$ looping track. It is convenient (though slightly less efficient) to divide the implementation into two parts, dovetailed together: which shifts the c marker one cell to the left, and which doubles the value on the $cU$ looping track.

In pseudocode,

does the following:

The following well-formed, normal form, partial transition function implements the reversible TM (which acts only on the mark track):

(3.20)

Doubling a number in binary simply appends a 0 onto the binary representation of the number. The Turing Machine implementation of this is particularly convenient in the little-endian convention we are using, as it simply means finding the first blank symbol and appending the 0 there. We can simplify the implementation slightly and avoid the Turing Machine head ever moving before the starting cell, by taking advantage of the fact that the input in our case is always a power of 2, so, in little-endian order, always consists of a string of zero or more 0’s followed by a single 1; in particular, the input is never blank. Thus we can overwrite the initial 0 or 1 with a blank symbol to mark the start of the tape, and restore the initial tape cell to 0 at the end of the algorithm. In pseudocode:

The following well-formed, normal form, partial transition function for (which acts only on the $cU$ looping track) does precisely this:

(3.21) $$ \begin{align} \begin{array}{l|ccc} & \# & 0 & 1 \\ \hline q_0 & & (\#,q_1,R) & (\#,q_2,R) \\ q_1 & & (0,q_1,R) & (0,q_2,R) \\ q_2 & (1,q_3,L) \\ q_3 & (0,q_f,N) & (0,q_3,L) & \\ q_f & (\#,q_0,N) & (0,q_0,N) & (1,q_0,N) \\ \end{array} \end{align} $$

We are now in a position to implement the complete controlled- $U_\varphi $ stage of the quantum phase estimation algorithm. We initialise the states of the auxiliary tracks, by first running a simple reversible TM that changes the $[\#,\#]$ in the first cell of the mark and $cU$ looping tracks into $[t,1]$ , then returns to the starting cell and halts. (Constructing a reversible TM for this is trivial.) We dovetail this with a proper, normal form reversible TM that scans to the end of the output qubits, initialises the mark track in that cell to a c, then returns to the starting cell and halts. In pseudocode:

The following normal form, partial transition function (which acts only on the mark and quantum tracks) accomplishes this:

(3.22)

On the mark track, this leaves a t and c over the ancilla qubit and the first output qubit, ¹⁰ respectively, and blanks everywhere else. The configuration prepared on the $cU$ looping track corresponds to the number 1 written in binary.

Next, we copy N from the input track to the outer looping track using the machine from Lemma 23. We then run a reversible looping TM from Lemma 27 which uses this track as its input track (so it will loop N times in total). For the special state of this looping machine, we substitute a QTM which dovetails the $cU^k$ machine from Lemma 30 with the and machines constructed above.

On appropriate input, the $cU^k$ machine from Lemma 30 runs for a number of steps which depends only on the classical part of the input supplied on the mark and looping tracks, and not on the quantum state in the quantum track. The and reversible TMs don’t touch the quantum track at all. So as long as the mark and $cU$ looping tracks are always in a suitable configuration (cf. Lemma 30) before the $cU^k$ machine is run in each iteration, the outer looping machine will be proper.

Now, we already initialised the $cU$ looping track to $k=1$ , above, and marked the ancilla qubit as the target and the first output qubit as the control. So the initial configuration of the mark and $cU$ looping tracks is suitable input for a $cU^k$ machine. When $cU^k$ is run in the first iteration of the outer looping machine, it applies a $cU^1 = cU$ between the first output qubit and the target qubit. and machines then run, which shifts the control marker one cell to the left onto the second output qubit and doubles k to $2$ , ready for the next iteration. In the second iteration, the looping machine therefore applies a $cU^2$ between the second output qubit and the ancilla, and doubles k to 4. The looping machine goes through a total of N iterations, each time feeding suitable input to the $cU^k$ machine to make it apply a $cU^{2^{n-1}}$ between the n’th output qubit and the ancilla, before halting with N written on the outer looping track, a t and c in the first and second cell of the mark track, and $N+1$ written on the $cU$ looping track.

Thus the outer looping machine is well-formed, normal form, unidirectional and proper. It runs for a total of N iterations with overhead $N \log N$ (cf. Lemma 27). In the n’th iteration it runs the $cU^k$ machine from Lemma 30 once with $k=2^{n-1}$ , and runs the and machines once each. The n’th iteration of the $cU^k$ machine takes time $O(N + 2^{n-1}\log 2^{n-1})$ , and the and machines always take time $O(n)$ . So the outer looping machine runs for a total time $O(N^2 2^N)$ .

Finally, we can uncompute (reset) the auxiliary tracks by running a reversible TM which transforms the configuration $N;N;tc;N+1$ left on the input, outer looping, mark, and $cU$ looping tracks, into $N;\#;\#;\#$ . We do this by running the reversal of the copying machine from Lemma 23 on the input and outer looping tracks to erase the outer looping track, decrementing the $cU$ looping track and running again to erase that track, and running a trivial reversible TM that changes $tc$ on the mark track into $\#\#$ .

Putting everything together, the control-U stage runs for a total time $O(N^2 2^N)$ and requires space $N+3$ (2 more cells than the number of qubits, which is $N+1$ ). When dovetailed with the preparation stage from Section 3.3, the overall QTM we have constructed implements the control-U circuit of Figure 2. If $\varphi _k$ denotes the k’th digit in the binary fraction expansion of $\varphi $ , then this prepares the state [62]

(3.23)

on the N output qubits (ordered as they are on the quantum track). All other tracks are blank, except for the input track which still has the input N written on it as a little-endian binary number.

3.5 Locating the LSB

The final stage of the quantum phase estimation algorithm is to apply the inverse quantum Fourier transform to the quantum state generated by the control-U stage. The structure of the quantum circuit for the QFT is rather reminiscent of that of the control-U stage. It again involves applying a “cascade” of control- $U^{2^n}$ gates between pairs of qubits, which we already know how to implement. Only now there is a new cascade starting from each output qubit (see Figure 3).

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

However, the phase $2^{-N}$ of the control- $U_{2^{-N}}$ rotation needed in the QFT circuit depends on the total number of qubits N that the QFT is being applied to. If we simply implemented the inverse QFT circuit directly on all N output qubits, the entries of the transition function in our $cU^k$ machine from Section 3.4 would have to depend on the input N, which is not allowed. It is not at all obvious whether the inverse QFT circuit on N qubits can be implemented exactly when N is given as input. ¹¹

On the other hand, the entries of the transition function are allowed to depend on the phase $\varphi $ that we are estimating – indeed, they necessarily do so, since the output of the $P_n$ QTM in Theorem 10 depends on n (or equivalently on $\varphi $ ). Rather than implementing the QFT on N qubits, we take a different approach. We supply our QTM with the $U_{2^{-{\lvert {\varphi }\rvert }}}$ gate, and implement the inverse QFT on ${\lvert {\varphi }\rvert }$ qubits, independent of the input N. (I.e. just enough qubits to hold all the digits of the binary fraction expansion of $\varphi $ .) However, for this to work, we must first identify which output qubit holds the least significant bit (LSB) of $\varphi $ , so that we know which qubits to apply the ${\lvert {\varphi }\rvert }$ -qubit inverse QFT to. The role of the input N is merely to provide us with an upper-bound on ${\lvert {\varphi }\rvert }$ , which allows us to identify the LSB in finite time and space.

Recall that the control-U stage prepared the state [62]

(3.24)

on the N output qubits (where $\varphi _k$ denotes the k’th digit in the binary fraction expansion of $\varphi $ ).

The least significant bit of $\varphi $ is the ${\lvert {\varphi }\rvert }$ ’th bit, and by assumption (cf. Theorem 10) ${\lvert {\varphi }\rvert } \leq N$ . So the ${\lvert {\varphi }\rvert }$ ’th bit of $\varphi $ is 1 and the ${\lvert {\varphi }\rvert }+1\dots N$ ’th bits are all 0. Thus the last $N-{\lvert {\varphi }\rvert }$ output qubits are in the state, and the ${\lvert {\varphi }\rvert }$ ’th qubit, which corresponds to the least significant bit of $\varphi $ , is in the state. (Recall that the output qubits are stored on the quantum track in reverse order.)

Therefore, if we construct a QTM that steps right, applying Hadamard rotations to the output qubits in the quantum track until it obtains a

and halts, we will be able to locate the least significant bit of $\varphi $ . More precisely, this will rotate the first $N-{\lvert {\varphi }\rvert }$ output qubits into the

state, and halt with the $N-{\lvert {\varphi }\rvert }+1$ ’th qubit (which corresponds to the ${\lvert {\varphi }\rvert }$ ’th bit of $\varphi $ ) rotated into the

state. The least significant bit of $\varphi $ is therefore identified by the first

on the quantum track after this machine has finished running.

The following well-formed, normal form, partial quantum transition function (which acts only on the quantum track) implements a proper QTM that steps along the quantum track, applying Hadamards until it obtains a . It can be verified that it obeys the three conditions of Theorem 18, so can be completed to a well-formed QTM:

(3.25)

(Note that the qubit in the starting cell of the quantum track is still in the state from the preparation and control-U stages. As we will not need this qubit again, this machine sets it to to mark the starting cell and leaves it in that state when it halts, for later convenience.)

The configuration written on the quantum track after this machine has finished is the $N+1$ -qubit state:

(3.26)

Note that the first $N-{\lvert {\varphi }\rvert }+2$ cells of the quantum track are not entangled with the rest of the track.

It will be helpful for later to record the number of output bits that we are skipping, i.e. to compute $N-{\lvert {\varphi }\rvert }$ and store the result on a separate auxiliary “count track”. We can do this using a construction that is very similar to the unary-to-binary converter of Lemma 29. Specifically, we will construct a reversible TM that steps right over ’s until it finds a on the quantum track, running the machine once each time it steps right. (This means first returning the head to the starting cell, running , then returning the head back to where it was previously.)

Consider the following partial transition function, which satisfies the conditions of Theorem 17 so can be completed to a proper, normal form, reversible TM:

(3.27) $$ \begin{align} \begin{array}{l|ccc} & \# & 0 & 1 \\ \hline q_0 & (\#,q_1,R) \\ q_1 & (\#,q_4,L) & (\#,q_2,L) & (1,q_4,L) \\ q_2 & (\#,q,N) & (0,q_2,L) \\ q & (\#,q_3,R) \\ q_3 & (0,q_1,R) & (0,q_3,R) \\ q_4 & (\#,q_f,N) & (0,q_4,L) \\ q_f & (\#,q_0,N) & (0,q_0,N) & (1,q_0,N) \\ \end{array} \end{align} $$

This machine effectively steps right over 0’s until it encounters a 1, at which point it moves its head back to the starting cell and halts. (It assumes that the first cell is marked with a $\#$ .) However, each time it is about to step right, it first temporarily marks the current head location by overwriting the 0 with a $\#$ , returns the head to the starting cell, enters a special internal state q for one time step, then returns the head back to where it was before, resets the quantum track to 0, and continues stepping right from where it left off. In pseudocode:

By Lemma 20, we can substitute for the state q the machine from Lemma 26 (acting on an initially blank “count track”). If we run the above TM on the quantum track, it will step right precisely $N-{\lvert {\varphi }\rvert }$ times before finding the first , so it will halt with $N-{\lvert {\varphi }\rvert }$ written to the count track.

The configuration left on the tape now consists of the little-endian binary number N written on the input track, the little-endian binary number $N-{\lvert {\varphi }\rvert }$ written on the count track, and the $N+1$ -qubit state from (3.26) written on the quantum track.

As the qubits storing the $N-{\lvert {\varphi }\rvert }$ trailing 0’s of the N-digit binary expansion of $\varphi $ now play no further role, it is convenient to shift the starting cell of subsequent machines to the tape cell containing the LSB. To this end, we copy the values N and $N-{\lvert {\varphi }\rvert }$ from the input and count tracks onto new auxiliary tracks. We then use a machine from Lemma 27, which uses the original count track as its input and work track, to run a machine from Lemma 24 acting on the tracks holding the copies of the count and input tracks. Thus the machine will run a total of $N-{\lvert {\varphi }\rvert }$ times, thereby shifting the binary strings on the copies so that they start in the $N-{\lvert {\varphi }\rvert }$ ’th cell – the one containing the LSB of ${\lvert {\varphi }\rvert }$ in the quantum track. We then run a trivial TM that steps the head right over the initial string of s on the quantum track, until it encounters the first identifying the LSB, and halts with the head at this LSB cell. When we refer to the input and count tracks in the following section, we mean the copies shifted to start at the LSB cell. (At the very end of the computation, we will uncompute the shifted copies of the count and input tracks and step the head left back to the original starting cell, to ensure the overall QTM remains proper.)

Now, we have been careful to ensure that the head is never moved to a location before the starting cell in any of the reversible and quantum TMs that we have constructed. Furthermore, the section of the complete tape configuration located before the LSB cell is unentangled with the rest (see (3.26), and note that all tracks other than the quantum track are in classical configurations). Thus, if we start any of our TMs in the LSB cell, it acts as if its input were the section of the tape configuration located after (and including) the LSB cell. We can therefore ignore the tape configuration of the first $N-{\lvert {\varphi }\rvert }$ cells in the following section, and restrict our attention to the following ${\lvert {\varphi }\rvert }$ cells.

3.6 QFT stage

We are now ready to apply the ${\lvert {\varphi }\rvert }$ -qubit inverse QFT to the ${\lvert {\varphi }\rvert }$ -qubit state stored on the quantum track. The inverse QFT circuit on ${\lvert {\varphi }\rvert }$ qubits consists of cascades of $cU_{2^{-{\lvert {\varphi }\rvert }}}^k$ gates, very reminiscent of the control-U stage we have already implemented (see Figure 3). The construction will therefore be similar. In the following, as we have shifted the starting cell, we relabel the output qubits and refer to the LSB qubit as the 1st qubit, the last one as the ${\lvert {\varphi }\rvert }$ ’th qubit.

In each cascade, we want to apply a $cU_{2^{m-n}} = (cU_{2^{-{\lvert {\varphi }\rvert }}})^{2^{{\lvert {\varphi }\rvert }+m-n}}$ gate between the m’th and n’th qubit ( $m<n$ ). Once again, we will use mark and $cU$ looping tracks to hold the input to a $cU_{2^{-{\lvert {\varphi }\rvert }}}^k$ machine from Lemma 30. However, the main loop will now consist of two nested loops: an outer loop to iterate the control qubit m of the $cU_{2^{-{\lvert {\varphi }\rvert }}}^{2^{{\lvert {\varphi }\rvert }+m-n}}$ gate over each output qubit, and an inner loop to iterate the target qubit n over qubits $m+1$ through ${\lvert {\varphi }\rvert }$ .

We first run a TM that initialises the mark and $cU$ looping tracks, so that the mark track contains the configuration $ct$ in the first two cells, and the $cU$ looping track contains a string of ${\lvert {\varphi }\rvert }-1$ 0’s followed by a 1. Note that this initial configuration of the $cU$ looping track is the little-endian binary representation of the number $2^{{\lvert {\varphi }\rvert }-1}$ . (Constructing a proper normal form, reversible TM that implements all of this is an easy exercise.)

We also use the machine from Lemma 26 to increment the number $N-{\lvert {\varphi }\rvert }$ stored on the count track to $N-{\lvert {\varphi }\rvert }+1$ . We then run the machine from Lemma 28, with the input and count tracks as the input tracks and the inner looping track as the output track, to write the number $N-(N-{\lvert {\varphi }\rvert }+1) = {\lvert {\varphi }\rvert }-1$ to the inner looping track.

3.4.2 Inner loop

The inner looping machine is very similar to the main looping machine from the control-U stage. We use a machine from Lemma 27, with the inner looping track as its input and work track. In each iteration, we first run a TM to divide the value on the $cU$ looping track by 2. (This is simply the reversal of the machine constructed in Section 3.4.2.) We dovetail this with the $cU_{2^{-{\lvert {\varphi }\rvert }}}^k$ machine from Lemma 30. Finally, we dovetail this with a TM that moves the target marker t on the mark track one cell to the right. (This can be implemented by taking the reversal of the machine from Section 3.4.2 and replacing c with t in its transition rules to give a machine.)

Assume that the inner looping track is initialised to ${\lvert {\varphi }\rvert }-m$ , the control and target markers on the mark track are initially over the m’th and $m+1$ ’th qubits, and the $cU$ looping track is initialised to $2^{{\lvert {\varphi }\rvert }}$ . Then the effect of this inner looping machine is to apply $cU_{2^{m-n}}$ operations between the m’th and n’th qubit for all $m < n \leq {\lvert {\varphi }\rvert }$ – the cascade of $cU$ ’s starting from the m’th qubit in Figure 3.

This inner looping TM leaves the mark track in the configuration with a c in the same cell that it started out in, a t in the ${\lvert {\varphi }\rvert }+1$ ’th cell (i.e. the cell after the last output qubit), and $2^{m-1}$ written on the $cU$ looping track. (The latter is the configuration consisting of an initial string of 0’s, followed by a 1 in the cell containing the c on the mark track.)

3.4.2 Outer loop

For the outer looping machine, we use a machine from Lemma 27 running on the input and count tracks (which hold the numbers N and $N-{\lvert {\varphi }\rvert }+1$ , respectively). By Lemma 27, this machine will therefore loop ${\lvert {\varphi }\rvert }-1$ times.

In each iteration, we first run the inner looping machine. Note that for the first iteration, the auxiliary tracks are already initialised as assumed above for the value $m=1$ . We dovetail this with a simple QTM that applies a Hadamard operation to the current control qubit (the one marked by a c on the mark track).

We then run a TM that changes the 1 on the $cU$ looping track to a 0, shifts the c on the mark track one cell to the right, steps right, and changes $[\#,\#]$ on the mark and $cU$ looping tracks to $[t,0]$ . The machine then steps right, changing $\#$ to 0 on the $cU$ looping track as it goes, until it reaches the end of the output qubits. Whereupon it changes $\#$ on the $cU$ looping track to $1$ , steps right, and changes the t on the mark track to $\#$ . Finally, it returns to its starting cell and halts. (Again, by now, constructing a proper, normal form, reversible TM for this is straightforward.) We dovetail this with the TM, acting on the inner looping track.

The effect of all this is to reset the configuration of the auxiliary tracks, ready for the next iteration of the inner loop. The control marker c is shifted to the next qubit along, qubit m say, and the target marker t is placed over the adjacent $m+1$ ’th qubit. The $cU$ looping track is reset to $2^{{\lvert {\varphi }\rvert }-1}$ , and the inner looping track is decremented to ${\lvert {\varphi }\rvert }-m$ , as required. In other words, the auxiliary tracks are initialised to the desired configuration for the new value of m.

Thus the outer looping machine runs the inner looping machine ${\lvert {\varphi }\rvert }-1$ times for each of the output qubits $m=1\dots {\lvert {\varphi }\rvert }-1$ . Each time it runs, the inner looping machine applies the desired cascade of $cU$ operations between the m’th and n’th qubits for all $m < n \leq {\lvert {\varphi }\rvert }$ . The outer looping machine then applies a final Hadamard operation to the m’th qubit, before moving onto the next qubit. One can therefore see that the overall effect is to apply the inverse quantum Fourier Transform circuit to the ${\lvert {\varphi }\rvert }$ output qubits.

3.7 Reset Stage

To reset all the auxiliary tracks, we dovetail the outer looping TM with a sequence of TMs that uncompute all the configurations we previously prepared on these tracks.

The first of these TMs changes the $ct$ left on the mark track over the final two qubits to $\#\#$ , and changes the final configuration $1;2^{{\lvert {\varphi }\rvert }-1}$ of the inner looping and $cU$ looping tracks to the blank configuration. (Note that $2^{{\lvert {\varphi }\rvert }-1}$ is the configuration consisting of a leading string of 0’s followed by a single 1 on the final output qubit, so is straightforward to reset without any arithmetic computations.)

To reset the final configuration $N;N-{\lvert {\varphi }\rvert }+1$ of the input and count tracks, we start by decrementing the count track to $N;N-{\lvert {\varphi }\rvert }$ (using ). Recall that we redefined the location of the starting cell before implementing the inverse QFT machine, so that the starting cell became the cell containing the LSB of $\varphi $ . We also shifted the copies of the input and count tracks accordingly (Section 3.5). We now step the head back to the original starting cell (which is easily located as we left a $\#$ written there on the quantum track, cf. Section 3.5). We can then run the reversal (constructed using Lemma 22) of the machine used in Section 3.5, to shift the copies of the input and count tracks used in the QFT stage back left again to the original starting cell, and run the reversal of the copy machines to erase the copies of the input and count tracks.

To erase the original count track, which contains $N-{\lvert {\varphi }\rvert }$ , we must run the reversal that we constructed in Section 3.5. (The first $N-{\lvert {\varphi }\rvert }$ qubits remain in the state and the LSB qubit in the state, so will indeed uncompute $N-{\lvert {\varphi }\rvert }$ .) Finally, to erase the original input track, we first use the machine from Lemma 24 on the quantum track, to shift the entire final state of the output qubits left. Note that this will work because the first qubit (the ancilla qubit of the control-U stage) was set to $\#$ in Section 3.5. We can then run the reversal of the unary-to-binary machine from Lemma 29, acting on the quantum track and input track, to uncompute the binary conversion of the unary input encoded in the length of the qubit state. Note that the machine only checks whether the symbols on the unary track are $\#$ or non- $\#$ . So the fact that the configuration of the quantum track is no longer necessarily a string of ’s does not matter; all that matters is that it is a string of N non- ’s.

The end result of all this is to reset all the auxiliary tracks to the blank state, leaving the output of the inverse QFT circuit stored in the first N cells of the quantum track.

3.8 Analysis

By dovetailing together the preparation stage (Section 3.3), control- $U_\varphi $ stage (Section 3.4), inverse-QFT stage (Section 3.6) and reset stage (Section 3.7), we have succeeded in constructing a family of well-formed, normal form, unidirectional quantum Turing Machines $P_n$ that behave properly on input $N\ge {\lvert {\varphi }\rvert }$ written in unary, and implement the quantum phase estimation algorithm on N qubits for phase $\varphi $ . By construction, $P_n$ satisfies part (i) of Theorem 10.

Now, we know [62] that the quantum phase estimation algorithm outputs the exact binary fraction expansion of the phase, as long as we run it on enough qubits to store the entire binary decimal expansion of the phase. Thus for $N\geq {\lvert {\varphi }\rvert } = {\lvert {n}\rvert }$ , the $P_n$ writes out the binary decimal expansion of $\varphi $ to N bits (in little-endian order, padding with 0’s as necessary). We choose $\varphi $ to be the rational number whose binary decimal expansion contains the digits of n in reverse order after the decimal, where n indexes $P_n$ . So our QTM $P_n$ implements the computation claimed in part (ii) of Theorem 10.

We were careful throughout to keep tight control on the space requirements of the reversible and quantum TMs that we used to construct $P_n$ . In fact, none of them used more than $N+3$ space. Finally, all steps of the computation take time , except the $cU_\varphi ^k$ and $cU_\varphi ^k$ computations, which take time $O(2^N)$ . Thus the overall run-time is . Thus $P_n$ fulfils the space and time requirements in part (ii) of Theorem 10.

The last thing we must check in order to finish the proof of Theorem 10 is part (iii). But the partial transition function defined so far for $P_n$ satisfies part (iii). It is trivial to check that one can complete this to a full transition function, whilst still satisfying part (iii). Indeed, by Theorem 18 the problem is equivalent to completing an orthonormal set of vectors with coefficients in

(3.28) $$ \begin{align} \mathcal{S} = \left\{ 0,1,\pm \frac{1}{\sqrt{2}},e^{i\pi\varphi}, e^{i\pi 2^{-{\lvert{\varphi}\rvert}}} \right\} \end{align} $$

to a full orthonormal basis with coefficients in $\mathcal {S}$ . Since any normalised vector with coefficients in $\mathcal {S}$ must be proportional to a vector in the canonical basis $\{e_j\}_j$ or of the form $\frac {1}{\sqrt {2}}(e_j\pm e_k)$ , $j\not = k$ , the result is immediate. This completes the proof of Theorem 10.

Note that the QTM we have constructed only implements the computation correctly when supplied a valid upper-bound on the number of digits in the binary fraction expansion of the phase. If the input is not actually a correct upper bound, we make no claim about the behaviour of the QTM. (This will be significant later, when we come in Section 6 to bound ground state energies of a Hamiltonian constructed out of this QTM.)

4 Encoding QTMs in local Hamiltonians

In Section 3, we obtained a QTM that implements exact quantum phase estimation deterministically, using a number of time-steps exponential in the bit-length of the phase being estimated. This gives us a way to generate any desired input to feed into a universal (reversible) Turing Machine (UTM). Dovetailing the phase estimation QTM and the UTM, we therefore obtain a family of QTMs of constant size (fixed alphabet size and number of internal states) for which the halting problem is undecidable on blank input tape.

In this section we will show how for any QTM, one can construct an associated Hamiltonian whose ground state encodes in a concrete way the evolution of the QTM. In particular, for the family of QTMs just described, it encodes the associated halting problem. We start by distilling the main ideas behind the construction from a historical perspective, to serve as a roadmap for this section.

The idea of encoding quantum computations into ground states of Hamiltonians goes back to Feynman [30], and was developed into its modern form by Kitaev [47]. The key object is the computational history state, which encodes the entire history of the computation in superposition. As these history states will play an important role in this section, we define them rigorously here:

Definition 31 (Computational history state)

A computational history state is a state of the form

(4.1)

where is an orthonormal basis for ${\mathcal {H}}_C$ , and for some initial state and set of unitaries $U_i\in {\mathcal {B}}({\mathcal {H}}_Q)$ .

${\mathcal {H}}_C$ is called the clock register and ${\mathcal {H}}_Q$ is called the computational register. If $U_t$ is the unitary transformation corresponding the t’th step of a quantum computation, then is the state of the computation after t steps. We say that the history state encodes the evolution of this quantum computation.

As Feynman realised, given a quantum circuit defined by the sequence of unitaries $\{U_t\}_{1\le t\le T}$ , it is straightforward to write down a Hamiltonian for which the ground space is precisely spanned by the set of computational history states (Definition 31), where one allows any initial state .

In order to obtain such a Hamiltonian, one first focuses on the clock register ${\mathcal {H}}_C$ . Let $d_C=T$ , and look for a Hamiltonian that has as ground state the superposition of all clock time steps:

(4.2)

This can be enforced by a standard hopping Hamiltonian:

(4.3)

To obtain the history state of Definition 31 from (4.2), one applies the controlled unitary on , where $U_{[1\cdots t]}$ is a shorthand notation for $U_t U_{t-1}\cdots U_1$ . At the level of the ground state, this boils down to considering the rotated Hamiltonian , which is nothing more than

(4.4)

The difficulty arises when one wants to implement this construction with a Hamiltonian that is (a) local, (b) one-dimensional and (c) translationally invariant. Issues (a)–(c) were addressed consecutively by Kitaev et al. [47], Aharonov et al. [2] and Gottesman and Irani [32].

As we already illustrated, the key ingredient to construct the history state Hamiltonian (4.4) is the clock. An important insight from [2] was to define a 1D local Hamiltonian whose ground state encodes in superposition a series of sweeps of particular product states, which act as as an oscillator of a clock. (Cf. Figure 4, which represents the particular clock oscillation we will use later).

Figure 4 Example of a clock oscillation cycle.

Now, apart from hopping terms in (4.3) (called evolution or transition rule terms) enforcing the evolution of the clock, one now needs to also include penalty terms that restrict the type of configurations that can appear in the ground state, by giving a positive energy to configurations that do not appear in the clock oscillation cycle. In the example of Figure 4, for instance, giving a positive energy to configurations of the form guarantees that no can appear to the right of a in any component of the ground state.

The type of constraints that can be enforced by penalty terms is characterised by the notion of a regular expressions, which for example (informally) allows one the express constraints of the form “write one , then as many ’s as you want, then write a or a , then as many as you want, and then a ”. (Note that this regular expression captures precisely the states present in the oscillation cycle of Figure 4.) The formal definition of regular expression is recalled in Definition 33, and the key result from [32] connecting regular expressions with penalty terms is stated in Lemma 36. An important point here is that we will be able to guarantee by other means that the sites at the two ends are always in states and , respectively. (We will enforce this using tiling constructions, described in detail Section 5; the same condition is enforced in a different way in [32].) We can therefore restrict our analysis just to these “bracketed” configurations.

The idea of a local clock was developed further by Gottesman and Irani [32] to obtain a translationally invariant clock where, analogous to a real clock, after each oscillation cycle (representing one “tick” of the clock), a counter gets incremented by one. In [32] the clock counter counts in unary, and is represented on a separate track of the TM. For a finite chain of length L, this means the clock can tick for $O(L)$ steps before the counter cannot be incremented further and the clock stops ticking. In our case, we need the clock to tick for an exponentially larger number of time steps. Hence we need to count in binary rather than unary. In fact, it will be convenient to have it count in an even larger (but fixed) base $\zeta $ . To achieve this, we will have to generalise the binary counter machine constructed in the previous section. This is done in Section 4.4.1.

There is an important subtlety. When one takes into account the full clock (oscillation and counter), penalty terms and transition rule terms are not enough to characterise the desired clock evolution. An example of this will be given below, immediately after the statement of Lemma 37. The key idea used to solve this problem in [2], also used crucially later in [32], was a more general way to guarantee for those particular constructions that all other product state configurations (except for those giving the desired clock evolution) have larger energy. Note that if a state does not follow the correct evolution, it picks up a positive energy contribution from the transition rule terms. Some of the undesired configurations pick up a positive energy contribution directly from the penalty terms, as before. There are other undesirable configurations that are not detected directly by the penalty terms. But these remaining undesirable configurations all evolve under the transition rule terms into configurations that do pick up such an energy penalty. Aharonov et al. [2] call this the Clairvoyance Lemma. This result may or may not hold for any given construction; the clock and Hamiltonian construction must be designed such that this property holds and the Clairvoyance Lemma proven for the specific construction at hand.

Aharonov et al. [2] proved their Clairvoyance Lemma by dividing the Hilbert space of the clock into subsets of product states that are invariant under the clock evolution, i.e. into orbits of the action of the clock Hamiltonian. If the above property holds – that undesired states get penalties or evolve to states with penalties – all orbits pick up energy penalties except the one corresponding to a valid clock evolution. This in turn ensures that the ground states of the full Hamiltonian are precisely the set of history states (Definition 31). Moreover, the analysis gives explicit lower bounds for the energies of the excited states.

We will prove a version of the Clairvoyance Lemma for our construction following the same approach. We first introduce penalty terms and transition rule terms for the clock Hamiltonian. We prove (building on the key result Lemma 37) that all product states that do not appear in the desired clock evolution either pick up an energy penalty from the penalty terms, or evolve to a configuration that picks up such a penalty. This allows us to prove that the clock Hamiltonian consisting of the sum over these penalty and transition rule terms has as its unique ground state the uniform superposition over the product states appearing in the desired clock evolution. This is the key ingredient in our version of the Clairvoyance Lemma (Section 4.7), which shows that for the complete Hamiltonian that includes both the clock and computational registers C and Q, the unique ground state is the computational history state of Definition 31, and all other eigenstates have energies lower bounded by $\Omega \left (\frac {1}{T^3}\right )$ .

The final insight to solve the issue (c) related to the translationally invariance property comes from Gottesman and Irani [32]. There, it was shown how all the ideas of [2] to address the local 1D case, could be implemented keeping the Hamiltonian translationally invariant. Indeed, this section can be seen as a self-contained analysis of a local Hamiltonian construction that generalises that of Gottesman and Irani [32] for the particular purposes of this paper.

Apart from adapting the clock construction to a translationally invariant setting, one of the main changes with respect to [2] (or to the original Feynman-Kitaev construction outlined above) in order to make the construction translationally invariant was to switch from quantum circuits to QTMs. That is, after each clock tick, a step of a QTM evolution is executed on a different track. In this case, the computational register Q in Definition 31 corresponds to the whole QTM configuration (internal state, head location, and tape configuration), encoded across a number of separate tracks. However, in order to apply our version of the Clairvoyance Lemma, one needs to guarantee that the $U_t$ terms appearing in (4.4) are indeed unitaries, and not partial isometries, even in the case in which the evolution corresponds to a QTM rather than a quantum circuit. In our case, this is guaranteed by restricting to a special class of QTMs, first identified in Bernstein and Vazirani [16], that has especially nice properties (well-formed Definition 38, normal-form Definition 15 and unidirectional Definition 16, to which we also add proper Definition 19) but that, at the same time, is general enough for our purposes. ¹² We give a more detailed overview of how these properties, together with a modification to the encoded computation, allow us to prove our version of the key Clairvoyance Lemma, in Section 4.7.

The following is the main result of this section:

Theorem 32 (Local Hamiltonian QTM encoding)

Let be the local Hilbert space of a 1-dimensional chain of length L, with special marker states . Denote the orthogonal complement of in by .

For any well-formed unidirectional Quantum Turing Machine $M = (\Sigma ,Q,\delta )$ and any constant $K>0$ ¹³ , we can construct a two-body interaction such that the 1-dimensional, translationally invariant, nearest-neighbour Hamiltonian $H(L)=\sum _{i=1}^{L-1} h^{(i,i+1)} \in {\mathcal {B}}({\mathcal {H}}(L))$ on the chain of length $L\geq K+3$ has the following properties:

1. (i) d depends only on the alphabet size and number of internal states of M.

2. (ii) $h \geq 0$ , and the overall Hamiltonian $H(L)$ is frustration-free for all L.

3. (iii) Denote and define . Then the unique ground state of $H(L)|_{S_{\!\text {br}}}$ is a computational history state encoding the evolution of M on input corresponding to the unary representation of the number $L-K-3$ , running on a finite tape segment of length $L-3$ .

Moreover, if M is proper on input given by the unary representation of $L-K-3$ , then:

1. (iv) The computational history state always encodes $\Omega (\zeta ^L)$ time-steps, where $\zeta ={\lvert {\Sigma \times Q}\rvert }$ ¹⁴ . If M halts in fewer than the number of encoded time steps, exactly one has support on a state that encodes a halting state of the QTM. The remaining time steps of the evolution encoded in the history state leave M’s tape unaltered, and have zero overlap with .

2. (v) If M runs out of tape within a time T less than the number of encoded time steps (i.e. in time-step $T+1$ it would move its head before the starting cell or beyond cell $L-3$ ), the computational history state only encodes the evolution of M up to time T. The remaining steps of the evolution encoded in the computational history state leave M’s tape unaltered.

3. (vi) Finally, if M satisfies part (iii) of Theorem 10, then h has the following form

   (4.5) $$ \begin{align} h = A + (e^{i\pi\varphi}B + e^{i\pi2^{-{\lvert{\varphi}\rvert}}} C + {\mathrm{h.c.}}), \end{align} $$
   with independent of n and with coefficients in , and Hermitian independent of n and with coefficients in .

Though we will not need it for our purposes, it is not difficult to prove that the next-highest eigenstate of $H(L)|_{S_{\!\text {br}}}$ has energy $\Omega (1/T^3)$ , where T is the total number of time-steps encoded in the computational history state.

4.1 Preliminaries

As our construction draws heavily on [32], we will follow their notation and terminology, which we summarise here. We divide the chain into multiple tracks:

Tracks 1-3 correspond to the clock register C and tracks 4-6 to the computational register Q in Definition 31 (see Figure 5 for an illustration).

Figure 5 Cartoon 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.

The local Hilbert space at each site is the tensor product of the local Hilbert space of each of the six tracks ${\mathcal {H}} = \otimes _{i=1}^6{\mathcal {H}}_{i}$ , where

(4.6)

$\Sigma $ is the tape alphabet of our given QTM M. $\Xi $ is the alphabet of the counter TM. $P_L,P_N,P_R$ are the sets of internal states of the counter TM that can be entered by the TM head moving left, not moving, or moving right (respectively). The states $p'\in P_R'$ duplicate the states $p\in P_R$ , and $p'\in P^{\prime }_L$ duplicate those in $P_L$ . Similarly for the internal states $Q_L,Q_N,Q_R$ of the QTM, with $q'\in Q^{\prime }_L$ duplicating the states $q\in Q_L$ . Recall that by the unidirection property of reversible and quantum Turing Machines (Theorems 17 and 18), these sets are disjoint.

The and Track 2 and 4 symbols are used for cells that do not currently hold the head. ¹⁵ The role of the Track 1 states is described in Section 4.2. That of the Track 6 “time-wasting” tape, as well as the role of the additional Track 4 $P\cup P^{\prime }_L$ states, will become apparent in Section 4.6.2.

The marker states , appearing in Theorem 32 will just be the states and . When a subset of tracks T is clear from the context, we will also write to denote and , respectively.

This set of states defines a standard basis for the single-site Hilbert space ${\mathcal {H}}$ . The product states over this single-site basis then give a basis for the Hilbert space ${\mathcal {H}}^{{\otimes } L}$ of the chain. We call these the standard basis states.

We will sometimes use regular expressions to specify subsets of standard basis states. A regular expression denotes a (possibly infinite) subset of finite-length strings over a finite alphabet. Equivalently, it can be thought of as a pattern that matches all the strings in the subset and no others. Regular expressions, and the regular expression notation we will use, can be defined inductively in the standard way:

Definition 33 (Regular expression)

Given a finite alphabet $\Sigma $ , let $\Sigma ^*$ denote the set of all finite-length strings of symbols from that alphabet. The following are regular expressions:

• • The empty regular expression $\epsilon $ denotes the set containing only the empty string.

• • Any symbol $x\in \Sigma $ denotes the singleton set $\{x\}$ containing only the string x.

Given two regular expressions $R_1,R_2$ , the following are also regular expressions:

• • $R_1 R_2$ denotes the set $\{xy : x\in R_1, y\in S_2\}$ of all concatenations of strings matching R and S.

• • The alternation $R_1|R_2$ denotes the set $R_1\cup R_2$ of strings matching either $R_1$ or $R_2$ (or both).

• • The Kleene-star $R^*$ denotes the Kleene closure of R, i.e. the smallest set of strings S such that $\epsilon , R\in S$ and S is closed under concatenation.

• • For $x_1,\dots ,x_n\in \Sigma $ , square brackets $[x_1,x_2,\dots ,x_n] := x_1|x_2|\dots |x_n$ are a shorthand notation for alternations of symbols.

Parentheses $(\dots )$ are used to group subexpressions, and have the highest precedence. Square brackets have higher precedence than the Kleene-star operator, which has higher precedence than the alternation operator. Concatenation has the lowest precedence.

Definition 34 (Bracketed state)

We call standard basis states that match the regular expression bracketed states (where stands for any single-site state other than ). We denote by ${S_{\!\text {br}}}$ the subspace spanned by the bracketed states.

We will often denote configurations of multiple tracks by writing them vertically, e.g.

denote, respectively, a single-site configuration of two tracks, a configuration on two neighbouring sites of one track, and a configuration on two neighbouring sites of three tracks. Since we will restrict throughout to the subspace ${S_{\!\text {br}}}$ of bracketed states, the

and

states will only ever appear at the left and right ends of the chain, across all the tracks. As a shorthand, we will therefore denote configurations involving

and

with symbols stretching vertically across all tracks, e.g.

We will also sometimes need to specify configurations in which the tracks are in any configuration other than

. We denote this with a

or

symbol stretching vertically across all tracks, e.g.

As usual in such constructions, the two-body Hamiltonian will contain two types of terms: penalty terms and transition rule terms. Penalty terms have the form where $a,b$ are standard basis states. This adds a positive energy contribution to any configuration containing a to the left of b. We call $ab$ an illegal pair, and denote a penalty term in the Hamiltonian by its corresponding illegal pair. We will sometimes also make use of single-site illegal states a. (Note that, even if we don’t allow ourselves to use single-site penalty terms, single-site illegal states are easily implemented in terms of illegal pairs, by adding penalty terms and for all pairs $ax$ and $xa$ in which the single-site state appears.)

Definition 35 (Legal and illegal states)

We call a standard basis state legal if it does not contain any illegal pairs, and illegal otherwise.

By using single-site illegal states one can enforce that, on all legal states, the marker (resp. ) can only ever appear simultaneously on all tracks. In this case, if one restricts to global bracketed states, one also gets bracketed states in each of the tracks individually. The single-site illegal states enforcing this are summarised in Table 1.

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

We will make repeated use of Lemma 5.2 from [32], which lets us use penalty terms to restrict to configurations matching a regular expression:

Lemma 36 (Regexps)

For any regular expression over the standard basis of single-site states in which each state appears at most once, we can use penalty terms to ensure that any legal standard basis state for the system is a substring of a string in the regular set.

All the regular expressions we will use start with a left-bracket state and end with a right-bracket . So whenever we apply this Lemma, the only substrings of the regular set that are bracketed states are in fact complete strings in the regular set, not substrings.

Transition rule terms have the form , where are states on the same pair of adjacent sites. We will often take and to be standard basis states. This forces any zero-energy eigenstate with amplitude on a configuration containing $ab$ to also have equal amplitude on the configuration in which that $ab$ is replaced by $cd$ . Conversely, if a zero-energy eigenstate has amplitude on a configuration containing $cd$ , it must also have equal amplitude on the configuration in which that $cd$ is replaced by $ab$ . Thus we can think of these terms as implementing the transition rules $ab \rightarrow cd$ , which we arbitrarily call the “forwards” direction, and the corresponding “backwards” transition $cd\rightarrow ab$ . Following the notation in [32], we will denote transition rule Hamiltonian terms by their associated forwards transitions $ab\rightarrow cd$ or, more generally, .

When a transition rule acts diagonally on a subset of the tracks, we will sometimes consider the restriction of the transition rule to those tracks. That is, for a transition rule with the general form , where T is some subset of the tracks, the restriction of the rule to T is given by .

When we specify a Hamiltonian term only on a subset of the tracks, we implicitly mean that it acts as identity on the remaining (unspecified) tracks. We will assume throughout this section that the ground state subspace of the Hamiltonian is restricted to the subspace ${S_{\!\text {br}}}$ of bracketed states, with at the left end of the chain and at the right. (We show how to enforce this later, in Section 6.)

4.2 Clock Oscillator

Every clock – even one unusual enough to be encoded in superposition into the ground state of a quantum many-body Hamiltonian! – needs some form of oscillator that oscillates with a fixed period (such as a pendulum), and a counter that is incremented after each complete oscillation of the oscillator (such as the hands on a clock). For the counter, we will use a reversible counter Turing Machine, described in Section 4.4. This section describes the Track 1 clock oscillator.

The legal configurations of Track 1 are states matching the regular expression . By Lemma 36, we can enforce this using penalty terms. Independent of the configuration of any other track, a arrow (either or ) sweeps right along the chain until it reaches the end, whereupon it turns around and becomes a . (When a reaches the end and turns around, the label on the arrow steps through the sequence $(0),(1),\dots ,(K)$ . This is used later on to correctly initialise the other tracks. The restriction to $L\ge K+3$ in Theorem 32 ensures that there is enough space for such sequences of transitions.) This arrow sweeps left until it reaches the beginning of the chain, at which point it turns around and becomes a again. We call this entire sequence an oscillator cycle. (One complete cycle is illustrated in Figure 4 for a chain of length six.) On a chain of length L, one complete oscillator cycle takes $2(L-2)$ steps. The following transition rules on Track 1 enforce this:

(4.7)

When a left-moving arrow returns to the beginning of the chain, it turns around and becomes a right-moving arrow again. However, the label $0$ on the arrow may change to a $1$ , depending on the Track 2 state. The arrow transitions to if the Track 2 state is $p_{\alpha }$ (the initial state of the counter TM). Whereas always transitions to unless the Track 2 state is $p_{\alpha }$ . The following transition rules implement this:

(4.8)

where $\neg p_{\alpha }$ here denotes any Track 2 state other than $p_{\alpha }$ .

4.3 Initialisation sweep

During the initial sweep of the Track 1 from left to right and back, Track 1 contains a or . We call this the initialisation sweep, and we want to use it to force Tracks 2 and 3 to be in the initial configurations

(4.9)

respectively. We do this by adding illegal pairs to forbid Track 2 from being anything other than when a is over it (except at the beginning of the chain):

(4.10)

and similarly to forbid Track 3 from being anything other than $\#$ when a is over it (except at the beginning of the chain):

(4.11)

where again denotes anything other than the state .

At the beginning of the chain, we use illegal pairs to forbid Track 2 from being anything other than $p_{\alpha }$ when is over it. We also forbid it from being $p_{\alpha }$ when a is at the beginning of the chain:

(4.12)

Thus any standard basis state containing a , or on Track 1 that matches the regular expressions (4.9), and is not in the initial configuration on Tracks 2 and 3, will evolve (either forwards or backwards) under the oscillator transition rules into an illegal configuration, in at most L steps.

If Tracks 2 and 3 are in their initial configurations, then a standard basis state containing a , or will evolve backwards until it reaches the initial configuration , the standard basis state for Tracks 1 to 3 which has the form:

(4.13)

4.4 Clock Counter

4.4.1 Counter TM construction

We construct the counter TM using a generalisation of the binary incrementing machine from Lemma 26, which will increment integers written in base- $\zeta $ instead of in binary. Recall that $\zeta = {\lvert {\Sigma \times Q}\rvert }$ . Constructing a base- $\zeta $ version of is largely a straightforward extension of Lemma 26.

Ensuring reversibility is similar to the binary case. The TM state $q_1$ scans along the digits of the little-endian input, changing all $\zeta -1$ ’s to $0$ ’s as it goes, until it finds the first digit different from $\zeta -1$ . It then increments this by one, to add the carry from all the previous $\zeta -1$ s digits. If no such digit exists, a $1$ will be appended to the end of the input. The difference with the binary case is that now there are three cases (or computational paths) that we must distinguish: the case in which a digit other than $0$ is incremented by one, and two different cases in which a $1$ can be written to the tape: incrementing $0$ , or writing a new $1$ in place of the first $\#$ symbol after the input. These three computational paths correspond respectively to TM states $p_2$ , $p_2'$ and $p_2''$ . The latter two paths are first merged into state $p_3'$ . The former transitions instead into state $p_3$ . Then, in a second stage, the two remaining paths are merged into state $p_4$ which, as in the binary case, is the state that then returns the head to the starting cell and halts.

In pseudocode:

The following well-formed, normal-form, partial transition function implements a reversible TM that increments any little-endian base- $\zeta $ number written on the tape with a leading “start-of-tape” symbol $\vdash $ , and returns the head to the starting cell without ever moving the head before the starting cell:

(4.14)

We now modify this machine slightly in order to make it loop forever. However, we must ensure that the loop reenters the initial state $p_0$ of reversibly. To accomplish this, we introduce new initial and final states $p_\alpha $ and $p_\omega $ , and modify the $p_0$ and $p_f$ transitions such that the TM reversibly transitions back into the state $p_0$ instead of halting, exploiting the fact that the symbol in the second tape cell will be blank in the first iteration, and non-blank thereafter.

In pseudocode:

The following set of transition rules accomplishes this:

(4.15)

These transition rules implement a reversible base- $\zeta $ counter TM. When started from the tape configuration consisting of a $\vdash $ symbol in the first cell followed by the all-blank tape (representing the number 0), this TM will loop indefinitely, incrementing the number written on the tape by 1 in each complete iteration. For brevity, we will refer to this particular initial tape configuration as the standard input to the counter TM tape.

We now declare certain configurations of the counter TM to be “illegal”. We will choose these illegal configurations to be such that they are never entered by the counter TM started from the standard input. Later on, when we come to encode the counter TM in a local Hamiltonian, we will use penalty terms to give energy penalties to all the configurations we declare “illegal” here, so that the corresponding standard basis states of the spin chain are indeed illegal in the sense of Definition 35. For now, however, the “illegal configurations” simply define a particular subset $\mathcal {I}$ of the complete set of counter TM head and tape configurations.

Anticipating the later use of penalty terms, when defining illegal configurations we will often make use of the illegal pair notation introduced above, where the top row denotes the counter TM head position and internal state p, and the bottom row denotes the tape symbols $ab$ in the section of tape near the head:

(4.16)

A single row always denotes a section of tape:

(4.17)

Certain configurations that we declare to be illegal will specify that the counter TM head is or is not located at the starting cell. Again anticipating later use of penalty terms, we introduce the following notation. We denote the starting cell by placing a symbol on the left. We denote tape cells other than the starting cell with on the left. For illustration, two examples of this would be:

(4.18)

Note that the counter TM started from the standard input never moves its head before the starting cell, never reenters its initial state $p_\alpha $ , and never enters its final state $p_\omega $ . We therefore declare any counter TM configuration which is in state $p_\alpha $ with the head anywhere other than the starting cell to be illegal:

(4.19)

We also declare any configuration in state $p_\omega $ to be illegal: ¹⁶

(4.20)

Similarly, we declare any configuration in state $p_\alpha $ with the head adjacent to a non-blank symbol to be illegal, i.e. any configuration containing the illegal pair

(4.21)

The transition table in (4.15) is partial; some transitions are never used, so were not defined. For each $(p,\tau )$ for which no transition rule is defined in (4.15), we declare configurations in which the counter TM is in state p and the head is reading $\tau $ to be illegal, i.e. any configuration containing the illegal pair

(4.22)

For each configuration $(p_L,\tau ,L)$ , $(p_R,\tau ,R)$ or $(p_N,\tau ,N)$ which is not entered by any transition rule in (4.15), we declare the corresponding TM head and tape configurations to be illegal, i.e. any configurations containing one of the following illegal pairs:

(4.23)

Note that during the evolution of the counter TM started from a blank tape, the head is never more than one cell to the right of a non-blank tape symbol. In fact, the only moment at which it is over a blank symbol at all is when the incrementer TM needs to carry a digit, and moves the head to the next blank cell in order to write the carry. We therefore declare configurations in which the head is more than one cell to the right of a non-blank tape symbol to be illegal, i.e. all configurations containing the illegal pair

(4.24)

Note also that, when started from the standard input, the counter TM never modifies the $\vdash $ in the first cell, never writes a $\vdash $ anywhere other than the first cell, and never creates an embedded blank symbol on the tape. We therefore define all tape configurations without a $\vdash $ in the starting cell, all tape configuration with a $\vdash $ anywhere other than the first cell, and all tape configurations with an embedded blank, to be illegal. These illegal TM configurations correspond exactly to tape configurations matching the regular expression

(4.25) $$ \begin{align} \vdash\,[0,\dots,\zeta-1]^*\,\#^*. \end{align} $$

The little-endian numbers written by the counter TM are never padded with leading 0’s, so the tape never has a 0 to the left of a $\#$ . We therefore define this combination to be illegal, i.e. all tape configurations containing the illegal pair

(4.26)

Later on, we will only be interested in configurations of the first L cells of the tape, and will stop the counter TM just before it tries to apply a transition rule that maps out of this portion of tape. Therefore, a 0 will never appear in the L’th tape cell, and we declare configurations containing a 0 in this cell to be illegal:

(4.27)

Lemma 37 (Evolve-to-illegal)

Any counter TM configuration that is reached starting from the standard input is legal. All other configurations with the head in position $r \in [0,L]$ are either illegal, or evolve forwards or backwards to an illegal configuration within $O(L)$ time steps in such a way that the head never leaves the portion of tape $[0,L]$ .

Before delving into the technical proof, let us briefly explain why the set of configurations reached by the counter TM during its computation (or rather, the complement of this set) cannot be characterised by illegal pairs. And why, therefore, one needs to exclude many of the invalid configurations by showing that they necessarily go on to evolve into an illegal configuration.

As an illustrative example, consider the valid configurations associated with state $p_1$ located in position $5$ . These are of the form:

with $\tau $ any element other than $\vdash $ . Any attempt to guarantee a $0$ in position $3$ in this configuration by declaring extra illegal pairs (which we recall can only be defined between nearest neighbours) would contradict the fact that, for state $p_0$ , all configurations of the form:

with $i_j\in \{0,\ldots \zeta -1\}$ are valid configurations reached by the counter TM during its evolution.

Proof Lemma 37. The first part of the Lemma is true by construction, since the partial transition rules of (4.15) implement the counter TM without using any of the undefined transitions, and the tape configurations defined to be illegal never occur when the counter TM is started from the standard input.

Recall that the alphabet of the counter TM is $\Xi = \{\vdash ,\#\}\cup \{0,\dots ,\zeta -1\}$ . Any tape configuration that does not start with a $\vdash $ , or which contains a $\vdash $ anywhere other than the first cell, or which contains an embedded blank, or contains a 0 to the left of a $\#$ , or with a $0$ in the L-th cell is illegal. So legal tape configurations match the regular expression

(4.28) $$ \begin{align} \vdash(\neg \#)^*\neg[0,\#]\#^*. \end{align} $$

Configurations in which the head is more than one cell away from a non-blank symbol are illegal by (4.24), so all legal configurations have the head located in, or immediately adjacent to, the non-blank portion of the tape. All other configurations are illegal.

We divide the legal configurations into separate cases, according to the internal state of the counter TM:

State $p_\alpha $ :

All configurations in state $p_\alpha $ are illegal by (4.19), except those with the head in the starting cell. The latter are illegal by (4.21) unless the tape cell to the right of the head is blank. The only such tape configuration which is legal is the standard input. Thus the only legal configuration in state $p_\alpha $ is the initial configuration of the counter TM started from the standard input.

State $p_{-1}$ :

There are no transitions out of $(p_{-1},x)$ where $x\neq \#$ in (4.15), so by (4.22) the only legal $p_{-1}$ configurations have their head over a $\#$ . Moreover, there is only one transition into $p_{-1}$ in (4.15). Hence, evolving any such configuration one step backwards according to (4.15) either enters a configuration that is illegal due to (4.22), or steps the head left and transitions to $p_\alpha $ . But we have shown that the only legal $p_\alpha $ configuration is the standard input. Thus any configuration in state $p_{-1}$ not reachable starting from the standard input will evolve backwards to an illegal configuration in one time step.

State $p_1$ :

Every TM configuration of the form

with the rest of the tape compatible with (4.28) is reached when evolving the counter TM from the standard input; this configuration is produced whilst the counter TM is incrementing the number with little-endian base- $\zeta $ expansion

$$ \begin{align*} \underbrace{(\zeta-1)\dots(\zeta-1)}_n \tau\cdots. \end{align*} $$

The remaining legal configurations have at least one tape symbol x to the left of the head that is neither 0, nor $\#$ , nor $\vdash $ :

Evolving any such configuration backwards according to (4.15) either enters into an illegal configuration due to (4.22), or rewinds the head left replacing 0’s with $\zeta -1$ ’s, eventually reaching the configuration with the head immediately to the right of the x:

The state $p_1$ can only be entered by moving right. But the configuration $(p_1,x,R)$ is not entered by any transition rule in (4.15), so this configuration is illegal by (4.23).

State $p_2$ :

The state $p_2$ is entered when incrementing any digit other than 0, $\#$ or $\zeta -1$ , so every TM configuration of the form

with the rest of the tape compatible with (4.28) is reached when evolving the counter TM from the standard input. This configuration is produced whilst the counter TM is incrementing the number with little-endian base- $\zeta $ expansion

$$ \begin{align*} \underbrace{(\zeta-1)\dots(\zeta-1)}_n (x-1) \tau\cdots \end{align*} $$

The state $p_2$ can only be entered by moving right. Configurations $(p_2,x,R)$ where $x\in \{\vdash ,\#,0,1\}$ are not entered by any transition rule in (4.15), so these configurations are illegal by (4.23).

The remaining legal configurations have at least one tape symbol y to the left of the head that is neither 0, $\#$ , nor $\vdash $ :

Evolving any such configuration backwards one time step according to (4.15) either produces an illegal configuration due to (4.22), or produces the configuration:

But we have already shown above that all such $p_1$ configurations evolve backwards in time to an illegal configuration.

States $p_2',p_2''$ :

The argument for states $p_2'$ and $p_2''$ is very similar to that for $p_2$ , except that the legal value of x is now $1$ .

State $p_3$ :

The state $p_3$ is entered by stepping left from $p_2$ , so every TM configuration of the form

with the rest of the tape compatible with (4.28) is reached when evolving the counter TM from the standard input. This configuration is produced whilst the counter TM is incrementing the number with little-endian base- $\zeta $ expansion

$$ \begin{align*} \underbrace{(\zeta-1)\dots(\zeta-1)}_n(\tau-1) \cdots \end{align*} $$

There is no transition out of $(p_3,x)$ where $\tau \in \{\vdash ,\#,0,1\}$ in (4.15), so all such configurations are illegal by (4.22). The remaining legal configurations have at least one tape symbol x to the left of the head that is neither 0, $\#$ , nor $\vdash $ :

Evolving any such configuration forwards one time step according to (4.15) either produces an illegal configuration (for example if $n=0$ ), or produces the configuration:

We show below that any such $p_4$ configuration evolves to an illegal configuration.

State $p_3'$ :

The argument for state $p_3'$ is very similar to that for $p_3$ , except that $\tau =1$ in this case.

State $p_4$ :

In a legal state $p_4$ configuration, the head must be over a $0$ or a $\vdash $ , since there is no transition out of $(p_4,x)$ for $x\notin \{0,\vdash \}$ . We first analyse the case in which it is over a $0$ .

Any TM configuration of the form

with the rest of the tape compatible with (4.28) is reached by evolving the counter TM from the standard input.

The remaining legal configurations have at least one tape symbol x to the left of the head that is neither 0, $\#$ , nor $\vdash $ :

Evolving any such configuration according to (4.15) steps the head left over the 0’s until the head is over the x:

But there is no transition out of $(p_4,x)$ in (4.15), so this configuration is illegal by (4.22).

We now analyse the case in which $p_4$ is over $\vdash $ . Evolving one step backwards according to (4.15) steps the head right and either enters an illegal configuration, transitions to state $p_4$ with the head over a $0$ , or transitions to states $p_3$ or $p_3'$ . In all three cases, we have already shown that all such configurations not reachable from the standard input evolve to illegal configurations.

State $p_f$ :

There are no transitions out of $(p_f,x)$ where $x \neq\ \vdash $ in (4.15), so the only legal $p_f$ configurations have the head over a $\vdash $ . The latter can only appear in the starting cell in legal configurations. Evolving any such configuration backwards according to (4.15) for one time step transitions to the state $p_4$ , and we have already shown than all $p_4$ configurations not reachable from the standard input evolve to illegal configurations.

State $p_f'$ :

There are no transitions out of $(p_f',x)$ where $x\in \{\vdash ,\#\}$ in (4.15), so the only legal $p_f'$ configurations have the head over a symbol in the set $\{0,\dots ,\zeta -1\}$ . Evolving any such configuration backwards according to (4.15) for one time step transitions to the state $p_f$ , and we have already shown than all $p_f$ configurations not reachable from the standard input evolve to illegal configurations.

State $p_0$ :

There are no transitions out of $(p_0,x)$ where $x \neq\ \vdash $ in (4.15), so the only legal $p_0$ configurations have the head over a $\vdash $ . The latter can only appear at the beginning of the tape in legal configurations. Since the only transitions in (4.15) into $p_0$ are from $p_1$ or $p_f'$ , evolving any such configuration one step backwards according to (4.15) either enters an illegal configuration, or steps the head right into state $p_{-1}$ or $p_f'$ . In both cases we have already shown that configurations not reachable from the standard input evolve to illegal ones.

State $p_\omega $ :

The counter TM never enters the state $p_\omega $ , and all such configurations are illegal.

4.4.2 Counter TM Hamiltonian

We want all legal Track 2 configurations to contain a single state $p\in P'$ marking the location of the counter TM head, and blanks everywhere else. I.e. the Track 2 configuration should match a regular expression where $p\in P'$ . By Lemma 36, we can enforce this using penalty terms. This Track 2 regular expression allows us to identify Tracks 2 and 3 with the configurations of the counter TM (with internal state p, its position being the head location, and Track 3 the tape). This will be explicitly or implicitly exploited in all that follows.

To encode the evolution of this counter TM in our local Hamiltonian, we encode its transition rules in transition terms. However, the transition rules will only apply when a arrow on Track 1 sweeps past the counter TM head encoded on Track 2, so that the counter TM advances exactly one step for each complete left-to-right sweep of the arrow. Since we are restricting to two-body interactions and the arrow is moving to the right, transitions in which the head moves left must be triggered when the is to the left of the TM head, in order to both move the arrow and update the head location. This way of implementing the left transitions means that

(4.29)

never occurs during the evolution of the counter TM if $\delta (p,\sigma ) = (\tau ,p_L,L)$ . We add a penalty term to make such configurations illegal.

Transitions in which the head moves to the right or stays still will be triggered when the is on top of the head. In order to avoid two transitions in which the head moves right from being triggered during the same sweep of the , we must split these latter transitions into two stages, in which we first transition into an auxiliary state $p^{\prime }_R\in P^{\prime }_R$ , and then transition into the correct state $p_R\in P_R$ in the following time step (adapting the construction of [32]). Thus, when the is on top of the head and the head will move right, we will update the tape, move the head, and step the to the right. But we transition into the auxiliary state $p^{\prime }_R\in P^{\prime }_R$ instead of $p_R\in P_R$ . In the next step, with the now on top of the $p^{\prime }_R$ state, we transition to the correct state $p_R$ , and step the to the right once more so that it is no longer on top of the head. This way of carrying out the right-moving transitions means that $p^{\prime }_R$ only ever appears below a , so we add a penalty term to make all other $p^{\prime }_R$ configurations illegal:

(4.30)

For TM transition rules $\delta (p,\sigma ) = (\tau ,p_N,N)$ , $\delta (p,\sigma ) = (\tau ,p_L,L)$ and $\delta (p,\sigma ) = (\tau ,p_R,R)$ (where $p\in P\backslash _{\{p_\alpha \}}$ , $p_{L,N,R}\in P_{L,N,R}$ and $\sigma ,\tau \in \Xi $ ), the following local transition terms on Tracks 1 to 3 implement the desired transformations (cells marked ${}\cdot {}$ can be in any state, and are left unchanged by the transition):

(4.31a)

(4.31b)

(4.31c)

Transitions in which the head moves left from the end of the chain are already covered by the left-moving transition in (4.31b). Transitions in which the head would move right off the end of the chain are not implemented. (Transitions in which the head would move left off the beginning of the chain are not implemented either, but in fact the counter TM construction of Section 4.4 will never attempt such a transition when initialised properly. Moreover, we just declared such configurations illegal in (4.29).)

When started from the blank input (which represents the number 0), the encoded counter TM will loop $\zeta ^{L-3}$ times before it exceeds the $L-2$ tape space available on Track 2 (the space overhead of 1 is due to the way the incrementer TM is implemented in (4.14)). The incrementer machine takes $\Theta (\log x)$ steps to increment the number x (written on the tape in base- $\zeta $ ). Thus the counter TM will run for at least $\Omega (\zeta ^L)$ (and at most $O( L \zeta ^L)$ ) time-steps before it exceeds the available tape space.

The transition function for the counter TM defines a transition rule for each pair $(p,\tau )\in P\times \Xi $ . So for any legal configuration containing a $p\in P$ on Track 2, exactly one of the transition rules in (4.31a) and (4.31b) will apply during each sweep. Similarly, for any configuration containing a $p^{\prime }_R\in P^{\prime }_R$ , a (4.31c) rule will apply. It is easy to verify that if any of the transition rules from (4.31a)–(4.31c) is applied to any legal configuration, none of the (4.31a) and (4.31b) rules can apply again to the resulting configuration. If the final (4.31b) rule applies, the (4.31c) rule will apply exactly once in the following step, after which none of the rules can apply again to the resulting configuration. The transition rules in (4.31a)–(4.31c) therefore implement a single step of the TM during each left-to-right sweep of the state on Track 1, as required. We call this phase of the evolution, in which Track 1 contains a or , the computation phase.

We also modify the clock oscillator rules from Section 4.2 involving a right-moving arrow to only apply when there is no TM head under the , since the movement is already taken care of by the above transition rules when there is a TM head present:

(4.32)

We must also enforce illegality of all the configurations declared to be illegal in Section 4.4.1. To do this, we simply introduce local penalty terms corresponding to the combinations declared illegal in (4.19)–(4.24), (4.26) and (4.27), and enforce the Track 3 regular expression of (4.25) using penalty terms and Lemma 36.

The complete set of Track 1 to 3 transition rules is summarised in Table 2. The regular expressions on Tracks 1 to 3 enforced by penalty terms, together with all the additional illegal pairs defined so far, are summarised in Table 3.

Table 2 All transition rules for Tracks 1 to 3.

¹Transition rules marked with an $(*)$ will be replaced in Section 4.6 by a set of rules that also act on Tracks 4, 5 and 6.

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

4.5 Clock Hamiltonian

Before considering the remaining tracks, it is helpful to analyse in depth the Hamiltonian defined so far on the first three tracks. For that we start with the definition of well-formed states.

Definition 38 (Well-formed state)

We say that a standard basis state on Tracks 1 to 3 is well-formed if it is a bracketed state, its Track 1 configuration matches the regular expression , and its Track 2 configuration matches the regular expression where $p\in P'$ .

The penalty terms defined previously give an energy penalty of at least 1 to any standard basis state in ${S_{\!\text {br}}}$ that does not match the desired regular expressions on Tracks 1–3. Thus only well-formed states can have zero energy. The following result shows that only one transition rule can apply to each well-formed state.

Lemma 39 (Well-formed transitions)

For any well-formed standard basis state, at most one transition rule applies in the forward direction, and at most one in the backwards direction. Furthermore, the set of well-formed states is closed under the transition rules.

Proof. A well-formed standard basis state contains exactly one of , , or on Track 1. Thus clearly only transition rules from one of the sets in Table 2 (the set of rules, rules, or rules) can apply in the forward direction. The left hand sides of the rules within the and sets are manifestly mutually exclusive. Since the counter TM is deterministic, there is a unique TM transition that applies at any step, so the left-hand-sides of the rules are also mutually exclusive.

The counter TM is reversible, so there is also a unique backwards TM transition at every step. Thus the same argument applies in the backwards direction to the right hand sides of the rules in each set, with the exception of the turning rule that changes a into a (in the backwards direction). But this rule clearly cannot apply at the same time as the right hand side of any rule from the set, which concludes the proof of the first part of the lemma.

It is straightforward to verify that all the transition rules in Table 2 preserve well-formedness, implying the second part.

Recall that the state is the standard basis state with on Track 1, on Track 2, and on Track 3. This corresponds to having the clock oscillator in the first state of the Track 1 sequence (see Figure 4), and the counter TM Tracks 1 and 2 in their initial configurations. There is no backwards transition out of , so we will refer to it as the initial clock state. Let be the standard basis state obtained by applying t transitions (in the forwards direction) to , which is well-defined thanks to Lemma 39.

Let us consider the form of the states . Note that contains a on Track 1. The only transition rules that apply when Track 1 contains a , or (see Table 2) are those that sweep the arrow all the way to the right and back again, without affecting Tracks 2 or 3. We saw in Section 4.2 that one complete oscillator cycle takes $2(L-2)$ steps. Thus $t\leq 2(L-2)$ corresponds to the initialisation sweep, in which the state contains a , or on Track 1, and Tracks 2 and 3 remain in their initial configurations.

At $t = 2(L-2)+1$ , the turns around and (because Track 2 contains a $p_\alpha $ at the beginning of the chain) becomes a . This is now over a $p_\alpha $ on Track 2. Thus the next step implements the first step of the counter TM on Tracks 2 and 3, causing Track 2 to transition to $p_\alpha $ .

Recall from Section 4.4 that the transition rules implement one step of the counter TM during each left-to-right sweep of the on Track 1, and then move the back to the beginning of the chain in the second half of the oscillator cycle. Note that the counter TM construction of Section 4.4 never transitions back to its initial state $p_\alpha $ . So when the reaches the beginning of the chain, it will never find a $p_\alpha $ on Track 3. Thus it will always transition into , never into (see Table 2). Therefore, for all $t> 2(L-2)$ the state contains a or on Track 1. At $t = 2(L-2)(n+1)$ the in is back at the beginning of the chain, and Tracks 2 and 3 are in the configuration corresponding to the n’th step of the counter TM.

Eventually, the number written on Track 3 will be incremented until it reaches $\zeta ^{L-4}$ , the maximum number that can be written in base- $\zeta $ in $L-4$ digits (the $-4$ accounts for the space-overhead of 2 required by the TM implementation, plus the two bracket states at the ends of the chain). When the counter TM tries to increment this number, the head will move right until it reaches the cell adjacent to the at the end of the chain. At this point, it will be in an internal state that would normally step right in order to write the carry. But the site to the right of the head contains instead of a blank Tape 2 cell. When the on Track 1 reaches the head at the end of on Track 2, there is no further forwards transition out of this configuration (see Table 2). Let T be the number of transitions required to reach this configuration starting from the initial state . We will refer to as the final clock state. Since this configuration occurs when the counter TM is about to exceed L tape space, which occurs after at most $O(L \zeta ^L)$ steps of the TM (see Section 4.4) each of which requires $2(L-2)$ transitions, we have that $T = O(L^2 \zeta ^L)$ . (Though this bound on the run-time will not be important for our purposes.)

The following result will be important later when we come to analyse the Hamiltonian.

Lemma 40 (Evolve-to-illegal)

Evolving any forwards or backwards in time according to the transition rules will never reach an illegal configuration. All other well-formed standard basis states will evolve either forwards or backwards to an illegal configuration after $O(L^2)$ transitions.

Proof. As in Lemma 37 the first part of the Lemma is true by construction. For the second part, let us analyse all possible well-formed standard basis states, which we divide into two cases depending on the type of arrow state we have on Track 1:

Case 1:

Track 1 contains , or . If Tracks 2 and 3 are in the initial configuration, then we are in one of the states with $0 \le t \le 2(L-2)$ .

If Tracks 2 and 3 are not in the initial configuration, then within at most $O(L)$ steps the or will move forwards or backwards along the chain due to the initialisation sweep clock oscillator transition rules, until it is over a site containing the wrong initial Track 2 or Track 3 state. But this is illegal due to the Track 1–3 illegal pairs from Table 3.

Case 2:

Track 1 contains or . Recall that there is a one-to-one correspondence between configurations of the counter TM and well-formed standard basis states that do not contain a $p^{\prime }_R\in P^{\prime }_R$ on Track 2.

Well-formed configurations containing a $p^{\prime }_R\in P^{\prime }_R$ on Track 2 evolve by a single backwards transition from (4.31b) to a configuration containing a $p\notin P^{\prime }_R$ on Track 2, and evolve by a single forwards transition from (4.31c) to a configuration containing a $p_R\in P_R$ . A configuration containing $p^{\prime }_R\in P^{\prime }_R$ is therefore reachable (resp. unreachable) by transition rules from the initial configuration iff the corresponding counter TM configuration with $p^{\prime }_R$ replaced by the corresponding $p_R$ is reachable (resp. unreachable).

For any well-formed configuration, each sweep of , the transition rules implements exactly one step of the counter TM encoded in Tracks 2 and 3. The only counter TM transitions that are not implemented are those that would move the head beyond the L sites between the and . Therefore, if the configuration of Tracks 2 and 3 is not reachable from the initial configuration, then Lemma 37 guarantees that evolving it forwards or backwards by the transition rules will reach an illegal configuration in $O(L)$ steps of the counter TM, which takes $O(L^2)$ transitions. (Note that it is crucial for this argument that to reach an illegal configuration in Lemma 37 never requires moving the head outside the portion of tape $[0,L]$ .)

It only remains to consider well-formed states with Track 2 and 3 configurations that are reachable from the initial configuration. For the initial Tracks 2–3 configuration itself, if is in the starting cell then we have the state for $t=2(L-2)+1$ . If not, either we have to the right of the head or on Track 1, with $p_\alpha $ at the start of Track 2. In both cases, evolving such a state forwards in time will reach a state with a over the $p_\alpha $ within $O(L)$ transitions, which is illegal by the second Track 1 and 2 illegal pair from Table 3.

If the Track 2–3 configuration is not the initial one, then all positions of and give rise to elements in the set except exactly those declared illegal in (4.29) and (4.30). This completes the proof of the Lemma.

4.6 QTM Hamiltonian

With the clock in place, encoding an arbitrary quantum Turing Machine in the Hamiltonian is now possible using ideas from [32] (and is similar to the construction used in Section 4.4 to encode the reversible counter TM). The configurations are now quantum states, so there can be arbitrary superpositions over standard basis states. But it suffices to verify that the construction does the right thing on standard basis states; this then extends to arbitrary superpositions by linearity and well-formedness.

When we later come to analyse the spectrum, we will require our Hamiltonian to be standard-form in the following sense:

Definition 41 (Standard-form Hamiltonian)

We say that a Hamiltonian $H = H_{\text {trans}} + H_{\text {pen}}$ acting on a Hilbert space is of standard form if $H_{\text {trans,pen}} = \sum _{i=1}^{L-1} h_{\text {trans,pen}}^{(i,i+1)}$ , and $h_{\text {trans,pen}}$ satisfy the following conditions:

1. (i) is a sum of transition rule terms, where all the transition rules act diagonally on in the following sense. Given standard basis states , exactly one of the following holds:

   • • there is no transition from $ab$ to $cd$ at all; or

   • • and there exists a unitary $U_{abcd}$ acting on together with an orthonormal basis for , both depending only on $a,b,c,d$ , such that the transition rules from $ab$ to $cd$ appearing in $h_{\text {trans}}$ are exactly for all i.

2. (ii) is a sum of penalty terms which act non-trivially only on and are diagonal in the standard basis.

In our case, corresponds to Tracks 1–3 and to Tracks 4–6. Transitions from $ab$ to $cd$ will correspond exactly to the transitions shown for Tracks 1–3 in Table 2. While adding new transitions involving Tracks 4–6, we will need to remove some of the transitions in Tracks 1–3, but they will be recovered as restrictions of the new rules to those tracks. (In Table 2, transitions that will be replaced later are marked with an asterisk.) We will define the unitaries $U_{abcd}$ partially, and then complete them to a full unitary. All we have to take care of is, firstly, that the new transition involving the rest of the tracks, when restricted to Tracks 1–3, recover exactly the transitions removed from Table 2; and, secondly, that orthogonality is preserved in the construction.

By the standard form,

(4.33)

Now, if we start with a family of QTM $P_n$ that satisfies part (iii) of Theorem 10, it will be immediate from our construction that the partial definition of all $U_{abcd}$ will only involve elements in the set

(4.34) $$ \begin{align} \mathcal{S} = \left\{0,1,\pm \frac{1}{\sqrt{2}},e^{i\pi\varphi}, e^{i\pi 2^{-{\lvert{\varphi}\rvert}}}\right\}. \end{align} $$

As argued above, the same will hold for the full $U_{abcd}$ , which gives part (vi) in Theorem 32.

4.6.1 QTM transition rules

We first analyse how to incorporate the QTM transition rules into the Hamiltonian. We will simulate the QTM transition rules during the second half of the clock oscillator cycle, when the Track 1 state sweeps from right to left. This is done by including the following transition rule terms (cf. (4.31a)–(4.31c)), where q is any state in $Q/\{q_f\}$ (i.e. we exclude all the transitions out of the QTM’s final state):

(4.35a)

(4.35b)

As in the implementation of the reversible counter TM (Section 4.4), these transition rules implement the Right-moving, Non-moving and Left-moving transitions separately. This time, since the arrow is sweeping to the left, it is the left-moving transitions that are implemented in two stages, first transitioning to an auxiliary state $q_L'\in Q_L'$ , then in a second step transitioning to the corresponding $q_L$ state.

Note that if the QTM head ever ends up at the end of the chain, the transition rules of (4.35a) can never apply, because they require the to be to the right of the QTM head. Thus the final Track 5 tape cell is not used, and the effective tape length available to the QTM for a chain of length $L+3$ is only L rather than ¹⁷ $L+1$ . If the Track 4 QTM head ends up next to the at the very end of the chain, this indicates that the head has stepped off the usable portion of the tape, regardless of the internal state.

We also include the following transition rules involving a left-moving arrow to cover the case where there is no QTM head present:

(4.36)

4.6.2 QTM Unitarity

With the set of transition rule terms defined so far in (4.35a), there is no transition out of the final state $q_f$ of the QTM. There is also no transition out of a QTM configuration in which the QTM head is at the end of the chain, and the next step would move the head to the right, off the end of the chain. The same is true of configurations trying to move the head left when it is located at the beginning of the chain. ¹⁸

Ideally, we would like it if, when the QTM reaches one of these configurations, the clock continued ticking but the encoded QTM did nothing for the remaining time steps. However, simply omitting transitions out of these configurations causes a subtle but important issue relating to unitarity of the quantum transition rules, which will be crucial to the analysis of the resulting Hamiltonian in Section 4.7.

If we complete the partial U (associated with the Track 1–3 transitions ) as defined so far by (4.35a)–(4.37) to a unitary, this will add additional transitions out of the final state $q_f$ , and also out of configurations with the head at the beginning or end of the chain. But this means that, instead of the encoded QTM doing nothing for the remaining time steps after reaching such a configuration, it will continue to evolve in some arbitrary way, depending on the particular choice of completion of U. On the other hand, if we omit transitions out of these configurations, the resulting U will only be a partial isometry, not a full unitary.

It will be important in what follows (Section 4.7) to ensure that the local update rules are extended to a unitary. We would therefore like to use up any remaining time steps in a controlled way, such that the Track 5 QTM tape is left unaltered after the QTM enters $q_f$ or runs out of tape. To this end, we deliberately add additional transitions out of the final state $q_f$ , and also out of configurations with the head at the beginning or end of the chain, which cause the QTM to switch over to running some other, inconsequential computation to use up the remaining time. This time-wasting computation will use Track 6 as its tape, leaving the configuration of the Track 5 QTM tape untouched.

The only requirement on this time-wasting computation is that it must be guaranteed not to halt or run out of tape before it has used up all the remaining time steps of the clock (otherwise we face the same unitarity issue once again). The natural choice is simply to run the same base- $\zeta $ counter computation as the clock (but running on Tracks 4 and 6). The counter TM never halts; it increments the number written on its tape forever, or – when encoded on a finite chain – until it runs out of tape space. Furthermore, since the clock will already have “ticked” for some positive number of time steps before this time-wasting counter TM starts running, the clock counter TM is guaranteed to run out of tape (and hence the clock stop ticking) first.

Transitioning from $q_f$ to the time-wasting counter TM can be accomplished simply by dovetailing the counter TM after the QTM, and encoding this dovetailed machine instead of the original QTM. Concretely, this means we must add to the Hamiltonian more transition rule terms of the form (4.35a) that encode all the transition rules of the counter TM from (4.15). ¹⁹ Note that Track 6 contains additional subscripted variants $\vdash _q$ of the $\vdash $ tape symbol; the time-wasting counter TM transition rules simply ignore the subscript, and treat all of these as a $\vdash $ . (I.e. the counter TM rules that read a $\vdash $ symbol in (4.15) are duplicated for each $\vdash _q$ variant.) These time-wasting counter TM transition rules involve a disjoint set of Track 4 internal states $q\in P'$ to those $q\in Q'$ used by the QTM. Thus the left- and right-hand sides of all time-wasting counter TM (4.35a) transition rules are orthogonal to those encoding the QTM transition rules.

We also add the following transition out of the final state $q_f$ of the original QTM into the initial state $p_\alpha $ of the counter TM, which dovetails the counter TM after the QTM. This transition rule acts on Tracks 1, 4 and 6:

(4.37)

We must also add transitions that switch to running the time-wasting counter TM if the QTM runs out of tape, i.e. if it enters a configuration in which the head is at the beginning of the tape and would move left in the next time step, or one with the head at the end of the chain that would move right. (Though in the case of the proper machines considered in parts (iv) to (vi) of Theorem 32, the former will never occur.) Moving left off the beginning of the tape is particularly easy, both because the head is already at the beginning of the chain, and because left-moving QTM transitions are implemented by first transitioning to an auxiliary $q^{\prime }_L\in Q^{\prime }_L$ state without moving the head. The following transition rule acting on Tracks 1, 2, 4 and 6 accomplishes this:

(4.38)

Note that, to preserve reversibility (unitarity), we must keep a record of which internal state $q^{\prime }_L$ led to the QTM running out of tape. We record this in the $\vdash _q$ symbol written to the Track 6 time-wasting TM tape.

Configurations in which the head steps right off the end of the chain involve slightly more effort, as the head is at the wrong end of the chain to start running the time-wasting counter TM. From Section 4.6, a configuration in which the Track 4 QTM head is at the very end of the chain indicates that the head has stepped right off the usable portion of the Track 5 tape. We first transition from any such configuration into an auxiliary Track 4 head reset state r, which moves the head all the way back to the beginning of the chain, before transitioning into the initial state of the counter TM. This requires three additional sets of transition rules.

We want the first new rule to act on Tracks 1 and 4 at the very end of the chain, and transition into the auxiliary reset state $r_q$ (depending on the state q it was in immediately before). However, we have to make it compatible with the transitions already defined for Tracks 1–3. Hence we include the following transitions acting on Tracks 1,2,4 and 1,2,3,4:

(4.39)

The second new rule also acts on Tracks 1 and 4, and steps the auxiliary r state to the left along with the :

(4.40)

The third acts on on Tracks 1, 2 4 and 6 at the very beginning of the chain, and transitions into the initial configuration of the time-wasting counter TM:

(4.41)

Again, to preserve reversibility, we record in the $\vdash _q$ symbol which internal state caused the QTM to run out of tape.

The transition rules in Table 4 implement all the transitions that will take place for a properly initialised QTM. All of them have the desired form where $ab\rightarrow cd$ is a Track 1–3 transition and $U_{abcd}$ are partial isometries defined by their action on a subset of the computational basis of Tracks 4–6. We can now complete the unitaries $U_{abcd}$ at will. All we have to check is that they do indeed define a partial isometry.

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

The left hand sides of each transition rule in (4.35a)–(4.41) are manifestly orthogonal. The right hand sides of all (4.36)–(4.41) and (4.35b) rules are clearly mutually orthogonal and normalised, and are also orthogonal to the right hand sides of all (4.35) rules.

It remains to show that (4.35) defines an isometry. Recall that there are two sets of (4.35) terms, one encoding the QTM transition rules, and the other the time-wasting counter TM. The left- and right-hand sides of all rules in the QTM set are orthogonal to those of the counter TM set, as they involve disjoint sets of internal states $Q'$ and $P'$ (respectively). Thus it suffices to prove that each set of transition rules considered separately defines an isometry. Since classical reversible TMs are special cases of QTMs, we prove the result for QTMs.

Let denote the state on the RHS of (4.35). Then

(4.42) $$ \begin{align} \begin{aligned} {\lVert{\psi(p,\sigma)}\rVert} &= \sum_{\tau,q_R} {\lvert{\delta(p,\sigma,\tau,q_R,R)}\rvert}^2 + \sum_{\tau,q_N}{\lvert{\delta(p,\sigma,\tau,q_N,N)}\rvert}^2\\ &\qquad + \sum_{\tau,q_L}{\lvert{\delta(p,\sigma,\tau,q_L,L)}\rvert}^2\\ &= {\lVert{\delta(p,\sigma)}\rVert} = 1 \end{aligned} \end{align} $$

by the normalisation condition of Theorem 18, so the right hand sides of (4.35) are normalised.

Similarly, for $(p_1,\tau _1) \neq (p_2,\tau _2)$ ,

(4.43)

by the orthogonality condition of Theorem 18, so the right hand sides of (4.35) are mutually orthogonal. Thus the QTM and time-wasting counter TM transition rules from (4.35) preserve orthonormality, as required.

4.6.3 QTM initialisation sweep

We use penalty terms that only apply during the initialisation sweep to enforce the correct initial configurations of Tracks 4, 5 and 6. For Track 4, we use the following penalty terms, which force a single $q_0$ at the very beginning of the track:

(4.44)

The Track 1 states only ever occur during the initialisation sweep in the final K sites at the right end of the chain. We use these to force the initial configuration of Track 5 to contain K blank symbols at the very end, as required by Theorem 32. ²⁰

(4.45)

Track 6 is forced to be in the all-blank configuration, except for the very first cell which contains a $\vdash $ :

(4.46)

4.7 Analysis

Lemmas 39 and 40 are the key results needed to prove the desired ground state properties of the Hamiltonian we have constructed, thanks to the “Clairvoyance Lemma” from Aharonov et al. [2, Lemma 4.2] (see also [32, Lemma 5.6]). ²¹ Since the Clairvoyance Lemma has previously only been stated and proven for specific constructions, we state and prove a very general version of the Lemma here, which applies to any standard-form Hamiltonian, as defined above.

First, we give some intuition behind the argument, before giving the rigorous proof. The starting point for the proof is that the structure of standard-form Hamiltonians (Definition 41) implies that the invariant subspaces of H decompose as a tensor product across the clock and quantum tracks, with the subspaces spanned by states connected by transition rules.

Furthermore, these invariant subspaces come in three types:

1. (1) subspaces in which all states are illegal (Definition 35), i.e. are in the support of one or more penalty terms;

2. (2) subspaces that contain legal and illegal states; and

3. (3) subspaces that only contain legal states, of which there can be at most one, spanned by the states corresponding to a valid evolution of the QTM.

We can then analyse the spectrum in each type of subspace separately, to show that the ground state energy (minimum eigenvalue) is either $>0$ or $=0$ , respectively, depending on whether the QTM halts or not.

The type 1 invariant subspaces trivially have positive energy from the penalty terms. Lemma 40 guarantees that any legal clock state in a type 2 subspace evolves to an illegal state, implying that all eigenstates in type 2 subspaces also have positive energy.

The analysis of the type 3 subspaces is reminiscent of Kitaev’s original QMA-hardness proof for local Hamiltonians [47]. We first construct a unitary transformation W that brings the Hamiltonian H into the form , where $E_C$ is a tridiagonal almost-Toeplitz matrix acting on the Hilbert space of the classical tracks.

This unitary is constructed by taking a product over the local unitaries corresponding to the local transition rules at each time step of the QTM. It is crucial that we have a local unitary at each time step, and not a partial isometry, otherwise this product would not necessarily be unitary. As seen in Section 3.1, the fact that the QTM is well-formed, normal form and unidirectional guarantees via Theorem 18 that the quantum transition rules define an isometry, thus can always be extended to a local unitary. Note it is not required (nor is it the case) that the clock transitions be extended to a full unitary; only the QTM transitions.

However, as discussed in Section 4.6.2, extending the QTM transition rules to a local unitary requires including the transitions out of the Halting state required of normal-form QTM’s (Definition 15), as well as transitions out of configurations where the QTM has run out of tape space. The time-wasting construction of Section 4.6.2 ensures we still have a handle on the behaviour of the QTM after such a transition. In particular, it will never enter the Halting state if it has not already done so before running out of tape.

Having brought the Hamiltonian into the almost-diagonal form , we can analyse the spectrum of the type 3 invariant subspaces. These subspaces do not contain any illegal states, so are in the kernel of all penalty terms except possibly the Halting penalty. In the absence of the Halting penalty, the minimum eigenvalue in this subspace is therefore given by that of the tridiagonal almost-Toeplitz matrix E, which is 0 by standard results. The associated eigenvector corresponds to the uniform superposition over all legal clock states. Inverting the unitary transformation W, this is exactly the history state of Definition 31.

Therefore, considering all invariant subspaces, if the QTM never halts, the ground state is the 0-energy history state, which lives in a type 3 subspace. If the QTM does halt, so that the type 3 subspace is no longer in the kernel of the Halting penalty term, the minimum eigenvalue in type 3 subspaces can also be bounded away from 0 by standard arguments, thus the ground state energy is necessarily positive.

We now give the rigorous version of this argument.

Lemma 42 (Invariant subspaces)

Let $H_{\text {trans}}$ and $H_{\text {pen}}$ define a standard-form Hamiltonian as in Definition 41. Let $\mathcal {S}=\{S_i\}$ be a partition of the standard basis states of ${\mathcal {H}}_C$ into minimal subsets $S_i$ that are closed under the transition rules (where a transition rule acts on ${\mathcal {H}}_C$ by restriction to , i.e. it acts as $ab \rightarrow cd$ ).

Then ${\mathcal {H}} = \left (\bigoplus _S \mathcal {K}_{S_i}\right ){\otimes }{\mathcal {H}}_Q$ decomposes into invariant subspaces $\mathcal {K}_{S_i}{\otimes }{\mathcal {H}}_Q$ of $H = H_{\text {pen}} + H_{\text {trans}}$ where $\mathcal {K}_{S_i}$ is spanned by $S_i$ .

Proof. $H_{\text {pen}}$ is diagonal in the standard basis by definition (part (ii) of Definition 41), so $\mathcal {K}_{S_i}{\otimes }{\mathcal {H}}_Q$ are trivially invariant under $H_{\text {pen}}$ . But, by the form of the transition rule terms (part (i) of Definition 41), the image of a standard basis state under $H_{\text {trans}}$ has support only on standard basis states of ${\mathcal {H}}_C$ that are reachable by transition rules from . Closure of $\mathcal {K}_{S_i}{\otimes }{\mathcal {H}}_Q$ under $H_{\text {trans}}$ is then immediate from the definition of $S_i$ .

Lemma 43 (Clairvoyance Lemma)

Let $H = H_{\text {trans}} + H_{\text {pen}}$ be a standard-form Hamiltonian as specified in Definition 41, and let $\mathcal {K}_S$ be defined as in Lemma 42. Let $\lambda _0(\mathcal {K}_S)$ denote the minimum eigenvalue of the restriction $H\vert _{\mathcal {K}_S{\otimes } {\mathcal {H}}_Q}$ of $H = H_{\text {trans}} + H_{\text {pen}}$ to the invariant subspace $\mathcal {K}_S{\otimes }{\mathcal {H}}_Q$ .

Assume that there exists a subset $\mathcal {W}$ of standard basis states for ${\mathcal {H}}_C$ with the following properties:

1. (i) All legal standard basis states for ${\mathcal {H}}_C$ are contained in $\mathcal {W}$ .

2. (ii) $\mathcal {W}$ is closed with respect to the transition rules.

3. (iii) At most one transition rule applies in each direction to any state in $\mathcal {W}$ .

4. (iv) For any subset $S\subseteq \mathcal {W}$ that contains only legal states, there exists at least one state to which no backwards transition applies.

Then each $\mathcal {K}_S$ falls into one of the following categories:

1. (1) S contains only illegal states, and $\lambda _0(\mathcal {K}_S) \geq 1$ .

2. (2) S contains both legal and illegal states, and $\lambda _0(\mathcal {K}_S) = \Omega (1/{\lvert {S}\rvert }^3)$ .

3. (3) S contains only legal states, and $\lambda _0(\mathcal {K}_S) = 0$ . The corresponding eigenspace is

   (4.47)

   
   where are the states in S, is any state in ${\mathcal {H}}_Q$ , and where $U_t$ is the unitary on ${\mathcal {H}}_Q$ appearing in the transition rule that takes to . All other states in $\mathcal {K}_S{\otimes }{\mathcal {H}}_Q$ have energy at least $\Omega (1/{\lvert {S}\rvert }^2)$ .

To prove this, we will need Kitaev’s geometrical lemma:

Lemma 44 (Geometrical Lemma – Lemma 14.4 in [47])

Let $A,B \geq 0$ be positive semidefinite operators such that , and . Then

(4.48) $$ \begin{align} A + B \geq 2\mu\sin^2\left(\frac{\theta}{2}\right) \end{align} $$

where

(4.49)

Proof of Clairvoyance Lemma 43

Case (1) is trivial since for any illegal standard basis state .

Now consider cases (2) and (3). By assumption, all legal standard basis states of ${\mathcal {H}}_C$ are contained in $\mathcal {W}$ , which is closed under transition rules. Thus closure of S (Lemma 42) implies $S \subseteq \mathcal {W}$ . Consider the directed graph of states in $\mathcal {W}$ formed by adding a directed edge between pairs of states connected by transition rules. By assumption, only one transition rule applies in each direction to any state in $\mathcal {W}$ , so the graph consists of a union of disjoint paths (which could be loops in case (2)). Minimality of S (Lemma 42) implies that S consists of a single such connected path.

Let $t=0,\dots ,|S|-1$ denote the states in S enumerated in the order induced by the directed graph. $H_{\text {trans}}$ then acts on the subspace $\mathcal {K}_S{\otimes }{\mathcal {H}}_Q$ as

(4.50)

where $U_t$ is the unitary on ${\mathcal {H}}_Q$ appearing in the transition rule that takes to . $T = {\lvert {S}\rvert }-1$ if the path in S is a loop, otherwise $T = {\lvert {S}\rvert }-2$ .

Consider a single term from (4.50). Defining the unitary , we have

(4.51)

Thus, whether the path in S forms a loop or not, we have ²²

(4.52)

with equality if the path is not a loop.

Defining the unitary

(4.53)

we have where

(4.54) $$ \begin{align} E = \begin{pmatrix} \frac{1}{2} & -\frac{1}{2} & 0 & \dots & & \dots & 0 & 0 \\ -\frac{1}{2} & 1 & -\frac{1}{2} & \ddots & & & & 0 \\ 0 & -\frac{1}{2} & 1 & -\frac{1}{2} & & & & \vdots \\ \vdots & \ddots & -\frac{1}{2} & 1 & \ddots & & & \\ & & & \ddots & \ddots & & \ddots & \vdots \\ \vdots & & & & & \ddots & \ddots & 0 \\ 0 & & & & \ddots & \ddots & 1 & -\frac{1}{2} \\ 0 & 0 & \dots & & \dots & 0 & -\frac{1}{2} & \frac{1}{2} \end{pmatrix}. \end{align} $$

The matrix E is the Laplacian of the random walk on a line, and it is well known that its eigenvalues are given by $\lambda _k = 1-\cos q_k$ where $q_k = k\pi /{\lvert {S}\rvert }$ , $k=0,\dots ,{\lvert {S}\rvert }-1$ , with corresponding eigenvectors [47]. Thus

(4.55)

where for any .

First consider case (2). Take $A = H_{\text {path}}$ and $B = H_{\text {pen}}|_{\mathcal {K}_S{\otimes }{\mathcal {H}}_Q}$ in Lemma 44. We have and . Furthermore, since S contains at least one illegal state in case (2), we have and

(4.56)

where is the projector onto and we have used the fact that $B = H_{\text {pen}}|_{\mathcal {K}_S{\otimes }{\mathcal {H}}_Q}$ is diagonal in the standard basis. Invoking Lemma 44, we obtain

(4.57) $$ \begin{align} \left(H_{\text{trans}} + H_{\text{pen}}\middle)\right\vert{}_{\mathcal{K}{\otimes}{\mathcal{H}}_Q} \geq H_{\text{path}} + H_{\text{pen}}\vert_{\mathcal{K}{\otimes}{\mathcal{H}}_Q} = \Omega(1/{\lvert{S}\rvert}^3), \end{align} $$

thus $\lambda _0(\mathcal {K}_S) = \Omega (1/{\lvert {S}\rvert }^3)$ as claimed.

Finally, consider case (3). Since S contains only legal states in this case, $H_{\text {pen}}\vert _{\mathcal {K}_S{\otimes }{\mathcal {H}}_Q} = 0$ . Furthermore, by condition (iv) the states in S cannot form a loop, so . The claim in the Lemma now follows from the form of the eigenvalues and kernel of E, given above.

Note that the proof of the Clairvoyance Lemma relied crucially on unitarity of the operators $U_{abcd}$ appearing in the transition rules (see Lemma 42). In particular, it is not sufficient for the $U_{abcd}$ to be partial isometries. That would not allow us to unitarily transform $H_{\text {trans}}\vert _{\mathcal {K}_S{\otimes }{\mathcal {H}}_Q}$ into using the unitary W in (4.53) and (4.54). Thus, in order to apply the Clairvoyance Lemma 43, we must complete the quantum parts of the transition rules to a full unitary. This necessitates the “time-wasting” construction in Section 4.6.2 (or similar).

We are finally in a position to prove Theorem 32, the main result of this section. As commented above, let and be the Track 1–3 and Track 4–6 Hilbert spaces, respectively, for a chain of length L, as specified in (4.6). Let be the sum of all the transition rule terms defined in Tables 2 and 4 (omitting those marked in Table 2) after completing to a full unitary so that the resulting Hamiltonian is standard-form. Let be the sum of all penalty terms defined in Tables 1 and 3, and be the sum of all Track 4–6 initialisation penalty terms defined in Table 5.

Table 5 Initialisation illegal pairs for Tracks 4–6.

Define the standard-form (Definition 41) Hamiltonian $H(L) = H_{\text {trans}}(L) + H_{\text {pen}}(L) \in {\mathcal {H}}_C{\otimes }{\mathcal {H}}_Q$ on a chain of length L, where $H_{\text {trans,pen}} = \sum _{i=1}^{L-1} h_{\text {trans,pen}}^{(i,i+1)}$ , and similarly define $H_{\text {init}}(L) := \sum _{i=1}^{L-1} h_{\text {init}}^{(i,i+1)}$ .

Proposition 45 (Unique ground state)

The unique 0-energy eigenstate of $\bigl (H_{\text {trans}}(L) + H_{\text {pen}}(L) + H_{\text {init}}(L)\bigr )\bigl |_{S_{\!\text {br}}}\bigr .$ is the computational history state

(4.58)

where $T = \Omega \left (L\,\zeta ^L\right )$ , is the initial configuration of the QTM with the unary representation of the number $L-K-3$ as input, and is the sequence of states produced by evolving under the QTM and time-wasting counter TM transition rules (where each such state is duplicated $O(L)$ times in succession in the sequence).

Proof. Let us first apply the Clairvoyance Lemma to $\bigl .\bigl (H_{\text {trans}}(L) + H_{\text {pen}}(L)\bigr )\bigr |_{S_{\!\text {br}}}$ . We have to check that $h_{\text {trans}}$ and $h_{\text {pen}}$ fulfil the requirements of the Lemma.

Take ${\mathcal {H}}_C$ to be the Hilbert space of Tracks 1–3, and ${\mathcal {H}}_Q$ the Hilbert space of Tracks 4–5. Define $\mathcal {W}$ to be the set of all well-formed Track 1–3 standard basis states. Any state that is not well-formed violates an illegal pair enforcing a regular expression, so all legal Track 1–3 states are well-formed. $\mathcal {W}$ therefore fulfils condition (i) of Lemma 43. By Lemma 39, the set of well-formed states is closed under the transition rules and at most one transition rule applies in each direction to any well-formed state, so $\mathcal {W}$ fulfils conditions (ii) and (iii) of Lemma 43. Finally, by Lemma 40, the only subset of legal Track 1–3 standard basis states that is closed under the transition rules is the set of clock states , which has one state to which no backward transition applies, and one state to which no forward transition applies. So $\mathcal {W}$ also fulfils condition (iv) of Lemma 43.

All penalty terms are diagonal in the standard basis, as required by Lemmas 42 and 43, and all transition rules are of the form required in Lemma 43, by construction. $h_{\text {trans}}$ and $h_{\text {pen}}$ therefore fulfil all the requirements of Lemmas 42 and 43.

Invoking the Clairvoyance Lemma 43, the 0-energy eigenspace of $(H_{\text {trans}} + H_{\text {pen}})|_{S_{\!\text {br}}}$ has the form

(4.59)

where and is any state of ${\mathcal {H}}_Q$ .

Now we include the $h_{\text {init}}$ terms, and show that must be as claimed in Proposition 45. For $0 \leq t \leq 2L-1$ , the clock states consist of an that sweeps from left to right and back along the chain (where for the time steps $t=L+1,\dots ,L+K$ of this sweep, the arrow is in the states , respectively). The transition rules that apply during the initialisation sweep act trivially on Tracks 4–5, so for $t \leq 2L-1$ . By construction, the $h_{\text {init}}$ penalty terms from Table 5 give an additional energy penalty to any Track 4–5 states that are not in the desired initial QTM configuration when the sweeps past.

Consider any Track 4–5 state that is not the desired initial QTM configuration. Then there is some $0 \leq t \leq 2L-1$ for which . Noting that the overall Hamiltonian $H \geq 0$ and the are mutually orthogonal, this immediately implies that the unique 0-energy state is that given in (4.58).

The initial state on Track 4 matches the regular expression . The transition rules $U_t$ preserve this form – which allows us to identify Tracks 4 and 5 with the head and tape configuration of the QTM – and by construction implement one step of the QTM or time-wasting counter TM in each sweep (all other unitaries applied to Tracks 4 and 5 during each sweep being identities).

Finally, the clock counter TM counts up to $\Omega (\zeta ^L)$ before it runs out of tape, and each step of this TM requires one complete sweep of the Track 1 arrow which takes $\Omega (L)$ steps. Thus $T = \Omega (L\,\zeta ^L)$ as claimed. ²³ ) We are done.

The local Hilbert space dimension in (4.6) manifestly depends only on the alphabet size and internal states of the counter TM encoded on Tracks 2 and 3, the QTM encoded on Tracks 4 and 5, and the time-wasting counter TM encoded on Tracks 4 and 6. However, the alphabet size and internal state space of both counter TMs depends only on the base $\zeta $ we choose, and this is completely determined by the alphabet size and internal state space of the QTM ( $\zeta ={\lvert {\Sigma \times Q}\rvert }$ ). Thus the local Hilbert space dimension d depends only on the alphabet size and number of internal states of the QTM, as claimed in part (i) of Theorem 32.

Since the local interaction h of our Hamiltonian is constructed by summing transition rule terms and penalty terms, and $h_{\text {trans}},h_{\text {pen}},h_{\text {init}} \geq 0$ , we have $h \geq 0$ . But we have shown that the overall Hamiltonian has a 0-energy eigenstate, hence it is frustration-free, satisfying part (ii) of Theorem 32.

Proposition 45 implies that the unique ground state of $H|_{S_{\!\text {br}}}$ has the computational history state form claimed in part (iii) of Theorem 32. Moreover, since the history state encodes $\Omega ({\lvert {\Sigma \times Q}\rvert }^L)$ complete sweeps of the Track 1 arrow, and the QTM is advanced by exactly one step in each right-to-left sweep, the computational history state encodes $\Omega ({\lvert {\Sigma \times Q}\rvert }^L)$ steps of the computation. If the QTM halts before this, it transitions by the $q_f$ rule of (4.37) to running the time-wasting counter TM, which never alters the QTM tape encoded on Track 5. Track 5 is therefore only in the state $q_f$ for one time step. Thus part (iv) of Theorem 32 is also satisfied.

Now imagine that the QTM reaches a configuration in which the next step would move the head before the starting cell. (Though in the case of the proper machines considered in parts (iv) to (vi) of Theorem 32, this will never occur.) Consider the corresponding in the computational history state. The QTM transition rules do not alter Track 6, so Track 6 is still in its initial configuration. Since the QTM has deterministic head movement, at no point during the evolution is its head ever in a superposition of locations. is therefore of the form:

(4.60)

where are unnormalised Track 5 QTM tape states, and all configurations in the superposition would step the QTM head left in the next time-step. The $q_f$ transition rule from (4.37) therefore applies to all states in the superposition, and the next state must have the form:

(4.61)

Thenceforth, only time-wasting counter TM transition rules apply.

A very similar argument applies if the QTM reaches a configuration in which the head moves beyond cell L. Since the time-wasting counter TM transitions never alter Track 5, part (v) of Theorem 32 follows.

This concludes the proof of Theorem 32, and this section.

5 Quasi-periodic tilings

In order to ultimately prove the required spectral properties of our final Hamiltonian, we require significantly stronger properties of quasi-periodic tilings than those used to prove tiling results. In particular, we will need strong “rigidity” results, which show that the quasi-periodic structure is in a sense robust to errors. As far as we are aware, these rigidity results are new. All the tiling results used in the proof of our main results are gathered in this section.

We exploit the very particular properties of a quasi-periodic tiling due to Robinson, which we briefly review in the following section. The Robinson tiling has a hierarchical geometric structure that lends itself to inductive proofs of the required rigidity results.

5.1 Robinson’s tiling

We now describe Robinson’s quasi-periodic tiling. It was discovered by Robinson in 1971 [70] as a tool to simplify Berger’s proof of the undecidability of the tiling problem [15].

Robinson’s tiling is based on the five basic tiles showed in Figure 6 and all rotations and reflections thereof. Tile (a) is called a cross, whereas tiles (b)–(e) are called arms. In a valid tiling, arrow heads must meet arrow tails. As drawn, cross (a) is said to face up/right. With this orientation convention, two consecutive crosses (meaning with no other cross in between them) in the same row or column are said to be facing each other, or to be back-to-back, as shown in Figure 7. An arm is said to point in the direction of its unique complete central arrow. Arrows that do not start or end in the mid-point of a square’s side are called side arrows.

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

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

For each one of the five basic tiles of Figure 6, we introduce two possible colours, red or green, to each of the side arrows (note that there is one tile without colour) with the following restrictions: colours must match between adjacent side arrows; at most one colour may be used horizontally and at most one colour may be used vertically; for the cross, the same colour must be used in both directions; for tile (b) one colour must be used horizontally and the other colour vertically. Moreover, we impose the restriction that green crosses must appear in alternate positions in alternate rows (and potentially in other positions too).

The latter can be achieved by adding parity markings to the above tiles: the additional arrows showed in Figure 8, which should match properly in any valid tiling, with the following rules: parity marking (a) is associated with green crosses, parity marking (b) with horizontal green arrows, and (c) with vertical green arrows. Parity marking (d) is associated with all tiles. It is important to remark here that parity markings “live in a different layer” than the five basic tiles. That is, arrows from the parity markings must match only those from the parity markings and arrows from the basic tiles must match only those from the basic tiles. Note that the parity markings Figure 8 already form a closed set under rotation and reflection—(c) is the rotation of (b)—in contrast to the five basic tiles of Figure 6 which are extended to the full set by including all rotations and reflections.

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

Figure 9 A possible Robinson tiling of the plane.

If we now draw only the red coloured lines, one possible tiling of the plane looks like Figure 9, which has the crucial (for our purposes) quasi-periodic structure consisting of interlocking squares of increasing size.

Let us try to explain briefly (full details can be found in [70]) how Figure 9 emerges, and the remaining freedom it allows in constructing valid tilings of the plane. The fact that crosses must appear in alternate rows in alternate positions, together with the form of the five basic tiles, means that any given cross completely determines the structure of the $3\times 3$ square constructed in the direction it faces. For example, assume we start with a green cross facing left/down. Then we are forced to complete the $3\times 3$ square having the cross we started with as the top/right corner, as shown in Figure 10. Furthermore, the central tile must be a red cross, with the only freedom being the choice of direction it faces.

Figure 10 Left: 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.)

Once the direction of the central cross is fixed, the $7\times 7$ square obtained by extending the $3\times 3$ square in the direction this red cross faces is fixed as shown in Figure 10. The green cross in the central position is forced, with the only freedom again being the choice of direction it faces. Continuing this procedure gives a tiling similar to that shown in Figure 9. It consists of a quasi-periodic structure of squares, formed by a continuous line of a single colour going through all the tiles on the perimeter of the square. These are called borders and have sizes $4^n$ (which—following Robinson’s terminology—means that the distance between two of the facing crosses delimiting the border is $4^n+1$ ) repeated with period $2^{2n+1}$ , for all .

Such a tiling can tile the whole plane, a half-plane or a quarter-plane, depending on how we sequentially choose the orientation of the central crosses. Lines between valid half or quarter planes must consist only of arms. If the tiling divides the plane into two half-planes, the patterns in these half-planes may be shifted relative to one another by an arbitrary even number of cells. In this case, the line separating the two half-planes is called a fault (see Figure 11). However, if a half-plane is further divided into two quarter-planes, no further shift is possible between these quarter-planes.

Figure 11 Left: 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).

5.2 Rigidity of the Robinson tiling

We have just seen that with the original Robinson tiles, the quasi-periodic pattern of borders does not necessarily extend throughout the entire plane; there can be a fault line between two half-planes, with “slippage” between the patterns on either side of the fault (see Section 5.1 and [70, § 8] and Figure 11).

It will be convenient to slightly modify the Robinson tiles in order to prevent fault lines. To this end, wherever one of the five basic tiles does not have side-arrows, we add dashed side-arrows parallel to the solid central arrows (see Figure 12). We then extend the five basic tiles to the full tile set by rotation and reflection, adding parity markings, and adding red and green colourings to the solid side arrows, exactly as in Section 5.1. We refer to these as the modified Robinson tiles. (Similar modifications to the Robinson tile set appear elsewhere in the literature, e.g. in [58].)

Figure 12 The basic tiles of the modified Robinson tiling.

Since the all original tile markings are still present, any tiling using the modified tiles must also be a valid tiling using the original tiles if the dashed side-arrows are ignored. It is easy to verify that, for any tiling in which the $2^n$ -borders repeat periodically throughout the plane for all n (i.e. any tiling that does not contain a fault line), dashed side-arrows can be added to make it into a valid tiling using the modified tiles.

However, if the tiling contains a fault line, there is no way to consistently add dashed side-arrows. To see this, assume without loss of generality that the fault line is vertical. Then there must exist two back-to-back crosses on either side of the fault that are not aligned, so that one points up and the other down (see Figure 11). Consider the cross to the left of the fault line. The dashed side-arrow on this cross that points to the right forces a dashed arm to extend in that direction, towards the other cross. Similarly, the left-pointing dashed side-arrow on the cross to the right of the fault forces a dashed arm to extend to the left. These dashed arms must meet somewhere between the two crosses. But, since one cross points up and the other down, one of these arms has the dashed side-arrow on top, the other has it on the bottom, so there is no way to consistently join up the arms.

The crucial property we will use is that the Robinson tiling has a very “rigid” structure. Even if we start from a tile configuration that contains a defect (a pair of non-matching adjacent tiles), outside of a ball around the defect, the defect has no effect on the pattern of borders that appears in the rest of the tiling. The following Lemmas make this rigorous. ²⁴

Lemma 46 (Cross rigidity)

In any tiling of a connected region with Robinson tiles, crosses must occur in alternate columns and in alternate rows.

Proof. Immediate from the observation that, for each “parity tile” in Figure 8, its neighbour in each direction is uniquely defined.

Lemma 47 (Robinson rigidity)

Consider a connected region of a 2D square grid made up of square blocks of size $2^{n+1}\times 2^{n+1}$ . Any tiling of such a region with modified Robinson tiles must contain a periodic pattern of $2^n$ -borders (some of which may be incomplete due to boundaries), repeating horizontally and vertically with period $2^{n+1}$ . That is, the tiling must contain the same periodic pattern of $2^n$ -borders as a section of the tiling of the infinite plane, up to translation and defects that do not affect the $2^n$ borders.

Proof. By Lemma 46, crosses must occur in alternate rows and columns throughout the region being tiled. Following Robinson [70], we refer to these crosses as “1-squares”. (Note that there may be additional crosses in the tiling that do not constitute 1-squares.) Pick an orientation for one of these 1-square crosses. Its solid side-arrows force a solid arm to extend in the directions it faces. Unless there is insufficient space to the boundary of the region, there must be a cross two cells away in the direction of each arm. Just as in Robinson [70, §3], these solid arms force the orientation of any two facing crosses to be mirror images.

Meanwhile, the dashed side-arrows force a dashed arm to extend in the directions that the cross faces away from. Again, these arms force the orientations of any back-to-back crosses to be mirror images. Thus, as soon as we pick the orientation of a single 1-square cross, the orientations of all adjacent crosses are forced, and hence the orientations of all 1-square crosses throughout the connected region.

Base case

Consider first the case $n=1$ with $4\times 4$ blocks. Since orientations of adjacent pairs of 1-square crosses are mirror images of each other, they are forced to form groups of four facing towards the centre of a $3\times 3$ block. As in Robinson [70, §3], these blocks must be completed to form “3-squares” with 2-borders running around the edges and crosses in the centre. (The orientation of the central crosses is not fixed.) In our modified Robinson tiles, the dashed side-arrows also force the orientations of back-to-back crosses to be mirror images, which forces adjacent 3-squares to be aligned. Thus the pattern of complete 2-borders must repeat horizontally and vertically with period $4$ throughout the region.

However, in general some of the 1-squares will be too close to the boundaries of the region to form complete 3-squares. We need to show that these still force partial 2-borders. If a 1-square faces a boundary and is located at that boundary, then there is no further section of 2-border in that direction in any case, and we have nothing to show. If a 1-square faces a boundary and is more than two cells away from it, there must be another 1-square facing it before reaching the boundary, and the section of 2-border between them must be completed as usual. The only interesting case is if a 1-square faces a boundary one cell away from it. In this case, the solid side-arrows still force the cell between the cross and the boundary form an arm extending to the boundary. The only difference is that there is no facing cross in that direction to force the side-arrows of the arm to point inwards; they could instead point towards the boundary. Thus any of the arm tiles with solid side-arrows (in a suitable orientation) can be used to form this piece of the 2-border. For our purposes, we consider any of these to still constitute a section of the 2-border. So partial 2-borders are still forced at the boundaries.

This completes the proof for the base case $n=1$ . It will be important for later to note that, if a partial 2-border is large enough to contain the cell that would normally be at the centre of the border, then the central cross is still forced in that cell. To see this, note that because our region is made up of adjacent square blocks, there must be arms on at least two sides of the central cell (not necessarily opposite sides, if the partial 2-square is located in a corner of the region). Regardless of which tile is used to form these arms, the central arrows perpendicular to the arms must face outwards as usual, because the solid side-arrows on the arms must be on the side away from the central cell. But the only tile that has outward-facing central arrows on adjacent sides is the cross, so it is forced.

$\mathbf {n=2}$ case

Before proving the general case, it is instructive to consider the next case $n=2$ (with $8\times 8$ blocks). We can always divide each $8\times 8$ block into four $4\times 4$ blocks and apply the previous argument, so the 2-borders must repeat horizontally and vertically with period 4, throughout the region, with a cross at the centre of each 2-border (whether partial or complete). Each $8\times 8$ block must therefore contain at least one complete 2-border, and all 2-borders must be aligned (hence their central crosses are also aligned).

Pick an orientation for one of these central crosses. The side-arrows of this cross force solid arms extending in the directions that the cross faces, and dashed arms extending in the directions it faces away from. Now, the only tile at which an arm can terminate is the cross. But there can be no crosses between adjacent 2-borders. Thus the arms must extend all the way from a central cross to its neighbours, again forcing the orientation of both facing and back-to-back crosses to be mirror images of each other, so that they form groups of four facing towards the centre of a $5\times 5$ block. As in Robinson [70, §3], these blocks must be completed to form “5-squares” with 4-borders running around the edges and crosses in the centre. As before, the dashed arms force adjacent 5-squares to be aligned. So the pattern of complete 4-borders repeats horizontally and vertically throughout the region, with period 8.

It remains to consider crosses that are too close to the boundaries to form complete 4-borders. If the central cross of a 2-border faces a boundary (rather than another cross), its solid side-arrows still force an arm that extends towards the boundary. The only tile that can terminate an arm is a cross. However, we cannot place a cross anywhere within the 3-square surrounding the central cross, as it would break the tiling within the 3-square. The only remaining possibility is to place a cross in the one-cell-wide corridor that runs along each side of a 3-square. However, where an arm intersects a 2-border it must point outwards, which prevents placing a cross in the corridor. Thus the arm must be extended all the way to the boundary to form a partial 4-border (with some additional freedom in which arm tiles are used to form this section of 4-border).

This proves the Lemma for $n=2$ . As in [70, § 3], a cross is forced at the centre of all complete 4-borders. If a partial 4-border is large enough to surround the cell that would be at the centre of the complete border, a cross is forced there too. To see this, observe that for partial borders of this size, the centre cell has partial 4-borders on at least two sides. The central arrows perpendicular to a border necessarily have arrow tails on the inside of the border. These force an arm extending back towards the central cell. That cell therefore has arrow tails on at least two sides, and the central cross is forced.

General case

The argument for general n is very similar to the argument for the $n=2$ case, and proceeds by induction on n. Assume for induction that the pattern of $2^{n-1}$ -borders repeats horizontally and vertically with period $2^n$ in any connected region made up of $2^n\times 2^n$ blocks, and that a cross is forced at the centre of each of those $2^{n-1}$ -borders (whether partial or complete).

Now consider a connected region made up of $2^{n+1}\times 2^{n+1}$ blocks. We can always divide each block into four $2^n\times 2^n$ blocks. So, by assumption, the pattern of $2^{n-1}$ -borders must repeat horizontally and vertically with period $2^n$ throughout the region, with a cross at the centre of each (partial or complete) $2^{n-1}$ -border. Each $2^{n+1}\times 2^{n+1}$ block therefore contains at least one complete $2^{n-1}$ -border, and adjacent borders (hence also their central crosses) are aligned. The solid and dashed side-arrows of these central crosses force arms extending between adjacent crosses, which in turn force the orientations of adjacent crosses to be mirror images. Thus the arms extending between facing crosses form $2^n$ -borders, and adjacent $2^n$ -borders are aligned. The pattern of $2^n$ -borders therefore repeats horizontally and vertically throughout the region, with period $2^{n+1}$ .

For central crosses that face a boundary instead of an adjacent cross, the solid side-arrows on the cross still force an arm extending towards the boundary. To show that this arm necessarily extends all the way to the boundary, we must show that it is impossible to place a cross anywhere along the arm. Within the $(2^n-1)$ -square surrounding the central cross, we cannot place a cross along the arm without breaking the tiling within $2^n-1$ -square (cf. [70, § 3]). Thus the arm must extend to the boundary of this $(2^n-1)$ -square. Similarly, we cannot place a cross along the arm anywhere within the adjacent $(2^n-1)$ -square. So, if the arm reaches the adjacent $(2^n-1)$ -square, it must continue onwards to the boundary. The only remaining possibility is to place a cross in the one-cell-wide corridor between the adjacent $(2^n-1)$ -squares. However, the arm necessarily points out of the $(2^n-1)$ -square, which prevents placing a cross in the corridor.

Finally, for the induction step we must show that a cross is forced at the centre of each (complete or partial) $2^n$ -border. The argument applies to any border that extends sufficiently far to surround its centre cell (which includes complete borders). The central cell has (complete or partial) $2^n$ -borders on at least two sides. The central arrows perpendicular to a border necessarily have arrow tails pointing inwards, which force arms extending back towards the central cell. That cell therefore has arrow tails on at least two sides, forcing the central cross.

Together with the base case $n=1$ , this completes the proof.

We refer to the top edge of a $2^n$ -border as a $2^n$ -segment. ²⁵

Lemma 48 (Segment bound)

The number of $2^n$ -segments in a tiling of an $L\times H$ rectangle (width L, height H) using modified Robinson tiles is $\ge \lfloor H/2^{n+1}\rfloor \bigl (\lfloor L/2^{n+1}\rfloor -1\bigr )$ and $\le \bigl (\lfloor H/2^{n+1}\rfloor +1 \bigr )\lfloor L/2^{n+1}\rfloor $ for all n.

Proof. Lemma 47 implies that the tiling must contain the usual periodic pattern of $2^n$ -borders, up to translation. The result then is a trivial consequence of the fact that borders repeat vertically and horizontally with period $2^{n+1}$ .

The following Lemma is the key rigidity result that we will need later. It shows that a defect in the tiling (i.e. a non-matching pair of adjacent tiles) cannot affect the pattern of $2^n$ -borders in the tiling outside a ball of size $2^{n+1}$ centred on the defect.

Lemma 49 (Segment rigidity)

In any tiling of an $L\times H$ rectangle (width L, height H) with d defects using modified Robinson tiles, the total number of $2^n$ -segments is at least $\lfloor H/2^{n+1}\rfloor \bigl (\lfloor L/2^{n+1}\rfloor -1\bigr ) - 2d$ .

Proof. Divide the $L\times H$ rectangle into contiguous square blocks of size $2^{n+1} \times 2^{n+1}$ , with $\lfloor L/2^{n+1}\rfloor $ blocks in each row and $\lfloor H/2^{n+1}\rfloor $ in each column. (Any leftover cells play no further role in the argument.) Delete any block that contains at least one defect (arbitrarily assigning defects that occur at block boundaries to the bottom/left block). Consider any horizontal row of blocks. If the row contains $d_i$ deleted blocks, those missing blocks divide it into at most $d_i+1$ strips of height $2^{n+1}$ .

Since each strip is a connected, defect-free region made up of $2^{n+1} \times 2^{n+1}$ blocks, Lemma 47 implies that it must be tiled with the usual periodic pattern of $2^n$ -borders, up to translations. The strip may be connected to strips in adjacent rows, in which case we are not free to translate the tiling in each strip independently. Nonetheless, we can lower-bound the number of $2^n$ -segments by allowing the tiling within each strip to be translated independently, and minimising over all such translations.

Each strip has height $2^{n+1}$ , so, regardless of how the pattern is translated vertically, it must contain exactly one row of $2^n$ -segments. The minimum number of segments within a strip of block-length l is $l-1$ (obtained by translating the pattern horizontally so that there are incomplete segments at the beginning and end of the strip). In other words, each block in the strip effectively contributes one segment to the total, except for the block at the right end of the strip, which does not contribute (we assign the segment between adjacent blocks to the left one).

If the row contains $d_i$ deleted blocks, those missing blocks divide it into at most $d_i+1$ strips. ²⁶ Thus the row contains $\lfloor L/2^{n+1}\rfloor - d_i$ non-deleted blocks, with at most $d_i+1$ of them located at ends of the strips. The whole row therefore contains at least $\lfloor L/2^{n+1}\rfloor - d_i - \bigl (d_i+1\bigr ) = \lfloor L/2^{n+1}\rfloor - 2d_i - 1$ segments.

Summing over all $\lfloor H/2^{n+1}\rfloor $ rows, and noting that the total number of deleted blocks cannot be more than the total number of defects, we obtain the claimed lower bound on the total number of $2^n$ -segments.

6 Putting it all together

6.1 Undecidability of the g.s. energy density

To prove our first main result, Theorem 5, we will prove a sequence of lemmas which allow us to combine together the Hamiltonian constructions from the previous sections, and progressively build up the final Hamiltonian.

We will repeatedly need to refer to 1D translationally invariant Hamiltonians with a particular set of properties. For conciseness, we will call these “Gottesman-Irani Hamiltonians”, captured in the following definition:

Definition 50 (Gottesman-Irani Hamiltonian)

Let be a finite-dimensional Hilbert space with two distinguished orthogonal states labelled , . A Gottesman-Irani Hamiltonian is a 1D, translationally invariant, nearest-neighbour Hamiltonian $H_q(r)$ on a chain of length $r\geq 2$ described by Hilbert space with local interaction , which satisfies the following properties:

1. (i) $h_q\geq 0$ .

2. (ii) .

3. (iii) $\lambda _0(r) := \lambda _0(H_q(r)|_{S_{\!\text {br}}}) < 1$ , where ${S_{\!\text {br}}}$ is the subspace of states with fixed boundary conditions at the left and right ends of the chain, respectively.

4. (iv) and $\sum _{n=1}^\infty \lambda _0(4^n) < 1/2$ .

5. (v) $\lambda _0(H_q(r)|_{S_<}) = \lambda _0(H_q(r)|_{S_>}) = 0$ , where $S_<$ and $S_>$ are the subspaces of states with, respectively, a at the left end of the chain or a at the right end of the chain.

Lemma 51 (Tiling + quantum layers)

Let be the local interactions of a 2D tiling Hamiltonian $H_c$ , with two distinguished states (tiles) . Let be the local interaction of a Gottesman-Irani Hamiltonian $H_q(r)$ , as in Definition 50. Then there is a Hamiltonian on a 2D square lattice with nearest-neighbour interactions with the following properties: For any region of the lattice, the restriction of the Hamiltonian to that region has an eigenbasis of the form , where is a product state representing a classical configuration of tiles. Furthermore, for any given , the lowest energy choice for consists of ground states of $H_q(r)$ on segments between sites in which contains an and an , a 0-energy eigenstate on segments between an or and the boundary of the region, and ’s everywhere else.

Proof. The idea is to sandwich the two Hamiltonians $H_c$ and $H_q$ together in two “layers”, so that the overall Hamiltonian acts as $H_c$ on the c-layer, with constraints between the layers that force low-energy configurations of the q-layer to be in the auxiliary “blank” state, except between pairs of and states appearing in the same row of the c-layer, where the q-layer acts like $H_q$ on that line segment.

To this end, define the local Hilbert space to be . The Hamiltonian H is defined in terms of the two-body interactions as follows:

(6.1a)

(6.1b)

(6.1c)

(6.1d)

(6.1e)

(6.1f)

(6.1g)

(6.1h)

(6.1i)

(6.1j)

(6.1k)

where , and are the identity operators on the corresponding Hilbert spaces. Operators living on ${\mathcal {H}}_q$ , or ${\mathcal {H}}_q\otimes {\mathcal {H}}_q$ , such as $h_q$ in (6.1c), are assumed to be extended in the trivial way (they are defined as zero in the extra sectors) to the larger space ${\mathcal {H}}_q \oplus {\mathcal {H}}_e$ , or $({\mathcal {H}}_q \oplus {\mathcal {H}}_e)\otimes ({\mathcal {H}}_q \oplus {\mathcal {H}}_e)$ .

The Hamiltonian can be understood as follows. (6.1e) and (6.1d) force a in the q-layer whenever there is an in the c-layer. (6.1f) and (6.1g) do the same with and . (6.1h) and (6.1i) force a non-blank to the left and right of an or , respectively. Finally, (6.1j) and (6.1k) force a non-blank to the left and right of any other non-blank in the q-layer, except when a non-blank coincides with an or in the c-layer.

Since $h_c$ is a tiling Hamiltonian, (6.1b) is by assumption diagonal in the canonical product basis on ${\mathcal {H}}_c^{{\otimes } 2}$ (and acts trivially on $({\mathcal {H}}_q\oplus {\mathcal {H}}_e)^{{\otimes } 2}$ ). Meanwhile, (6.1c) is block-diagonal with respect to the four one-dimensional subspaces of ${\mathcal {H}}_q^{{\otimes } 2}$ spanned by products of and , together with the orthogonal complement thereof. ((6.1c) acts trivially on ${\mathcal {H}}_c^{{\otimes } 2}$ .) The remaining terms are manifestly block-diagonal with respect to both of these decompositions simultaneously. The overall Hamiltonian is therefore block-diagonal w.r.t. the product basis on the c-layer. Hence there is a basis of eigenstates of H of the form , where is a product state in the canonical basis of the c-layer. This proves the first claim of the Lemma.

For a given classical tile configuration on the c-layer, let $\mathcal {L}$ denote the set of all horizontal line segments $\ell $ that lie between an and an (inclusive) in the classical configuration . Let $\mathcal {L}_L$ denote the set of all horizontal line segments between an L and the right boundary of the region, and similarly $\mathcal {L}_R$ the segments between the left boundary and an R.

Consider first a state consisting of the ground state of $H_q(\ell )$ in the q-layer for each $\ell \in \mathcal {L}$ , a 0-energy eigenstate of $H_q(\ell )$ in the q-layer for each $\ell \in \mathcal {L}_L\cup \mathcal {L}_R$ , and everywhere else in the q-layer. The associated energy is clearly . Indeed is the contribution of (6.1a) and (6.1b), and $\sum _{\mathrm {\ell \in \mathcal {L}}} \lambda _0({\lvert {\ell }\rvert })$ the contribution of (6.1c), the rest of the terms being $0$ as satisfies all constraints imposed by (6.1d) to (6.1k).

To see that this is the lowest energy state for a given classical configuration on the c-layer, we define a signature $\sigma $ for each state in the canonical basis of the q-layer. The local Hilbert space at site i in the q-layer is ${\mathcal {H}}_e\oplus {\mathcal {H}}_q$ , so we assign $\sigma _i=0$ for states in ${\mathcal {H}}_e$ and $\sigma _i=1$ for states in ${\mathcal {H}}_q$ . By collecting computational basis states with the same signature, we decompose ${\mathcal {H}}_q$ into a direct sum of subspaces with given signature,

(6.2) $$ \begin{align} \bigotimes_{i\in\Lambda}{\mathcal{H}}_q^{(i)}\simeq\bigoplus_{\sigma}{\mathcal{H}}_\sigma. \end{align} $$

The overall Hamiltonian H is block-diagonal with respect to this decomposition, so all eigenstates have a part with well-defined signature. We distinguish two cases:

Case 1:

$\sigma _i= 1$ for all $i\in \ell \in \mathcal {L}$ . Consider a q-layer state with this signature; that is, a state supported on the corresponding Hilbert space $H_\sigma $ . Since all Hamiltonian terms (6.1d) to (6.1k) are $\ge 0$ , and for all $\ell \in \mathcal {L}$ the (6.1c) contribution is $\ge \lambda _0({\lvert {\ell }\rvert })$ , we easily get that , with equality iff .

Case 2:

There exists $i\in \ell \in \mathcal {L}$ such that $\sigma _i=0$ . Let j be the rightmost position in $\ell $ such that $\sigma _j=0$ . If this is the right or left end of $\ell $ , then the state picks up an energy contribution of $1$ from (6.1d) or (6.1f). If it is the position next to the right or left end, it picks up a contribution of $1$ from from (6.1h) or (6.1i). Finally, if it is not one of the above cases, it acquires a contribution of $1$ from (6.1k). In all cases, the contribution is $\geq \lambda _0({\lvert {\ell }\rvert })$ since $\lambda _0({\lvert {\ell }\rvert }) < 1$ by assumption for a Gottesman-Irani Hamiltonian (see Definition 50). As all terms in the Hamiltonian apart from (6.1a) and (6.1b) are positive-semidefinite, and the contribution from (6.1a) and (6.1b) is , we have that , which completes the proof of the Lemma.

With this, we can now prove the following:

Lemma 52 (Robinson + Gottesman-Irani Hamiltonian)

Let be the local interactions of the tiling Hamiltonian associated with the modified Robinson tiles. For a given ground state configuration (tiling) of $H_c$ , let $\mathcal {L}$ denote the set of all horizontal line segments of the lattice that lie between down/right-facing and down/left-facing red crosses (inclusive). Let be the local interaction of a Gottesman-Irani Hamiltonian $H_q(r)$ , as in Definition 50.

Then there is a Hamiltonian on a 2D square lattice of width L and height H with nearest-neighbour interactions such that, for any $L,H$ , the ground state energy $\lambda _0(H^{\Lambda (L\times H)})$ on a lattice of size $L\times H$ is contained in the interval

(6.3) $$ \begin{align} \left[ \sum_{n=1}^{\lfloor\log_4(L/2)\rfloor} \left( \left\lfloor\frac{H}{2^{2n+1}}\right\rfloor \left(\left\lfloor\frac{L}{2^{2n+1}}\right\rfloor -1\right) \right) \lambda_0(4^n)\; ,\; \sum_{n=1}^{\lfloor\log_4(L/2)\rfloor} \left(\left( \left\lfloor\frac{H}{2^{2n+1}}\right\rfloor +1\right) \left\lfloor\frac{L}{2^{2n+1}}\right\rfloor \right) \lambda_0(4^n)\right] \end{align} $$

Proof. Construct the Hamiltonian H as in Lemma 51, with the red down/right- and down/left-facing crosses from the modified Robinson tile set as the designated and states.

The tiling and QTM Hamiltonians satisfy the requirements of Lemma 51, implying that the lowest energy for a given c-layer configuration is attained by putting ’s in the q-layer everywhere except in the segments between an and an , inclusive. In the modified Robinson tiling, these are exactly the $4^n$ -segments. Therefore, to bound the ground state energy, we can restrict our attention to classical configurations of Robinson tiles (not necessarily valid tilings) with an eigenstate of $h_q$ along each $4^n$ -segment.

By Lemma 48, the minimum energy of an eigenstate with a defect-free Robinson tiling on the $L\times H$ rectangle, $E(0 \text { defects}) = \sum _{\ell \in \mathcal {L}}\lambda _0({\lvert {\ell }\rvert })$ , is contained in the interval (6.3). (Recall that we only use the red $4^n$ -segments to define line-segments on which $h_q$ acts non-trivially in the ground state.)

On the other hand, since each defect in the classical tile configuration contributes energy at least 1 from the $h_c$ term, Lemma 49 implies that the energy of an eigenstate with d defects on the $L\times H$ rectangle is at least

(6.4) $$ \begin{align} E(d \text{ defects}) = d + \sum_{\ell\in\mathcal{L}} \lambda_0({\lvert{\ell}\rvert}) \geq d + \mspace{-20mu} \sum_{n=1}^{\lfloor\log_4(L/2)\rfloor} \Biggl( \left\lfloor\frac{H}{2^{2n+1}}\right\rfloor \left(\left\lfloor\frac{L}{2^{2n+1}}\right\rfloor -1\right) - 2d \Biggr) \lambda_0(4^n). \end{align} $$

Since $\sum _{n=1}^\infty \lambda _0(4^n) < 1/2$ by assumption for a Gottesman-Irani Hamiltonian (see Definition 50), for all $d>0$ this is in turn lower-bounded by

(6.5) $$ \begin{align} E(d \text{ defects}) \geq \sum_{n=1}^{\lfloor\log_4(L/2)\rfloor} \left( \left\lfloor\frac{H}{2^{2n+1}}\right\rfloor \left(\left\lfloor\frac{L}{2^{2n+1}}\right\rfloor -1\right) \right) \lambda_0(4^n). \end{align} $$

The Lemma follows.

We can now apply this Lemma to construct a Hamiltonian $h_u$ with ground state energy that is undecidable even with a constant promise on the energy gap.

Proposition 53 (Diverging g.s. energy)

Choose any , as small as desired. There exists a family of interactions and with operator norm $\le 1/2$ and algebraic (hence computable) matrix entries, and there exist strictly positive (uncomputable) functions $\delta _1(n), \delta _2(n)$ such that either $\lambda _0(H_u^{\Lambda (L)}(n)) \le -L\; \beta /2$ for all L, or $\lambda _0(H_u^\Lambda (n)) \ge L^2\; \delta _2(n) - L\; \delta _1(n)$ for all $L\ge L_0(n)$ ( $L_0(n)$ uncomputable), but determining which is undecidable.

Moreover, the interactions can be taken to have the following form: where $\alpha _2(n)$ is an algebraic number, $h^{col}_u(n)$ is $\{0,\beta \}$ -valued and independent of n and

(6.6) $$ \begin{align} h^{row}_u(n)=\beta \left(A+e^{i\pi\varphi} B+e^{i\pi2^{-{\lvert{\varphi}\rvert}}} C\right) + h.c. \end{align} $$

where is independent of n and has coefficients in , and are independent of n and have coefficients in . (Recall that $\varphi $ is defined as the rational number whose binary fraction expansion contains the digits of n in reverse order after the decimal.)

Proof. Let $h_{q\mathit {0}}$ be the Hamiltonian obtained by applying Theorem 32 with $K=3$ to the QTM from Theorem 10 with a proper reversible universal TM dovetailed after it. The Hamiltonian $h_q(n)$ in Lemma 52 will then be , where is the halting state of the universal TM. Clearly, $h_q$ has the form given in part (vi) of Theorem 32. We claim that this Hamiltonian is a Gottesman-Irani Hamiltonian according to Definition 50.

The only requirements in Definition 50 that are not immediate are those concerning the minimum eigenvalues restricted to various subspaces. Recall the construction of the computational history state Hamiltonian from Theorem 32. In the initialisation sweep, the normally sweeps once from left-to-right along the chain, turns around at the to become a , which sweeps once right-to-left back along the chain. The superpositions over the standard basis states in these sequences contain no illegal pairs as long as the other tracks are initialised correctly. However, if the is missing, then when the reaches the right end of the chain, there is no forward transition out of the resulting state. Thus the uniform superposition over the first part of the initialisation sweep, involving just the left-to-right sweep, is an eigenstate of $h_q$ . Furthermore, it has 0 energy if the rest of the tracks are correctly initialised. Similarly, if the is missing, there is no further forward transition once the reaches the left end of the chain, and the superposition over the full initialisation sweep is a 0-energy eigenstate of $h_q$ . Thus condition (v) of Definition 50 is satisfied.

Let be the normalised computational history state for the QTM, where $T = \Omega ({\lvert {\Sigma \times Q}\rvert }^r)$ and is the state encoding the t’th step of the computation. Note that is a zero-energy eigenstate of $H_{q\mathit {0}}$ , and at most one can have support on the state that represents the halting state of the universal TM, by Theorem 32. For $r>2$ , we have

(6.7)

thus $\sum _{m=1}^\infty \lambda _0(4^m) < 1/2$ . The remaining conditions (iii) and (iv) of Definition 50 are therefore also satisfied. Hence $h_q(n)$ is a Gottesman-Irani Hamiltonian, as claimed.

Let $\tilde {h}_u^{\text {row}}(n),\tilde {h}_u^{\text {column}}(n)$ be the local interactions obtained by applying Lemma 52 to $h_q(n)$ . Let $N(n) := \max \{{\lVert {\tilde {h}^{row}_u(n)}\rVert },{\lVert {\tilde {h}^{\text {column}}_u(n)}\rVert }\}$ , and fix any rational number $\beta \le \frac {1}{N(n)}$ for all n. Such a $\beta $ exists by the form of $h_q$ guaranteed by part (vi) in Theorem 32 and the definition of $\tilde {h}_u^{\text {row}}(n),\tilde {h}_u^{\text {column}}(n)$ based on $h_q$ . Define the normalised local interactions $h_u^{\text {row}}(n) := \beta \tilde {h}_u^{\text {row}}(n)$ , $h_u^{\text {column}}(n) := \beta \tilde {h}_u^{\text {column}}(n)$ .

For any $r\geq {\lvert {n}\rvert }+6$ , the QTM from Theorem 10 has sufficient tape and time to finish, and we can be sure that the reversible universal TM starts. Consider first the case in which the universal TM does not halt on input n. In that case, for all $r\geq {\lvert {n}\rvert }+6$ we have that $\lambda _0(r)=0$ . Let $L_0(n)$ denote the minimal L such that the modified Robinson tiling of $\Lambda (L)$ necessarily contains a $4^m$ -segment of size $4^m \ge {\lvert {n}\rvert }+6$ . If we take $L\ge L_0(n)$ , thanks to Lemma 52 we can bound the ground state energy for $H^{\Lambda (L)}(n)$ :

(6.8a)

(6.8b)

(6.8c) $$ \begin{align} &=: \beta\;\left(L^2\alpha_2(n) + L\alpha_1(n,L) - \alpha_0(n,L)\right), \hspace{90pt} \end{align} $$

where $\operatorname {\mathrm {frac}}(x):=x-\lfloor x\rfloor $ denotes the fractional part of x. Since the number of terms in the sum is bounded by ${\lvert {n}\rvert }$ and for any fixed r the quantity $\lambda _0(r)$ is an eigenvalue of a finite-dimensional matrix, $\alpha _2(n)$ is an algebraic number. Moreover, $\alpha _2(n)\le \beta $ .

We now shift the ground state energy by adding to $h_{\text {row}}$ and adding a 1-body term . Overall, this adds the Hamiltonian . Note that this commutes with all the other terms in the Hamiltonian. After this shift, and using the fact that $\alpha _0(n,L)\ge 0$ , the ground state energy in the non-halting case becomes

(6.9) $$ \begin{align} \lambda_0(H^{\Lambda(L)}) \le \beta L\left(\alpha_1(n,L) - 1\right) \le -\frac{\beta}{2}L\,, \end{align} $$

since

(6.10)

Consider now the case in which the universal TM does halt on input n. Take r of the form $4^m$ large enough so that the TM has sufficient time and tape to halt. Let $r_1(n)$ denote the minimal such r. The computational history state encoding the evolution necessarily has support on and is the unique ground state of $h_{q\mathit {0}}\ge 0$ . Thus $\lambda _0(r)>0$ and by Lemma 52 the ground state energy $\lambda _0(H^{\Lambda (L)})$ is, after the energy shift, lower-bounded by

(6.11a)

(6.11b)

(6.11c) $$ \begin{align} &=: \beta\left(L^2\; \delta_2(n) - L \; \delta_1(n,L) + \delta_0(n,L)\right) \hspace{134pt} \end{align} $$

(6.11d) $$ \begin{align} &\ge \beta\left(L^2\; \delta_2(n) - L \; \delta_1(n)\right), \hspace{184pt} \end{align} $$

where

(6.12)

and $\delta _2(n)>0$ , since in the halting case $\lambda _0(r)>0$ for all $r\ge r_1(n)$ .

Summarising, the ground state energy of $H^{\Lambda (L)}$ in the non-halting case is bounded by

(6.13) $$ \begin{align} \lambda_0(H^{\Lambda(L)})\leq -L\; \frac{\beta}{2} \end{align} $$

whereas in the halting case we have the bound

(6.14) $$ \begin{align} \lambda_0(H^{\Lambda(L)}) \geq L^2\; \delta_2(n) - L\; \delta_1(n). \end{align} $$

The Proposition follows from undecidability of the Halting Problem.

The following corollary follows immediately by letting $L(n)$ be the minimal L in Proposition 53 such that, in the halting case, $L^2\delta _2(n) - L \delta _1(n) \geq 1$ . This will be useful shortly.

Corollary 54 (Undecidability of g.s. energy with promise)

There exists a family of interactions and with operator norm $\le 1/2$ and algebraic (hence computable) matrix entries, and an (uncomputable) function $L(n)$ , such that either $\lambda _0(H_u^{\Lambda (L)}(n)) \leq 0$ for all L, or $\lambda _0(H_u^\Lambda (n)) \ge 1$ for all $L\ge L(n)$ , but determining which is undecidable. Moreover, the interactions can be taken to have the same form as in Proposition 53.

Undecidability of the ground state energy density is now immediate from Proposition 53 by the definition $E_\rho := \lim _{L\rightarrow \infty }\lambda _0(H^{\Lambda (L)})/L^2$ of the ground state energy density. We restate this result here for convenience:

Theorem 5 (restated)

Let $d\in \mathbb {N}$ be sufficiently large but fixed, and consider translationally invariant nearest-neighbour Hamiltonians on a 2D square lattice with open boundary conditions, local Hilbert space dimension d, algebraic (hence computable) matrix entries, and local interaction strengths bounded by 1. Then determining whether $E_\rho =0$ or $E_\rho>0$ is an undecidable problem.

6.2 From g.s. energy density to spectral gap

We are finally in a position to prove our main result: undecidability of the spectral gap, which we restate here for convenience. The overall intuition behind the proof is illustrated in Figure 13.

Figure 13 Starting 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.

Recall that for each natural number n, we define $\varphi =\varphi (n)$ to be the rational number whose binary fraction expansion contains the digits of n in reverse order after the decimal. ²⁷

Theorem 3 (restated)

For any given universal Turing Machine UTM, we can construct explicitly a dimension d, $d^2\times d^2$ matrices $A,A',B,C,D,D'$ , a $d\times d$ diagonal projector $\Pi $ and a rational number $\beta $ which can be as small as desired, with the following properties:

1. (i) A is diagonal with entries in .

2. (ii) $A'$ is Hermitian with entries in ,

3. (iii) $B,C$ have integer entries,

4. (iv) D is diagonal with entries in ,

5. (v) $D'$ is hermitian with entries in .

For each natural number n, define:

$$ \begin{align*} &h_1(n)=\alpha(n)\Pi, \qquad\qquad \alpha(n)\le 2\;\beta \text{ an algebraic number}\\ &h_{\text{col}}(n)=D +\beta D', \ \qquad\text{ independent of } n \\ &h_{\text{row}}(n)=A + \beta\left(A'+e^{i\pi\varphi} B + e^{-i\pi\varphi} B^{\dagger} + e^{i\pi2^{-{\lvert{\varphi}\rvert}}} C + e^{-i\pi2^{-{\lvert{\varphi}\rvert}}} C^{\dagger}\right). \end{align*} $$

Then:

1. (i) The local interaction strength is bounded by 1, i.e. $\max ({\lVert {h_1(n)}\rVert }, {\lVert {h_{\text {row}}(n)}\rVert }, {\lVert {h_{\text {col}}(n)}\rVert }) \leq 1$ .

2. (ii) If UTM halts on input n, then the associated family of Hamiltonians $\{H^{\Lambda (L)}(n)\}$ is gapped in the strong sense of Definition 1 and, moreover, the gap $\gamma \ge 1$ .

3. (iii) If UTM does not halt on input n, then the associated family of Hamiltonians $\{H^{\Lambda (L)}(n)\}$ is gapless in the strong sense of Definition 2.

Proof. We assign a Hilbert space to each site $i\in \Lambda $ , where denotes the generating element of . Let $h_u^{(i,j)}$ be the two-body interactions obtained in Corollary 54 (keeping the one-body term $h^{(i)}_u(n)$ separate, for later convenience).

Let $h_d$ be the two-body interaction of any nearest-neighbour Hamiltonian $H_d$ with 0 ground state energy whose spectrum becomes dense in the thermodynamic limit (cf. Definition 2): . (For example [53], we can take $D=2$ and $h_d$ to be the critical XY-model along the rows, where $\sigma _{x,y,z}$ are the Pauli matrices, with no interactions along the columns.) We normalise the interaction strength such that ${\lVert {h_d}\rVert }\le \frac {1}{2}$ .

Define the Hamiltonian $H(n)$ in terms of its two-body and one-body interactions $h(n)$ as follows (with $\alpha (n) = \alpha _2(n)$ , $\Pi = \Pi _{ud}$ ): 0

(6.15a)

(6.15b)

(6.15c)

(6.15d) $$ \begin{align} h^{(i)}(n) := &-\beta(1+\alpha_2(n))\Pi_{ud}^{(i)}. \qquad\qquad \end{align} $$

Clearly, both have norm bounded by $1$ . Note that we can also rescale $h_d$ so that ${\lVert {h_d}\rVert }\le \beta $ .

As in Lemma 51, denote the identity operators on ${\mathcal {H}}_u,{\mathcal {H}}_d$ , and $\Pi _{ud}$ denotes the projection of ${\mathcal {H}}$ onto its ${\mathcal {H}}_u{\otimes }{\mathcal {H}}_d$ subspace. We decompose the global Hamiltonian in the square $\Lambda (L)$ as $H^{\Lambda (L)}=:\tilde {H}_0 + \tilde {H}_d + \tilde {H}_u$ , where $\tilde {H}_0,\tilde {H}_d,\tilde {H}_u$ are defined by taking the sum over sites separately for the expressions in (6.15a), (6.15b), and (6.15c) + (6.15d), respectively. Note that the three terms commute with each other and

(6.16)

Let us analyse the spectrum of $H^{(\Lambda (L)}$ in both the halting and non-halting cases. First consider the halting case, and take $L\ge L(n)$ as defined in Corollary 54. In that case, $\tilde {H}_d, \tilde {H}_u\ge 0$ and hence $H^{\Lambda (L)}\ge \tilde {H}_0$ . Since $|0\rangle ^{\otimes \Lambda (L)}$ is the unique ground state of $\tilde {H_0}$ , with energy $0$ , and is also a 0-energy state for $H^{\Lambda (L)}$ , we have that the spectral gap of $H^{\Lambda (L)}$ is at least as large as the spectral gap of $\tilde {H}_0$ , which is $1$ .

In the non-halting case, it is clear from the structure of the Hamiltonians (6.15) that

(6.17)

Since is contained in the set of non-negative integers, and converges in the thermodynamic limit to $[0,+\infty )$ , and $\lambda _0(\tilde {H}_u)\le 0$ for all L by (6.16), statement (iii) in the Theorem follows.

6.3 Periodic boundary conditions

The previous section proves Theorem 3 for open boundary conditions. This is arguably the most important type of boundary conditions in the context of the spectral gap problem. Both physically, because periodic boundary conditions rarely occur in real physical systems, and mathematically, because the thermodynamic limit is better behaved. Nonetheless, our result can also be extended to other types of boundary condition. Extending it to fixed boundary conditions is trivial, so we omit the argument. In this section, we consider the more interesting case of periodic boundary conditions.

To extend our result to periodic boundary conditions, we add to the modified Robinson tiles of Section 5 the three new tile types shown in Figure 14.

Figure 14 Boundary tiles for periodic boundary condition construction.

Let $h_c$ be the standard tiling Hamiltonian of the modified Robinson tiles. We consider the Hamiltonian given by $3h_c$ plus the weighted terms given by the following tables (where stands for any modified Robinson tile):

(6.18)

The resulting weighted tiling Hamiltonian $\tilde {h}_c$ effectively turns the weighted tiling problem for an $L\times L$ square region with periodic boundary conditions (a torus), into the standard tiling problem for the modified Robinson tile set on a square region with open boundary conditions of size $(L-1)\times (L-1)$ :

Lemma 55 (Periodic to open b.c.)

For any , all minimum weight tilings of an $L\times L$ torus using the tile set described above consist of a single tile at an arbitrary location, a complete row of tiles extending horizontally from the , a complete column of tiles extending vertically from the , and a valid modified Robinson tiling of the remaining $(L-1)\times (L-1)$ region.

Proof. The tilings described in the statement of the Lemma have total weight $+4$ (coming from the and tiles adjacent to the ). We must show that all other tilings have higher weight. First, consider the case in which only modified Robinson tiles are used. By the aperiodicity of Robinson tiling, there are at least two mismatching tiles in an $L\times L$ torus, one in the vertical and one in the horizontal direction. Since we multiplied the original modified Robinson tiling Hamiltonian $H_c$ by a factor of 3, each of these mismatches has weight $3$ and we get a total weight of $6$ . Thus any weight $<5$ tiling must contain at least one , or .

If the tiling contains any tile other than or to the left or right of a , it has weight $\geq 5$ . Thus, in any weight $\leq 5$ tiling, tiles can only appear in complete rows of and tiles. The analogous argument for columns implies that tiles can only appear in complete rows of and tiles. A adjacent to a modified Robinson tile has weight $+5$ , so tiles can only appear where such rows and columns meet. Moreover, adjacent and tiles have weight $+5$ , so all such rows and columns must meet at tiles.

Therefore, any tiling with weight $<5$ must consist of some non-zero number of rows of tiles and columns of tiles meeting at tiles, with modified Robinson tiles everywhere else. Each intersection of a row with a column at a contributes weight $+4$ , so the weight is minimised by having just one such row and column.

Finally, the remaining region to be filled with modified Robinson tiles is a square of size $(L-1)\times (L-1)$ . It contributes weight 0 iff, in addition, they form a valid tiling.

Using this weighted tile set in Lemma 51, the proofs of Lemmas 51 and 52, Proposition 53, and Corollary 54 go through unchanged for square lattices with periodic boundary conditions. Undecidability of the ground state energy density (Theorem 5), and undecidability of the spectral gap (Theorem 3) follow easily.