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 [Reference Arad, Landau, Vazirani and Vidick15] 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. [Reference Blum, Smale, Hirsch, Marsden and Shub33]).

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 [Reference De Roeck and Salmhofer29]. 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.Footnote ¹

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.Footnote ² . 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 [Reference Arad, Landau, Vazirani and Vidick15, Reference Feynman70]), but can exploit the simpler undecidability of the completion problem, already proven by Wang [Reference Robinson74]. 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 [Reference Feynman70, 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.Footnote ³

Following Robinson [Reference Feynman70], 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.1 Quantum Turing Machinery

For completeness we quote the basic definitions of Turing Machines and Quantum Turing Machines verbatim from [Reference Arad, Kitaev, Landau and Vazirani16].

Definition 11 (Turing Machine – Definition 3.2 in [Reference Arad, Kitaev, Landau and Vazirani16])

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 [Reference Arad, Kitaev, Landau and Vazirani16, 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.Footnote ⁵

Definition 12 (Quantum Turing Machine – Definition 3.2 in [Reference Arad, Kitaev, Landau and Vazirani16])

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.

Following Bernstein and Vazirani [Reference Arad, Kitaev, Landau and Vazirani16], we define various classes of deterministic and quantum Turing Machines:

It is easy to see (Theorem 4.2 in [Reference Arad, Kitaev, Landau and Vazirani16]) 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 [Reference Arad, Kitaev, Landau and Vazirani16])

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

(3.4)

In [Reference Arad, Kitaev, Landau and Vazirani16] 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 [Reference Arad, Kitaev, Landau and Vazirani16].

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.

Bernstein and Vazirani [Reference Arad, Kitaev, Landau and Vazirani16] 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:

Bernstein and Vazirani [Reference Arad, Kitaev, Landau and Vazirani16] 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 [Reference Arad, Kitaev, Landau and Vazirani16].) 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.

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.

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.Footnote ⁷ 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 [Reference Kliesch, Gross and Eisert50]), 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 [Reference Arad, Kitaev, Landau and Vazirani16] 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.Footnote ⁸ To avoid technical issues, we follow Bernstein and Vazirani [Reference Arad, Kitaev, Landau and Vazirani16] 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.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 [Reference Orús13], 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 [Reference Arad, Kitaev, Landau and Vazirani16, 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 [Reference Arad, Kitaev, Landau and Vazirani16, 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 [Reference Arad, Kitaev, Landau and Vazirani16], 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 [Reference Cubitt, Gu, Perales, Perez-Garcia and Wolf62]).

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,Footnote ¹⁰ 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 [Reference Cubitt, Gu, Perales, Perez-Garcia and Wolf62]

(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 [Reference Cubitt, Gu, Perales, Perez-Garcia and Wolf62]).

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.Footnote ¹¹

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 [Reference Cubitt, Gu, Perales, Perez-Garcia and Wolf62]

(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.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 [Reference Cubitt, Gu, Perales, Perez-Garcia and Wolf62] 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.1 Preliminaries

As our construction draws heavily on [Reference Hofstadter32], 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.Footnote ¹⁵ 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:

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.)

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 [Reference Hofstadter32], which lets us use penalty terms to restrict to configurations matching a regular expression:

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 [Reference Hofstadter32], 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: