# Quantum Frequential Computing: a quadratic run time advantage for all algorithms

Mischa Woods

<figure><img src="image_1.png" /></figure>

## To cite this version:

Mischa Woods. Quantum Frequential Computing: a quadratic run time advantage for all algorithms. 2024. [https://hal.science/hal-04529846](https://hal.science/hal-04529846)

HAL Id: hal-04529846

https://hal.science/hal-04529846

Preprint submitted on 2 Apr 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Quantum Frequential Computing: a quadratic runtime advantage for all algorithms

Mischa P. Woods¹

¹University Grenoble Alpes, Inria, Grenoble, France

We introduce a new class of computer called a quantum frequential computer. They harness quantum properties in a different way to conventional quantum computers to generate a quadratic computational runtime advantage for all algorithms as a function of the power consumed. They come in two variants: type 1 can process classical algorithms only while type 2 can also process quantum ones. In a type-1 quantum frequential computer, only the control is quantum, while in a type 2 the logical space is also quantum. We also prove that a quantum frequential computer only requires a classical data bus to function. This is useful, because it means that only a relatively small part of the overall architecture of the computer needs to be quantum in a type-1 quantum frequential computer in order to achieve a quadratic runtime advantage. As with classical and conventional quantum computers, quantum frequential computers also generate heat and require cooling. We also characterise these requirements.

## I. INTRODUCTION

These runtime speedups originate from using a quantum rather than classical logical register. This extra freedom allows for algorithms which require less gates than their classical counterparts.

Here we will explore the possibility of using quantum properties in a different way in order to achieve a runtime speedup. Namely, rather than using quantum properties to reduce the gate count itself, we will aim to reduce the runtime by reducing the time required to apply each gate.

The application of a logical gate requires the passage through phase space (if classical) or Hilbert space (if quantum) of a system controlling the gate application. As such, it is feasible that quantum theory allows for a shorter passage time than classical theory permits. We will show that there is such an advantage.

This manuscript is organised as follows: we start in section II giving some intuition from classical mechanics regarding the upper limits to computational speed, followed by deriving upper limits for quantum and classical systems. These two upper bounds have a quadratic separation as a function of power and motivate the definition of a quantum frequential computer. In section III we show that there exist computers which can saturate both of these bounds. This proves that both optimal classical computers and optimal quantum frequential computers exist, at least in theory. In section IV we go on to add additional architecture to the quantum frequential computer, namely an internal data bus. This allows it to run more efficiently, and, most importantly, we show that the bus only requires classical control even when powering an optimal quantum frequential computer. Up to this point, the models involve Hamiltonian dynamics, and thus do not admit a nonequilibrium steady-state solution. Conventional computers do run in this form, and there are a number of advantages in doing so. In section V we show that an optimal quantum frequential computer can also be formulated under the evolution of a dynamical semigroup and admits a nonequilibrium steady-state solution. Finally, we end the main text with a discussion and conclusion (Sections VI and VII respectively).

## II. CLASSICAL AND QUANTUM UPPER LIMITS TO COMPUTATION

For intuition, let us start by observing that in classical computation, a reasonable assumption is that there are algorithms for which the logical state of the computer passes through a sequence of orthogonal states as the sequence of logical gates are applied. This is a necessary but not sufficient requirement. A very simple toy model which replicates this feature is a puck of length $\Delta x_0$ and mass $m$ travelling along the x-axis with velocity $V > 0$ in a frictionless and flat potential, with initial position $x_0 = 0$. Every time the puck traverses a distance $\Delta x_0$ a new gate is applied, so that when the puck has position $x_l = l\Delta x_0$, the first $l$ gates have been implemented; see fig. 1.

Denoting by $T_0$ the total runtime and solving the Liouvillian for this setup leads to a frequency

$$f = \frac{V}{\Delta x_0} = \sqrt{\frac{2T_0}{m\Delta x_0^2}} \sqrt{P}, \qquad (II.1)$$
<figure><img src="image_3.png" /><figcaption>FIG. 1. A puck, depicted by a black rectangle, moves from left to right. In the snapshot of the dynamics depicted, the 1st two gates of the algorithm have been implemented.</figcaption></figure>

where $P$ is the total power (initial energy over runtime $T_0$). Assuming a constant ratio $T_0/(m\Delta x_0^2)$, we see that we have a square-root scaling of the frequency with the power already in this simple setup. Ultimately, this non-linearity can be traced-back to the fact that the energy in classical mechanics scales as the square of the velocity. However, if one were to parametrize the product of the mass and length-squared so that $m\Delta x_0^2 \to 0$ at some chosen rate as $P \to +\infty$, then it is readily apparent from eq. (II.1) that one could, in principle, achieve any frequency-power dependency. Unfortunately, classical mechanics breaks down in the limit of infinitely small mass and/or infinitely narrow width. Indeed, it was due to inconsistencies between experimental observations on small systems and classical mechanics which led to the development of quantum theory. Thus in order to gain meaningful insight about classical limitations, in the following we shall assume quantum theory holds, but restrict ourselves to classical states and/or measurements.

Our strategy for deriving generic bounds will be to see how accurately one can deduce the elapsed runtime $t$ during a computation by measuring the logical state of the computer mid computation. We will then use results from the field of metrology to obtain frequency-power relations. In our model, the computer's dynamics is governed by a time-independent Hamiltonian $H_{\text{Com}}$ evolving unitarily from its initial state. It is multipartite and includes the logical register, and any control systems, memory registers and batteries required for its functioning. It may even include a thermal bath and hence thermodynamic effects. It implements a total of $N_g$ gates sequentially with the $j^{\text{th}}$ gate at time $t_j := j T_0/N_g$. The state of the computational logical space passes through a sequence of orthogonal states at times $t_1, t_2, \dots, t_{N_g}$. We will measure the logical space in the computational basis at an unknown time between starting the computation at $t=0$ and it finishing at a fixed runtime $T_0$. We then choose an estimator function, which estimates the time (given our measurement outcome). The Cramér-Rao bound and its generalizations [3, 4], then put upper bounds on how precisely we can use this estimate to work out the time. It allows one to generate bounds on the gate frequency as a function of the power available.

We first consider the case in which there are no quantum effects. In particular, we assume that there exists $l \in \{0, 1, \dots, N_g - 1\}$ such that the pair of states $\rho_{\text{Com}}(t_l), \rho_{\text{Com}}(t_{l+1})$ are non-squeezed states with respect to the measurement basis and the Hamiltonian $H_{\text{Com}}$ (for full definition, see appendix A.) then the frequency $f = N_g/T_0$ at which $N_g$ gates are implemented sequentially in a fixed time $T_0$ is bounded by

$$f \le C_{\text{SQL}} \sqrt{P}, \qquad (\text{II.2})$$

where $C_{\text{SQL}}$ is independent of $P = (\text{tr}[\rho_0 H_{\text{Com}}] - E_{\text{Com}}^0)/T_0$, with $E_{\text{Com}}^0$ the ground state energy of $H_{\text{Com}}$. The exact definition of $C_{\text{SQL}}$ depends on the precise definition of squeezed states, which we give in appendix A. In this manuscript, we refer to objects which have standard quantum limit properties as “classical”.

Thus eq. (II.2) confirms the suggestion from classical mechanics that the ultimate classical frequency-power limit of computation scales as the square-root of the available power.

However, if one does not put any additional constraints beyond those of quantum theory on the allowed measurements or dynamics such that squeezed states are permitted, the so-called Heisenberg limit applies. Under this scenario it follows that

$$f \le C_{\text{HL}} P, \qquad (\text{II.3})$$

where $C_{\text{HL}}$ is independent of $P$. See section VI 10 for a discussion on the relation to quantum speed limits.

These bounds naturally lead to a new question: is the linear scaling of eqs. (II.2) and (II.3) actually achievable? While it is known that the Heisenberg limit in standard metrological settings is achievable, one needs much more to achieve universal classical or quantum computation. At a minimum, one needs to be able to load any sequence of gates from a universal set into a memory, and then implement the gate sequence. The bound eq. (II.3) only demands that the logical space passes through a sequence of orthogonal states. It could, in principle, be saturable only for systems which cannot perform universal computation, such as a quantum system oscillating in a fixed basis.

Two important questions thus naturally arise: 1) Can one construct a family of classical universal computers which saturate the classical scaling bound eq. (II.2)? 2) Can we construct a family of computers with quantum states
which surpass the classical scaling bound and if so under what conditions? We will answer both these questions in this manuscript going into substantial detail. Moreover, in anticipation of a positive answer to both these questions, let us introduce the following definition.

Let us denote by $f$ the frequency at which logical gates are applied sequentially from a gate set. We call a computer a *quantum frequential computer* if it satisfies

$$f \geq C_a P^a, \quad a \in (1/2, 1], \quad P \geq P_a \qquad (II.4)$$

where $C_a$ and $P_a$ are $P$-independent. If it is capable of universal classical computation, it is called a *type-1 quantum frequential computer*. If it is capable of universal quantum computation, it is called a *type-2 quantum frequential computer*. A quantum frequential computer (either of type 1 or 2), satisfying eq. (II.4) for $a = 1 - \epsilon$ (with $\epsilon > 0$ arbitrarily close to zero), is called an *optimal quantum frequential computer*. These definitions will suffice in this manuscript since we will only discuss the asymptotic scaling behaviour, but more generally one can define a quantum frequential computer as any computer with quantum states whose gate-frequency-to-power-consumption relation is unobtainable via classical or standard-quantum-limited states.

### III. EXISTENCE OF OPTIMAL TYPE-1 AND TYPE-2 QUANTUM FREQUENTIAL COMPUTERS

We have seen how quantum metrology imposes upper bounds. We will now prove optimal type-1 and type-2 quantum frequential computers exist. We start by introducing the model. We will model explicitly the relevant 3 subsystems: 1) the physical or logical space on which the gate sequence is implemented S (since we will not consider error correction here, there is no requirement to distinguish between the logical and physical spaces). 2) the memory space $M_0$ which stores the gate sequence $(m_1, m_2, \dots, m_{N_g})$, where each element belongs to an alphabet $G^1$. 3) the control space C, which will encode the degrees of freedom of the system which implements the gate sequence.

For every element $m \in G$, there is a corresponding unitary $U(m)$ on S. The set of these $\{U(m) | m \in G\} =: U_G$ is the gate set and is of finite cardinality but otherwise arbitrary. As such, the model can accommodate both universal classical and universal quantum computing. (Note that for simplicity, we have referred to both $G$ and $U_G$ as “gate set”. The former refers to their symbolic representation, while the latter to the maps themselves. It will be clear from the context and notation which one we are referring to.)

We assume the memory, $M_0$, is formed by $N_g \in N_{>0}$ local memory cells, i.e. $C_{M_0} = C_{Cell}^{\otimes N_g}$, where each cell is of the dimension of the gate set: $\text{Dim}(H_{Cell}) = |G|$. Its initial state, $|0\rangle_{M_0}$, belongs to the set representing the memory states corresponding to all possible gate sequences the computer can implement:<fnref n="2" />

$$C_{M_0} := \{ |m_1\rangle_{M_{0,1}} |m_2\rangle_{M_{0,2}} |m_3\rangle_{M_{0,3}} \dots |m_{N_g}\rangle_{M_{0,N_g}} | m_1, m_2, \dots, m_{N_g} \in G \} \qquad (III.1)$$

where $\{|m_l\rangle_{M_{0,l}}\}_{m_l \in G}$ forms an orthonormal basis for the $l$th memory cell. These states are classical in the sense that there is no coherence in the above basis. See fig. 2 for a diagrammatic illustration of the setup.

<figure><img src="image_4.png" /><figcaption>FIG. 2. Diagram of the different systems involved: the memory $M_0$, the logical space S, and control C.</figcaption></figure>

Let $t_j := jT_0/N_g$, ($j = 0, 1, 2, \dots, N_g$) be the time necessary to implement the 1st $j$ gates on S, so that $T_0 > 0$ is the total time required for the computation (i.e. to implement all $N_g$ gates sequentially). Likewise, we denote the state on S at time $t_j$ by

$$|t_j\rangle_S := U(m_j)U(m_{j-1})\dots U(m_1)|0\rangle_S, \qquad (III.2)$$

<footnote n="1">¹To avoid ambiguities stemming from notation, we assume it to not contain purely numeric symbols nor symbols of the form $t_x$ where $x$ is any symbol in the subscript.</footnote>

<footnote n="2">²We omit tensor products with the identity and tensor product symbols between kets and bras by convention. We also refrain from using the common partial trace convention, i.e. $O_B \neq \text{tr}_A O_{AB}$ for operators $O_{AB}$ over a bipartite system.</footnote>
where the initial state, $|0\rangle_S \in \mathcal{P}(\mathcal{H}_S)$, with $\mathcal{P}(\mathcal{H}_S)$ the set of normalised pure states on $\mathcal{H}_S$. The corresponding gate frequency is

$$f := \frac{N_g}{T_0}. \qquad (III.3)$$

We do not impose any further structure on the control state on C at time $t_j$ other than it being a tensor product state with the rest of the computer. As such, the total state of the computer at time $t_j$ (for $j = 0, 1, 2, \dots, N_g$) is

$$|0\rangle_{M_0} |t_j\rangle_S |t_j\rangle_C. \qquad (III.4)$$

The question we will want to answer is with what frequency $f$ can the gates be implemented as a function of available power. To do so we introduce a family of Hamiltonians over $S, M_0$ and $C$ and then ask how well Hamiltonians from this family can mimic the dynamics of the states of the computer we have introduced at times $\{t_j\}_{j}$.

These time-independent Hamiltonians have a particular structure, namely

$$H_{M_0 SC} = H_C + \sum_{l=1}^{N_g} I_{M_0 S}^{(l)} \otimes I_C^{(l)}, \qquad (III.5)$$

where we use subscripts $M_0, S, C$ to indicate which subsystems the individual terms act upon. $H_{M_0 SC}$ is self-adjoint and has a ground state energy of zero. While the Hamiltonians $H_{M_0 SC}$ can depend on $\mathcal{G}$, they cannot depend on the initial memory state $|0\rangle_{M_0} \in \mathcal{C}_{M_0}$. This is because we want the gate sequence to be encoded in $|0\rangle_{M_0}$ and not the Hamiltonian. In other words, the Hamiltonians we are considering have to be as universal as the alphabet $\mathcal{G}$ permits.

The control system $C$ requires a non-trivial free Hamiltonian $H_C$ since the control state is permitted to freely evolve. Conversely, the initial state of the memory, $|0\rangle_{M_0}$, does not evolve—hence the absence of a term of the form $H_{M_0}$. It does however require interaction terms with the physical space, $\{I_{M_0 S}^{(l)}\}_{l=1}^{N_g}$ in order to be read. Similarly, there is no free Hamiltonian on the logical space, since the only evolution comes from the application of gates in $\mathcal{U}_G$. The $l$th interaction term, $I_{M_0 S}^{(l)}$, only acts non-trivially on $S$ and $M_{0,l}$. As such, we can associate the presence of $I_{M_0 S}^{(l)}$ with the application of $U(\pi_l)$ on $S$.

The Hamiltonians $H_C$ have a discrete spectrum which forms a basis $\{|E_n\rangle_C\}_n$. The terms $\{I_C^{(l)}\}_{l=1}^{N_g}$ are diagonal in the discrete Fourier transform basis generated from $\{|E_n\rangle_C\}_n$.

As before, we define the power for this model as

$$P := \frac{E_0}{T_0}, \qquad E_0 := \text{tr}[\rho_{M_0 SC}^0 H_{M_0 SC}], \qquad (III.6)$$

where $\rho_{M_0 SC}^0$ is the density matrix for the initial state, $|0\rangle_{M_0} |0\rangle_S |0\rangle_C$. For the following theorems, it is convenient to introduce the set of classical states of the control $\mathcal{C}_C$: this is the class of non-squeezed states with respect to the free control Hamiltonian $H_C$ and its conjugate Hermitian operator $t_C$ (which is diagonal in the same basis as operators $\{I_C^{(l)}\}_{l=1}^{N_g}$). In other words, the control states in $\mathcal{C}_C$ have equal uncertainty with respect to both operators (up to normalization and vanishing corrections in the large $P$ limit.) See appendix A 2 for their full definitions.

For $\mathfrak{m} \in \mathcal{G}$, $\tilde{d}(\mathfrak{m})$ is the number of distinct eigenvalues of $U(\mathfrak{m})$ (which we assume to have point spectrum). For the following theorem, we introduce some notation: $g(\bar{\epsilon}) > 0$ is a $P$-independent function of $\epsilon > 0$, while $\text{poly}(P)$ is a polynomial in $P$ and $\bar{\epsilon}$ independent. Both are independent of the elements in $\{\tilde{d}(\mathfrak{m})\}_{\mathfrak{m} \in \mathcal{G}}$. The runtime $T_0$ is assumed to be fixed (we discuss below the theorem what happens if $T_0$ varies).

We use $T(|A\rangle, |B\rangle)$ to denote the trace distance between two normalised kets $|A\rangle, |B\rangle$. As such, in the following the term $T(e^{-it_j H_{M_0 SC}} |0\rangle_{M_0} |0\rangle_S |0\rangle_C, |0\rangle_{M_0} |t_j\rangle_S |t_j\rangle_C)$ can be understood colloquially as the error in running the computer up to time $t_j$.

**Theorem 1** (Optimal classical and quantum frequential computers exist). For all gate sets $\mathcal{U}_G$, initial memory states $|0\rangle_{M_0} \in \mathcal{C}_{M_0}$ and initial logical states $|0\rangle_S \in \mathcal{P}(\mathcal{H}_S)$, there exists triplets $\{|t_j\rangle_C\}_{j=0}^{N_g}, N_g, H_{M_0 SC}$ parametrised by the power $P > 0$ and a dimensionless parameter $\bar{\epsilon}$, such that for all $j = 1, 2, \dots, N_g$ and fixed $\bar{\epsilon} > 0$ the large-$P$ scaling is as follows

$$T(e^{-it_j H_{M_0 SC}} |0\rangle_{M_0} |0\rangle_S |0\rangle_C, |0\rangle_{M_0} |t_j\rangle_S |t_j\rangle_C) \le \left( \sum_{k=1}^{j} \tilde{d}(\mathfrak{m}_k) \right) g(\bar{\epsilon}) \text{poly}(P) P^{-1/\sqrt{\bar{\epsilon}}}, \qquad (III.7)$$
for the following two cases:

Case 1):

$$f = \frac{1}{T_0} (T_0^2 P)^{1/2-\bar{\epsilon}} + \delta f, \quad |\delta f| \le \frac{1}{T_0} + \mathcal{O}\left(\text{poly}(P) P^{-1/\sqrt{\bar{\epsilon}}}\right) \text{ as } P \to \infty, \qquad (\text{III.8})$$

and $|t_j\rangle_C \in \mathcal{C}_C, j = 0, 1, 2, \dots, N_g$.

Case 2):

$$f = \frac{1}{T_0} (T_0^2 P)^{1-\bar{\epsilon}} + \delta f', \quad |\delta f'| \le \frac{1}{T_0} + \mathcal{O}\left(\text{poly}(P) P^{-1/\sqrt{\bar{\epsilon}}}\right) \text{ as } P \to \infty. \qquad (\text{III.9})$$

The proof can be found in appendix B. It is by construction. In the proof, the parametrization of triplets $\{|t_j\rangle_C\}_{j=0}^{N_g}$, $N_g$, $H_{M_0SC}$ is defined explicitly in terms of $\bar{\epsilon}$, while its parametrization in terms of $P$ in implicitly defined via eq. (III.6).

Thus, up to an error in trace distance which decays faster than any polynomial, Theorem 1 shows the following. Case 1): Both conventional quantum and classical computers with optimal classical control exist. Case 2): Optimal quantum frequential computers (either of type 1 or 2) exist. This is to say that upper bounds eqs. (II.3) and (II.4) can both be saturated.

The coefficients $\tilde{d}(\mathfrak{m}_k)$ are related to the number of qubits in $S$ which the gate $U(\mathfrak{m}_k)$ acts non-trivially on. E.g. if $U(\mathfrak{m}_k)$ is a 2-bit/qubit gate, then $\tilde{d}(\mathfrak{m}_k) \le 4$. It is important that the error only grows with the number of qubits the gates act upon, rather than the total dimension $d_S$ of the computation space $S$, which could be orders of magnitude larger. Note that the units in eqs. (III.8) and (III.9) are those of frequency as required since in this manuscript we are using units such that $\hbar = 1$.

As stated previously we have assumed $T_0$ to be constant. Let us briefly examine what happens if it is not constant. The initial energy $E_0$ is approximately proportional to $1/T_0$, thus the power scales as $(1/T_0)^2$, thus from eqs. (III.8) and (III.9) we see that $f$ in linear in $(1/T_0)$. Hence while one can increase the gate frequency by increasing $1/T_0$, it only follows the classical scaling limit of eq. (II.2).

From Theorem 1 it also follows how $N_g$ scales with $P$. In case 1) $N_g = T_0 f \sim \sqrt{P}$ as $P \to \infty$, while in case 2) $N_g = T_0 f \sim P$ as $P \to \infty$. This might be undesirable from a physical standpoint, since one may wish to increase the total number of gates $N_g$ to be implemented at a give frequency $f$, without needing to increase the frequency itself. The reason behind this is because in our construction, every interaction term $I_{M_0S}^{(l)} \otimes I_C^{(l)}$ is only “used” once, to implement one gate (since the number of interaction terms and number of gates are equal). Such a setup would be highly wasteful from an engineering perspective. The underlying reason can be traced back to the fact that each interaction term only reads one memory cell.

One way to circumvent this shortcoming, would be to partition the gate sequence $\mathfrak{m}_1, \mathfrak{m}_2, \mathfrak{m}_3, \dots$ one wishes to implement into sequences of length $N_g$, run the computer with the 1st partition in the initial memory state $|0\rangle_{M_0}$ and then reset the control state to its initial state $|0\rangle_C$ at time $t_{N_g}$ and $|0\rangle_{M_0}$ to the state which encodes the next partition. Then run the computer again. This however would require external control and thus unforeseeable costs, including, potential, a drop in frequency and or more power.

## IV. QUANTUM FREQUENTIAL COMPUTERS ONLY REQUIRE A CLASSICAL INTERNAL BUS

In this section we will show how to extend the setup from the previous section to overcome the shortcomings mentioned in the previous paragraph. Moreover, we will show that even when we are operating in the quantum frequential computer regime, we only require additional classical resources to overcome these aforementioned difficulties. In other words, these additional classical resources in total will only require the same power consumption as the quantum ones, thus their addition will not change how the gate frequency of the quantum frequential computer scales with total power consumption.

To achieve this we will add to the setup an additional memory and control system which together can be thought of as an “internal bus” which will refresh the memory cells in $M_0$ at an appropriate rate. We will show that an optimal quantum frequential computer (either of type 1 or 2), only requires an internal bus whose control state is classical, and consumes the same amount of power as the quantum control system on $C$. In light of Theorem 1 and the upper bounds from section II, this may seem a priori surprising, since this additional control system has to perform the same number $N_g$ of unitaries as the control on $C$ in the same time interval $T_0$. We will give an intuitive explanation of why later in section VI 3. Let us start by introducing the additional computer architecture associated with this new setup.
As with the previous section, we will define the exact states of the computer at times $t_j$ just after the $j$th gate has been applied, and later see how fast (as a function of power) they can be reached under the dynamics of a time-independent Hamiltonian up to a small error.

We consider the setup in which the total number of logical gates implemented sequentially is $N_G = LN_g$ within a total runtime of the computer of $(L+1)T_0$, $L \in \mathbb{N}_{>0}$. The gate frequency is $f = N_G/LT_0 = N_g/T_0$ (since in the initial time interval $[0, T_0]$ the gates applied are not computational logic gates in $\mathcal{U}_G$). We denote by $t_{j,l}$ the time at which the $(j+lN_g)$th gate is applied: $t_{j,l} := t_{j+lN_g} = t_k + lT_0$ $(j = 0, 1, 2, \dots, N_g; l = 0, 1, 2, \dots, L)$, $L \in \mathbb{N}_{\ge 0}$. The computer goes through $L+1$ “cycles” during the computation by which it is meant that the state on C is periodic with a period $T_0$, so that

$$|t_{j,l}\rangle_C = |t_{j,m}\rangle_C, \qquad (IV.1)$$

for all $l, m = 0, 1, 2, \dots, L$ and $j = 0, 1, \dots, N_g$.

With the exception of the 1st cycle, the computer will run analogously to that of the previous section, but with the memory $M_0$ refreshed so that it implements a new gate sequence on every cycle. The quantum frequential computer will implement a logical gate sequence with elements in $\mathcal{U}_G$, according to the sequence $(\mathfrak{m}_{1,1}, \mathfrak{m}_{1,2}, \dots, \mathfrak{m}_{1,N_g}, \mathfrak{m}_{2,1}, \mathfrak{m}_{2,2}, \dots, \mathfrak{m}_{2,N_g}, \mathfrak{m}_{3,1}, \dots, \mathfrak{m}_{3,N_g}, \dots, \mathfrak{m}_{L,1}, \mathfrak{m}_{L,2}, \dots, \mathfrak{m}_{L,N_g})$ with elements in $\mathcal{G}$. The logical space will remain unchanged during the first cycle: $|0\rangle_S = |t_{k,0}\rangle_S$, $k = 1, 2, 3, \dots, N_g$, and the gate sequence is fully implemented on it over the subsequent cycles: For $k = 1, 2, \dots, N_g; l = 1, 2, \dots, L$

$$|t_{k,l}\rangle_S = U(\mathfrak{m}_{l,k})U(\mathfrak{m}_{l,k-1})U(\mathfrak{m}_{l,k-2})\dots U(\mathfrak{m}_{2,2})U(\mathfrak{m}_{2,1})U(\mathfrak{m}_{1,N_g})\dots U(\mathfrak{m}_{1,3})U(\mathfrak{m}_{1,2})U(\mathfrak{m}_{1,1})|0\rangle_S. \qquad (IV.2)$$

The system responsible for refreshing the memory is what we call the internal bus. It has $N_g$ bus lanes, where the $l$th lane is responsible for refreshing the $l$th memory cell on $M_0$. All bus lanes cannot be turned on at once, but instead need to be turned on in a staggered manner over the 1st cycle. This requires a switch space W consisting in $N_g$ switches—one per lane. Each switch state can be in an “on” or “off” state at time $t_{k,l}$:

$$|t_{k,l}\rangle_W := |t_{k,l}\rangle_{W_1} |t_{k,l}\rangle_{W_2} \dots |t_{k,l}\rangle_{W_{N_g}}, \quad |t_{k,l}\rangle_{W_j} \in C_{W_j} := \{|\text{off}\rangle_{W_j}, |\text{on}\rangle_{W_j}\}, \qquad (IV.3)$$

where $|\text{off}\rangle_{W_j}, |\text{on}\rangle_{W_j}$ form an orthonormal basis for the Hilbert space $\mathcal{H}_{W_j}$. The switches are initiated to the all-off state: $|0\rangle_W := |\text{off}\rangle_{W_1} |\text{off}\rangle_{W_2} \dots |\text{off}\rangle_{W_{N_g}}$. Similarly, the memory cells on $M_0$ are initialised to a state $0 \notin \mathcal{G}$,

$$|0\rangle_{M_0} := |0\rangle_{M_{0,1}} |0\rangle_{M_{0,2}} \dots |0\rangle_{M_{0,N_g}}, \qquad (IV.4)$$

where $|0\rangle_{M_0}$ is orthogonal to all states in $C_{M_0}$. At later times, some of the memory cells in $M_0$ will have changed to take on values in $\mathcal{G}$, and as such the elements of $\{|t_{j,l}\rangle_{M_0}\}_{j,l}$ belong to $C'_{M_0} := C'_{\text{Cell}} \otimes^{N_g}, C'_{\text{Cell}} = \{|\mathfrak{m}\rangle\}_{\mathfrak{m} \in \mathcal{G} \cup \{0\}}$. We want to describe a scenario where the state $|0\rangle_{M_{0,k}}$ informs the control on C to turn the $k$th switch from the off state, $|\text{off}\rangle_{W_k}$, to the on state $|\text{on}\rangle_{W_k}$. Moreover, we will now assume that the control system on C reads memory cell $M_{0,k}$ and implements the corresponding gate on S or W over a time interval $t \in [t_{k-1,l}, t_{k,l}]$. Thus all switches are turned on in the first cycle and are not turned off again. Explicitly, and defining $|t_{k,0}\rangle_W$ as the state of the switch at time $t_{k,0}$:

$$|t_{k,0}\rangle_W := \left[ |\text{on}\rangle_{W_1} |\text{on}\rangle_{W_2} \dots |\text{on}\rangle_{W_k} |\text{off}\rangle_{W_{k+1}} |\text{off}\rangle_{W_{k+2}} |\text{off}\rangle_{W_{k+3}} \dots \right]_{N_g}, \qquad (IV.5)$$

for $k = 1, 2, \dots, N_g$ and where the notation $[\cdot]_{N_g}$ indicates that only the first $N_g$ kets in the sequence are kept. In later cycles, the switches stay in their on position. I.e., for $k = 0, 1, 2, \dots, N_g; r = 1, 2, \dots, L$

$$|t_{N_g,0}\rangle_W = |t_{k,r}\rangle_W := |\text{on}\rangle_{W_1} |\text{on}\rangle_{W_2} \dots |\text{on}\rangle_{W_k} |\text{on}\rangle_{W_{N_g}}. \qquad (IV.6)$$

In the 2nd cycle, the aim is for the control on C of the quantum frequential computer to implement the first $N_g$ gates in the gate sequence. For this, we need the internal bus, with control space $C_2$, to exchange the state on $M_0$ in eq. (IV.4) for one containing the instructions for the 1st $N_g$ logical gates, namely $\mathfrak{m}_{1,1}, \mathfrak{m}_{1,2}, \mathfrak{m}_{1,3}, \dots, \mathfrak{m}_{1,N_g}$. Similarly, in the $l$th cycle, the control on C should implement the gates corresponding to the sequence $\mathfrak{m}_{l,1}, \mathfrak{m}_{l,2}, \mathfrak{m}_{l,3}, \dots, \mathfrak{m}_{l,N_g}$.

Each of the $N_g$ internal bus lanes control their own memory block. In particular, the initial state of the $l$th memory block, $|0\rangle_{M_{\#l}}$, is a tensor-product state encoding a partition of the to-be-implemented gate sequence and thus belongs to the set:

$$C_{M_{\#l}} := \{ |0\rangle_{M_{0,l}} |\mathfrak{m}_{1,l}\rangle_{M_{1,l}} |\mathfrak{m}_{2,l}\rangle_{M_{2,l}} \dots |\mathfrak{m}_{L,l}\rangle_{M_{L,l}} |\mathfrak{m}_{1,l}, \mathfrak{m}_{2,l}, \dots, \mathfrak{m}_{L,l} \in \mathcal{G}\}, \qquad (IV.7)$$
$l = 1, 2, \dots, N_g$. Thus collectively, the initial state of the entire memory, $|0\rangle_M := |0\rangle_{M_{\#1}} |0\rangle_{M_{\#2}} |0\rangle_{M_{\#3}} \dots |0\rangle_{M_{\#N_g}} \in C_{M_{\#1},1} \otimes C_{M_{\#2},1} \dots \otimes C_{M_{\#N_g},1} =: C_M$ encodes the entire logical gate sequence which is to be implemented on S. See fig. 3 for an illustration of the subsystems involved in their initial-state configuration.

While the memory $M_0$ is initially in a product state over the distinct memory cells, since the control on $C_2$ will be operating at a much lower frequency than that of the logical gate implementation, $f = N_g L / (T_0 L) = N_g / T_0$, it need not maintain its product-state nature at times $\{t_{k,l}\}_{k,l}$, ($k \neq 0$ and $l \neq 0$). Intuitively, one may think of the state at these times as containing some memory elements $\{\mathfrak{m}_{k,l}\}_{k,l}$ which are in the process of being read/written to. Consequently, while initially the memory and control on $C_2$ will be in product-state form, $|0\rangle_M |0\rangle_{C_2}$, they will be described by a non-product state a later times: $\{|t_{j,l}\rangle_{MC_2}\}_{j,l}$. Nonetheless, it is important that the memory state being read during the interval $[t_{k-1,l}, t_{k,l}]$ by the control on C is in the appropriate state so that the gate sequence eq. (IV.2) is implemented. Denoting $|t\rangle_{M_{l,k}}$ the state of the cell $M_{l,k}$ at time $t$; we thus require,

$$|t\rangle_{M_{0,k}} = |\mathfrak{m}_{l,k}\rangle_{M_{0,k}}, \qquad (IV.8)$$

for all $t \in [t_{k-1,l}, t_{k,l}]$, and $l = 1, 2, 3, \dots, L$; $k = 1, 2, \dots, N_g$. Note that this condition also necessitates that the state of the memory cell on $M_{0,k}$ at time $t \in [t_{k-1,l}, t_{k,l}]$ is a product state with the other systems. Moreover, it allows one to define the bus frequency $f_{bus}$ as the frequency at which each bus lane re-freshens the memory $M_0$ with new information about the logical gate sequence. From eq. (IV.8) we see that this frequency, (i.e. the inverse time between updates of the memory cell on $M_{0,k}$) is bus-lane independent (i.e. $k$-independent), and given by

$$f_{\text{bus}} = \frac{1}{T_0}. \qquad (IV.9)$$

<figure><img src="image_5.png" /><figcaption>FIG. 3. Schematic of the computer's architecture (i.e. the systems involved). The switch W and memory M are shown in their initial states. The logical space S, is further divided into sub register spaces, as in a conventional quantum or classical computation register (this substructure only enters indirectly via the values of $\tilde{d}(\mathfrak{m})$, $\mathfrak{m} \in \mathcal{G}$ in this work). It is convenient to think of the dynamics induced via the Hamiltonian on states in $C_M$ as the result of a bus whose control emanates from a system $C_2$. It is also convenient to think of this bus as consisting in a number $N_g$ of lanes.ª The $l^{th}$ bus lane can copy and write to memory cells in memory block $M_{\#l}$ and can be turned on or off via changing the state of the switch in $C_{Wl}$ (which is located directly above the bus lane in the figure). The control system C can only read memory cells in $M_0$ sequentially from left to right, once per cycle and apply logical operations from $U_G$ to S sequentially and turn switches in W on or off. (Each cycle is of duration $T_0$.)</figcaption></figure>

As in section IV, we aim to mimic this behaviour up to a small error with a time-independent Hamiltonian and at

<footnote>ªThe “lane” terminology is in analogy with lanes in a motorway where the vehicles carry data, and the bus is the motorway. In this analogy, the vehicles cannot change lanes, so information initially in one lane will arrive at the end of the motorway in the same lane.</footnote>
particular gate frequency and power. The locality structure of our new Hamiltonian is

$$ H_{\text{MWSCC}_2} := H_{\text{M}_0\text{WSC}} + H_{\text{MWC}_2}, \quad H_{\text{MWC}_2} := H_{\text{C}_2} + \sum_{l=1}^{N_g} I_{\text{MW}}^{(l)} \otimes I_{\text{C}_2}^{(l)}, \quad H_{\text{M}_0\text{WSC}} := H_{\text{C}} + \sum_{l=1}^{N_g} I_{\text{M}_0\text{WS}}^{(l)} \otimes I_{\text{C}}^{(l)}, \qquad (\text{IV.10}) $$

where $I_{\text{MW}}^{(l)}$ only acts non-trivially on memory cells and switch states on $M_{\#l}W_l$ i.e.—the $l$th bus lane and its corresponding on/off switch. The Hamiltonian $H_{\text{M}_0\text{WSC}}$ is identical to those described in eq. (III.5) up to the interaction terms $\{I_{\text{M}_0\text{WS}}^{(l)}\}$ having additional support on the switch space—this is so that it can implement the turning on/off of the switches in the first cycle. The total Hamiltonian $H_{\text{MWSCC}_2}$ is self-adjoint and has a ground state energy of zero. As with Hamiltonians eq. (III.5), the Hamiltonians in eq. (IV.10) can depend on $\mathcal{G}$ but are independent of the initial memory state in $\mathbf{C}_M$. This constraint is motivated analogously to the reasons given before in section III.

Analogously to the $H_C$, $\{I_C^{(l)}\}_l$ pair, the terms $\{I_{C_2}^{(l)}\}_l$ are diagonal in the discrete Fourier Transform basis generated from the energy-eigenbasis of $H_{C_2}$.

As before, the power is defined as the ratio between the total initial state average energy and the total number of gates implemented:

$$ P' := \frac{E_0'}{T_0(L+1)}, \qquad E_0' := \text{tr}[\rho_{\text{MWSCC}_2}^0 H_{\text{MWSCC}_2}], \qquad (\text{IV.11}) $$

where $\rho_{\text{MWSCC}_2}^0$ is the density matrix for state $|0\rangle_M |0\rangle_W |0\rangle_S |0\rangle_C |0\rangle_{C_2}$. Analogously to how we defined the set of classical states for the control on $\mathbf{C}$, we need to define the set of classical states for the control of the bus on $C_2$ as the set of non-squeezed states: the set $C_{C_2}$ is the set of minimum-uncertainty states which share the same standard deviation with respect to $H_{C_2}$ and a canonically conjugate operator $t_{C_2}$ (up to normalization and vanishing corrections in the large $P$ limit). See appendix A2 for their full definitions.

Importantly, while we plan to implement a total of $LN_g$ logical gates sequentially, the Hamiltonian only has $2N_g$ interaction terms. Since $L$ will be large, this means we are “re-using” each interaction term many times during the computation which is far more efficient from an engineering perspective.

Note that the terms $H_{\text{M}_0\text{WSC}}$ and $H_{\text{MWC}_2}$ do not commute in general since they both act non-trivially on memory cells $M_0$ and switches W. Physical speaking, this is because $H_{\text{M}_0\text{WSC}}$ generates the dynamics for performing gates on S and W controlled on the state of $M_0$, while $H_{\text{MWC}_2}$ generates the dynamics to write to $M_0$ the necessary memory cells from $M_{\#1}, M_{\#2}, \dots, M_{\#L}$; controlling these operations on the state of W.

One may wonder why we included switch bits and did not simply use a simpler setup where they are always on. The reason for including switch states on $W_j$ for turning on/off the control of the memory block on $M_{\#j}$, is because of initial-condition requirements. In particular, in our construction, we need to turn on the memory blocks $\{M_{\#j}\}_j$ sequentially to avoid malfunction. It is expected (we will not prove this here) that if the states on $C_2$ where quantum, that these switch bits would not be required and all bus lanes could always be on. However, they only add a relatively small overhead to the computational architecture and, as we will see, will permit us to use far fewer quantum resources to obtain the same performance—see section VI 3 for a longer discussion.

In the following, $h(\bar{\epsilon})$ is independent of $P$ and $L$, while poly((L+1)P') is a polynomial in $(L+1)P'$ and independent of $\bar{\epsilon}$. Both are independent from the elements in the set $\{\tilde{d}(\mathfrak{m})\}_{\mathfrak{m}\in\mathcal{G}}$. We also extend the definition of $\tilde{d}(\mathfrak{m})$ for $\mathfrak{m} \notin \mathcal{G}$: $\tilde{d}(0) = 2$.

**Theorem 2** (Optimal quantum frequential computers only require a classical internal bus). For all gate sets $\mathcal{U}_G$, initial memory states $|0\rangle_M \in \mathcal{C}_M$ and initial logical states $|0\rangle_S \in \mathcal{P}(\mathcal{H}_S)$, there exists $|0\rangle_C, |0\rangle_{C_2}$, $\{|t_{j,l}\rangle_C, |t_{j,l}\rangle_{MC_2}\}_{j=1,2,\dots,N_g; l=0,1,\dots,L}$, $N_g$, $H_{\text{M}_0\text{SC}}$ parametrised by the power $P > 0$ and a dimensionless parameter $\bar{\epsilon}$ (where elements $|t_{j,l}\rangle_C, |t_{j,l}\rangle_{MC_2}$ satisfy eqs. (IV.1) and (IV.8) respectively), such that for all $j = 1, 2, 3, \dots, N_g$; $l = 0, 1, 2, \dots, L$ and fixed $\bar{\epsilon} > 0$, the large-$P$ scaling is as follows

$$ T\left( e^{-i t_{j,l} H_{\text{MWSCC}_2}} |0\rangle_M |0\rangle_{C_2} |0\rangle_W |0\rangle_S |0\rangle_C, \quad |t_{j,l}\rangle_{MC_2} |t_{j,l}\rangle_W |t_{j,l}\rangle_S |t_{j,l}\rangle_C \right) \qquad (\text{IV.12}) $$

$$ \le \left( \sum_{r=0}^{l} \sum_{k=1}^{j} \tilde{d}(\mathfrak{m}_{r,k}) \right) h(\bar{\epsilon}) \text{poly}((L+1)P') ((L+1)P')^{-1/\sqrt{\bar{\epsilon}}}, \qquad (\text{IV.13}) $$

where $|0\rangle\langle 0|_{C_2}$, $\text{tr}_M[|t_{j,l}\rangle\langle t_{j,l}|_{MC_2}] \in \mathcal{C}_{C_2}$ and

$$ f = \frac{1}{T_0} (T_0^2 (L+1) P')^{1-\bar{\epsilon}} + \delta f'', \qquad |\delta f''| \le \frac{1}{T_0} + \mathcal{O}\left(\text{poly}((L+1)P')((L+1)P')^{-1/\sqrt{\bar{\epsilon}}}\right) \text{ as } P' \to \infty. \qquad (\text{IV.14}) $$
Thus, up to an error in trace distance which decays faster than any polynomial, we have that an optimal quantum
frequential computer (either of type 1 or 2) can run over many cycles while only requiring a classical bus.

Here, analogously to as Theorem 1, the gate frequency increase achieved by increasing $1/T_0$ results in only a classical scaling with power. However, since $E'_0$ is $L$-independent, the combination $(L+1)P'$ is $L$-independent and as such $L$ can be increased without changing the gate frequency $f$ (this is what one should expect, since $L$ is the total number of cycles the computers runs through). Meanwhile, since $(\sum_{r=0}^l \sum_{k=1}^j \tilde{d}(\mathbb{m}_{r,k}))$ scales, at most, linearly in $L$ (since $G$ is a finite set), the error, characterized by the r.h.s. of eq. (IV.12), only increases linearly with $L$ while it decreases faster than any polynomial in $P'$. As such, the quantum frequential computer can run over many cycles before errors become intolerable. More precisely, by setting $\bar{\epsilon}$ small enough, the number of cycles can increase arbitrarily fast as a function of energy: $L \sim E'_0^{1/\sqrt{2\bar{\epsilon}}}$, and the r.h.s. of eq. (IV.12) still converges to zero for large $E'_0$.

Note that the power $P'$ goes to zero in this limit. This is not inconsistent with bound eq. (II.3), since it is derived under the assumption of a fixed computational runtime interval. This assumption is broken as soon as the total run time, $T_0(L+1)$, is not constant. However, in said limit, the initial state also tends to infinite energy, and after $L+1$ cycles, would be degraded and would require renewing. This renewal would itself cost resources such as energy, among other things. As such, while this limit is in-principle physical, $P$ in this case should not be considered as capturing the total cost. The principle goal of the next section is to remedy this.

V. NONEQUILIBRIUM STEADY-STATE DYNAMICS, POWER CONSUMPTION AND HEAT DISSIPATION

Theorems 1 and 2 demonstrate that computation can be formulated in a Hamiltonian dynamics picture with finite energy. However, we have seen that the errors in the computation build up over time, and at some point would cause a malfunction. At least in theory this is a priori not a problem: since in practice all algorithms one runs terminate in finite time, one could simply reset the oscillators to their initial state at the end of the computation. One could then simply quantify the costs associated with the reset process. However, this is not how conventional computers work, indeed, they work in a nonequilibrium steady-state configuration where the computer's clock is a self-oscillator [5]. The advantages of this is that self-oscillators automatically stabilise themselves leading to the above-mentioned nonequilibrium steady-state configuration where computation can (in principle) run indefinitely. This stabilisation mechanism requires head dissipation allowing the computer to remain in a low-entropy state.

The physics of classical and semi-classical self-oscillators is well studied [5–11], but the case of an oscillator in a non classical state implementing gates, such as in the case of a quantum frequential computer in unknown. An important question is whether a quantum frequential computer can also run in a nonequilibrium steady-state where the oscillators are stabilised. In such a scenario, it is no longer meaningful to define the power as the ratio of total initial energy divided by the time the computation can run for before large errors occur (as per Theorems 1 and 2) since this ratio is zero because the runtime is infinite. In contrast, a meaningful definition of power in the current setup is the total energy flowing into the system per unit of time. Since nonequilibrium steady-states can be formulated as open quantum systems, energy can be exchanged between the system and its environment. While such a change in the definition of power would be natural, it could be that in the quantum control setting, a gate frequency proportional to the power consumed is no longer obtainable. In this section, we will prove that it is indeed still obtainable and characterise the heat dissipation rate (we comment on the consequences for cooling in section VI).

We now describe the mathematical framework for this section. We use an open quantum system to stabilise the
oscillator on $C$ which is driving the computation. We will also have a bus playing the same role as in Theorem 2.
However, since we have already proved in Theorem 2 that it can operate at the classical limit, even in the case of
an optimal quantum frequential computer, we will not need to model it explicitly this time around. This is because
the physics of stable classical oscillators is well understood. In particular, a class of so-called self-oscillators are
stable under small perturbations and thus when used for the bus in our protocol, would be stabilised. However, since
these stabilization protocols are for classical oscillators, it is not clear if our quantum oscillator on $C$ can also be
autonomously stabilized while also implementing logical gates, and if so, at what cost.

We model the dynamics of the computer and its interaction with the environment via a dynamical semigroup.

Before we explain each term of said dynamical semigroup, let us pause for a moment to garner intuition from the Hamiltonian model of a quantum frequential computer in section IV about the properties said dynamical semigroup should posses: in the Hamiltonian model, the state of the oscillator on $C$ at times $t_{0,l} = lT_0$ is close to (but not equal to) its initial state, $|0\rangle_C$. These deviations grow with increasing $l$; see fig. 4 a) for an illustration. The origin of these deviations can be understood as a consequence of back-action on the control due to the implementation of gates, since
<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /><figcaption>FIG. 4. Qualitative illustration of representative dynamics of the oscillator on C in quadrature space over 3 cycles (1st cycle in blue, 2nd in red, 3rd in purple). Arrows indicate direction of dynamics over time. Fig a). State of the oscillator from section III: At the end of each cycle (of duration $T_0$) the oscillator gets close to the state it started in when initiating the cycle. In this way, small errors accumulate over many cycles ultimately leading to an intolerable error $E_R$. While we see from Theorem 2 that said errors decrease rapidly with increasing power, for any given power, they eventually become large after sufficiently many cycles. Fig b). State of the oscillator from section V: With high probability, the oscillator is renewed to its initial state at the end of each cycle, leading to a quantum frequential computer in a nonequilibrium steady-state. Observe that the dynamics during each cycle are not identical, due to differing perturbations caused by the implementation of different gate sequences in each cycle. As such, this renewal cannot be unique: it must map many states to the same initial state, correcting for these small errors towards the end of each cycle to prevent them becoming large over many cycles.</figcaption></figure>

when the interaction terms responsible for gate implementation, $\{I_{M_0WS}^{(l)} \otimes I_C^{(l)}\}_l$, are removed, the resulting dynamics of the control on C is *exactly* periodic, i.e. it is returned to its initial state $|0\rangle_C$ at times $t_{0,l} = lT_0$, $l \in \mathbb{N}_{>0}$.

We therefore want the dynamical semigroup to have the property that it maps the state of the oscillator on C to *exactly* its initial state periodically at the end of each time interval $[0, T_0]$; see fig. 4 b). Since these perturbations are small, this only consists in a small correction per cycle orchestrated via the coupling to the environment.

To avoid the action of this stabilisation mechanism inadvertently corrupting the application of the last gate in each cycle, we will refrain from applying said gate in each cycle. We will therefore only apply $N_g - 1$ gates per cycle and will only require $N_g - 1$ bus lanes (memory bloque $M_{\#N_g}$ is removed).<fnref n="3" /> Furthermore, since we will not model the bus explicitly, we can use a Hamiltonian of the form eq. (III.5) but without the interaction for the last gate. Recall that it is bloque-diagonal in the memory-basis of the register, $C_{M_0}$ (recall eq. (III.1)). Therefore, since the dissipative part of the dynamical semigroup will not couple to the register, this latter condition ensures that the memory will not evolve under the dynamics we are modelling explicitly.

The time-independent generator of dynamics is thus of the form

$$ \mathcal{L}_{M_0SWC}(\cdot) = -i[H'_{M_0SWC}, \cdot] + \mathcal{D}_C(\cdot), \qquad (V.1) $$

where $\mathcal{D}_C$ is a dynamical semigroup dissipater on C. In our case, it can be further decomposed as $\mathcal{D}_C = \mathcal{D}_C^{re} + \mathcal{D}_C^{no\ re}$, where $\mathcal{D}_C^{re}$ generates the renewal process: it maps all input states to one unique output state $|0\rangle_C$ and $|0\rangle_C$. This many-to-one aspect is crucial for stability since the state of the control towards the end of each cycle depends on the gate sequence implemented in said cycle. And since this differs for each cycle, so does the control state. As such, it is important that all said states are mapped back to the same state to complete the cycle of the oscillator exactly so that it is stable under the perturbations caused by gate implementations. The probability with which this renewal process occurs is however input-state dependent—This is also crucial, since it is important that the stabilisation events occur with overwhelming probability at the end of each cycle, and not at some other time earlier on in the cycle. This is the mechanism via which we will accomplish this.

The Hamiltonian part is

$$ H'_{M_0SWC} = H_C + \sum_{l=1}^{N_g-1} I_{M_0SW}^{(l)} \otimes I_C^{(l)}, \qquad (V.2) $$

<footnote n="3">³As we will see, this change will not affect the asymptotic since $N_g - 1 \sim N_g$ for large $N_g$.</footnote>
and bloque-diagonal in the $C_{M_0}$ basis.

The initial state of the computer we will consider in the theorem in this section are pure states of the form $|0\rangle_S|0\rangle_W|0\rangle_{M_0}|0\rangle_C$ (although see section VI for generalisations to mixed states). Similarly to the Hamiltonians in the previous sections, we demand that the generator of dynamics eq. (V.1) is independent of the gate sequence $(m_{l,k})_{l,k}$ encoded into the initial state $|0\rangle_M$. The reason for imposing this constraint is the same as that explained in section III.

Let us denote by $\rho_{M_0SWC}(\tau)$ said initial state after evolving for a time $\tau > 0$ according to the generator of dynamics, eq. (V.2). This state is a mixed state. What is more, since the renewal process is probabilistic in time, at any time $\tau = \tau_l + t$, the mixed state of the dynamics can be written as an ensemble of states where each element of the ensemble has been renewed a number $l \in \mathbb{N}_{\ge 0}$ of times: $\rho_{M_0SWC}(\tau) = \sum_{l=0}^{\infty} P(t|\tau_l) \rho_{M_0SWC}(t|\tau_l)$ is the state in the ensemble at time $\tau = \tau_l + t$, which has passed through the state $|0\rangle_C$ (due to the application of the renewal map $D^{\text{re}}$) a total of $l$ times in the time interval $[0, \tau_l]$, and none in the interval $(\tau_l, t]$. We denote by $P(t, +1|\tau_l)$ the probability associated with this state being renewed one more time at time $\tau$.<fnref n="4" />

Since we are not modelling the bus explicitly, the only requirement is that it can perform its function of updating the memory on $M_0$ analogously to how it did in section IV. We can write this condition in terms of $t$ as

$$|t\rangle_{M_{0,k}} = |m_{l,k}\rangle_{M_{0,k}}, \qquad (V.3)$$

for all $t \in [t_{k-1}, t_k)$, $k = 1, 2, \dots, N_g - 1$. Since we will be operating in a steady-state, eq. (V.3) must hold for all $l \in \mathbb{N}_{\ge 0}$ which implies we are either assuming that the memory on $M$ is unbounded or that the gate sequence is periodic (this is a merely mathematically convenient assumption for the obvious reasons).

As with Theorems 1 and 2, it is useful to introduce states which correspond to the state of the quantum frequential computer during its computational runtime under the hypothetical assumption that no errors occurred. In our current setup, this corresponds to states at times $\{t_j + \tau_l\}_{j,l}$ (given that the $l^{\text{th}}$ renewal occurred at time $\tau_l$), where the dynamics of the $l^{\text{th}}$ cycle has not introduced any errors. The utility of introducing such states is that we can see how close the actual dynamics to said states is, thus quantifying errors. We denote these states by $\{|[t_j|\tau_l]\rangle_{M_0SWA}|[t_j|\tau_l]\rangle_C\}_{j=0}^{N_g}$. Here A is a fictitious purifying system to allow us to work with pure states for simplicity of notation. It is useful for these states to only capture the idealised dynamics between each renewal. As such, they are defined to be equal to the actual dynamics just after each renewal event occurs:

$$|0|\tau_l\rangle_{M_0SWA} = |\rho(0|\tau_l)\rangle_{M_0SWA} = |\rho(0|\tau_l)\rangle_{M_0SWA}|0\rangle_C, \qquad (V.4)$$

where $\text{tr}_A[|\rho(0|\tau_l)\rangle\langle\rho(0|\tau_l)|_{M_0SWA}] = \rho_{M_0SWC}(0|\tau_l)$ and the last equality is due to the fact that the renewal process maps the state on $C$ to $|0\rangle_C$ at time $\tau_l$. The idealised states $|[t_k|\tau_l]\rangle_{M_0SWA}$ update via the exact application of the logical gates $\{U(m_{l,j})\}_{j=1}^k$ on $S$ or $W$ and a set of local unitaries on the memory $\{U_{M_0A}^{(l,j)}\}_{j=1}^k$ to guarantee the fulfilment of eq. (V.3):

$$|[t_k|\tau_l]\rangle_{M_0SWA} = U_{M_0A}^{(l,k)} \dots U_{M_0A}^{(l,2)} U_{M_0A}^{(l,1)} U(m_{l,k}) \dots U(m_{l,2}) U(m_{l,1}) |\rho(0|\tau_l)\rangle_{M_0SWA}. \qquad (V.5)$$

Since we assume this for all $l \in \mathbb{N}_{\ge 0}$, this assumption is implicitly assuming that the oscillator on $C_2$ has been stabilized, otherwise small errors would add up over many cycles leading to the impossibility to implement eq. (V.3) to high precision. The exact nature of the state of $M_0 \setminus M_{0,k}$ over the time interval $t \in [t_{k-1}, t_k]$ is not so relevant since the dynamics will have close to zero support on it. For concreteness, we will assume zero knowledge of this state i.e. that it is in a maximally mixed state.

As the following theorem proves, this system can now function in a nonequilibrium steady-state. As such, unlike in Theorems 1 and 2, defining power as initial energy over runtime is meaningless, as discussed above. Moreover, like in an actual computer, since this formulation of a quantum frequential computer is an open system, energy flows into the system and is dissipated out of it in the form of heat. Using standard theory [12, 13], the amount of energy flowing out of the system in an infinitesimal interval $[\tau, \tau + d\tau]$ is $-\text{tr}[H'_{M_0SWC}D_C(\rho_{M_0SWC}(\tau))]d\tau$, where $\rho_{M_0SWC}(\tau)$ is the solution to eq. (V.1) at time $\tau$. We however are interested in the energy flow per cycle. We can break the energy flow of the $l^{\text{th}}$ cycle into two parts: the energy required for the renewal event itself, $E^{\text{re}}$, occurring at time $\tau_l$, and any energy flow occurring in the time interval $(\tau_l, \tau_{l+1})$ corresponding to the time between the $l^{\text{th}}$ renewal and the subsequent one; denoted $E^{\text{after re}}$. On cycle average, $E^{\text{re}}$ is given by

$$\langle E^{\text{re}} \rangle := - \int_{0}^{\infty} ds \text{tr}[H'_{M_0SWC} D_C^{\text{re}}(\rho_{M_0SWC}(s|\tau_{l-1}))] \qquad (V.6)$$

<footnote n="4">⁴We use the convention $\tau_0 := 0$, such that $P(t, +1|\tau_0)$ is the probability associated with the 1st renewal.</footnote>
and is negative, implying that it corresponds to energy flowing into the computer. This can be interpreted as work done on C to renew the oscillator. On cycle average, $E^{\text{after re}}$ is given by

$$ \langle E^{\text{after re}} \rangle := - \int_{0}^{\infty} dt P(t, +1|\tau_l) \int_{0}^{t} ds \operatorname{tr}[H'_{M_0SWC} \mathcal{D}_{C}^{\text{no re}}(\rho_{M_0SWC}(s|\tau_l))], \quad (V.7) $$

and is positive, implying that between cycles energy flows out of the computer into the environment. It corresponds to energy from the renewal event which is slowly—over the course of a complete cycle—dissipated back out of the quantum frequential computer. This energy is likely irrecoverable and so in a worst-case scenario can be completely associated with heat. As we show in the proof of theorem 3, $\langle E^{\text{re}} \rangle$ and $\langle E^{\text{after re}} \rangle$ are both l-independent up to a vanishingly small and uniformly bounded quantity and as such we have not explicitly displayed their l-dependency in our notation. Physically, this vanishingly small l dependency stems from the fact that a different gate sequence is being implemented in each cycle.

Note that given a term $\mathcal{D}_{C}^{\text{re}}$ what stabilises the oscillator, the term $\mathcal{D}_{M_0SWC}^{\text{no re}}$ is necessary in order for the sum of the two terms to form a valid dissipater for a dynamical semigroup. Hence the necessity of the dissipation of energy within our model—This is likely a universal feature. We define the power as the total energy per cycle over the cycle time

$$ P'' := P^{\text{re}} + P^{\text{after re}}, \quad P^{\text{re}} := \frac{|\langle E^{\text{re}} \rangle|}{T_0}, \quad P^{\text{after re}} := \frac{\langle E^{\text{after re}} \rangle}{T_0}. \quad (V.8) $$

As before, we assume $T_0$ to be constant, so that an increase in $P''$ stems from an increase in energy per cycle, rather than a change in the cycle time itself (varying the cycle time $T_0$ is not very interesting, as commented on after Theorem 3). Some of the energy flowing out of the system, $\langle E^{\text{after re}} \rangle$, will come from the energy flowing into the system, $\langle E^{\text{re}} \rangle$, and thus this is an overestimate. However, since we want to deal with the worst-case-scenario energy consumption, we use this definition. Moreover, we show in the proof of Theorem 3 that $\langle E^{\text{after re}} \rangle \le -\langle E^{\text{re}} \rangle + \delta E$, where $\delta E$ vanishes as $\langle E^{\text{re}} \rangle$ becomes large. As such the inclusion of $\langle E^{\text{before re}} \rangle$ in the definition does not change how quantities scale with increasing $P''$, which is what we are interested in.

We are now ready to state our existence theorem for optimal nonequilibrium steady-state quantum frequential computers. We just clarify notation beforehand: In below theorem, since we have removed the $N_g^{\text{th}}$ bus lane, the memory states $\{\mathfrak{m}_{l,N_g}\}_l$ do not exist, and we make the association $\tilde{d}(\mathfrak{m}_{l,N_g}) = 1$. Like before, $g(\bar{\epsilon}) > 0$ is a $P$-independent function of $\epsilon > 0$, while $\text{poly}(P)$ is an $\bar{\epsilon}$-independent polynomial in $P$. They are both l independent.

**Theorem 3** (Nonequilibrium steady-state optimal quantum frequential computers exist). For all gate sets $\mathcal{U}_G$, initial gate sequences $(\mathfrak{m}_{l,k})_{l,k}$ with elements in $\mathcal{G}$, and initial logical states $|0\rangle_S \in \mathcal{P}(\mathcal{H}_S)$, there exists $|0\rangle_C$, $\{|t_j|\tau_l\rangle_C\}_{j=1,2,...,N_g; l \in \mathbb{N}_{\ge 0}}$, $N_g$, $\mathcal{L}_{M_0SWC}$ parametrised by the power $P'' > 0$ and a dimensionless parameter $\bar{\epsilon}$ (where elements $|[t_j|\tau_l]\rangle_C$, satisfy eq. (V.5)), such that for all $j = 1,2,3,...,N_g; l \in \mathbb{N}_{\ge 0}$ and fixed $\bar{\epsilon} > 0$, the following large-$P''$ scaling hold simultaneously

1) Given that $l \in \mathbb{N}_{\ge 0}$ renewals occurred in the time interval $[0, \tau_l]$, the probability that the next renewal occurs in the interval $[\tau_l + T_0 - t_1, \tau_l + T_0]$ is:

$$ \int_{\tau_l + T_0 - t_1}^{\tau_l + T_0} dt P(t, +1|\tau_l) = 1 - \epsilon_r, \quad 0 < \epsilon_r \le \left( \sum_{k=1}^{N_g} \tilde{d}(\mathfrak{m}_{l,k}) \right) g(\bar{\epsilon}) \text{poly}(P'') P''^{-1/(2\sqrt{\bar{\epsilon}})}, \quad (V.9) $$

2) The deviations in the state between renewals are small: For $j = 1, 2, ..., N_g$,

$$ T \left( \rho_{M_0SC}(t_j|\tau_l), \left| [t_j|\tau_l] \right\rangle_{M_0SWA} \left| [t_j|\tau_l] \right\rangle_C \right) \le \left( \sum_{k=1}^{j} \tilde{d}(\mathfrak{m}_{l,k}) \right) g(\bar{\epsilon}) \text{poly}(P'') P''^{-1/\sqrt{\bar{\epsilon}}}, \quad (V.10) $$

3) The gate frequency has the asymptotically optimal scaling in terms of power:

$$ f = \frac{1}{T_0} (T_0^2 P'')^{1-\bar{\epsilon}} + \delta f', \quad |\delta f'| \le \frac{1}{T_0} + \mathcal{O}\left(\text{poly}(P'') P''^{-1/(2\sqrt{\bar{\epsilon}})}\right) \text{ as } P'' \to \infty. \quad (V.11) $$

A few important observations: First note that, the bus width $N_g - 1$ is given by $T_0 f - 1$ and thus grows defectively linearly in the power [analogously to as in Theorem 2]. Secondly, the only dependency on $l$ in the r.h.s. of the inequalities in items 1), 2), 3) is through the summation over $\tilde{d}(\mathfrak{m}_{l,k})$. However, since $\mathcal{G}$ is a finite set, $\sum_{k=1}^{N_g} \tilde{d}(\mathfrak{m}_{l,k})$ is upper bounded by a linear-in-$P''$ function which is $l$ and $\bar{\epsilon}$ independent. This $l$ independency of the r.h.s. of
the inequalities is important, because it means that the errors are independent of how many cycles the quantum
frequential computer has been through. This is in contrast to the summation $(\sum_{r=0}^{l} \sum_{k=1}^{j} \tilde{d}(\mathfrak{m}_{r,k}))$ from eq. (IV.13)
in Theorem 2, which grows approximately linearly in $l$, the total number of cycles the computer at been through.

Also note that increasing $1/T_0$ would only result in an increase of $f$ in line with the classical scaling limit [see discussion after Theorem 1 which can readily be seen to apply equally well to Theorem 3].

Item 1) demonstrates that, up to a vanishing error, the renewal is occurring exactly when we want it to: in the interval just before the cycle ends. Moreover, recall that $t_1 = T_0/N_g \sim 1/P''$ so the length of interval of integration $[\tau_l + T_0 - t_1, \tau_l + T_0]$ approaches zero at a rate inversely proportional to the power.

As regards to item 2) while errors on the control are not accumulative, logical errors due to small errors in gate
implementation will still persist. These are small and can be corrected using conventional error correction as elaborated
on in section VI.

Since we have modelled the classical oscillator on $C_2$ driving the bus implicitly via the assumption eq. (V.3), the power consumption, $P''$, of the oscillator on $C$ controlling the implementation of logical gates is not the only power consumption of the quantum frequential computer. The oscillator on $C_2$ controlling the bus has the same cycle time and mean energy as the state on $C$ (recall section IV). The main difference is that, contrary to the state on $C$, it is a non-squeezed state. Squeezing states generally requires energy and as such the power required to stabilise the oscillator on $C_2$ should be less than that required to stabilise the oscillator on $C_2$. As such, at most, the power requirements for the oscillator on $C_2$ should be proportional to those of $C$, namely $P''$. Therefore, the total power requirements $P_{tot}$ should scale as $P_{tot} \sim P''$ and hence the quantum advantage of quantum frequential computers should be maintained when total power considerations are taken into account. Note also that these total-power-to-gate-frequency relationships are in line with the results obtained in Theorem 2, where both oscillators (the one on $C$ and $C_2$) where modelled explicitly and the total power of both oscillators taken into account. Of course, in practice this would likely be a large engineering challenge, requiring careful design not to waste too much power in non-linear dissipative processes. Moreover, other necessary processes such as register initialization, error correction of the logical computation registers and readout will require some power consumption, However, there is priori no reason to believe that the cost of readout and register initialization should be any different for a quantum frequential computer, as a conventional quantum or classical computer. We argue that the same should be true for the error correction of the logical computation register in section VI.

# VI. DISCUSSION

## 1. *Pure vs. mixed states*

Pure states are arguably an idealisation of mixed states. In this manuscript, in the main, we have used a pure-
state formalism for simplicity of expression. Moreover, in the theorems of the main text, the pure system state on $S$
can be identified with the purification of a mixed state of a smaller system which we would now associate with the
"actual" logical/physical system. In such a scenario, the upper bounds on the dynamics still hold when replacing the
purifications with their mixed counterparts since the trace distance satisfies the data processing inequality and the
operations performed on $S$ would act trivially on the ancillary purifying system. For the classical register, we could
replace it with a probabilistic mixture over the pure orthogonal register states. Since our bounds hold for every said
pure state, they would also hold for the ensemble state. This would of course correspond to increase error in the
computation due to uncertainty in the initial state of the memory—This setup would correspond to the computer
implementing different algorithms according to some probability distribution over them.

As for the control system, as can be seen in the appendices, there are parameters of the initial state which could
have been chosen differently for which effectively the same bounds hold, such as $n_0$. As such, replacing it with a
probabilistic mixture over said states would not change the results qualitatively.

## 2. *Error correction*

The logical space of the computation in a quantum frequential computer will likely require error correction. This
will naturally be simpler for a type-1 quantum frequential computer than the type-2 variants, since error correction
for solely classical algorithms is notoriously easier than for quantum ones; e.g. the Eastin-Knill no-go theorem [14]
does not hold for classical algorithms. The reason why error correction should still be necessary is that the gate
implementation is not error-free as we have seen. One may be concerned that this will be much harder for a quantum
frequential computer compared with a conventional quantum or classical computer running at a much lower gate
frequency. However, note that the theorems developed here show that errors per gate can decrease with power fast enough so that, in a fixed time window, while the total number of implemented gates is increasing, the total gate error is decreasing. Therefore, even if the gate frequency is much higher than the time required to perform one round of error correction, one can “pause” the computation for the required time needed to implement one round of error correction at regular intervals (say a fixed multiple of $T_0$). Thus error correction should only add a small multiplicative factor to the runtime. Of course, this reasoning only takes into account errors caused directly by the control itself, but not those from the environment. However, the rate of environmentally-induced errors should depend solely on the rate of background processes unrelated to the control itself (e.g. an incoming galactic gamma-ray). As such these errors should also be adequately correctable via the above scheme. Its also important to note that the “pausing” of the quantum frequential computer mentioned above can be achieved completely autonomously already within the models presented here. To do so, one only needs to include the identity gate *id* in gate set $G$ and insert sequences (*id*, *id*, ..., *id*) of length *J* in-between the memory cells encoding the algorithm at regular intervals. Since the identity gate acts trivially on *S* this will “pause” the computation for a time $Jt_1$ at regular intervals allowing external intervention. While these error correction intervals can be predicted in advance of starting the computation and hence already interlaced with the memory cells containing the algorithm before starting the computation, one can also do it on the fly with only classical control since the memory cells are only read/written to by the bus at the bus frequency, $f_{bus} = 1/T_0$, thus leading to ample time for updating. Note also that this “pausing” mechanism can also be used at read out, if the readout mechanism is slower than the logical gate frequency.

### 3. Intuitive explanation to why the internal bus of a quantum frequential computer can be classical

In the model of a quantum frequential computer of section IV, the oscillator on $C$ which controls the application of the logical gates is quantum while the oscillator on $C_2$ responsible for updating the memory cells on $M_0$ with gate instructions is classical. However, both oscillators perform the same number of unitary operations per cycle and consume the same power. Since the computer is an optimal quantum frequential computer, this may a priori seem contradictory in light of the upper bound eq. (II.2). The intuitive explanation of what is occurring is as follows: In the case of the application of logical gates on $C$ the time windows in which said gates are being applied have to be non-overlapping—This is because the logical gates do not commute in general. However, the time windows over which the unitaries are being applied by the bus control system on $C_2$ significantly overlap. This is not a problem because, on cycle average, only one unitary transformation is applied per bus lane. Each bus lane is on a different space (recall fig. 3), and thus unitaries applied to different bus lanes commute. The only restriction on the time window over which each unitary transformation is applied is that of the cycle time $T_0$, since if it were larger, then the applications of unitaries on the same bus lane would start to overlap and cause errors. Note that it is because these time windows are the same as the cycle time itself, that updates to memory cells in $M_0$ required for the next cycle, are already starting in the previous cycle. It is because of this fact, together with the desire to start in a product state of the memory cells in $M$, that the bus lanes needed to be turned on in a staggered fashion, and hence the need for the switch bits on $W$.

The classical state on $C_2$ used in the proof of the theorem in section IV is at the optimal classical limit (i.e. optimal quantum standard limit) of performance. We suspect that this is necessary and that noisier classical states would only suffice for controlling the bus of a sub optimal quantum frequential computer. Future work will aim to show this. Also see section VII 2 for discussion on classical systems which are anticipated to suffice.

A small after-remark: in the above explanation, the terminology “time window” suggests that before and after said window, the unitary in question is not being applied. This is purely for simplicity of explanation, in the actual model, the gates are being applied always, and thinking in terms of time windows with the above properties is simply an extremely good approximation of the underlying dynamics.

### 4. Oscillator synchronization

In the context of Theorem 3 some synchronization of the two oscillators is required due to the small statistical fluctuations in cycle time originating from interactions with the environment. Synchronisation of two classical oscillators is routine and well understood [15, 16] but one may wonder if quantum resources are required to do this in the case of a quantum frequential computer, since one of the oscillators is quantum in nature. We envisage that even for quantum frequential computers, the physics of classical synchronization suffice. This is because the conditions on the registers (eq. (V.3)) are only necessary conditions, in practice the classical bus oscillator can write this information to the allocated memory cell before this time and update it after this time. It can do this at some constant fraction of the bus frequency $f_{bus}$ with high probability. Indeed, this is actually the case for the classical oscillator on $C_2$
in the case of the oscillator used in the proof of Theorem 2 (as can be seen in appendix C). As such, the classical
oscillator on $C_2$ controlling the bus only needs to be in sync with the oscillator on $C$ within a constant fraction of the
frequency $f_{bus}$, which is a far cry from the much faster gate frequency $f$. Therefore, in order to keep the oscillator
on $C_2$ sufficiently in sync with that on $C$, the oscillator on $C$ only needs to generate a classically-detectable signal at
the end of each cycle. This can either be done by measuring a classical bit on $S$ which $C$ generates per cycle or via
monitoring classically when the renewal process occurs. In appendix D3 we show how the renewal process can easily
generate this classical bit in the setting of Theorem 3.

5. *Heat generation and cooling requirements*

We have shown that an optimal quantum frequential computer operating in a nonequilibrium steady state is achievable in which the heat generated is proportional to the power. This is not surprising, since heat generation is usually proportional to the power consumption in classical devices. Moreover, the cooling rate required to prevent a device from overheating is proportional to the rate at which heat is produced, so that a constant temperature can be maintained. Since we have shown that an optimal quantum frequential computer has a quadratically higher frequency as a function of power, it also has a quadratically higher frequency as a function of the required cooling.

In practice, there might be some heat generated when each gate is applied due to some noisy coupling with the
environment, but since our results show that this coupling would not be fundamental, in principle, it could be made
arbitrarily small by a sequence of improved less-noisy engineered gates operations. Thus not leading to a significant
overall increase in heat generation.

6. Irreversible computing

While our quantum frequential computer is modelled with unitary gates (both in the type-1 and type-2 cases),
it can nevertheless easily accommodate irreversible computation without difficulty: to do so, one has to erase and
subsequently re-use subspaces of the logical space $S$ if the information stored on it becomes redundant during the
computation. This—like in the conventional computing setting—allows for a smaller logical space overhead for certain
algorithms. It will of course have the usual associated costs with it: Landauer erasure entropy production.

7. *Nature of the logical space in a type-1 quantum frequential computer*

In this type, $\mathcal{G}$ only admits a classical gate set, and hence the logical space is always in a tensor-product state of
logical zeros and ones after the application of each gate—as is to be expected in classical computation. However,
we have not restricted the dynamics during the application of said gates. Therefore, it is likely that said dynamics
takes logical states momentarily into superpositions of logical zeros and ones only returns to a logical state of zeros
and ones at the end of the gate application. In this sense, the logical space, even when implementing purely classical
algorithms, is “quantum”. However, conventional classical active error correction techniques still apply, even when
the logical space is only classical between gate applications. This is an advantage of a type-1 quantum frequential
computer over the type-2 variant since classical active error correction is easier than quantum error correction as
discussed in section VI 2.

8. *Classical control states*

In this manuscript, we have used the term “classical states” to refer to quantum systems on $C$ or $C_2$ with standard
quantum limit properties. The motivation is that quantum theory is the best representation of the world that we have
for non-relativistic physics, and as such the most meaningful. We have also noted via a simple example in section II
how a Liouvillian description leads to unphysical results, when optimising the power-gate-frequency relation. It is
expected that the results of this manuscript can be reproduced when the systems we have referred to as classical can
be replaced by stochastic ones. Furthermore, oscillators with the same relevant properties as the conventional laser
should suffice for usage as the classical oscillator systems we consider here—see section VII 2 for more details.
## 9. Coupling terms in the Hamiltonian

We have explained that the state on $\mathcal{C}$ is non-classical in the case of a quantum frequential computer. It is worth remarking that the nature of the interaction terms $\{I_C^{(l)}\}_l$ used for the Hamiltonians of the quantum frequential computers in this manuscript also appear to be critical. They have to be chosen in a way that they exert minimal back-reaction on the state of the oscillator in order not to degrade it too quickly.

As detailed in section III, they are chosen to have a particular form, namely diagonal in the discrete Fourier transform basis of the eigenbasis of the free Hamiltonian $H_C$ (a quantum harmonic oscillator). This is not a common basis for interaction terms to couple to. It is far more common for the coupling terms to be diagonal in the position basis, (i.e. a function of the position operator $\hat{x}$) or sometimes the momentum basis (i.e. a function of the momentum operator $\hat{p}$). An interesting question is whether such Hamiltonians (i.e. Hamiltonians of the form eq. (III.5) with $I_C^{(l)} \mapsto I_C^{(l)'}(\hat{x})$, $I_C^{(l)'}(\cdot) : \mathbb{R} \to \mathbb{R}_{\ge 0}$) are capable of producing quantum frequential computers—We suspect not. Interaction terms of the form $\{I_C^{(l)}\}_l$ can be constructed in physical settings, as shown theoretically in [17].

## 10. Quantum speed limits

All quantum systems evolving under Hamiltonian dynamics obey so-called quantum speed limits. These are lower bounds on the time required for a quantum state to become orthogonal to itself as a function of its mean and standard deviation in energy [18, 19]. While originally formulated for Hamiltonian evolutions, they were later generalised to dynamical semigroups [20, 21]. Here we will discuss their relation to the results in this paper, starting from the classical and quantum upper bounds, eqs. (II.2) and (II.3), followed by Theorems 1 and 2.

The optimal classical bound of eq. (II.2) does not follow from what was known about quantum speed limits. Indeed, until recently it was widely believed that classical systems do not satisfy a speed limit at all [22, 23], not least as to whether there exists any quantum advantage. It is necessary to have both the classical and quantum limits in order to show there is a quantum advantage to computing when the control is quantum even for classical algorithms. Without such a result, the concept of a quantum frequential computer is void of meaning. The upper quantum bound, eq. (II.3), could have alternatively been derived from quantum speed limits. However, deriving both bounds using a metrology approach helps to understand their connection. Furthermore, the upper quantum bound, eq. (II.3) (or equivalently, quantum speed limits) while imposing an upper bound on the speed of computation, does not by any means imply that it is actually achievable by a computer, since a useful computer requires far more structure than merely passing through a sequence of orthogonal states in tandem with the application of the gate sequence. Theorem 1 on the another hand, shows that it is an achievable rate for universal computation.

In [19], it was shown that the Salecker-Wigner-Peres clock model [24, 25] saturates the quantum speed limit bounds derived in [18, 19]. These can be viewed as infinitely squeezed versions of the quasi-ideal clock [26, 27]. The control state used for $\mathcal{C}$ in the proofs of Theorems 1 to 3 correspond to quasi-ideal clock states but with finite squeezing (the exact amount is chosen to optimise performance.) These quasi-ideal clock states maintain, up to small corrections, a constant amount of squeezing with respect to a fixed basis. Meanwhile, this is not true when the amount of initial squeezing surpasses a certain threshold. Moreover, in this latter scenario, the squeezing oscillates in time, and the states becomes anti-squeezed in the basis which diagonalises the interaction terms. Thus unfortunately, we suspect that any computer using Salecker-Wigner-Peres clock states for the control, would not result in a quantum frequential computer—Future research is required to verify or refute this. Moreover, quasi-ideal clock states allow for good approximations to canonically conjugate operators, while Salecker-Wigner-Peres clock states do not—see [26, 27] for details

The mean energy of the state required to sequentially pass through $N$ orthogonal states in the Salecker-Wigner-Peres clock model is proportional to $N$ itself [19]. The same is true for the Hamiltonian used in the proof of Theorem 1. The consequence of this is the undesirable necessity to increase gate frequency linearly in the total number of gates which can be implemented. As discussed, this is remedied in Theorem 2. When phrased in the language of quantum speed limits, Theorem 2 provides new results, because it shows that the optimal orthogonalization rate can be maintained for far longer than previously known in a Hamiltonian framework.

In [28], the results from [18, 19] were used to conclude a lower bound on the amount of power required to implement one gate in a computation in the context of unitary Hamiltonian dynamics. These results re correct. However, a computer requires the application of many gates to be useful, and it does not follow that the total power for implementing $N$ gates is $N$ times the power of implementing one gate, since the energy can be recycled in the Hamiltonian picture used in [28]. Indeed, this is precisely the case with Theorems 1 and 2. See discussion following Theorem 2 on this topic and how it was used to motivate section V.
## 11. Technicalities

From a technical standpoint, the main tools for deriving the upper bounds from section II came from Cramér-Rao-bound-like arguments and [4]. While Theorems 1 to 3 use technical results derived across papers [26, 27, 29] and new insights developed here. Since the proofs are by construction (up to a constant in an exponentially decaying term which is via existence), the power of the polynomials poly(·) in Theorems 1 to 3, can be calculated exactly if desired. It is expected that they will be of low order.

# VII. CONCLUSION

## 1. Summary

We have introduced a new class of quantum computer called a quantum frequential computer which comes in two variants; type 1 can only process classical algorithms while type 2 can also process quantum ones. In a type-1 quantum frequential computer, the only part of the computer which cannot be modelled using classical physics is the gate control, while in a type-2 variant both the control and the computational logical space are quantum. We prove that an optimal quantum frequential computer has a quadratic runtime advantage over both classical and conventional quantum computers given a specific power consumption or cooling rate. Conversely, they can also run algorithms in the same runtime as a classical computer (in the case of type 1) or conventional quantum computer (in the case of type 2) while only requiring quadratically less power to do so.

We also show that quantum frequential computers only require an internal data bus which operates using classical physics. This latter point is important because in the case of a type-1 quantum frequential computer, only a small part of the total computer architecture (the logical-gate control) needs to be quantum while the rest of the computer can be described by classical physics. Since quantum systems are notoriously more fragile than their classical counterparts, this makes the future construction of a quantum frequential computer more feasible.

One of the biggest advantages of a type-1 quantum frequential computer is that it provides a quadratic runtime speed up for all classical algorithms. Many of these computational problems have no quantum algorithm either because it does not exist or because it has not been discovered. Either way, a quantum frequential computer may be the only method to obtain a quadratic runtime advantage for said problems.

## 2. Outlook

One important criteria for how useful a quantum frequential computer can be in practice in the near term, is at what power values does its quantum advantage start. Indeed, in this manuscript we dealt solely with asymptotic behaviour. There is good reason to be optimistic since in [17] similar mathematics to that used here for the control on C was used to demonstrate that a quantum quadratic advantage on the decay of an electron via spontaneous emission achieves the quantum advantage in timing already at Hilbert space dimension two. Therefore, there is reason to be hopeful that a quantum frequential computer is achievable already in a low-power regime. The lack of such a result for conventional quantum computers is one of the reasons why truly useful versions are so hard to build [30].

One of the next big challenges is understanding what physical systems can be used to build a quantum frequential computer. To much surprise, it has recently been discovered that conventional lasers only operate at a classical limit of coherence length (also known as the Schawlow-Townes limit), while a quantum limit lays beyond [31]. The physics of these standard quantum limited and Heisenberg limited lasers apply more generally to other oscillating systems [32]. We envisage that a quantum frequential computer can be built using the physics of Heisenberg limited oscillators while its internal bus can operate using an optimal standard quantum limit oscillator such a conventional laser. Proposals for building said oscillators have already been made [31] and could be used in the construction of a quantum frequential computer while providing insight into designs for the necessary oscillator-gate couplings which will be required for their construction.

All this said, whatever subsequent work reveals about the practicalities of building types 1 and 2 quantum frequential computers, useful versions will inevitably be *hard* to build. However, such challenges should not deter us from trying, just like they should not deter us from working on the lofty goal of building a useful conventional quantum computer: ultimately both will be extremely challenging, but so long as theory predicts that they should be buildable in the real world, humanity should not give up trying.
ACKNOWLEDGMENTS

We acknowledge useful discussions with Álvaro Alhambra, Christopher Chubb, Omar Fawzi, Mark Mitchison and Daniel Stilck França.

This work benefited from a government grant managed by the Agence Nationale de la Recherche under the Plan France 2030 with the reference ANR-22-PETQ-0006.

CONTENTS

<table><tr><td>I. Introduction</td><td>1</td></tr><tr><td>II. Classical and quantum upper limits to computation</td><td>1</td></tr><tr><td>III. Existence of optimal Type-1 and type-2 quantum frequential computers</td><td>3</td></tr><tr><td>IV. Quantum frequential computers only require a classical internal bus</td><td>5</td></tr><tr><td>V. Nonequilibrium steady-state dynamics, power consumption and heat dissipation</td><td>9</td></tr><tr><td>VI. Discussion</td><td>13</td></tr><tr><td>VII. Conclusion</td><td>17</td></tr><tr><td>Acknowledgments</td><td>18</td></tr><tr><td>A. Classical limit and quantum upper bounds</td><td>19</td></tr><tr><td>1. Proof for upper classical and quantum bounds based on metrology</td><td>19</td></tr><tr><td>2. Definition for sets C<sub>C</sub> and C<sub>C2</sub> of classical states of the control</td><td>20</td></tr><tr><td>B. Proof of Theorem 1: Attaining the quantum limit</td><td>21</td></tr><tr><td>1. Main structural technical lemma</td><td>21</td></tr><tr><td>2. Some additional definitions required for the lemmas of appendix B 3</td><td>23</td></tr><tr><td>3. Final technical lemmas</td><td>24</td></tr><tr><td>4. Proof of the theorem</td><td>30</td></tr><tr><td>5. Generic known useful technical lemmas</td><td>35</td></tr><tr><td>C. Proof of Theorem 2: Attaining the quantum limit with a classical bus</td><td>36</td></tr><tr><td>1. Main technical lemma: A decoupling of error contributions</td><td>36</td></tr><tr><td>2. Lemmas bounding error contributions from control on C</td><td>38</td></tr><tr><td>3. Description of the control on C<sub>2</sub></td><td>40</td></tr><tr><td>4. Generalization of Theorem 9.1 in [26]</td><td>43</td></tr><tr><td>5. Lemmas bounding error contributions from control on C<sub>2</sub></td><td>44</td></tr><tr><td>D. Nonequilibrium steady-state dynamics</td><td>52</td></tr><tr><td>1. Setup of the dynamical semigroup</td><td>52</td></tr><tr><td>2. Proof of Theorem 3</td><td>55</td></tr><tr><td>3. Generation of a classical signal when each renewal process occurs</td><td>64</td></tr><tr><td>References</td><td>64</td></tr></table>
# Appendix A: Classical limit and quantum upper bounds

## 1. Proof for upper classical and quantum bounds based on metrology

In the Fisher information approach to quantum metrology, the mean square error of the signal (which in our case is $t \in [0, T_0)$) is given by [33]

$$ \langle (t_{\text{est}}(\xi) - t)^2 \rangle = \int_{\xi} d\xi P(\xi|t)(t_{\text{est}} - t)^2, \qquad (A.1) $$

where $P(\xi|t)$ is the probability of predicting measurement outcome $\xi$ given that the signal takes on value $t$, and $t_{\text{est}}(\xi) \in \mathbb{R}$ is our estimate for $t \in [0, T_0)$ which we make based on our measurement outcome $\xi$. By assumption, the logical space of our computer is initialised to $|0\rangle$ and then passes through a sequence $(|l\rangle)_{L_0}^{N_g}$ of states after the application of the first $l$ gates: the logical state is $|l\rangle_{L_0}$ for $t = t_l$ for $l = 0, 1, 2, \dots, N_g - 1$. The conditional probability $P(\xi|t)$ can be written as $P(\xi|t) = \text{tr}[M(\xi)\rho_{\text{Com}}(t)]$ where $\{M(\xi)\}_{\xi}$ is a complete set of POVM elements and $\rho_{\text{Com}}(t)$ the state of the computation (which includes the logical space as a subspace) at time $t$.

For our estimate, we choose projective POVMS on the logical state the computation passes through, namely

$$ M(\xi) = \sum_{l=0}^{N_g-1} |l\rangle\langle l|_{L_0} \delta(l - \xi), \qquad (A.2) $$

where $\delta(\cdot)$ is the Dirac-delta distribution. Our chosen estimate $t_{\text{est}}(\xi)$ of the signal is such that it coincides with $t_l$ when measurement outcome $\xi = l$ is obtained, up to a small bias $\Delta_0 T_0 / N_g > 0$ which we introduce for technical reasons and will choose below:<fnref n="5" />

$$ t_{\text{est}}(\xi) = (\xi + \Delta_0) \frac{T_0}{N_g}, \qquad (A.3) $$

Thus the root-mean-squared error in our measurement as a function of the signal $t$ at times $t = t_l$ is

$$ \Delta t_{\text{est}}(t_l) := \sqrt{\langle (t_{\text{est}} - t_l)^2 \rangle} = \Delta_0 \frac{T_0}{N_g}, \qquad (A.4) $$

for $l = 0, 1, \dots, N_g - 1$. We start by proving eq. (II.3), followed by eq. (II.2). From the appendix of [3] it is stated that for any signal $x \in \mathbb{R}$ with a mean-squared-error $\Delta X(x)$ for which there exist $x, x'$ such that:

$$ 1) \quad \Delta(x) > 0, \quad \Delta(x') > 0 \qquad (A.5) $$

$$ 2) \quad |x - x'| = (\lambda + 1)(\Delta X(x) + \Delta X(x')) \qquad (A.6) $$

$$ 3) \quad \Delta(x) = \Delta(x') \qquad (A.7) $$

where $\lambda = 4.64$, then

$$ \Delta X(x) \le \frac{\kappa}{\text{tr}[H\rho_0] - E_0}, \qquad (A.8) $$

where $\kappa$ is a numerical constant $\kappa \approx 0.091$, $\rho_0$ the initial probe state, $\rho(x) = e^{xiH} \rho_0 e^{-xiH}$ is the probe state for signal value $x$, and $E_0$ is the ground state of Hamiltonian $H$. (Here we have specialised to the case of a single copy of the probe state since this is sufficient for our purposes.)

In our case, we can choose the two values of the signal to be $t = t_{l+1}$ and $t' = t_l$, such that $|t - t'| = T_0 / N_g$, and $\Delta t_{\text{est}}(t_l) + \Delta t_{\text{est}}(t_{l+1}) = 2\Delta_0 T_0 / N_g$. Therefore, by choosing $\Delta_0 = 1/(2(\lambda + 1)) \approx 0.0887$ it follows that

$$ \Delta t_{\text{est}}(t_l) \le \frac{\kappa}{\text{tr}[H_{\text{Com}}\rho_0] - E_{\text{Com}}^0}, \qquad (A.9) $$

<footnote n="5">⁵Other choices are possible, and would lead to different bounds. However: 1) We only care about scaling, so different valid choices are not helpful. 2) The Cramer-Rao bound has a singular point at $t = t_{\text{est}}$ so this choice is not valid.</footnote>
where we have denoted the ground state of $H_{\text{Com}}$ by $E_{\text{Com}}^0$. Therefore, by recalling that $f = N_g/T_0$ with no restrictions of the probe state nor the Hamiltonian, from eqs. (A.4) and (A.8) we arrive at eq. (II.3).

We now move on to the proof of eq. (II.2). Using techniques from quantum metrology, in [4] the quantum advantage for squeezed states under similar unitary encoding scheme via a signal-independent Hamiltonian was investigated. Their setup is such that our choice of estimator above is such that their results also apply to it. The authors show that given an energy budget $E = \text{tr}[H\rho]$, (for a signal $\varphi$ unitarily encoded via hamiltonian $H$ into a probe state $\rho(\varphi)$), the optimal non-squeezed, state can achieve a bound on $\Delta\varphi$ which scales as $\sqrt{g(E)}$ for large $E$, where $g(E)$ is the optimal scaling of $\Delta\varphi$ with $E$ when the optimal squeezed state of energy $E$ is used. The optimal squeezed states can achieve the optimal Heisenberg scaling is the same as that above, and so $g(E) \sim E$.

In our case, we have for $l = 0, 1, 2, \dots, N_g - 1$:

$$ \Delta t_{\text{est}} \le \frac{c_0}{\sqrt{\text{tr}[H_{\text{Com}}\rho_0] - E_{\text{Com}}^0}} \quad (A.10) $$

if $\rho_{\text{Com}}(t_l)$ and $\rho_{\text{Com}}(t_{l+1})$ [where $\rho_{\text{Com}}(t) := e^{itH_{\text{Com}}} \rho_{\text{Com}}(0)e^{-itH_{\text{Com}}}$] are non-squeezed. Here $c_0$ is a numerical constant from [4]. Thus since $f = N_g/T_0$, $P := E/T_0$ and our signal is $t$, for constant $T_0$, eq. (II.2) follows.

The definition of classical states for which bound eq. (II.2) holds, is that of non-squeezed states used in [4] which is that of [34]. In our setup, this corresponds to minimum uncertainty eigenstates of the operator $L(\lambda) := \lambda M' + iH_{\text{Com}}$, with $|\lambda| = 1$ and where $M' = \sum_{l=0}^{N_g-1} |l\rangle\langle l|_{L_0}$. (When $|\lambda| > 1$, the eigenstates of $L(\lambda)$ are said to be squeezed in $H_{\text{Com}}$ and anti-squeezed in $M'$; and vice versa when $|\lambda| < 1$.)

## 2. Definition for sets $C_C$ and $C_{C_2}$ of classical states of the control

At times $\{t_j\}_{j=0}^{N_g}$, the state of the memory of the computer described section III is always in a classical state. Likewise, in the case of a gate set $\mathcal{G}$ which can only implement classical algorithms, the logical space of the computer $S$ is also in a classical state at said times. Thus the only component which may be in a quantum state is the state of the control on $C$ itself. Moreover, even in the case where $\mathcal{G}$ permits the application of quantum algorithms, the logical gate speed $f$ is independent of the state of $S$; thus while the states of $S$ may be quantum at times $\{t_j\}_{j=0}^{N_g}$, this should not lead to a quantum advantage in frequency. In this case (like with the classical algorithm case), the only source of quantumness which may lead to a better scaling of $f$ with power $P$, is the state of the control at times $\{t_j\}_{j=0}^{N_g}$. As such, we will introduce a special set of states on $C$ which we will call the classical set. Its relevance is that we show that the classical upper bound eq. (II.2) can be reached under these circumstances and it is thus tight (as far as the scaling is concerned).

As we have seen in appendix A 1, the definition of a squeezed/non-squeezed state requires the identification of two observables: one for measurement, the other for the generation of dynamics. Here the relevant ones are the Hamiltonian of the control, $H_C$, and the basis which diagonalises the interaction terms $\{I_C^{(l)}\}_{l=1}^{N_g}$. The Hamiltonian $H_C$ we use in the proof of Theorem 1 is $H_C = \sum_{n=0}^{d-1} n |E_n\rangle\langle E_n|_C$,<fnref n="6" /> while the basis which diagonalises the terms $\{I_C^{(l)}\}_{l=1}^{N_g}$ is the discrete Fourier transform basis of the orthonormal basis $\{|E_n\rangle_C\}_n$, namely $\{|\theta_k\rangle = \frac{1}{\sqrt{d}} \sum_{n=0}^{d-1} e^{-i2\pi nk/d} |E_n\rangle\}_{k=0}^{d-1}$. One thus defines the “time observable” by $t_C := \sum_{k=0}^{d-1} k |\theta_k\rangle\langle\theta_k|_C$.<fnref n="7" /> Thus defining the operator $L_C := \lambda t_C + iH_C$, we say that a pure state $|\psi\rangle_C$ on $C$ is classical (non-squeezed) if it is an eigenstate of $L_C$ for which $|\lambda| = 1$ up to vanishingly small additive corrections in the large $d$ limit, i.e. if $L_C |\psi(d)\rangle_C = E(\psi) |\psi(d)\rangle_C + |\epsilon(d)\rangle_C$ for $|\lambda| = 1$, $E(\psi) \in \mathbb{C}$ and where $\langle\epsilon(d)|\epsilon(d)\rangle_C = 0$ as $d \to \infty$. We denote the set of such states by $C_C$. Note that while this set is defined asymptotically for large $d$, this quantity increases with power $P$, so $d \to \infty$ as $P \to \infty$ and so the set is well-defined in the context of Theorem 1.

For the case of Theorem 2, in section IV, the classical states on $C_2$ are correlated with the state of the memory $M$. As such, we cannot define them as eigenstates of an operator. However, the important characteristic of non-squeezed states is that they are minimum uncertainty states and their standard deviation with respect to the two observables with respect to which they are defined. As such, we define the set of non-squeezed states on $C_2$, as the set of minimum-uncertainty states which share the same standard deviation with respect to $t_{C_2}$ and $H_{C_2}$ as the non-squeezed pure states for $L_{C_2} = \lambda t_{C_2} + iH_{C_2}$.

<footnote n="6">⁶Up to a constant factor with units of energy.</footnote>

<footnote n="7">⁷Up to a constant factor with units of time—See [26] for more insights into $t_C$ and $H_C$.</footnote>
More formally, one can define this set as follows. In eq. (IV.10), the Hamiltonian $H_{C_2}$ is defined identically to $H_C$ up to the change of Hilbert space $C \to C_2$. We can thus define the discrete Fourier transform basis $\{|\theta_k\rangle_{C_2}\}_k$ analogously to above but for $C_2$. (The interaction terms $\{I_{C_2}^{(l)}\}_{l=1}^{N_g}$ are also diagonal in this basis.) The operator $t_{C_2}$ can thus be defined as $t_{C_2} := \sum_{k=0}^{d-1} k |\theta_k\rangle\langle\theta_k|_{C_2}$, and the non-squeezed pure states on $C_2$, by solving $L_{C_2}|\psi(d)\rangle_{C_2} = E(\psi)|\psi(d)\rangle_{C_2} + |\epsilon(d)\rangle_{C_2}$ for $|\lambda| = 1$, $E(\psi) \in \mathbb{C}$ and where $\langle\epsilon(d)|\epsilon(d)\rangle_{C_2} = 0$ as $d \to \infty$. We define $\rho_{C_2}$ as classical (non-squeezed) if there exists $|\psi(d)\rangle_{C_2}$ such that $\Delta t_{C_2}(\rho_{C_2}) := \text{tr}[t_{C_2}^2 \rho_{C_2}] - (\text{tr}[t_{C_2} \rho_{C_2}])^2$ and $\Delta H_{C_2}(\rho_{C_2}) := \text{tr}[H_{C_2}^2 \rho_{C_2}] - (\text{tr}[H_{C_2} \rho_{C_2}])^2$ are equal to $\langle C_2 \psi(d) | t_{C_2}^2 | \psi(d) \rangle_{C_2} - (\langle C_2 \psi(d) | t_{C_2} | \psi(d) \rangle_{C_2})^2$ and $\langle C_2 \psi(d) | H_{C_2}^2 | \psi(d) \rangle_{C_2} - (\langle C_2 \psi(d) | H_{C_2} | \psi(d) \rangle_{C_2})^2$ respectively. We denote the set of all such states by $\mathcal{C}_{C_2}$.

## Appendix B: Proof of Theorem 1: Attaining the quantum limit

Before stating the proof of the main theorem, we prove several crucial lemmas. The proof of the main theorem is by construction. We will specialise definitions as we proceed and as becomes necessary to prove the desired results.

### 1. Main structural technical lemma

Let us introduce hamiltonians of the form

$$H_{\text{SC}} := H_{\text{C}} + \sum_{l=1}^{N_g} I_{\text{S}}^{(l)} \otimes I_{\text{C}}^{(l)}. \qquad (\text{B.1})$$

In the following lemma, we assume that the states $\{|t_j\rangle_S, |t_j\rangle_C\}_{j=0}^{N_g}$ are normalised and $H_{\text{SC}}$ in eq. (B.1) is finite-dimensional.<fnref n="8" />

**Lemma B.1.** For $j = 1, 2, 3, \dots, N_g$

$$\| e^{-it_j H_{\text{SC}}} |0\rangle_S |0\rangle_C - |t_j\rangle_S |t_j\rangle_C \|_2 \le \sum_{k=1}^j \| |t_k\rangle_S |t_k\rangle_C - e^{-it_1 H_{\text{SC}}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C \|_2 \quad (\text{B.2})$$

$$\le \sum_{k=1}^{j} \left( \| |t_k\rangle_S |t_k\rangle_C - e^{-it_1 H_{\text{SC}}^{(k)}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C \|_2 \right) \quad (\text{B.3})$$

$$+ t_1 \max_{x \in [0, t_1]} \| \bar{H}_{\text{SC}}^{(k)} e^{-ixH_{\text{SC}}^{(k)}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C \|_2 \quad (\text{B.4})$$

where

$$H_{\text{SC}}^{(k)} := H_{\text{C}} + I_{\text{S}}^{(k)} \otimes I_{\text{C}}^{(k)}, \qquad \bar{H}_{\text{SC}}^{(k)} := H_{\text{SC}} - H_{\text{SC}}^{(k)} = \sum_{\substack{l=1 \\ l \ne k}}^{N_g} I_{\text{S}}^{(l)} \otimes I_{\text{C}}^{(l)}. \qquad (\text{B.5})$$

The Lemma is useful because it permits us to compute the error by only computing unitary evolution w.r.t. $H_{\text{SC}}^{(k)}$ rather than $H_{\text{SC}}$. While the latter does not factorise into a product between system and control, it is readily apparent that the former does. This is of great utility as we will see in later proofs.

**Proof.** The first inequality in eq. (B.2) is a direct consequence of Lemma B.4. To see this, in Lemma B.4 we choose $|\Phi_m\rangle = |t_m\rangle_S |t_m\rangle_C$ and $\Delta_m = e^{-it_1 H_{\text{SC}}}$ and note $t_j = jt_1$. We can now add and subtract an appropriately-chosen term and apply the triangle inequality to achieve

$$\| e^{-it_j H_{\text{SC}}} |0\rangle_S |0\rangle_C - |t_j\rangle_S |t_j\rangle_C \|_2 \qquad (\text{B.6})$$

<footnote n="8">⁸This last assumption is overkill; indeed under minimal assumptions it can be extended to the infinite-dimensional case. However, for our purposes this will suffice.</footnote>
$$ \leq \sum_{k=1}^{j} \| |t_k\rangle_S |t_k\rangle_C - e^{-it_1 H_{SC}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C \|_2 \quad (B.7) $$

$$ \leq \sum_{k=1}^{j} \left( \| |t_k\rangle_S |t_k\rangle_C - e^{-it_1 H_{SC}^{(k)}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C \|_2 \right) \quad (B.8) $$

$$ + \| e^{-it_1 H_{SC}^{(k)}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C - e^{-it_1 H_{SC}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C \|_2 \right). \quad (B.9) $$

The first term after the inequality is the first term after the inequality in eq. (B.2). We focus on upper bounding the 2nd term in eq. (B.6). For this, we start by applying Lemma B.4 again. This time, we make the association $|\Phi_m\rangle = e^{-i\delta_n H_{SC}^{(k)}} |\Phi_{m-1}\rangle = e^{-i\delta_n(m-1)H_{SC}^{(k)}} |\Phi_0\rangle$, $\Delta_m = e^{-i\delta_n H_{SC}}$, with $\delta_n = t_1/n$. Thus applying Lemma B.4, we have for all $n \in \mathbb{N}_{>0}$

$$ \| e^{-it_1 H_{SC}^{(k)}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C - e^{-it_1 H_{SC}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C \|_2 \quad (B.10) $$

$$ \leq \sum_{m=1}^{n} \| e^{-im\delta_n H_{SC}^{(k)}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C - e^{-i\delta_n H_{SC}} e^{-i(m-1)\delta_n H_{SC}^{(k)}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C \|_2 \quad (B.11) $$

$$ = \sum_{m=1}^{n} \left\| \left( e^{-i\delta_n H_{SC}^{(k)}} - e^{-i\delta_n H_{SC}} \right) e^{-i(m-1)\delta_n H_{SC}^{(k)}} |t_{k-1}\rangle_S |t_{j-1}\rangle_C \right\|_2 \quad (B.12) $$

$$ \leq \sum_{m=1}^{n} \max_{x_n \in [0, t_1]} \left\| \left( e^{-i\delta_n H_{SC}^{(k)}} - e^{-i\delta_n H_{SC}} \right) e^{-ix_n H_{SC}^{(k)}} |t_{k-1}\rangle_S |t_{j-1}\rangle_C \right\|_2 \quad (B.13) $$

$$ = n \max_{x_n \in [0, t_1]} \sqrt{S \langle t_{k-1} | C \langle t_{k-1} | e^{ix_n H_{SC}^{(k)}} A^{\dagger}(\delta_n) A(\delta_n) e^{-ix_n H_{SC}^{(k)}} | t_{k-1} \rangle_S | t_{k-1} \rangle_C}, \quad (B.14) $$

where $A(y) := (e^{-iyH_{SC}^{(k)}} - e^{-iyH_{SC}})$. Applying Taylor's remainder theorem to the real function $f: \mathbb{R} \to \mathbb{R}$

$$ f(y) := S \langle t_{k-1} | C \langle t_{k-1} | e^{ix_n H_{SC}^{(k)}} A^{\dagger}(y) A(y) e^{-ix_n H_{SC}^{(k)}} | t_{k-1} \rangle_S | t_{k-1} \rangle_C \quad (B.15) $$

about the point $y = 0$, we find

$$ f(y) = S \langle t_{k-1} | C \langle t_{k-1} | [\dot{A}^{\dagger}(y) \dot{A}(y)]_{y=0} | t_{k-1} \rangle_S | t_{k-1} \rangle_C y^2 + R(y) y^3, \quad (B.16) $$

where dots represent derivatives w.r.t. $y$ and $R: \mathbb{R} \to \mathbb{R}$ is a remainder function satisfying $\lim_{y \to 0} R(y) = 0$. Calculating explicitly the derivatives $\dot{A}^{\dagger}(y)\dot{A}(y)$ and plugging into eq. (B.14) and recalling $\delta_n = t_1/n$ we find

$$ \| e^{-it_1 H_{SC}^{(k)}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C - e^{-it_1 H_{SC}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C \|_2 \quad (B.17) $$

$$ \leq \max_{x_n \in [0, t_1]} \sqrt{S \langle t_{k-1} | C \langle t_{k-1} | e^{ix_n H_{SC}^{(k)}} (\bar{H}_{SC}^{(k)})^2 e^{-ix_n H_{SC}^{(k)}} | t_{k-1} \rangle_S | t_{k-1} \rangle_C t_1^2 + R(t_1/n) t_1^3 / n}, \quad (B.18) $$

for all $n \in \mathbb{N}_{>0}$. Therefore, taking the limit $n \to \infty$ and noting that the remainder term is uniformly bounded in $x_n \in [0, t_1]$, and that the only dependency on $n$ in the non-remainder term in eq. (B.16) is via its dependency on $x_n$, we find that

$$ \| e^{-it_1 H_{SC}^{(k)}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C - e^{-it_1 H_{SC}} |t_{k-1}\rangle_S |t_{k-1}\rangle_C \|_2 \quad (B.19) $$

$$ \leq \lim_{n \to \infty} \max_{x_n \in [0, t_1]} \sqrt{S \langle t_{k-1} | C \langle t_{k-1} | e^{ix_n H_{SC}^{(k)}} (\bar{H}_{SC}^{(k)})^2 e^{-ix_n H_{SC}^{(k)}} | t_{k-1} \rangle_S | t_{k-1} \rangle_C t_1^2 + R(t_1/n) t_1^3 / n}, \quad (B.20) $$

$$ \leq \sqrt{\left( \lim_{n \to \infty} \max_{x_n \in [0, t_1]} S \langle t_{k-1} | C \langle t_{k-1} | e^{ix_n H_{SC}^{(k)}} (\bar{H}_{SC}^{(k)})^2 e^{-ix_n H_{SC}^{(k)}} | t_{k-1} \rangle_S | t_{k-1} \rangle_C t_1^2 \right) + \left( \lim_{n \to \infty} \max_{x_n \in [0, t_1]} R(t_1/n) \frac{t_1^3}{n} \right)}, \quad (B.21) $$

$$ = \max_{x_n \in [0, t_1]} t_1 \sqrt{S \langle t_{k-1} | C \langle t_{k-1} | e^{ix_n H_{SC}^{(k)}} (\bar{H}_{SC}^{(k)})^2 e^{-ix_n H_{SC}^{(k)}} | t_{k-1} \rangle_S | t_{k-1} \rangle_C}. \quad (B.23) $$

Thus identifying the last line with the corresponding 2-norm, we conclude the proof. ■
## 2. Some additional definitions required for the lemmas of appendix B 3

Here we specialise the form of the terms in Hamiltonian eq. (B.1) and the states of the control on C. There will still be some free parameters which will only be set at later stages as it becomes required in order to prove the desired results.

The free control term, $H_C$, is chosen identically to that of [26], namely:

$$H_C = \sum_{n=0}^{d-1} n\omega_0 |E_n\rangle\langle E_n|, \qquad (B.24)$$

where $\{|E_n\rangle\}_{n=0}^{d-1}$ forms an orthonormal basis for the Hilbert space of the control, $\mathcal{H}_C$. The frequency $\omega_0$ determines both the energy recurrence of the control when no interaction terms are present, $T_0 = 2\pi/\omega_0 > 0$, as $e^{-i\hat{H}_C T_0} = 1_C$.

The states $\{|\theta_k\rangle\}$ are the discrete Fourier Transform basis of the energy basis: For $k \in \mathbb{Z}$

$$|\theta_k\rangle = \frac{1}{\sqrt{d}} \sum_{n=0}^{d-1} e^{-i2\pi nk/d} |E_n\rangle. \qquad (B.25)$$

Note that any subset of $d$ consecutive terms forms an orthonormal basis for $\mathcal{H}_C$. We will make use of this redundancy below when defining the stats on C.

Let us now define the interaction terms: For $l = 1, 2, 3, \dots, N_g$

$$I_C^{(l)} := \frac{d}{T_0} \sum_{k \in S_d(k_0)} I_{C,d}^{(l)}(k) |\theta_k\rangle\langle\theta_k|, \qquad I_{C,d}^{(l)}(x) := \frac{2\pi}{d} \bar{V}_0 \left( \frac{2\pi}{d} x \right) \Big|_{x_0=x_0^{(l)}}, \qquad (B.26)$$

with $S_d(k_0) := \{k | k \in \mathbb{Z} \text{ and } -d/2 \le k_0 - k < d/2\}$ and where $x_0^{(l)} := 2\pi(l - 1/2)/N_g$. The function $\bar{V}_0: \mathbb{R} \to \mathbb{R}$ is defined in [27]. It has $x_0 \in \mathbb{R}$ as a parameter in its definition, which is<fnref n="9" />

$$\bar{V}_0(x) = nA_0 \sum_{p=-\infty}^{+\infty} V_B(n(x - x_0 + 2\pi p)), \qquad (B.27)$$

where $n > 0$, $x_0 \in \mathbb{R}$ and $A_0$ is a normalization constant such that

$$\int_0^{2\pi} \bar{V}_0(x) dx = 1, \qquad (B.28)$$

and takes on the value (see F168 in [27])

$$A_0 = \frac{1}{\int_{-\infty}^{\infty} dx V_B(x)}, \qquad (B.29)$$

where

$$V_B(\cdot) = \mathrm{sinc}^{2N}(\cdot) = (\sin(\pi \cdot)/(\pi \cdot))^{2N}, \quad N \in \mathbb{N}_{>0}. \qquad (B.30)$$

Notice that $\bar{V}_0(\cdot)$ is $2\pi$ periodic and as such, the summation in $I_C^{(l)}$ is independent of $k_0 \in \mathbb{R}$. We will later take advantage of this $k_0$ independency and also show how to parametrise $n$ in terms or $d$ to achieve our desired result. As we will see, $N$ on the other hand will be chosen such that it is $d$ independent.

One can use the Weierstrass M test (see Theorem 7.10 in [35]), to show that the sum in eq. (B.27) converges uniformly. We thus have

$$\int_a^b dx \bar{V}_0(x) = nA_0 \sum_{p=-\infty}^{+\infty} \int_a^b dx V_B(n(x - x_0 + 2\pi p)), \quad \forall a, b, x_0 \in \mathbb{R}, n > 0. \qquad (B.31)$$

<footnote n="9">⁹Technically, $\bar{V}_0$ comes with the additional additive factor of $1/\delta d$ is its definition in [27], but in the current application it is not required and has thus been neglected for simplicity by setting $\delta = 1$ and mapping the $1/d$ additive factor to zero. (Importantly, it is readily seen by following the proofs in [27], that the lemmas from [27] which we will require hold equally well when it is omitted in the definition up to minor modifications which we will highlight as the become come up in the manuscript. We leave it as an exercise to re-do the derivations in [27]) under this minor modification. When we use a modified result in this manuscript, we will notify the reader of the modification.</footnote>
We will use this property extensively in proofs in this manuscript.

Let

$$|t_j\rangle_S := e^{iI_S^{(j)}} |t_{j-1}\rangle_S, \quad j = 1, 2, \dots, N_g, \qquad (B.32)$$

where we assume w.l.o.g. that the spectrum of $I_S^{(j)}$ lies in the interval $(0, 2\pi]$. Its eigenvalues are arbitrary so that states $|t_j\rangle_S$ and $|t_{j-1}\rangle_S$ can be related by any unitary transformation (we will later specify the spectrum in relation to the gate set $\mathcal{G}$). As mentioned in the main text, $|0\rangle_S$ is any pure state in $\mathcal{H}_S$.

Since the memory is fixed in this section, the definition of $\tilde{d}(\mathfrak{m}_l)$ corresponds to the number of non-identical eigenvalues of $I_S^{(l)}$ and

$$t_j := jT_0/N_g, \qquad (B.33)$$

for $j = 1, 2, 3, \dots, N_g$.

As for the states of the control, we use so-called quasi-ideal clock states coming from [26]. In particular, we define $|t_j\rangle_C := |\Psi(t_j d/T_0)\rangle_C$ for $j = 0, 1, 2, \dots, N_g$, where for $t \in \mathbb{R}$, $T_0 > 0$, $d \in \mathbb{N}_{>0}$,

$$|\Psi(td/T_0)\rangle_C := \sum_{k \in S_d(td/T_0)} \psi_{\text{nor}}(td/T_0, k) |\theta_k\rangle, \qquad (B.34)$$

where

$$\psi_{\text{nor}}(k_0; k) := A_{\text{nor}} e^{-\frac{\pi}{\sigma^2}(k-k_0)^2} e^{i2\pi n_0(k-k_0)/d}. \qquad (B.35)$$

with $\sigma > 0$, $n_0 \in (0, d-1)$. The amplitude $A_{\text{nor}}$ is defined such that $|\Psi(td/T_0)\rangle_C$ is normalised. Its large-$d$ scaling is

$$|A_{\text{nor}}|^2 = \left(\frac{2}{\sigma^2}\right) + \epsilon(d), \qquad (B.36)$$

where $\epsilon(d) \to 0$ as $d \to \infty$ (under reasonable assumptions about how $\sigma$ depends on $d$ which are satisfied in this manuscript; see appendix E in [26] for details).

### 3. Final technical lemmas

**Lemma B.2.** For all $k \in 1, 2, 3, \dots, N_g$, the last terms in lemma B.1 are upper bounded by

$$t_1 \max_{x \in [0, t_1]} \left\| \bar{H}_{\text{SC}}^{(k)} e^{-ixH_{\text{SC}}^{(k)}} |t_{k-1}\rangle_S |\Psi(t_{k-1}d/T_0)\rangle_C \right\|_2 \le \qquad (B.37)$$

$$\frac{\tilde{d}(\mathfrak{m}_k)4\pi^2 n A_0}{T_0} \left( 3A_{\text{nor}}d N_g \left( e^{-\frac{\pi}{\sigma^2}\left(\frac{d^2}{4N_g}\right)^2} + \left(\frac{2N_g}{\pi^2 n}\right)^{2N} \right) \right) \qquad (B.38)$$

$$+ A_{\text{nor}} \left( \pi^2 - \frac{79}{9} \right) N_g d \left( \frac{1}{2\pi n} \right)^{2N} + N_g d \left( 1 + \frac{\pi^2}{3} \right) \epsilon_v(t_1, d), \qquad (B.39)$$

where $n > 0$, $N \in \mathbb{N}_{>0}$ and

$$\epsilon_v(t, d) = |t| \frac{d}{T_0} \left[ \mathcal{O} \left( \frac{\sigma^3}{\sigma d^{-\epsilon_5+1}} \right)^{1/2} + \mathcal{O} \left( \frac{d^2}{\sigma^2} + 2C_0 n \right) \right] \exp \left( -\frac{\pi}{4} \frac{\alpha_0^2}{(1+d^{\epsilon_5}/\sigma)^2} d^{2\epsilon_5} \right) \\ + \mathcal{O} \left( |t| \frac{d^2}{\sigma^2} + 1 \right) e^{-\frac{\pi}{4} \frac{d^2}{\sigma^2}} + \mathcal{O} \left( e^{-\frac{\pi}{2} \sigma^2} \right) \quad \text{as } d \to \infty, \quad (0, d) \ni \sigma \to \infty \qquad (B.40)$$

where $C_0 > 0$, $\alpha_0 > 0$, $\epsilon_5 > 0$ are fixed constants and

$$A_{\text{nor}} \le \left(\frac{2}{\sigma^2}\right)^{1/4} + \sqrt{\frac{\bar{\epsilon}_1 + \bar{\epsilon}_2}{\frac{\sigma}{\sqrt{2}}\left(\frac{\sigma}{\sqrt{2}} - \bar{\epsilon}_1 - \bar{\epsilon}_2\right)}}, \qquad (B.41)$$

with

$$\bar{\epsilon}_2 := \frac{\sigma}{\sqrt{2}} \frac{2e^{-\frac{\pi \sigma^2}{2}}}{1 - e^{-\pi \sigma^2}}, \quad \bar{\epsilon}_1 := \frac{2e^{-\frac{\pi d^2}{2\sigma^2}}}{1 - e^{-2\pi d \sigma^2}}. \qquad (B.42)$$
Proof. For all $x \in [0, t_1]$

$$ \| \tilde{H}_{\text{SC}}^{(k)} e^{-ixH_{\text{SC}}^{(k)}} |t_{k-1}\rangle_S |\Psi(t_{k-1}d/T_0)\rangle_C \|_2 \quad (B.43) $$

$$ \le \sum_{\substack{l=1 \\ l \ne k}}^{N_g} \| I_S^{(l)} \otimes I_C^{(l)} e^{-ixH_{\text{SC}}^{(k)}} |t_{k-1}\rangle_S |\Psi(t_{k-1}d/T_0)\rangle_C \|_2 \quad (B.44) $$

$$ \le \sum_{j=1}^{\tilde{d}(\mathfrak{m}_k)} \sum_{\substack{l=1 \\ l \ne k}}^{N_g} |A_j^{(k-1)}| \| I_S^{(l)} \otimes I_C^{(l)} |\theta_j^{(k-1)}\rangle_S e^{-ixH_C^{(k)}(\theta_j^{(k)})} |\Psi(t_{k-1}d/T_0)\rangle_C \|_2 \quad (B.45) $$

$$ = \sum_{j=1}^{\tilde{d}(\mathfrak{m}_k)} \sum_{\substack{l=1 \\ l \ne k}}^{N_g} |A_j^{(k-1)}| \| I_S^{(l)} |\theta_j^{(k-1)}\rangle_S \|_2 \| I_C^{(l)} e^{-ixH_C^{(k)}(\theta_j^{(k)})} |\Psi(t_{k-1}d/T_0)\rangle_C \|_2 \quad (B.46) $$

$$ \le \sum_{\substack{l=1 \\ l \ne k}}^{N_g} \sum_{j=1}^{\tilde{d}(\mathfrak{m}_k)} |A_j^{(k-1)}| \| I_S^{(l)} \|_2 \max_{\vartheta \in [-\pi, \pi]} \| I_C^{(l)} e^{-ixH_C^{(k)}(\vartheta)} |\Psi(t_{k-1}d/T_0)\rangle_C \|_2 \quad (B.47) $$

$$ \le 2\pi \tilde{d}(\mathfrak{m}_k) \sum_{\substack{l=1 \\ l \ne k}}^{N_g} \max_{\vartheta \in [-\pi, \pi]} \| I_C^{(l)} e^{-ixH_C^{(k)}(\vartheta)} |\Psi(t_{k-1}d/T_0)\rangle_C \|_2 \quad (B.48) $$

where in line eq. (B.44) we have used eq. (B.5) together with the triangle inequality. For line eq. (B.45), we have used the decomposition

$$ |t_{k-1}\rangle_S = \sum_{j=1}^{\tilde{d}(\mathfrak{m}_k)} A_j^{(k-1)} |\theta_j^{(k)}\rangle_S, \quad (B.49) $$

where $|\theta_j^{(k)}\rangle_S$ belongs to the subspace spanned by the vectors of eigenvalue $\theta_j^{(k)}$ for the operator $I_S^{(k)}$. Thus $\tilde{d}(\mathfrak{m}_k) \le d_S^{(k)}$, where recall that $\tilde{d}(\mathfrak{m}_k)$ is the number of non-identical eigenvalues of $I_S^{(k)}$. We have also defined

$$ H_C^{(k)}(\gamma) := H_C + \gamma I_C^{(k)}, \quad (B.50) $$

$\gamma \in \mathbb{R}$ (c.f. def. of $H_{\text{SC}}^{(k)}$ in eq. (B.5)). For line eq. (B.46), we have used the fact that the 2-norm of a tensor product is the product of the 2-norms. In line eq. (B.47), we have used $\|I_S^{(l)}\|_2$ to denote the 2-norm-induced operator norm. In line eq. (B.48), we have used the assumption $\|I_S^{(l)}\|_2 \le 2\pi$ for all $l = 1, 2, \dots, N_g$.

To continue, we will need the particular form of the interaction terms introduced in eq. (B.26) and we will need to recall Theorem IX.1 (Moving the clock through finite time with a potential) from [26], which states

$$ e^{-it(H_C + \hat{V}_d)} |\bar{\Psi}_{\text{nor}}(k_0, \Delta)\rangle_C = |\bar{\Psi}_{\text{nor}}(k_0 + t d/T_0, \Delta + t d/T_0)\rangle_C + |\epsilon\rangle_C, \quad \| |\epsilon\rangle_C \|_2 \le \epsilon_v(t, d), \quad (B.51) $$

where

$$ |\bar{\Psi}_{\text{nor}}(k_0, \Delta)\rangle_C := \sum_{k \in S_d(k_0)} e^{-i \int_{k-\Delta}^{k} dy V_d(y)} \psi_{\text{nor}}(k_0; k) |\theta_k\rangle_C, \quad (B.52) $$

$$ \hat{V}_d := \frac{d}{T_0} \sum_{k=0}^{d-1} V_d(k) |\theta_k\rangle\langle\theta_k|_C, \quad V_d(x) = \frac{2\pi}{d} \bar{V}_0 \left(\frac{2\pi}{d} x\right). \quad (B.53) $$

We can apply this theorem to approximate $e^{-ixH_C^{(k)}(\vartheta)} |\Psi(t_{k-1}d/T_0)\rangle_C$ appearing in line eq. (B.48) by identifying $x$ with $t$, and $\hat{V}_d$ with $\vartheta I_C^{(k)}$. To do so, first note that by definition it follows that $|\Psi_{\text{nor}}(t_{k-1}d/T_0)\rangle_C = |\bar{\Psi}_{\text{nor}}(t_{k-1}d/T_0, 0)\rangle_C$ (recall definition eq. (B.34)).
Continuing from line eq. (B.48), but now maximizing over $x$ we thus find

$$ \max_{x \in [0, t_1]} 2\pi \tilde{d}(\mathfrak{m}_k) \sum_{\substack{l=1 \\ l \neq k}}^{N_g} \max_{\vartheta \in [0, 2\pi]} \left\| I_C^{(l)} e^{-ixH_C^{(k)}(\vartheta)} |\Psi(t_{k-1}d/T_0)\rangle_C \right\|_2 \quad (B.54) $$

$$ \leq \max_{x \in [0, t_1]} 2\pi \tilde{d}(\mathfrak{m}_k) \sum_{\substack{l=1 \\ l \neq k}}^{N_g} \max_{\vartheta \in [0, 2\pi]} \left\| \frac{d}{T_0} \sum_{q \in S_d([t_{k-1}+x]d/T_0)} I_{C,d}^{(l)}(q) |\theta_q\rangle\langle\theta_q| (|\tilde{\Psi}_{\text{nor}}([t_{k-1}+x]d/T_0, xd/T_0)\rangle_C + |\varepsilon_C(x, d)\rangle) \right\|_1 \quad (B.55) $$

$$ \leq \max_{x \in [0, t_1]} \frac{2\pi \tilde{d}(\mathfrak{m}_k)}{T_0} \sum_{\substack{l=1 \\ l \neq k}}^{N_g} \max_{\vartheta \in [0, 2\pi]} \sum_{q \in S_d([t_{k-1}+x]d/T_0)} \left( \left| I_{C,d}^{(l)}(q) \psi_{\text{nor}}([t_{k-1}+x]d/T_0, q) e^{-i\vartheta \int_{q-xd/T_0}^{q} I_{C,d}^{(k)}(y)dy} \right| \right. \quad (B.56) \\ \left. + \left| I_{C,d}^{(l)}(q) \langle \theta_q | \varepsilon_C(x, d) \rangle \right| \right) \quad (B.57) $$

$$ \leq \frac{\tilde{d}(\mathfrak{m}_k) 4\pi^2}{T_0} \left( \max_{x \in [0, t_1]} \left[ \sum_{\substack{l=1 \\ l \neq k}}^{N_g} \sum_{q \in S_d([t_{k-1}+x]d/T_0)} \left| nA_0 \sum_{p=-\infty}^{+\infty} V_B \left( n(2\pi q/d - x_0^{(l)} - 2\pi p) \right) A_{\text{nor}} e^{-\frac{\pi}{\sigma^2} (q - [t_{k-1}+x]d/T_0)^2} \right| \right] \right) \quad (B.58) $$

$$ + \frac{d}{2\pi} \sum_{\substack{l=1 \\ l \neq k}}^{N_g} \sum_{q \in S_d([t_{k-1}+x]d/T_0)} \frac{2\pi}{d} \left( \max_{y \in [0, 2\pi]} \bar{V}_0(y) \right) \varepsilon_v(t_1, d) \quad (B.59) $$

$$ \leq \frac{\tilde{d}(\mathfrak{m}_k) 4\pi^2}{T_0} \left( \left[ \max_{x' \in [0, 1]} \sum_{\substack{l=1 \\ l \neq k}}^{N_g} d \max_{q \in [-d/2+(k-1+x')d/N_g, d/2+(k-1+x')d/N_g]} \right] \right) \quad (B.60) $$

$$ \left| nA_0 \sum_{p=-\infty}^{+\infty} V_B \left( n(2\pi q/d - x_0^{(l)} - 2\pi p) \right) A_{\text{nor}} e^{-\frac{\pi}{\sigma^2} (q - [t_{k-1}+x't_1]d/T_0)^2} \right| \quad (B.61) $$

$$ + N_g d n A_0 \left( 1 + \sum_{p \in \mathbb{Z} \setminus \{0\}} \frac{1}{p^{2N}} \right) \varepsilon_v(t_1, d) \quad (B.62) $$

$$ \leq \frac{\tilde{d}(\mathfrak{m}_k) 4\pi^2 n A_0}{T_0} \left( \left[ A_{\text{nor}} \max_{x' \in [0, 1]} \sum_{\substack{l=1 \\ l \neq k}}^{N_g} d \max_{q' \in [-d/2, d/2]} \sum_{p=-\infty}^{+\infty} V_B \left( 2\pi n \left( \frac{q'}{d} + \frac{k-l+x'-1/2}{N_g} - p \right) \right) e^{-\frac{\pi}{\sigma^2} q'^2} \right] \right) \quad (B.63) $$

$$ + N_g d \left( 1 + \frac{\pi^2}{3} \right) \varepsilon_v(t_1, d) \quad (B.64) $$

$$ \leq \frac{\tilde{d}(\mathfrak{m}_k) 4\pi^2 n d A_0}{T_0} \left( \left[ A_{\text{nor}} \max_{x' \in [0, 1]} \sum_{\substack{l=1 \\ l \neq k}}^{N_g} q' \max_{q' \in [-d/2, d/2]} \sum_{p \in \{0, \pm 1\}} V_B \left( 2\pi n \left( \frac{q'}{d} + \frac{k-l+x'-1/2}{N_g} - p \right) \right) e^{-\frac{\pi}{\sigma^2} q'^2} \right] \right) \quad (B.65) $$

$$ + \left[ A_{\text{nor}} \sum_{\substack{l=1 \\ l \neq k}}^{N_g} \max_{q' \in [-d/2, d/2]} \sum_{p \in \mathbb{Z} \setminus \{0, \pm 1\}} \left| 2\pi n \left( \frac{1}{2} - p \right) \right|^{-2N} \right] + N_g \left( 1 + \frac{\pi^2}{3} \right) \varepsilon_v(t_1, d), \quad (B.66) $$

$$ \leq \frac{\tilde{d}(\mathfrak{m}_k) 4\pi^2 n d A_0}{T_0} \left( \left[ A_{\text{nor}} \max_{x' \in [0, 1]} \sum_{\substack{l=1 \\ l \neq k}}^{N_g} q' \max_{q' \in [-d/2, d/2]} \sum_{p \in \{0, \pm 1\}} V_B \left( 2\pi n \left( \frac{q'}{d} + \frac{k-l+x'-1/2}{N_g} - p \right) \right) e^{-\frac{\pi}{\sigma^2} q'^2} \right] \right) \quad (B.67) $$
$$ + \left[ A_{\text{nor}} N_g \left( \frac{1}{2\pi n} \right)^{2N} \sum_{p \in \mathbb{Z} \setminus \{0, \pm 1\}} |1/2 - p|^{-2N} \right] + N_g \left( 1 + \frac{\pi^2}{3} \right) \varepsilon_v(t_1, d) \right], \quad (B.68) $$

$$ \le \frac{\tilde{d}(\mathfrak{m}_k) 4\pi^2 n d A_0}{T_0} \left( \left[ A_{\text{nor}} \max_{x' \in [0,1]} \sum_{\substack{l=1 \\ l \ne k}}^{N_g} q' \in [-d/2, d/2] \max_{p \in \{0, \pm 1\}} \sum_{p \in \{0, \pm 1\}} V_B \left( 2\pi n \left( \frac{q'}{d} + \frac{[k-l+x'-1/2]}{N_g} - p \right) \right) e^{-\frac{\pi}{\sigma^2} q'^2} \right] \right) \quad (B.69) $$

$$ + A_{\text{nor}} \left( \pi^2 - \frac{79}{9} \right) N_g \left( \frac{1}{2\pi n} \right)^{2N} + N_g \left( 1 + \frac{\pi^2}{3} \right) \varepsilon_v(t_1, d), \quad (B.70) $$

where in line eq. (B.55), we have inserted the definition of $I_C^{(l)}$ and chosen $k_0 = [t_{k-1} + x]d/T_0$ in $S_d(k_0)$, followed by applying eq. (B.51) and using the fact that the 1-norm upper bounds the 2-norm. In line eq. (B.56), we have used definition eq. (B.52) and the triangle inequality. In line eq. (B.58) we have first removed the maximization over $\vartheta$ since it is $\vartheta$-independent and then substituted in eq. (B.27). In line eq. (B.59) we have used the definition of $\varepsilon_v(\cdot, \cdot)$. In line eq. (B.60) we have defined $x' = x/t_1 \in [0, 1]$ and used the fact that $q \in S_d([t_{k-1} + x]d/T_0)$ is equivalent to $q \in \{[-d/2 + [k-1+x']d/N_g], [-d/2 + [k-1+x']d/N_g] + 1, [-d/2 + [k-1+x']d/N_g] + 2, \dots, [-d/2 + [k-1+x']d/N_g] + d-1\}$. Since $[-d/2 + [k-1+x']d/N_g] + d-1 = [-d/2 + d-1 + [k-1+x']d/N_g] \le d/2 + [k-1+x']d/N_g$, we have that $q$ takes on $d$ values in the interval $q \in [-d/2 + [k-1+x']d/N_g, d/2 + [k-1+x']d/N_g]$. In line eq. (B.63) we have first made the change of variables $q' = q - [t_{k-1} + x't_1]d/T_0$ so that $q' \in [-d/2, d/2]$, followed by substituting for $t_{k-1}$ and $x_0^{(l)}$. In line eq. (B.62) we used definition eq. (B.27) to upper bound the maximization over $y$. For line eq. (B.64) we have used $\sum_{p \in \mathbb{Z} \setminus \{0\}} \frac{1}{p^{2N}} \le \sum_{p \in \mathbb{Z} \setminus \{0\}} \frac{1}{p^2} = \pi^2/3$ for all $N \in \mathbb{N}_{>0}$.

For line eq. (B.66) have used the bound $\sum_{p \in \mathbb{Z} \setminus \{0, 1\}} V_B(2\pi n(x-p)) \le (2\pi n)^{-2N} \sum_{p \in \mathbb{Z} \setminus \{0\}} (1/2-p)^{-2N}$ for all $x \in [-1/2, 3/2]$, $n > 0$, (which follows from the function's definition, eq. (B.27)), and the observation that $q'/d + [k-l+x'-1/2]/N_g \in [-1/2, 3/2]$ for all $x' \in [0, 1]$, $q' \in [-d/2, d/2]$ and $l, k \in 1, 2, \dots, N_g$ s.t. $l \ne k$.

We will now focus on the $p=0, 1$ terms in the summation. To bound these terms, we will separate the range of $q' \in [-d/2, d/2]$ into three intervals, two “tail” intervals and one “centre” interval and proceed to bound the central and tail intervals separately. In particular, observe that $q'/d$ is contained in the intervals $q'/d \in [-1/2, 1/2] = [-1/2, -1/(4N_g)] \cup [-1/(4N_g), 1/(4N_g)] \cup [1/(4N_g), 1/2]$. For the $p=0$ term in brackets in line eq. (B.63) we find

$$ \max_{x' \in [0,1]} A_{\text{nor}} \sum_{\substack{l=1 \\ l \ne k}}^{N_g} \sum_{q' \in [-d/2, d/2]} \sum_{p \in \{0, \pm 1\}} V_B \left( 2\pi n \left( \frac{q'}{d} + \frac{[k-l+x'-1/2]}{N_g} - p \right) \right) e^{-\frac{\pi}{\sigma^2} q'^2} \quad (B.71) $$

$$ \le \max_{x' \in [0,1]} A_{\text{nor}} \sum_{\substack{l=1 \\ l \ne k}}^{N_g} \sum_{p \in \{0, \pm 1\}} \left( \max_{q'' \in [-1/2, -1/(4N_g)] \cup [1/(4N_g), 1/2]} V_B \left( 2\pi n \left( \frac{q''}{d} + \frac{[k-l+x'-1/2]}{N_g} - p \right) \right) e^{-\pi \frac{d^2}{\sigma^2} q''^2} \right) \quad (B.72) $$

$$ + \max_{q''' \in [-1/(4N_g), 1/(4N_g)]} \left( \frac{1}{2\pi^2 n |q''' + (k-l+x'-1/2)/N_g - p|} \right)^{2N} e^{-\pi \frac{d^2}{\sigma^2} q'''^2} \quad (B.73) $$

$$ \le \max_{x' \in [0,1]} A_{\text{nor}} \sum_{\substack{l=1 \\ l \ne k}}^{N_g} \left( 3 \left( \max_{y \in \mathbb{R}} V_B(y) \right) e^{-\pi \frac{d^2}{\sigma^2 (4N_g)^2}} + \max_{q''' \in [-1,1]} \sum_{p \in \{0, \pm 1\}} \left( \frac{N_g}{2\pi^2 n |q'''/4 + (k-l+x'-1/2) - pN_g|} \right)^{2N} \right) \quad (B.74) $$

$$ \le 3A_{\text{nor}}N_g \left( e^{-\pi \frac{d^2}{\sigma^2 (4N_g)^2}} + \left( \frac{2N_g}{\pi^2 n} \right)^{2N} \right), \quad (B.75) $$

Where in line eq. (B.73) we have used the bound $V_B(x) \le (1/|\pi x|)^{2N}$ for the first term (which follows from the function's definition, eq. (B.27)). In line eq. (B.75) we have used the bound $V_B(x) \le 1 \forall x \in \text{for the first term.}$ For the second term, we have noted that for $p \in \{0, \pm 1\}$, $k, l \in 1, 2, \dots, N_g$ s.t. $l \ne k$ we have $k-l-pN_g \in (-\infty, -1] \cup [1, +\infty)$. Therefore, $|q'''/4 + (k-l+x'-1/2) - pN_g| \ge 1/4$. Observe that it is critical for this argument that the summation is restricted to $l \ne k$, since for $l=k$ the denominator takes on the value zero and the second term is infinite.

Finally, the upper bound for eq. (B.41) is derived in [26] [Appendix E.1.1., pg 208].

<figure><img src="image_8.png" /></figure>
**Lemma B.3.** For all $k \in 1, 2, 3, \dots, N_g$, the first term in lemma B.1 is upper bounded by

$$ \| |t_k\rangle_S |\Psi(t_k d/T_0)\rangle_C - e^{-it_1 H_{SC}^{(k)}} |t_{k-1}\rangle_S |\Psi(t_{k-1} d/T_0)\rangle_C \|_2 \quad (B.76) $$

$$ \le \sqrt{2\epsilon_v(t_{k-1}, d)} + \pi \sqrt{2dA_{\text{nor}}} \left( e^{-\frac{\pi}{16} \left(\frac{d}{\sigma N_g}\right)^2} + 4\pi n A_0 \left( \left(\frac{2N_g}{\pi^2 n}\right)^{2N} + \frac{\pi^2}{3} \left(\frac{1}{2\pi^2 n}\right)^{2N} \right) \right), \quad (B.77) $$

where $\epsilon_v$ and $A_{\text{nor}}$ are defined in lemma B.2 and $n > 0$, $N \in \mathbb{N}_{>0}$.

*Proof.*

$$ \| |t_k\rangle_S |\Psi(t_k d/T_0)\rangle_C - e^{-it_1 H_{SC}^{(k)}} |t_{k-1}\rangle_S |\Psi(t_{k-1} d/T_0)\rangle_C \|_2 \quad (B.78) $$

$$ = \sqrt{2 \left( 1 - \Re \left[ \left( \langle t_k |_S \langle \Psi(t_k d/T_0) |_C \rangle (e^{-it_1 H_{SC}^{(k)} |t_{k-1}\rangle_S |\Psi(t_{k-1} d/T_0)\rangle_C) \right) \right] \right)} \quad (B.79) $$

$$ = \sqrt{2 \left( 1 - \Re \left[ \sum_{j_1, j_2=1}^{\tilde{d}(\mathfrak{m}_k)} A_{j_1}^{(k-1)*} A_{j_2}^{(k-1)} e^{i\theta_{j_1}^{(k)}} \langle \theta_{j_1}^{(k)} |_S \langle \Psi(t_k d/T_0) |_C \rangle (e^{-it_1 H_{SC}^{(k)} |\theta_{j_2}^{(k)}\rangle_S |\Psi(t_{k-1} d/T_0)\rangle_C) \right] \right)} \quad (B.80) $$

$$ = \sqrt{2 \left( 1 - \sum_{j=1}^{\tilde{d}(\mathfrak{m}_k)} |A_j^{(k-1)}|^2 \Re \left[ e^{i\theta_j^{(k)}} \langle \Psi(t_k d/T_0) |_C e^{-it_1 H_C^{(k)}(\theta_j^{(k)})} |\Psi(t_{k-1} d/T_0)\rangle_C \right] \right)} \quad (B.81) $$

$$ = \sqrt{2 \left( 1 - \sum_{j=1}^{\tilde{d}(\mathfrak{m}_k)} |A_j^{(k-1)}|^2 \Re \left[ \sum_{l \in S(t_k d/T_0)} |\psi_{\text{nor}}(t_k d/T_0; l)|^2 e^{i\theta_j^{(k)}} (1 - \int_{l-t_1 d/T_0}^{l} I_{C,d}^{(k)}(y) dy) + e^{i\theta_j^{(k)}} \langle \Psi(t_k d/T_0) | \epsilon_C(t_{k-1}, d) \rangle_C \right] \right)} \quad (B.82) $$

$$ = \sqrt{2} \sqrt{1 - \sum_{j=1}^{\tilde{d}(\mathfrak{m}_k)} |A_j^{(k-1)}|^2 \left( \Re \left[ \sum_{l \in S(t_k d/T_0)} |\psi_{\text{nor}}(t_k d/T_0; l)|^2 e^{i\theta_j^{(k)}} (1 - \int_{l-t_1 d/T_0}^{l} I_{C,d}^{(k)}(y) dy) \right] - \epsilon_v(t_{k-1}, d) \right)} \quad (B.83) $$

$$ = \sqrt{2} \sqrt{1 + \max_{\vartheta \in [0,2\pi]} \left( -\Re \left[ \sum_{l \in S(t_k d/T_0)} |\psi_{\text{nor}}(t_k d/T_0; l)|^2 e^{i\vartheta} (1 - \int_{l-t_1 d/T_0}^{l} I_{C,d}^{(k)}(y) dy) \right] \right) + \epsilon_v(t_{k-1}, d)} \quad (B.84) $$

$$ \le \sqrt{2} \sqrt{\epsilon_v(t_{k-1}, d) + \sum_{l \in S(t_k d/T_0)} |\psi_{\text{nor}}(t_k d/T_0; l)|^2 4\pi^2 \left(1 - \int_{l-t_1 d/T_0}^{l} I_{C,d}^{(k)}(y) dy\right)^2} \quad (B.85) $$

$$ \le \sqrt{2} \sqrt{\epsilon_v(t_{k-1}, d) + 2d\pi^2 \max_{q \in [-1/2, 1/2]} |\psi_{\text{nor}}(t_k d/T_0; t_k d/T_0 - dq)|^2 \left(1 - \int_{t_{-1/2}d/T_0 - qd}^{t_{1/2}d/T_0 - qd} I_{C,d}^{(k)}(y' + x_0^{(k)} d/(2\pi)) dy'\right)^2} \quad (B.86) $$

$$ \le \sqrt{2} \sqrt{\epsilon_v(t_{k-1}, d) + 2d\pi^2 \max_{q \in [-1/2, -1/(4N_g)] \cup [1/(4N_g), 1/2]} A_{\text{nor}} e^{-\frac{\pi d^2 q^2}{\sigma^2}} \left( 1 - \frac{2\pi}{d} \int_{-d/(2N_g)-qd}^{d/(2N_g)-qd} \bar{V}_0 \left( 2\pi y'/d + x_0^{(k)} \right) \Big|_{x_0=x_0^{(k)}} dy' \right)^2} \quad (B.87) $$

$$ + 2d\pi^2 \max_{q \in [-1/(4N_g), 1/(4N_g)]} A_{\text{nor}} e^{-\frac{\pi d^2 q^2}{\sigma^2}} \left( 1 - \frac{2\pi}{d} \int_{-d/(2N_g)-qd}^{d/(2N_g)-qd} \bar{V}_0 \left( 2\pi y'/d + x_0^{(k)} \right) \Big|_{x_0=x_0^{(k)}} dy' \right)^2 \\ \le \sqrt{2} \sqrt{\epsilon_v(t_{k-1}, d) + 2d\pi^2 A_{\text{nor}} e^{-\frac{\pi}{8} \left(\frac{d}{\sigma N_g}\right)^2} + 2d\pi^2 \max_{q \in [-1, 1]} A_{\text{nor}} \left( 1 - \frac{2\pi}{N_g} \int_{-1/2-q/4}^{1/2-q/4} \bar{V}_0 \left( 2\pi y''/N_g + x_0^{(k)} \right) \Big|_{x_0=x_0^{(k)}} dy'' \right)^2} \quad (B.88) $$
In line eq. (B.79) we have used $\Re[\cdot]$ to denote the real part. In line eq. (B.80), we have used eq. (B.32) followed by eq. (B.49). In line eq. (B.81) we have used definition eq. (B.50). In line eq. (B.82), we have used the theorem displayed in eq. (B.51), taking into account the definition $|\Psi(\cdot)\rangle_C = |\bar{\Psi}_{\text{nor}}(\cdot, 0)\rangle_C$. In line eq. (B.83) we have used the fact that for all $c \in \mathbb{C}$, $|\Re[c]| \le |c|$ and that $\|\varepsilon_C(t_{k-1}, d)\|_C \|2 \le \varepsilon_v(t_{k-1}, d)$. In line eq. (B.84) we have used that $\sum_{j=1}^{\tilde{d}(m_k)} |A_j^{(k-1)}|^2 = 1$ due to state normalization. In line eq. (B.85) we have taken the real part of the term in square brackets and used $-\cos(\theta) \le \theta^2 - 1$ for all $\theta \in \mathbb{R}$. In line eq. (B.86) we have made the change of variable $y' = y - dx_0^{(k)}/(2\pi)$ which shifts $I_{C,d}^{(k)}(y)$ to be centred at zero. We have also defined $\tilde{q} := t_k/T_0 - l/d$ and noted that $l \in S(t_k d/T_0)$ implies $-1/2 \le \tilde{q} < 1/2$ and finally upper bounded the summation for a maximization over the set $[-1/2, 1/2]$. In line eq. (B.87) we have substituted in the definition of the functions, followed by upper bounding the maximization over $q \in [-1/2, 1/2]$ as the sum of maximizations over the sub-intervals $[-1/2, -1/(4N_g)] \cup [1/(4N_g), 1/2]$ and $[-1/(4N_g), 1/(4N_g)]$. In line eq. (B.88), for the first term, we have used that $\tilde{V}_0$ is a non-negative, $2\pi$-periodic function integrated over an interval less than $2\pi$. For the second term we performed a change of variable.

We will now derive an alternative expression for the term in brackets in line eq. (B.88) before continuing. From eq. (B.28) it follows:

$$1 = \int_{-\pi}^{\pi} \bar{V}_0 (x + x_0^{(k)}) \bigg|_{x_0=x_0^{(k)}} dx = \frac{2\pi}{N_g} \left( \int_{-N_g/2}^{q/4-1/2} + \int_{q/4-1/2}^{q/4+1/2} + \int_{q/4+1/2}^{N_g/2} \bar{V}_0 \left( \frac{2\pi}{N_g} y + x_0^{(k)} \right) \right) \bigg|_{x_0=x_0^{(k)}} dy \quad (B.89)$$

$$= \frac{2\pi}{N_g} \left( \int_{-q/4+1/2}^{N_g/2} + \int_{q/4-1/2}^{q/4+1/2} + \int_{q/4+1/2}^{N_g/2} \bar{V}_0 \left( \frac{2\pi}{N_g} y + x_0^{(k)} \right) \right) \bigg|_{x_0=x_0^{(k)}} dy, \quad (B.90)$$

where we have used the property $\bar{V}_0(\frac{2\pi}{N_g}y + x_0^{(k)}) = \bar{V}_0(-\frac{2\pi}{N_g}y + x_0^{(k)})$ which follows from eq. (B.27). Therefore,

$$\max_{q \in [-1, 1]} \left( 1 - \frac{2\pi}{N_g} \int_{-1/2-q/4}^{1/2-q/4} \bar{V}_0 \left( 2\pi y''/N_g + x_0^{(k)} \right) \bigg|_{x_0=x_0^{(k)}} dy'' \right)^2 \quad (B.91)$$

$$\le \max_{q \in [-1, 1]} \left( \frac{4\pi}{N_g} \int_{q/4+1/2}^{N_g/2} \bar{V}_0 \left( \frac{2\pi}{N_g} y + x_0^{(k)} \right) \bigg|_{x_0=x_0^{(k)}} dy \right)^2 \quad (B.92)$$

$$= \left( \frac{4\pi}{N_g} \int_{1/4}^{N_g/2} \bar{V}_0 \left( \frac{2\pi}{N_g} y + x_0^{(k)} \right) \bigg|_{x_0=x_0^{(k)}} dy \right)^2 \quad (B.93)$$

$$= \left( \frac{4\pi n A_0}{N_g} \right)^2 \left( \int_{1/4}^{N_g/2} \left( \frac{N_g}{2n\pi^2 y} \right)^{2N} dy + \int_{1/4}^{N_g/2} \left( \frac{N_g}{2n\pi^2} \frac{1}{N_g - y} \right)^{2N} dy + \sum_{p \in \mathbb{Z} \setminus \{0, -1\}} \int_{1/4}^{N_g/2} \left( 2n\pi^2 \left( \frac{y}{N_g} + p \right) \right)^{-2N} dy \right)^2 \quad (B.94)$$

$$\le \left( \frac{4\pi n A_0}{N_g} \right)^2 \left( \left( \frac{2N_g}{\pi^2 n} \right)^{2N} \frac{N_g}{2} + \left( \frac{N_g}{\pi^2 n} \right)^{2N} \frac{N_g}{2} + \frac{N_g}{2} \left( \frac{1}{2\pi^2 n} \right)^{2N} \sum_{p \in \mathbb{Z} \setminus \{0, -1\}} \left( \min_{y \in [1/4, N_g/2]} \left| \frac{y}{N_g} + p \right| \right)^{-2N} \right)^2 \quad (B.95)$$

$$\le \left( \frac{4\pi n A_0}{N_g} \right)^2 \left( 2 \left( \frac{2N_g}{\pi^2 n} \right)^{2N} \frac{N_g}{2} + \frac{N_g}{2} \left( \frac{1}{2\pi^2 n} \right)^{2N} \left( \sum_{p \in \mathbb{N}_{>0}} p^{-2N} + \sum_{p \in \mathbb{N}_{>0}} \left| \frac{1}{2} - p - 1 \right|^{-2N} \right) \right)^2 \quad (B.96)$$

$$\le (2\pi n A_0)^2 \left( 2 \left( \frac{2N_g}{\pi^2 n} \right)^{2N} + \left( \frac{2\pi^2}{3} - 5 \right) \left( \frac{1}{2\pi^2 n} \right)^{2N} \right)^2 \quad (B.97)$$

$$\le (4\pi n A_0)^2 \left( \left( \frac{2N_g}{\pi^2 n} \right)^{2N} + \frac{\pi^2}{3} \left( \frac{1}{2\pi^2 n} \right)^{2N} \right)^2 \quad (B.98)$$

where in line eq. (B.92) we have taken into account the integrals with intervals of integration $[-q/4 + 1/2, N_g/2]$ and $[q/4 + 1/2, N_g/2]$, map to one another under the transformation $q \to -q$. In line eq. (B.93) we have used the non-negativity of $\bar{V}_0$. In line eq. (B.94) we have substituted for $\bar{V}_0$ using eq. (B.27) and used the bound $V_B(x) \le (\pi x)^{-2N}$ for all $x \in \mathbb{R}$. We have also exchanged the limits of summation and integration. This is justified via the Weierstrass
M-test (see Theorem 7.10 in [35]). In line eq. (B.97), we have used the fact that the expression is upper bounded by the smallest value of N, i.e. one.

Thus using $\sqrt{a+b} \le \sqrt{a} + \sqrt{b}$ for all $a, b > 0$ and plugging eq. (B.98) into eq. (B.88), we finalise the proof. ■

So far in the appendix we have considered a Hamiltonian of the form eq. (B.1) while we are interested in ones of the form eq. (III.5) since these are the Hamiltonians appearing in Theorem 1. We now introduce a Hamiltonian of the form eq. (III.5) and relate it to the Hamiltonian appearing in lemma B.1

$$H_{M_0 SC} = H_C + \sum_{l=1}^{N_g} I_{M_0 S}^{(l)} \otimes I_C^{(l)}, \qquad (B.99)$$

where $\{I_{M_0 S}^{(l)}\}_l$ are defined by

$$I_{M_0 S}^{(l)} := \sum_{\mathfrak{m} \in \mathcal{G}} |\mathfrak{m}\rangle\langle\mathfrak{m}|_{M_{0,l}} \otimes I_S^{(l,\mathfrak{m})}, \qquad (B.100)$$

$l \in 1, 2, \dots, N_g$, and where $|\mathfrak{m}\rangle_{M_{0,l}}$ is the memory state of cell $M_{0,l}$ corresponding to gate $\mathfrak{m} \in \mathcal{G}$, where recall $\mathcal{G}$ is the gate set. Each term $I_S^{(l,\mathfrak{m})}$ is defined as follows: it has spectrum which lies in the interval $(0, 2\pi]$ and the unitary $U(\mathfrak{m}) = e^{iI_S^{(l,\mathfrak{m})}} \in \mathcal{U}_\mathcal{G}$ is the representation of gate $\mathfrak{m} \in \mathcal{G}$ on $S$. While $I_S^{(l,\mathfrak{m})}$ is $l$-independent, we keep the label to distinguish it from the term $I_S^{(l)}$.

What is more, given our previous definitions, it is readily apparent that $H_C \ge 0$ and $\{I_C^{(l)} \ge 0\}_{l=1}^{N_g}$. As such $H_{M_0 SC} \ge 0$. Therefore if $H_{M_0 SC} > 0$ we allow for an additional vector $|\text{ground}\rangle_{M_0 SC}$ in the Hilbert space of $M_0 SC$ which is orthogonal to the terms in eq. (B.99). This is the ground state of $H_{M_0 SC}$. As such we always have that the ground state of $H_{M_0 SC}$ has zero energy. This is purely for convenience since later it will allow us to calculate the mean energy of state $\rho_{M_0 SC}$ by simply taking its trace with $H_{M_0 SC}$. Since none of the states nor operators discussed in this manuscript have support on $|\text{ground}\rangle_{M_0 SC}$, we neglect its mention for now on for simplicity.

## 4. Proof of the theorem

Finally we are in a stage to prove Theorem 1:

**Theorem 1 (Optimal classical and quantum frequential computers exist).** For all gate sets $\mathcal{U}_\mathcal{G}$, initial memory states $|0\rangle_{M_0} \in \mathcal{C}_{M_0}$ and initial logical states $|0\rangle_S \in \mathcal{P}(\mathcal{H}_S)$, there exists triplets $\{|t_j\rangle_C\}_{j=0}^{N_g}$, $N_g$, $H_{M_0 SC}$ parametrised by the power $P > 0$ and a dimensionless parameter $\bar{\epsilon}$, such that for all $j = 1, 2, \dots, N_g$ and fixed $\bar{\epsilon} > 0$ the large-$P$ scaling is as follows

$$T\left(e^{-it_j H_{M_0 SC}} |0\rangle_{M_0} |0\rangle_S |0\rangle_C, \ |0\rangle_{M_0} |t_j\rangle_S |t_j\rangle_C\right) \le \left(\sum_{k=1}^{j} \tilde{d}(\mathfrak{m}_k)\right) g(\bar{\epsilon}) \text{poly}(P) P^{-1/\sqrt{\bar{\epsilon}}}, \qquad (III.7)$$

for the following two cases:
Case 1):

$$f = \frac{1}{T_0} (T_0^2 P)^{1/2-\bar{\epsilon}} + \delta f, \qquad |\delta f| \le \frac{1}{T_0} + \mathcal{O}\left(\text{poly}(P) P^{-1/\sqrt{\bar{\epsilon}}}\right) \text{ as } P \to \infty, \qquad (III.8)$$

and $|t_j\rangle_C \in \mathcal{C}_C$, $j = 0, 1, 2, \dots, N_g$.
Case 2):

$$f = \frac{1}{T_0} (T_0^2 P)^{1-\bar{\epsilon}} + \delta f', \qquad |\delta f'| \le \frac{1}{T_0} + \mathcal{O}\left(\text{poly}(P) P^{-1/\sqrt{\bar{\epsilon}}}\right) \text{ as } P \to \infty. \qquad (III.9)$$

*Proof.* We will first show that this trivially reduces to a problem not involving the memory states. Then we will prove the scaling in eq. (III.7) via lemmas B.1 to B.3, but as a function of dimension rather than power. We will then proceed to bound the dimension as a function of power and frequency as a function of power.
From eq. (B.99), we observer that $H_{M_0 SC}$ is block-diagonal in the basis of the memory, $\{|m_1\rangle_{M_{0,1}}, |m_2\rangle_{M_{0,2}}, \dots, |m_{N_g}\rangle_{M_{0,N_g}}\}_{m_l \in G}$. Since on the l.h.s. of eq. (B.99), the kets are a tensor product of an element of this set, the sole effect of commuting the memory state with the exponentiated Hamiltonian, is the mapping of $H_{M_0 SC}$ in eq. (B.99) to

$$H_C + \sum_{l=1}^{N_g} I_S^{(l,m_l)} \otimes I_C^{(l)}. \qquad (B.101)$$

In the remainder of this proof, we will work with Hamiltonians of this form but using the shorthand notation $I_S^{(l)}$ rather than $I_S^{(l,m_l)}$. Since our proof considers operators $I_S^{(l)}$ which can implement arbitrary gates, it can implement any corresponding gate $m_l$, from any gate set.

Plugging the bounds from lemmas B.2 and B.3 into the bounds from lemma B.1, and simplifying the resultant expression we find, for $j = 1, 2, 3, \dots, N_g$

$$\|e^{-it_j H_{SC}} |0\rangle_S |\Psi(0)\rangle_C - |t_j\rangle_S |\Psi(t_j d/T_0)\rangle_C\|_2 \qquad (B.102)$$

$$\le \sum_{k=1}^{j} \left( \| |t_k\rangle_S |\Psi(t_k d/T_0)\rangle_C - e^{-it_1 H_{SC}^{(k)}} |t_{k-1}\rangle_S |\Psi(t_{k-1} d/T_0)\rangle_C \|_2 \right) \qquad (B.103)$$

$$+ t_1 \max_{x \in [0, t_1]} \| \bar{H}_{\text{SC}}^{(k)} e^{-ixH_{\text{SC}}^{(k)}} |t_{k-1}\rangle_S |\Psi(t_{k-1} d/T_0)\rangle_C \|_2 \qquad (B.104)$$

$$= \sum_{k=1}^{j} \left[ \sqrt{2\epsilon_v(t_{k-1}, d)} + \pi \sqrt{2dA_{\text{nor}}} \left( e^{-\frac{\pi}{16} \left(\frac{d}{\sigma N_g}\right)^2} + 4\pi n A_0 \left( \left(\frac{2N_g}{\pi^2 n}\right)^{2N} + \frac{\pi^2}{3} \left(\frac{1}{2\pi^2 n}\right)^{2N} \right) \right) \right] + \qquad (B.105)$$

$$\sum_{k=1}^{j} \left[ \frac{\tilde{d}(m_k) 4\pi^2 n A_0}{T_0} \left( 3A_{\text{nor}} d N_g \left( e^{-\pi \frac{d^2}{\sigma^2 (4N_g)^2}} + \left(\frac{2N_g}{\pi^2 n}\right)^{2N} \right) \right. \right. \qquad (B.106) \\ \left. \left. + A_{\text{nor}} \left( \pi^2 - \frac{79}{9} \right) N_g d \left( \frac{1}{2\pi n} \right)^{2N} + N_g d \left( 1 + \frac{\pi^2}{3} \right) \epsilon_v(t_{k-1}, d) \right] \qquad (B.107)$$

$$\le \sqrt{j(j-1)} \frac{T_0}{N_g} \sqrt{2\epsilon_v(1,d)} + j\pi \sqrt{2dA_{\text{nor}}} \left( e^{-\frac{\pi}{16} \left(\frac{d}{\sigma N_g}\right)^2} + 4\pi n A_0 \left( \left(\frac{2N_g}{\pi^2 n}\right)^{2N} + \frac{\pi^2}{3} \left(\frac{1}{2\pi^2 n}\right)^{2N} \right) \right) \qquad (B.108)$$

$$+ \left( \sum_{k=1}^{j} \tilde{d}(m_k) \right) \left[ \frac{4\pi^2 n A_0}{T_0} \left( 3A_{\text{nor}} d N_g \left( e^{-\pi \frac{d^2}{\sigma^2 (4N_g)^2}} + \left(\frac{2N_g}{\pi^2 n}\right)^{2N} \right) \right. \right. \qquad (B.109)$$

$$\left. + A_{\text{nor}} \left( \pi^2 - \frac{79}{9} \right) N_g d \left( \frac{1}{2\pi n} \right)^{2N} + d \left( 1 + \frac{\pi^2}{3} \right) T_0(j-1) \epsilon_v(1,d) \right], \qquad (B.110)$$

where in lines eqs. (B.108) and (B.110), we have used the definition of $\epsilon_v(t, d)$ from eq. (B.40). Now observe that in order for lines eqs. (B.108) and (B.110) to be small, we need $d/(\sigma N_g)$ to tend to infinity as $d \to \infty$, and $[2N_g/(\pi^2 n)]^N$ to tend to zero as $d \to \infty$ sufficiently quickly. We start by recalling the definitions of $N$ and $n$ used in [27] (see eqs. F18, F220 in [27]):

$$N = \left\lceil \frac{3 - 4\epsilon_5 - \epsilon_9}{2(\epsilon_7 - \epsilon_5)} \right\rceil \ge \frac{3 - 4\epsilon_5 - \epsilon_9}{2(\epsilon_7 - \epsilon_5)}, \qquad (B.111)$$

$$n = \frac{\ln(\pi\alpha_0\sigma^2)}{2\pi C_0\alpha_0\kappa} \frac{d^{1-\epsilon_5}}{\sigma}, \qquad (B.112)$$

$$\alpha_0 = 1 - \left| 1 - n_0 \left( \frac{2}{d-1} \right) \right| \in (0, 1], \qquad (B.113)$$

<footnote n="10">¹⁰ where $\kappa = 0.792$, and $C_0(N)$ is solely a function of $N$, (e.g. independent of $d$, $\sigma$, and $N_g$; see Lemma 28 in [27]) and where $\alpha_0$ is related to the initial mean energy parameter $n_0$ (recall eq. (B.35)) via</footnote>

<footnote n="10">¹⁰Note that eqs. (B.111) and (B.112) differ slightly from the definitions cited from [27]. Namely an $\epsilon_8$ (which was introduced via eq. F232 in [27]) has been omitted in the r.h.s. of eqs. (B.111) and (B.112) and $n\delta$ has been replaced with $n$. These modifications are due to the modification of eq. (B.27). See footnote 9 for explanation.</footnote>
and is uniformly bounded from below since we assume that $n_0 = \tilde{n}_0(d-1)$, $\tilde{n}_0 \in (0, 1)$ a fixed constant (i.e. independent of $d$). The coefficients $\epsilon_5, \epsilon_7, \epsilon_9, \eta$ can be chosen to be any $d$-independent constants satisfying the relations

$$0 < \epsilon_5 < \epsilon_6 = \frac{\ln \sigma}{\ln d} < 1, \qquad (B.114)$$

$$0 < \epsilon_7 < \eta/2, \qquad (B.115)$$

$$\epsilon_5 < \epsilon_7, \qquad (B.116)$$

$$0 < \epsilon_9 < \eta, \qquad (B.117)$$

$$0 < 3 - 4\epsilon_5 - \epsilon_9, \qquad (B.118)$$

$$\frac{4}{\sigma} < d^{\eta/2} \le \frac{d}{\sigma}. \qquad (B.119)$$

Let us choose

$$\epsilon_5 = \eta\bar{\epsilon}, \quad \epsilon_7 = 2\eta\bar{\epsilon}, \quad \epsilon_9 = \eta/2, \quad \sigma = d^{\eta/2} = d^{\epsilon_6} \qquad (B.120)$$

We observe that for this choice of constants satisfies eqs. (B.114) to (B.119) for all $0 < \bar{\epsilon} < 1/6$ and $0 < \eta \le 1$. It now follows

$$\left(\frac{2N_g}{\pi^2 n}\right)^{2N} \le \left(\frac{4C_0(N)\alpha_0\kappa}{\pi \ln(\pi\alpha_0)}\right)^{2N} d^{[\eta(\bar{\epsilon}+1/2)-\epsilon_g]3/(\eta\bar{\epsilon})}, \qquad (B.121)$$

where we have defined

$$N_g = \lfloor d^{1-\epsilon_g} \rfloor \le d^{1-\epsilon_g}, \quad \epsilon_g > 0, \qquad (B.122)$$

and were it follows from the definitions and properties of $C_0$, that the prefactor

$$\left(\frac{4C_0(N)\alpha_0\kappa}{\pi \ln(\pi\alpha_0)}\right)^{2N} \qquad (B.123)$$

is independent of $d$. (It is however dependent on $\bar{\epsilon}$ and $\eta$ and might diverge if we were to take a limit in which either or both tend to zero. This is why they are fixed and $d$-independent by definition.) Now choose

$$\epsilon_g = \eta(\bar{\epsilon} + 1/2) + \eta\sqrt{\bar{\epsilon}} \qquad (B.124)$$

thus resulting in the bound

$$\left(\frac{2N_g}{\pi^2 n}\right)^{2N} \le \left(\frac{4C_0(N)\alpha_0\kappa}{\pi \ln(\pi\alpha_0)}\right)^{2N} d^{-3/\sqrt{\bar{\epsilon}}}. \qquad (B.125)$$

Since $\eta$ and $\bar{\epsilon}$ are $d$-independent by definition, so is $\epsilon_g$. Therefore, for sufficiently large $d$, we have $N_g > 1$ and both terms $(1/(2\pi^2 n))^{2N}$, $(1/(2\pi n))^{2N}$ appearing in eqs. (B.108) and (B.110) are upper bounded by eq. (B.125). For $(d/(\sigma N_g))^2$ we find from the above definitions

$$\left(\frac{d}{\sigma N_g}\right)^2 = \frac{d^{2-\eta}}{\left(\lfloor d^{1-\eta(\bar{\epsilon}+1/2)-\eta\sqrt{\bar{\epsilon}}} \rfloor\right)^2} \sim d^{2\eta(\bar{\epsilon}+\sqrt{\bar{\epsilon}})}, \qquad (B.126)$$

as $d \to \infty$.

Finally, from eq. (B.40) and eq. (B.120), it follows that $\epsilon_v(1, d)$ decays faster than any polynomial in $d$. Therefore, taking into account that $N_g \le d$, and $n \le d$ for sufficiently large $d$, and taking into account the upper bound on $A_{\text{nor}}$ (see eq. (B.41)), and that $A_0$ is solely a function of $N$ (see eq. (B.29)), it follows from eq. (B.110) that

$$\|e^{-it_j H_{\text{SC}}} |0\rangle_S |\Psi(0)\rangle_C - |t_j\rangle_S |\Psi(t_j d/T_0)\rangle_C\|_2 \le \left(\sum_{k=1}^j \tilde{d}(\mathfrak{m}_k)\right) f(\eta, \bar{\epsilon}) \text{poly}(d) d^{-3/\sqrt{\bar{\epsilon}}}, \qquad (B.127)$$

for all $\eta \in (0, 1]$, $\bar{\epsilon} \in (0, 1/6)$, $d \in \mathbb{N}_{>0}$. The function $f \ge 0$ is independent of $d$ and the elements $\{\tilde{d}(\mathfrak{m}_k)\}_{k=1}^j$. Meanwhile, $\text{poly}(d) \ge 0$ is independent of, $\eta, \bar{\epsilon}$, and the elements $\{\tilde{d}(\mathfrak{m}_k)\}_{k=1}^j$. Note that while the degree of the
polynomial poly(d) is easily deducible from line eq. (B.110), it is not important for our purposes. We can lower bound the difference in kets appearing on the l.h.s. of eq. (B.127) in terms of trace distance rather (than 2-norm) as per Theorem 1, via the use of lemma B.5.

We now turn our attention to calculating the mean energy of the initial state. Recall the discussion below eq. (B.99): the Hamiltonian $H_{M_0SC}$ has a ground-state energy of zero. As such the mean energy of the initial state is

$$ M_0 \langle \vec{m} | S \langle 0 | C \langle 0 | H_{M_0 SC} | \vec{m} \rangle_{M_0} | 0 \rangle_S | 0 \rangle_C = C \langle \Psi(0) | H_C | \Psi(0) \rangle_C + \sum_{l=1}^{N_g} S \langle 0 | I_S^{(l,m_l)} | 0 \rangle_S C \langle \Psi(0) | I_C^{(l)} | \Psi(0) \rangle_C. \quad (B.128) $$

We will now show that the terms $\{C \langle \Psi(0) | I_C^{(l)} | \Psi(0) \rangle_C\}_{l=1}^{N_g}$ are zero in the large d limit. For all $l = 1, 2, \dots, N_g$ we find

$$ |C \langle \Psi(0) | I_C^{(l)} | \Psi(0) \rangle_C| \le \frac{2\pi}{T_0} \sum_{k \in S(k_0)} \left| \bar{V}_0 \left( \frac{2\pi}{d} k \right) \right|_{x_0=x_0^{(l)}} \left| \langle \theta_k | \Psi(0) \rangle_C \right|^2 \quad (B.129) $$

$$ \le \frac{2\pi}{T_0} A_{\text{nor}} n A_0 \sum_{k \in S(0)} \sum_{p=-\infty}^{\infty} V_B \left( n 2\pi (k N_g / d - l + 1/2 + N_g p) / N_g \right) e^{-2\pi \left( \frac{k}{\sigma} \right)^2} \quad (B.130) $$

$$ \le \frac{2\pi}{T_0} A_{\text{nor}} n A_0 \left( d \max_{k' \in [-1/2, 1/2]} \sum_{p \in \{0, \pm 1\}} V_B \left( n 2\pi (k' N_g - l + 1/2 + N_g p) / N_g \right) e^{-2\pi \left( \frac{k'}{\sigma} \right)^2} \right) \quad (B.131) $$

$$ + \sum_{k \in S(0)} \sum_{p \in \mathbb{Z} \setminus \{0, \pm 1\}} \left| n 2\pi^2 (k N_g / d - l + 1/2 + N_g p) / N_g \right|^{-2N} e^{-2\pi \left( \frac{k}{\sigma} \right)^2} \quad (B.132) $$

$$ \le \frac{2\pi}{T_0} A_{\text{nor}} n A_0 \left[ 2d e^{-2\pi \left( \frac{d}{4N_g \sigma} \right)^2} + d \max_{k' \in [-1/(4N_g), 1/(4N_g)]} \sum_{p \in \{0, \pm 1\}} V_B \left( \frac{n 2\pi}{N_g} (k' N_g - l + 1/2 + N_g p) \right) \right] \quad (B.133) $$

$$ + d(n 2\pi^2)^{-2N} \max_{k \in S(0)} \sum_{p=2}^{\infty} \left( \left| \frac{k}{d} - (l - 1/2)/N_g + p \right|^{-2N} + \left| \frac{k}{d} - (l - 1/2)/N_g - p \right|^{-2N} \right) \quad (B.134) $$

$$ \le \frac{2\pi}{T_0} A_{\text{nor}} n A_0 \left[ 2d e^{-2\pi \left( \frac{d}{4N_g \sigma} \right)^2} + d \max_{q' \in [-1/4, 1/4]} \sum_{p \in \{0, \pm 1\}} \left| \frac{n 2\pi^2}{N_g} (q - l + 1/2 + N_g p) \right|^{-2N} \right] \quad (B.135) $$

$$ + d(n 2\pi^2)^{-2N} \sum_{p=2}^{\infty} \left( \left| -\frac{1}{2} - 1 + p \right|^{-2N} + \left| \frac{1}{2} - p \right|^{-2N} \right) \quad (B.136) $$

$$ \le \frac{2\pi}{T_0} A_{\text{nor}} n A_0 \left[ 2d e^{-2\pi \left( \frac{d}{4N_g \sigma} \right)^2} + 3d \left| \frac{n 2\pi^2}{4N_g} \right|^{-2N} \right] \quad (B.137) $$

$$ + d(n 2\pi^2)^{-2N} \sum_{p=2}^{\infty} \left( \left| -\frac{1}{2} - 1 + p \right|^{-2N} + \left| \frac{1}{2} - p \right|^{-2N} \right) \quad (B.138) $$

$$ \le \frac{2\pi}{T_0} A_{\text{nor}} n A_0 d \left[ 2 e^{-2\pi \left( \frac{d}{4N_g \sigma} \right)^2} + 3 \left( \frac{2N_g}{\pi^2 n} \right)^{2N} + \pi^2 \left( \frac{1}{n 2\pi^2} \right)^{2N} \right], \quad (B.139) $$

where in line eq. (B.129) we have used eq. (B.26). In line eq. (B.130) we have set $k_0 = 0$ (recall that $I_C^{(l)}$ is independent of this parameter due to the periodicity of the summand). This choice means we can easily calculate the overlaps $\langle \theta_k | \Psi(0) \rangle_C$. In line eq. (B.133) we have used the fact that $k' = k/d \in [-1/2, 1/2] = [-1/2, -1/(4N_g)] \cup [-1/(4N_g), 1/(4N_g)] \cup [1/(4N_g), 1/2]$ and the bound $V_B(x) \le 1$ for all $x \in \mathbb{R}$. In line eq. (B.136) we have used the fact that $k/d - (l - 1/2)/N_g \in [-1/2 - 1, 1/2]$ for all $k \in S_d(0)$, $l \in \{1, 2, \dots, N_g\}$, $N_g \in \mathbb{N}_{>0}$. In line eq. (B.137) we have used the fact that $-l + 1/2 + N_g p$ is always a half integer. In line eq. (B.139) we have used $N \in \mathbb{N}_{>0}$.

Therefore, using eq. (B.125) and the similar lines of reasoning to those used just after this equation, we conclude

$$ \left| \sum_{l=1}^{N_g} S \langle 0 | I_S^{(l,m_l)} | 0 \rangle_S C \langle \Psi(0) | I_C^{(l)} | \Psi(0) \rangle_C \right| \le 2\pi d \max_{l=1,2,\dots,N_g} \left| C \langle \Psi(0) | I_C^{(l)} | \Psi(0) \rangle_C \right| \quad (B.140) $$
$$ \leq f'(\eta, \bar{\epsilon}) \text{poly}'(d) d^{-3/\sqrt{\bar{\epsilon}}}, \quad (B.141) $$

for all $\eta \in (0, 1]$, $\bar{\epsilon} \in (0, 1/6)$, $d \in \mathbb{N}_{>0}$. In line eq. (B.140) we used the fact that the spectrum of $I_S^{(l,m_l)}$ is in the interval $(0, 2\pi]$. The function $f' \ge 0$ is independent of $d$ and $\text{poly}'(d) \ge 0$ is independent of $\eta$, and $\bar{\epsilon}$.

In [26], the mean energy of the initial state $|\Psi(0)\rangle_C$ for the Hamiltonian $H_C$ was calculated. It was found that

$$ 0 < C \langle \Psi(0) | H_C | \Psi(0) \rangle_C = \frac{2\pi}{T_0} n_0 + \epsilon_E, \quad (B.142) $$

where

$$ |\epsilon_E| \le \text{poly}''(d) e^{-\frac{\pi}{4} \left(\frac{d}{\sigma}\right)^2}. \quad (B.143) $$

Recall that we assume in this manuscript that $n_0 = \tilde{n}_0(d-1)$, with $\tilde{n}_0 \in (0, 1)$ and $d$-independent. It is easily verified that $\text{poly}''(d)$ is independent of the parameters $\eta, \bar{\epsilon}$ introduced here. Since $\sigma = d^{\eta/2}$, $\eta \in (0, 1]$ here, we have using eq. (B.128) that

$$ E_0 := {}_{M_0}\langle \vec{m} | {}_S\langle 0 | {}_C\langle 0 | H_{{}_M {}_S} {}_C\langle \vec{m} | {}_M\rangle {}_0\rangle {}_S\langle 0 | {}_S\rangle {}_C = \frac{2\pi}{T_0} \tilde{n}_0(d-1) + \delta E', \quad (B.144) $$

where

$$ |\delta E'| \le f''(\eta, \bar{\epsilon}) \text{poly}'''(d) d^{-3/\sqrt{\bar{\epsilon}}}, \quad (B.145) $$

with $f'' \ge 0$ independent of $d$ and $\text{poly}'''(d) \ge 0$ independent of $\eta$, and $\bar{\epsilon}$. Therefore, from the definition $P = E_0/T_0$, we find

$$ d = \frac{T_0^2}{2\pi \tilde{n}_0} P + \delta d, \quad \delta d := 1 - \frac{T_0}{2\pi \tilde{n}_0} \delta E'. \quad (B.146) $$

This provides a parametrization of $d$ in terms of $P$. We have to be cautious, because $\delta E'$ depends on $\eta, \bar{\epsilon}$ and $d$, and thus if we plug this relation into a function which depends on $d$ but not on $\eta$, or $\bar{\epsilon}$, we will not obtain a function which depends on $P$ but not on $\eta$, or $\bar{\epsilon}$. Nevertheless, note that since $\delta d$ converges to 1 in the large $d$ limit for all $\eta \in (0, 1]$ and $\bar{\epsilon} \in (0, 1/6)$, we have that for all $\bar{\epsilon} \in (0, 1/6)$, here exists $P_0(\eta, \bar{\epsilon}) > 0$ such that for all $\eta \in (0, 1]$, $\bar{\epsilon} \in (0, 1/6)$, and $P \ge P_0(\eta, \bar{\epsilon})$, the following holds

$$ f(\eta, \bar{\epsilon}) \text{poly}(d) d^{-3/\sqrt{\bar{\epsilon}}} \le f(\eta, \bar{\epsilon}) \left( \frac{T_0^2}{2\pi \tilde{n}_0} \right)^{-3/\sqrt{\bar{\epsilon}}} \text{poly}''''(P) P^{-3/\sqrt{\bar{\epsilon}}}, \quad (B.147) $$

where $\text{poly}''''(P) > 0$ for all $P \ge 0$, is a polynomial which is independent of $\eta$ and $\bar{\epsilon}$. Now let $R$ denote the ratio between the l.h.s and the r.h.s. of eq. (B.147) and let $h > 0$ be defined by $h := \max_{P \in [0, P_0(\eta, \bar{\epsilon})]} R(P)$, where the l.h.s. of eq. (B.147) is written as a function of $P$ rather than $d$ by virtue of eq. (B.146). Clearly $h$ depends on $\eta$ and $\bar{\epsilon}$ but not $P$. Therefore there exists a function $g(\eta, \bar{\epsilon}) > 0$ which is $P$ independent such that

$$ f(\eta, \bar{\epsilon}) \text{poly}(d) d^{-3/\sqrt{\bar{\epsilon}}} \le g(\eta, \bar{\epsilon}) \text{poly}''''(P) P^{-3/\sqrt{\bar{\epsilon}}}, \quad (B.148) $$

holds for all $P \ge 0$ obeying eq. (B.146). Plugging this relation into the r.h.s. of eq. (B.127), we obtain eq. (III.7) after a re-labelling of $\text{poly}''''(P)$ by $\text{poly}(P)$, and defining $g(\bar{\epsilon}) = g(\eta(\bar{\epsilon}), \bar{\epsilon})$, where the parametrization $\eta(\bar{\epsilon})$ is chosen differently in cases 1) and 2) below.

We now turn our attention to calculating the gate frequency as a function of the power. Using eq. (B.122)

$$ f = \frac{N_g}{T_0} = \frac{\lfloor d^{1-\epsilon_g} \rfloor}{T_0} = \frac{\left( \frac{T_0^2}{2\pi \tilde{n}_0} P + \delta d \right)^{1-\epsilon_g} + \delta_1}{T_0} = \frac{1}{T_0} \left( \frac{T_0^2}{2\pi \tilde{n}_0} P \right)^{1-\epsilon_g} + \delta f, \quad |\delta f| \le \left| \frac{\left( \frac{T_0^2}{2\pi \tilde{n}_0} P \right)^{-\epsilon_g}}{T_0} \delta d + \frac{\delta_1}{T_0} \right|, \quad (B.149) $$

where $\delta_1 := -d^{1-\epsilon_g} + \lfloor d^{1-\epsilon_g} \rfloor \in (-1, 0]$. For case 1) of Theorem 1, we choose $\eta$ such that $\epsilon_g = 1/2 + \bar{\epsilon}$, which from eq. (B.124) gives us

$$ \eta(\bar{\epsilon}) = \frac{1/2 + \bar{\epsilon}}{1/2 + \bar{\epsilon} + \sqrt{\bar{\epsilon}}} \quad (B.150) $$
which satisfies the condition $\eta \in (0,1]$ for all $\bar{\epsilon} \in (0,1/6)$. To finalise case 1) of the proof, we need to show that $|t_j\rangle_C \in \mathcal{C}_C$. Recalling the definition of $\mathcal{C}_C$ from appendix A 2, this consists in showing that $|t_j\rangle_C$ is an eigenstate of $L_C = \lambda t_C + iH_C$ with $|\lambda| = 1$ up to an additive vanishing term in the large $d$ limit. For the case of states $|t_j\rangle_C$ [which have $\sigma = d^{1/\eta} = \sqrt{d}$], up to an additive term (which vanished as $d \to \infty$), it was shown in [26, Lemma 7.0.1, page 144] that these states have amplitudes which are of equal magnitude in both the $\{|\theta_k\rangle\}_k$ and $\{|E_n\rangle\}_n$ basis. As such, (up to this vanishingly small additive term), they are eigenstates of $L_C$ for $\lambda = i$.

For case 2), we choose $\eta$ such that $\epsilon_g = \bar{\epsilon}$ which gives, using eq. (B.124),

$$ \eta(\bar{\epsilon}) = \frac{2\bar{\epsilon}}{2\bar{\epsilon} + 2\sqrt{\bar{\epsilon}} + 1} \qquad (B.151) $$

and tends to zero from above as $\bar{\epsilon}$ tends to zero from above. We can therefore make $\epsilon_g$ arbitrarily small by choosing $\bar{\epsilon} > 0$ sufficiently small. Now, from eq. (B.149) it follows

$$ f = \frac{1}{T_0} \left( \frac{T_0^2}{2\pi\bar{n}_0} P \right)^{1-\bar{\epsilon}} + \delta f', \quad |\delta f'| \le \frac{1}{T_0} + \mathcal{O}\left(\text{poly}(P)P^{-1/\sqrt{\bar{\epsilon}}}\right) \text{ as } P \to \infty. \qquad (B.152) $$

To achieve eq. (III.9), we choose $\tilde{n}_0 = 1/(2\pi)$. This is consistent with the parameter regime of $\tilde{n}_0$ [see text below eq. (B.113)]. Note that we cannot make $f$ arbitrarily large by choosing $\tilde{n}_0$ arbitrarily small because in said limit $P$ also becomes arbitrarily small [recall eq. (B.144)]. ■

## 5. Generic known useful technical lemmas

The following two lemmas are rather trivial but crucial for this work.

**Lemma B.4** (Unitary errors add linearly: Lemma C.0.2. in [26] or [36]). Let $\{|\Phi_m\rangle\}_{m=1}^n$ be a set of states$^{11}$ in a 2-normed vector space satisfying $\| |\Phi_m\rangle - \Delta_m |\Phi_{m-1}\rangle \|_2 \le \epsilon_m$, $\|\Delta_m\|_2 \le 1$. Then

$$ \| |\Phi_n\rangle - \Delta_n \Delta_{n-1} \dots \Delta_1 |\Phi_0\rangle \|_2 \le \sum_{m=1}^{n} \epsilon_m. \qquad (B.153) $$

*Proof.* By induction. The theorem is true by definition for $n=1$, and if the theorem is true for all $n$ up to $k$, then for $n=k+1$,

$$ \| |\Phi_{k+1}\rangle - \Delta_{k+1} \Delta_k \dots \Delta_1 |\Phi_0\rangle \|_2 = \| |\Phi_{k+1}\rangle - \Delta_{k+1} |\Phi_k\rangle + \Delta_{k+1} (|\Phi_k\rangle - \Delta_k \dots \Delta_1 |\Phi_0\rangle) \|_2 \qquad (B.154) $$

$$ \le \| |\Phi_{k+1}\rangle - \Delta_{k+1} |\Phi_k\rangle \|_2 + \| \Delta_{k+1} (|\Phi_k\rangle - \Delta_k \dots \Delta_1 |\Phi_0\rangle) \|_2 \qquad (B.155) $$

$$ \le \| |\Phi_{k+1}\rangle - \Delta_{k+1} |\Phi_k\rangle \|_2 + \| \Delta_{k+1} \|_2 \| (|\Phi_k\rangle - \Delta_k \dots \Delta_1 |\Phi_0\rangle) \|_2 \qquad (B.156) $$

$$ \le \| |\Phi_{k+1}\rangle - \Delta_{k+1} |\Phi_k\rangle \|_2 + \| |\Phi_k\rangle - \Delta_k \dots \Delta_1 |\Phi_0\rangle \|_2 \qquad (B.157) $$

$$ = \epsilon_{k+1} + \sum_{m=1}^{k} \epsilon_m = \sum_{m=1}^{k+1} \epsilon_m \qquad (B.158) $$

where we used the Minkowski vector norm inequality and the equivalence between the induced $l_2$ operator norm and the property $\|\Delta_m\|_2 \le 1$ in line eq. (B.156). ■

**Lemma B.5** (Upper bounding trace distance by Euclidean distance for pure states). The trace distance and Euclidean distance between two normalised pure states $|A\rangle, |B\rangle$ is

$$ T(|A\rangle, |B\rangle) = \sqrt{1 - |\langle A|B\rangle|^2}, \quad \| |A\rangle - |B\rangle \|_2 = \sqrt{1 - \Re[\langle A|B\rangle]}, \qquad (B.159) $$

respectively. They are related by

$$ T(|A\rangle, |B\rangle) \le \sqrt{2} \| |A\rangle - |B\rangle \|_2. \qquad (B.160) $$

<footnote>$^{11}$In Lemma C.0.2. in [26] these states were normalised by definition. Here we remove this assumption since it is not necessary and we will use it in the proof of Theorem 3 in the case of sub-normalized states.</footnote>
Proof.

$$ \begin{aligned} \sqrt{1 - |\langle A|B \rangle|^2} &= \sqrt{1 - \Re(\langle A|B \rangle)^2 - \Im(\langle A|B \rangle)^2} \le \sqrt{1 - \Re(\langle A|B \rangle)^2} = \| |A\rangle - |B\rangle \|_2 \sqrt{1 + \| |A\rangle - |B\rangle \|_2^2 / 4} \quad (B.161) \\ &\le \| |A\rangle - |B\rangle \|_2 \sqrt{2} \quad (B.162) \end{aligned} $$

<figure><img src="image_9.png" /></figure>

## Appendix C: Proof of Theorem 2: Attaining the quantum limit with a classical bus

The proof will rely heavily on material from appendix B. We first prove a theorem which allows us to decouple the errors originating from the control of the gates and the control of the memory.

For this we will need to introduce a few definitions (eqs. (C.1) are reproduced from the main text for convenience).

$$ H_{\text{MWSCC}_2} := H_{\text{M}_0\text{WSC}} + H_{\text{MWC}_2}, \quad H_{\text{MWC}_2} := H_{C_2} + \sum_{l=1}^{N_g} I_{\text{MW}}^{(l)} \otimes I_{C_2}^{(l)}, \quad H_{\text{M}_0\text{WSC}} := H_C + \sum_{l=1}^{N_g} I_{\text{M}_0\text{WS}}^{(l)} \otimes I_C^{(l)}, \quad (C.1) $$

$$ H_{\text{MWSCC}_2}^{(k)} := H_{\text{M}_0\text{WSC}}^{(k)} + \bar{H}_{\text{MWC}_2}^{(k)}, \quad (C.2) $$

$k = 1, 2, \dots, N_g$, where we define $H_{\text{M}_0\text{WSC}}^{(k)}$ via

$$ H_{\text{M}_0\text{WSC}}^{(k)} := H_C + I_{\text{M}_0\text{WS}}^{(k)} \otimes I_C^{(k)}, \quad (C.3) $$

$$ I_{\text{M}_0\text{WS}}^{(k)} := I_{\text{M}_0\text{S}}^{(k)} + |\mathbf{0}\rangle\langle\mathbf{0}|_{\text{M}_{0,k}} \otimes I_{\text{W}_k}^{(k)}, \quad (C.4) $$

with $I_{\text{M}_0\text{S}}^{(k)}$ defined in eq. (B.100) and we restrict the spectrum of $I_{\text{W}_k}^{(k)}$ to lie in the interval $(0, 2\pi]$. The term $\bar{H}_{\text{MWC}_2}^{(k)}$ is defined via

$$ \bar{H}_{\text{MWC}_2}^{(k)} := H_{\text{MWC}_2} - I_{\text{MW}}^{(k)} \otimes I_{C_2}^{(k)} = H_{C_2} + \sum_{\substack{l=1 \\ l \ne k}}^{N_g} I_{\text{MW}}^{(l)} \otimes I_{C_2}^{(l)}, \quad (C.5) $$

where $H_{\text{MWC}_2}$ is defined in eq. (IV.10) to be $H_{\text{MWC}_2} = H_{C_2} + \sum_{l=1}^{N_g} I_{\text{MW}}^{(l)} \otimes I_{C_2}^{(l)}$. Here we additionally define the structure

$$ I_{\text{MW}}^{(l)} := I_{\text{M}}^{(l)} \otimes |\text{on}\rangle\langle\text{on}|_{W_l}. \quad (C.6) $$

We will define the terms $\{I_M^{(l)}, I_{C_2}^{(l)}\}_l$ and $H_{C_2}$ in the proofs when the need for their definitions arises. The terms $\{I_{\text{M}_0\text{S}}^{(l)}, I_C^{(l)}\}_l$ and $H_C$ have been defined in appendix B.

## 1. Main technical lemma: A decoupling of error contributions

The following lemma permits one to decouple the errors resulting from the application of the gates under Hamiltonian $H_{\text{M}_0\text{WSC}}$ and the errors due to shuttling memory around via Hamiltonian $H_{\text{M}_0\text{WSC}_2}$ (Indeed, in the following, lines eq. (C.8) and eq. (C.10) correspond to errors associated to dynamics under $H_{\text{M}_0\text{WSC}}$ while lines eq. (C.9) and eq. (C.11), to errors associated to dynamics under $H_{\text{MWC}_2}$).

Unless stated otherwise, the lemmas and theorems in this section hold for all states $|0\rangle_S \in \mathcal{C}_C$. The states $\{|t_{k,r}\rangle_{\text{MC}_2}\}_{k,r}$ are assumed to obey eq. (IV.8) throughout. They will later be further specialised in appendix C3 and all proceeding lemmas and theorems will apply to these specialised versions. Likewise the states of the control on C, $\{|t_{k,r}\rangle_{\text{MC}_2}\}_{k,r}$, will be general at first and then specialised. The same is true for the Hamiltonians. The only generic assumption is that they act on a finite-dimensional Hilbert-space and are Hermitian (the former assumption could be easily relaxed for a lot of the lemmas in this section, but for our purposes this will be irrelevant and thus we have this assumption for simplicity).

The states $\{|t_{r,k}\rangle_W\}_{r,k}$ and $\{|t_{k,l}\rangle_S\}_{k,l}$ are given by eqs. (IV.2), (IV.5) and (IV.6) respectively throughout. All lemmas and theorems hold for any gate set $\mathcal{U}_G$.
**Lemma C.1 (Quantum-control-and-bus error decoupling).** For $j = 1, 2, 3, \dots, N_g$ and $l = 0, 1, 2, \dots, L$ we have

$$ \|e^{-it_{j,l}H_{\text{MWSC}_2}} |0\rangle_M |0\rangle_W |0\rangle_S |0\rangle_C |0\rangle_{C_2} - |t_{j,l}\rangle_{\text{MC}_2} |t_{j,l}\rangle_W |t_{j,l}\rangle_S |t_{j,l}\rangle_C \|_2 \quad (C.7) $$

$$ \le \sum_{r=0}^{l} \sum_{k=1}^{j} \left( \| |t_{k,r}\rangle_{\text{W}_k} |t_{k,r}\rangle_S |t_{k,r}\rangle_C - e^{-it_1 H_{\text{WSC}}^{(k,m_r,k)}} |t_{k-1,r}\rangle_{\text{W}_k} |t_{k-1,r}\rangle_S |t_{k-1,r}\rangle_C \|_2 \right) \quad (C.8) $$

$$ + \| |t_{k,r}\rangle_{\bar{M}_{0,k}C_2} |t_{k,r}\rangle_{\bar{W}_k} - e^{-it_1 \bar{H}_{\text{MWC}_2}^{(k)}} |t_{k-1,r}\rangle_{\bar{M}_{0,k}C_2} |t_{k-1,r}\rangle_{\bar{W}_k} \|_2 \quad (C.9) $$

$$ + t_1 \max_{x \in [0, t_1]} \max_{\{m_l \in \mathcal{G} \cup \{0\} \}_{l=1}^{N_g}} \| \bar{H}_{\text{WSC}}^{(k, \vec{m})} e^{-ixH_{\text{WSC}}^{(k,m)}} |t_{k-1,r}\rangle_W |t_{k-1,r}\rangle_S |t_{k-1,r}\rangle_C \|_2 \quad (C.10) $$

$$ + t_1 \max_{y \in [0, t_1]} \| (I_{\text{MW}}^{(k)} \otimes I_{C_2}^{(k)}) e^{-iy\bar{H}_{\text{MWC}_2}^{(k)}} |t_{k-1,r}\rangle_{\text{MC}_2} |t_{k-1,r}\rangle_W \|_2 \quad (C.11) $$

where

$$ H_{\text{WSC}}^{(k,m_k)} := H_{M_0, \#} \langle \vec{m} | H_{M_0 \text{WSC}}^{(k)} | \vec{m} \rangle_{M_0, \#} = H_C + I_S^{(k,m_k)} \otimes I_C^{(k)} + I_W^{(k,m_k)} \otimes I_C^{(k)} \quad (C.12) $$

$$ H_{\text{WSC}}^{(k,m_{r,k})} := H_{\text{WSC}}^{(k,m_k)} \Big|_{\mathfrak{m}_k \mapsto \mathfrak{m}_{r,k}} \quad (C.13) $$

$$ \bar{H}_{\text{WSC}}^{(k, \vec{m})} := H_{M_0, \#} \langle \vec{m} | (H_{M_0 \text{WSC}} - H_{M_0 \text{WSC}}^{(k)}) | \vec{m} \rangle_{M_0, \#} = \sum_{\substack{q=1 \\ q \neq k}}^{N_g} (I_S^{(q, m_q)} \otimes I_C^{(q)} + I_W^{(q, m_q)} \otimes I_C^{(q)}), \quad (C.14) $$

where $\vec{m} = (m_1, m_2, \dots, m_{N_g})$, $|\vec{m}\rangle_{M_0, \#} := |m_1\rangle_{M_{0,1}} |m_2\rangle_{M_{0,2}} \dots |m_{N_g}\rangle_{M_{0,N_g}}$ with $m_l \in \mathcal{G} \cup \{0\}$ and recall $I_S^{(q, m_q)}$ is defined in eq. (B.100) for $m_l \in \mathcal{G}$. For $m_l = 0$ we define $I_S^{(k,0)} := \hat{0}$ (with $\hat{0}$ the zero operator) and $I_W^{(k,0)} := I_{W_k}^{(k)}$ and $I_{W_k}^{(k,m_k)} := \hat{0}$ for all $m_l \in \mathcal{G}$.

Note that while in the above 4 lines on the r.h.s. of the inequality, the kets belong to different tensor-product subspaces, these subspaces are consistent with the spaces upon which the distinct Hamiltonians act non-trivially upon.

**Proof.** For $j = 1, 2, 3, \dots, N_g$, $l = 0, 1, 2, \dots, L$

$$ \|e^{-it_{j,l}H_{\text{MWSC}_2}} |0\rangle_M |0\rangle_W |0\rangle_S |0\rangle_C |0\rangle_{C_2} - |t_{j,l}\rangle_{\text{MC}_2} |t_{j,l}\rangle_W |t_{j,l}\rangle_S |t_{j,l}\rangle_C \|_2 \quad (C.15) $$

$$ \le \sum_{r=0}^{l} \sum_{k=1}^{j} \| |t_{k,r}\rangle_{\text{MC}_2} |t_{k,r}\rangle_W |t_{k,r}\rangle_S |t_{k,r}\rangle_C \quad (C.16) $$

$$ - e^{-it_1 H_{\text{MWSC}_2}} |t_{k-1,r}\rangle_{\text{MC}_2} |t_{k-1,r}\rangle_W |t_{k-1,r}\rangle_S |t_{k-1,r}\rangle_C \|_2 \quad (C.17) $$

$$ \le \sum_{r=0}^{l} \sum_{k=1}^{j} \left( \| |t_{k,r}\rangle_{\text{MC}_2} |t_{k,r}\rangle_W |t_{k,r}\rangle_S |t_{k,r}\rangle_C \right. \quad (C.18) $$

$$ - e^{-it_1 H_{\text{MWSC}_2}^{(k)}} |t_{k-1,r}\rangle_{\text{MC}_2} |t_{k-1,r}\rangle_W |t_{k-1,r}\rangle_S |t_{k-1,r}\rangle_C \|_2 \quad (C.19) $$

$$ + t_1 \max_{x \in [0, t_1]} \| \bar{H}_{\text{MWSC}_2}^{(k)} e^{-ixH_{\text{MWSC}_2}^{(k)}} |t_{k-1,r}\rangle_{\text{MC}_2} |t_{k-1,r}\rangle_W |t_{k-1,r}\rangle_S |t_{k-1,r}\rangle_C \|_2 \quad (C.20) $$

where $H_{\text{MWSC}_2}^{(k)}$ is given by eq. (C.2) and $\bar{H}_{\text{MWSC}_2}^{(k)}$ by

$$ \bar{H}_{\text{MWSC}_2}^{(k)} := H_{\text{MWSC}_2} - H_{\text{MWSC}_2}^{(k)} = H_{M_0 \text{WSC}} - H_{M_0 \text{WSC}}^{(k)} + I_{\text{MW}}^{(k)} \otimes I_{C_2}^{(k)} = \bar{H}_{M_0 \text{WSC}}^{(k)} + I_{\text{MW}}^{(k)} \otimes I_{C_2}^{(k)}, \quad (C.21) $$

where in the last line we substituted using eq. (B.99). Lines eq. (C.16) to eq. (C.20) follow analogously to the proof of lemma B.1. Now recall that $I_{\text{MW}}^{(l)}$ acts trivially on memory cells $M_{0,1}, M_{0,2}, \dots, M_{0,l-1}, M_{0,l+1}, \dots, M_{0,N_g}$ and switches $W_1, W_2, \dots, W_{l-1}, W_{l+1}, \dots, W_{N_g}$ (see eq. (IV.10)). Therefore, it follows from the definitions of $H_{M_0 \text{WSC}}^{(k)}$ and $\bar{H}_{\text{MWC}_2}^{(k)}$ that these terms commute since they only act non-trivially on different Hilbert spaces. Therefore
$e^{-it_1 H_{\text{MWSCC}_2}^{(k)}} = e^{-it_1 H_{\text{M}_0 \text{WSC}}^{(k)}} e^{-it_1 \bar{H}_{\text{MWC}_2}^{(k)}}$. Now recall the following identities for operators $O_A$, $O_B$ and kets $|A\rangle_A$, $|A'\rangle_A$ and $|B\rangle_B$, $|B'\rangle_B$, on Hilbert spaces $\mathcal{H}_A$ and $\mathcal{H}_B$ respectively: $\| |A\rangle_A |B\rangle_B - |A'\rangle_A |B'\rangle_B \|_2 \le \| |A\rangle_A - |A'\rangle_A \|_2 + \| |B\rangle_B - |B'\rangle_B \|_2$, which follows from the triangle inequality, and $\|(O_A \otimes O_B) |A\rangle_A |B\rangle_B \|_2 = \|O_A |A\rangle_A \|_2 \|O_B |B\rangle_B \|_2$. For $j = 1, 2, 3, \dots, N_g$, $l \in 0, 1, 2, \dots, L$

$$ \| e^{-it_{j,l} H_{\text{MWSCC}_2}} |0\rangle_M |0\rangle_W |0\rangle_S |\Psi(0)\rangle_C |\Psi(0)\rangle_{C_2} - |t_{j,l}\rangle_{MC_2} |t_{j,l}\rangle_W |t_{j,l}\rangle_S |\Psi(t_{j,l}d/T_0)\rangle_C \|_2 \quad (C.22) $$

$$ \le \sum_{r=0}^{l} \sum_{k=1}^{j} \left( \right. \\ \qquad + \| |t_{k,r}\rangle_{M_{0,k}} |t_{k,r}\rangle_W |t_{k,r}\rangle_S |\Psi(t_{k,r}d/T_0)\rangle_C - e^{-it_1 H_{M_0 \text{WSC}}^{(k)}} |t_{k-1,r}\rangle_{M_{0,k}} |t_{k-1,r}\rangle_W |t_{k-1,r}\rangle_S |\Psi(t_{k-1}d/T_0)\rangle_C \|_2 \quad (C.24) $$

$$ + \| |t_{k,r}\rangle_{\bar{M}_{0,k}C_2} |t_{k,r}\rangle_{\bar{W}_k} - e^{-it_1 \bar{H}_{\text{MWC}_2}^{(k)}} |t_{k-1,r}\rangle_{\bar{M}_{0,k}C_2} |t_{k-1,r}\rangle_{\bar{W}_k} \|_2 \quad (C.25) $$

$$ + t_1 \max_{x \in [0, t_1]} \left( \| \bar{H}_{M_0 \text{WSC}}^{(k)} e^{-ixH_{M_0 \text{WSC}}^{(k)}} |t_{k-1,r}\rangle_S |\Psi(t_{k-1}r d/T_0)\rangle_C e^{-ix\bar{H}_{\text{MWC}_2}^{(k)}} |t_{k-1,r}\rangle_{\text{MC}_2} |t_{k-1,r}\rangle_W \|_2 \right) \quad (C.26) $$

$$ + \left\| \left( I_{\text{MW}}^{(k)} \otimes I_{C_2}^{(k)} \right) e^{-ix\bar{H}_{\text{MWC}_2}^{(k)}} |t_{k-1,r}\rangle_{\text{MC}_2} |t_{k-1,r}\rangle_W \|_2 \right\| \quad (C.27) $$

where in line eq. (C.27) we have used the fact that $H_{M_0 \text{WSC}}^{(k)}$ is block-diagonal in the $\{|m\rangle_{M_{0,k}}\}_{m \in G \cup \{0\}}$ basis. To complete the proof for line eq. (C.24), we first recall eq. (IV.8) (which asserts that $|t_{k-1,r}\rangle_{M_{0,k}} = |t_{k,r}\rangle_{M_{0,k}} = |m_{k,r}\rangle_{M_{0,k}}$). Now taking into account the block diagonality of $H_{M_0 \text{WSC}}^{(k)}$, we conclude line eq. (C.8). For line eq. (C.26), first note that $e^{-ix\bar{H}_{\text{MWC}_2}^{(k)}} |t_{k-1,r}\rangle_{\text{MC}_2} |t_{k-1,r}\rangle_W = |t_{k-1,r}\rangle_W e^{-ix\bar{H}_{\text{MC}_2}^{(k,\bar{w})}} |t_{k-1,r}\rangle_{\text{MC}_2}$ where $\bar{H}_{\text{MC}_2}^{(k,\bar{w})} := W \langle t_{k-1,r} | \bar{H}_{\text{MWC}_2}^{(k)} | t_{k-1,r} \rangle_W$, since $H_{\text{MC}_2}^{(k)}$ is block-diagonal in the basis of the switches: $\{|\text{on}\rangle_{W_t}, |\text{off}\rangle_{W_t}\}_{l=1}^{N_g}$. Second, we expand the normalised vector $e^{-ix\bar{H}_{\text{MC}_2}^{(k,\bar{w})}} |t_{k-1,r}\rangle_{\text{MC}_2}$ in the orthonormal basis of the memory $\{\Pi_{k,l} |m_{k,l}\rangle_{M_{k,l}} |m_{k,l} \in G \text{ or } m_{0,l} = 0\}$ and an arbitrary orthonormal basis for the state of $C_2$. Third, we now note that $\bar{H}_{M_0 \text{WSC}}^{(k)} e^{-ixH_{M_0 \text{WSC}}^{(k)}}$ acts trivially on $C_2$ and is block-diagonal in the above orthonormal basis of the memory. By applying the definition of the two-norm, line eq. (C.10) follows. ■

## 2. Lemmas bounding error contributions from control on C

We will now state and prove a lemma which will bound lines eqs. (C.8) and (C.10) in eq. (C.7). We use the same specialised control states as in appendix B, namely $\{|t_{k,r}\rangle_C = |\Psi(t_{k,r}d/T_0)\rangle_C\}_{k,r}$ where $|\Psi(td/T_0)\rangle_C$ is defined in eq. (B.34). These states satisfy the cyclicity condition, eq. (IV.1), as shown in the proof to the following lemma.

**Lemma C.2 (Bound on quantum-control-like terms).** There exists parametrizations of the control states $\{|\Psi(t_{k,r}d/T_0)\rangle_C\}_{k,r}$ ($k = 0, 1, 2, \dots, N_g$; $r = 0, 1, 2, \dots, L$) and Hamiltonian $H_{M_0 \text{SC}}^{(k)}$ in terms of $\bar{\epsilon}$ such that the following holds for all $\bar{\epsilon} \in (0, 1/6)$ and $j = 1, 2, 3, \dots, N_g$; $l \in 0, 1, \dots, L$,

$$ \sum_{r=0}^{l} \sum_{k=1}^{j} \left( \| |t_{k,r}\rangle_{W_k} |t_{k,r}\rangle_S |\Psi(t_{k,r}d/T_0)\rangle_C - e^{-it_1 H_{\text{WSC}}^{(k,m_{r,k})}} |t_{k-1,r}\rangle_{W_k} |t_{k-1,r}\rangle_S |\Psi(t_{k-1,r}d/T_0)\rangle_C \|_2 \right) \quad (C.28) $$

$$ + t_1 \max_{x \in [0, t_1]} \max_{\{m_l \in G \cup \{0\}\}_{l=1}^{N_g}} \left\| \bar{H}_{\text{WSC}}^{(k, \bar{m})} e^{-ixH_{\text{WSC}}^{(k, m_k)}} |t_{k-1,r}\rangle_W |t_{k-1,r}\rangle_S |\Psi(t_{k-1,r}d/T_0)\rangle_C \right\|_2 \quad (C.29) $$

$$ \le \left( \sum_{r=0}^{l} \sum_{k=1}^{j} \tilde{d}(m_{r,k}) \right) h(\bar{\epsilon}) \text{poly}(d) d^{-3/\sqrt{\bar{\epsilon}}}, \quad (C.30) $$

and

$$ N_g = \lfloor d^{1-\bar{\epsilon}} \rfloor, \quad (C.31) $$
where the function $h \ge 0$ is independent of $d$ and the elements $\{\tilde{d}(\mathfrak{m}_{r,k})\}_{k=1}^j$. Meanwhile, $\text{poly}(d) \ge 0$ is independent of $\bar{\varepsilon}$ and the elements $\{\tilde{d}(\mathfrak{m}_{r,k})\}_{k=1}^j$.

*Proof.* In Theorem 1, the clock on C ran over one oscillation of the oscillator over a total time $T_0 = 2\pi/\omega_0$. In the current setup, we are running the computer over multiple $l$ runs of the oscillator. The proof consists in relating terms from the $l^{th}$ run of the oscillator to the 1st run, and then using the results from appendix B to bound them.

We start by recalling that $t_{l,r} = t_{l+rN_g} = t_l + rT_0$. Thus, recalling the definition of $|\Psi{td/T_0}\rangle_C$ in eq. (B.34), we find

$$S_d(t_{l,r}d/T_0) = \{k - rd | k \in \mathbb{Z} \text{ and } -d/2 \le t_l d/T_0 - k < d/2\}, \quad (C.32)$$

$$\psi_{\text{nor}}(t_{l,r}d/T_0) = A_{\text{nor}} e^{-\frac{\pi}{\sigma^2}(|k-rd|-t_l d/T_0)^2} e^{-i2\pi(|k-rd|-t_l d/T_0)/d}, \quad (C.33)$$

from which it follows

$$|\Psi(t_{l,r}d/T_0)\rangle_C = |\Psi(t_l d/T_0)\rangle_C \quad (C.34)$$

for all $j = 1, 2, \dots, N_g$, and $l \in \mathbb{N}_{\ge 0}$.

A state of the logical computational space $|t_{p,r}\rangle_S$ is generated by applying $p$ gates to the state of the logical computational space after $rN_g$ gates to it, i.e. $|t_{p,r}\rangle_S = \Pi_{l=1}^p U(\mathfrak{m}_{r,l})|t_{0,r}\rangle_S$, for $r = 1, 2, \dots, L$. For $r = 0$, recall that we are applying unitaries to the switches to turn them on sequentially, rather than applying gates to the computation: at times $t_{p,0}$, we apply $U(0)|\text{off}\rangle_{W_p} = |\text{on}\rangle_{W_p}$. Let us start by evaluating the terms in eqs. (C.28) and (C.29) for $r = 0$ and $r > 0$ separately:

$$\| |t_{k,r}\rangle_{W_k} |t_{k,r}\rangle_S |\Psi(t_{k,r}d/T_0)\rangle_C - e^{-it_1 H_{\text{WSC}}^{(k,\mathfrak{m}_k)}} |t_{k-1,r}\rangle_{W_k} |t_{k-1,r}\rangle_S |\Psi(t_{k-1,r}d/T_0)\rangle_C \|_2 \quad (C.35)$$

$$= \begin{cases} \| |\text{on}\rangle_{W_k} |\Psi(t_k d/T_0)\rangle_C - e^{-it_1 H_{\text{WSC}}^{(k)}} |\text{off}\rangle_{W_k} |\Psi(t_{k-1} d/T_0)\rangle_C \|_2 & \text{if } r = 0 \\ \| |t_{k,r}\rangle_S |\Psi(t_k d/T_0)\rangle_C - e^{-it_1 H_{\text{WSC}}^{(k,\mathfrak{m}_k)}} |t_{k-1,r}\rangle_S |\Psi(t_{k-1} d/T_0)\rangle_C \|_2 & \text{if } r = 1, 2, \dots, L \end{cases} \quad (C.36)$$

where

$$H_{\text{WC}}^{(k)} := H_C + I_W^{(k)} \otimes I_C^{(k)}, \quad (C.37)$$

$$H_{\text{SC}}^{(k,\mathfrak{m}_k)} := H_C + I_S^{(k,\mathfrak{m}_k)} \otimes I_C^{(k)}, \quad \mathfrak{m}_k \in \mathcal{G} \quad (C.38)$$

Similarly,

$$\| \bar{H}_{\text{WSC}}^{(k,\bar{m})} e^{-i x H_{\text{WSC}}^{(k,\bar{m})}} |t_{k-1,r}\rangle_W |t_{k-1,r}\rangle_S |\Psi(t_{k-1,r}d/T_0)\rangle_C \|_2 \quad (C.39)$$

$$= \begin{cases} \| \bar{H}_{\text{WSC}}^{(k,\bar{m})} e^{-i x H_{\text{WSC}}^{(k)}} |t_{k-1,r}\rangle_W |t_{k-1,r}\rangle_S |\Psi(t_{k-1}d/T_0)\rangle_C \|_2 & \text{if } \mathfrak{m}_k = \mathbf{0} \\ \| \bar{H}_{\text{WSC}}^{(k,\bar{m})} e^{-i x H_{\text{WSC}}^{(k,\mathfrak{m}_k)}} |t_{k-1,r}\rangle_W |t_{k-1,r}\rangle_S |\Psi(t_{k-1}d/T_0)\rangle_C \|_2 & \text{if } \mathfrak{m}_k \in \mathcal{G}, \end{cases} \quad (C.40)$$

where we can write $\bar{H}_{\text{WSC}}^{(k,\bar{m})}$ in the form $\bar{H}_{\text{WSC}}^{(k,\bar{m})} = \sum_{q=1}^{N_g} \left( I_{\gamma_1(\mathfrak{m}_q)}^{(q,\mathfrak{m}_q)} \otimes I_C^{(q)} \right)$, where $\gamma_1(\mathfrak{m}_q) = S$ if $\mathfrak{m}_q \in \mathcal{G}$, and $\gamma_1(\mathfrak{m}_q) = W$ if $\mathfrak{m}_q = \mathbf{0}$. (This follows from its definition; eq. (C.14).) In appendix B, we dealt with states of this form in eqs. (C.36) and (C.40) (i.e. in lemmas B.2 and B.3 respectively).

Using the above identities we can now apply the proof of Theorem 1 from lines eqs. (B.103) and (B.104) onwards. Importantly, the only difference is that we have $H_{\text{WC}}^{(k)}$ and $\bar{H}_{\text{WSC}}^{(k,\bar{m})}$ (or $H_{\text{SC}}^{(k)}$ and $\bar{H}_{\text{WSC}}^{(k,\bar{m})}$), rather than $H_{\text{SC}}^{(k)}$ and $\bar{H}_{\text{SC}}^{(k)}$. These only differ by the fact that the latter have interaction terms $I_S^{(l)}$ while the former has terms $I_S^{(l,\mathfrak{m}_l)}$ or $I_W^{(l)}$. Recall that $I_S^{(l)}$ is a generic term responsible of implementing any unitary on S, while $I_W^{(l,\mathfrak{m}_l)}$ is responsible for implementing the gate $\mathfrak{m}_l \in \mathcal{G}$ on S, and $I_W^{(l)}$ is responsible for implementing the gate $\mathbf{0}$ on W. Since the proof of Theorem 1 was for all generic terms $I_S^{(l)}$, it also applies in the case at hand (once one identifies the subsystems W and S in the current proof with S in the original proof) and the maximization over gates, $\max_{\{\mathfrak{m}_l \in \mathcal{G} \cup \{\mathbf{0}\}\}_{l=1}^{N_g}}$, vanishes.

Thus from eq. (B.127), we conclude that there exists an initial clock state $|\Psi(0)\rangle_C$ (the same clock state used in case 2) of Theorem 1) such that

$$\sum_{k=1}^{j} \left( \| |t_{k,r}\rangle_{W_k} |t_{k,r}\rangle_S |\Psi(t_{k,r}d/T_0)\rangle_C - e^{-it_1 H_{\text{WSC}}^{(k,\mathfrak{m}_k)}} |t_{k-1,r}\rangle_{W_k} |t_{k-1,r}\rangle_S |\Psi(t_{k-1,r}d/T_0)\rangle_C \|_2 \right) \quad (C.41)$$
$$ + t_1 \max_{x \in [0, t_1]} \max_{\{\mathfrak{m}_l \in \mathcal{G} \cup \{\mathbf{0}\}\}_{l=1}^{N_g}} \| \bar{H}_{\text{WSC}}^{(k, \bar{\mathfrak{m}})} e^{-i x H_{\text{WSC}}^{(k, \mathfrak{m}_k)}} |t_{k-1,r}\rangle_{\text{W}} |t_{k-1,r}\rangle_{\text{S}} |\Psi(t_{k-1,r} d/T_0)\rangle_{\text{C}} \|_2 \quad (C.42) $$

$$ \le \left( \sum_{k=1}^{j} \tilde{d}(\mathfrak{m}_{r,k}) \right) f(\eta, \bar{\epsilon}) \text{poly}(d) d^{-3/\sqrt{\bar{\epsilon}}}, \quad (C.43) $$

where the parameters are defined as per eq. (B.127); the only difference between line eq. (C.43) and the r.h.s. of eq. (B.127) is the replacement of $\tilde{d}(\mathfrak{m}_k)$ with $\tilde{d}(\mathfrak{m}_{r,k})$. Thus we have that eq. (C.43) holds for all $\eta \in (0, 1]$, $\bar{\epsilon} \in (0, 1/6)$, $d \in \mathbb{N}_{>0}$. The function $f \ge 0$ is independent of $d$ and the elements $\{\tilde{d}(\mathfrak{m}_{r,k})\}_{k=1}^j$. Meanwhile, $\text{poly}(d) \ge 0$ is independent of $\eta, \bar{\epsilon}$, and the elements $\{\tilde{d}(\mathfrak{m}_{r,k})\}_{k=1}^j$.

To finalise the proof, we simply need to specialise to case 2) by choosing $\eta$ such that $\epsilon_g = \bar{\epsilon}$, which provides that parametrization of $\eta$ as a function of $\eta$ according to eq. (B.151). We then define $h(\bar{\epsilon}) := f(\bar{\epsilon}, \bar{\epsilon})$ and recall the definition of $N_g$ in terms of $\epsilon_g$ in eq. (B.122).

### 3. Description of the control on $C_2$

In order to bound the terms associated with the dynamics of Hamiltonian $H_{\text{MWC}_2}$, in eq. (C.7) (namely lines eqs. (C.9) and (C.11)), we have to specialise further the Hamiltonian. We do this here. In particular, the free Hamiltonian of the clock $H_{\text{C}_2}$ will be a copy the free Hamiltonian of the clock controlling the gates, $H_{\text{C}}$, i.e. $H_{\text{C}_2} = \sum_{n=0}^{d-1} \omega_0 n |E_n\rangle\langle E_n|_{\text{C}_2}$, where $\omega_0 = 2\pi/T_0$ and $\{|E_n\rangle\}_n$ is an orthonormal basis for the Hilbert space associated with $\text{C}_2$. Also similar to before, the clock interaction terms, $\{I_M^{(l)}\}_{l=1}^{N_g}$, will be chosen to be diagonal in the discrete Fourier Transform basis associated with $\{|E_n\rangle\}_n$, namely

$$ I_{C_2}^{(l)} := \frac{d}{T_0} \sum_{k \in S_d(k_0)} I_{C_2, d}^{(l)}(k) |\theta_k\rangle\langle\theta_k|_{C_2}, \quad I_{C_2, d}^{(l)}(x) := \frac{2\pi}{d} \bar{V}_0 \left(\frac{2\pi}{d}x\right) \Big|_{x_0=x_0^{(l)}} \quad (C.44) $$

where $I_{C_2, d}(k)$ is chosen such that $I_{C_2}^{(l)}$ is independent of $k_0 \in \mathbb{R}$ (as was the case with the interaction terms for the clock on C.) and

$$ \begin{gathered} \bar{V}_0(x) = n_2 A_0 \sum_{p=-\infty}^{+\infty} V_B(n_2(x - x_0 + 2\pi p)), \qquad (C.45) \\ V_B(\cdot) = \text{sinc}^{2N_2}(\cdot) = (\sin(\pi \cdot)/(\pi \cdot))^{2N_2}, \quad N_2 \in \mathbb{N}_{>0}. \end{gathered} $$

which is the same as before (c.f. eq. (B.27)), except for exchanging the free parameters $n > 0$ for $n_2 > 0$ and $N$ for $N_2$. This is necessary since we will parametrise $n_2$ with $d$ differently for the interactions terms of C ($A_0$ above is the same as in eq. (B.27)) but with $N$ replaced with $N_2$). Likewise, the parameter $x_0$ (appearing in the definition of $\bar{V}_0(\cdot)$), will not take on the same value as for the clock on C, moreover, it will take on a value $x_0^{(l)}$ which will be chosen differently in this case. This is necessary, in order to avoid a "read-write issue": we cannot write to a memory cell which is simultaneously read without incurring a large error. To avoid such issues we want the unitary on the memory corresponding to the interaction $I_{C_2}^{(l)}$ to be performed out of phase in time with the average time at which the $I_{C_2}^{(l)}$ logical gate is performed. Since $x_0^{(l)}$ encodes this time for the $l$th logical gate as angle in cycle R, we choose

$$ x_0^{(l)} = x_0^{(l)} + \pi = \frac{2\pi}{N_g} \left( l - \frac{1}{2} \right) + \pi. \quad (C.46) $$

The justification of this choice (beyond physical intuition) will become apparent in the subsequent proofs. Finally, the parameters $n$ and $N$ in the definition of $\bar{V}(\cdot)$ will be denoted by $n_2$ and $N_2$ respectively, in order to distinguish them from those coming from the interaction terms $\{I_C^{(l)}\}_{l=1}^{N_g}$.

Now that we have justified the actual timing, we should choose the interaction terms $\{I_{\text{MW}}^{(l)}\}_{l=1}^{N_g}$ in $H_{\text{MWC}_2}$ appropriately. First recall the initial configuration of the memory: The total memory consists in $\tilde{N}_g(L+1)$ cells, arranged in a grid. Each cell stores in an orthogonal state a gate to be implemented. The initial memory state is thus of the form $|\tilde{\vec{m}}\rangle_M := |\tilde{\vec{m}}_0\rangle_{M_0} |\tilde{\vec{m}}_1\rangle_{M_1} \dots |\tilde{\vec{m}}_L\rangle_{M_L}$ with $|\tilde{\vec{m}}_j\rangle_{M_j} := |\tilde{\vec{m}}_{j,1}\rangle_{M_{j,1}} |\tilde{\vec{m}}_{j,2}\rangle_{M_{j,2}} \dots |\tilde{\vec{m}}_{j,N_g}\rangle_{M_{j,N_g}}$. The clock on C can only read sequentially the memory cells in the first row, namely $|\tilde{\vec{m}}_0\rangle_{M_0}$. Therefore the clock on $C_2$ is responsible for updating
the memory cells on $|\vec{m}_0\rangle_{M_0}$ so that the entire gate sequence can be implemented. A consistent way to achieve is to have $\{I_M^{(l)}\}_{l=1}^{N_g}$ in $H_{MC_2}$ satisfy the following conditions (for all $l = 1, 2, \dots, N_g$)

$$
\begin{align}
& e^{-iI_M^{(l)}} |\mathfrak{m}_{0,l}\rangle_{M_{0,l}} |\mathfrak{m}_{1,l}\rangle_{M_{1,l}} |\mathfrak{m}_{2,l}\rangle_{M_{2,l}} \cdots |\mathfrak{m}_{L-1,l}\rangle_{M_{L-1,l}} |\mathfrak{m}_{L,l}\rangle_{M_{L,l}} \nonumber \\
& = |\mathfrak{m}_{1,l}\rangle_{M_{0,l}} |\mathfrak{m}_{2,l}\rangle_{M_{1,l}} |\mathfrak{m}_{3,l}\rangle_{M_{2,l}} \cdots |\mathfrak{m}_{L,l}\rangle_{M_{L-1,l}} |\mathfrak{m}_{0,l}\rangle_{M_{L,l}}, \nonumber \\
& e^{-iI_M^{(l)}} |\mathfrak{m}_{1,l}\rangle_{M_{0,l}} |\mathfrak{m}_{2,l}\rangle_{M_{1,l}} |\mathfrak{m}_{3,l}\rangle_{M_{2,l}} \cdots |\mathfrak{m}_{L-1,l}\rangle_{M_{L-2,l}} |\mathfrak{m}_{L,l}\rangle_{M_{L-1,l}} |\mathfrak{m}_{0,l}\rangle_{M_{L,l}} \nonumber \\
& = |\mathfrak{m}_{2,l}\rangle_{M_{0,l}} |\mathfrak{m}_{3,l}\rangle_{M_{1,l}} |\mathfrak{m}_{4,l}\rangle_{M_{2,l}} \cdots |\mathfrak{m}_{L,l}\rangle_{M_{L-2,l}} |\mathfrak{m}_{0,l}\rangle_{M_{L-1,l}} |\mathfrak{m}_{1,l}\rangle_{M_{L,l}}, \nonumber \\
& e^{-iI_M^{(l)}} |\mathfrak{m}_{2,l}\rangle_{M_{0,l}} |\mathfrak{m}_{3,l}\rangle_{M_{1,l}} |\mathfrak{m}_{4,l}\rangle_{M_{2,l}} \cdots |\mathfrak{m}_{L-1,l}\rangle_{M_{L-3,l}} |\mathfrak{m}_{L,l}\rangle_{M_{L-2,l}} |\mathfrak{m}_{0,l}\rangle_{M_{L-1,l}} |\mathfrak{m}_{1,l}\rangle_{M_{L,l}} \tag{C.47} \\
& = |\mathfrak{m}_{3,l}\rangle_{M_{0,l}} |\mathfrak{m}_{4,l}\rangle_{M_{1,l}} |\mathfrak{m}_{5,l}\rangle_{M_{2,l}} \cdots |\mathfrak{m}_{L,l}\rangle_{M_{L-3,l}} |\mathfrak{m}_{0,l}\rangle_{M_{L-2,l}} |\mathfrak{m}_{1,l}\rangle_{M_{L-1,l}} |\mathfrak{m}_{2,l}\rangle_{M_{L,l}}, \nonumber \\
& \vdots \nonumber \\
& e^{-iI_M^{(l)}} |\mathfrak{m}_{L-1,l}\rangle_{M_{0,l}} |\mathfrak{m}_{L,l}\rangle_{M_{1,l}} |\mathfrak{m}_{0,l}\rangle_{M_{2,l}} \cdots |\mathfrak{m}_{L-1,l}\rangle_{M_{L-1,l}} |\mathfrak{m}_{L-2,l}\rangle_{M_{L,l}} \nonumber \\
& = |\mathfrak{m}_{L,l}\rangle_{M_{0,l}} |\mathfrak{m}_{0,l}\rangle_{M_{1,l}} |\mathfrak{m}_{1,l}\rangle_{M_{2,l}} \cdots |\mathfrak{m}_{L-2,l}\rangle_{M_{L-1,l}} |\mathfrak{m}_{L-1,l}\rangle_{M_{L,l}}, \nonumber
\end{align}
$$

for $\mathfrak{m}_{j,l} \in \mathcal{G}$, $j \in 1, \dots, L$, such that $\mathfrak{m}_{0,l} = \mathbf{0}$ for all $l = 1, 2, 3, \dots, N_g$. Thus since the action of $e^{-iI_M^{(l)}}$ maps from one orthonormal basis set to another, it is guaranteed that a unitary representation of $e^{-iI_M^{(l)}}$ exists. What is more, from its construction it readily follows that it is independent of the initial memory state $|0\rangle_M \in \mathcal{C}_M$ which encodes the to-be-implemented gate sequence.

Note that the memory states $\mathbf{0}$ play an additional role here beyond their primary role of controlling the turning on of the switches. Namely, they ensure that the states in eq. (C.47) before and after the application of $e^{-iI_M^{(l)}}$ are indeed orthogonal. To see this, imagine the fictitious scenario in which $\mathfrak{m}_{0,l} \neq \mathbf{0}$, $\mathfrak{m}_{0,l} \in \mathcal{G}$, $\mathbf{0} \notin \mathcal{G}$ and all initial memory cells in M have the same value $m \in \mathcal{G}$. This is highly degenerate, and the states in eq. (C.47) before and after the application of $e^{-iI_M^{(l)}}$ are indistinguishable and hence cannot be orthogonal. Since however, $\mathbf{0} \notin \mathcal{G}$ by definition, even if the initial memory state is highly degenerate in the sense which has just been described, the states before and after the application of $e^{-iI_M^{(l)}}$ are always mutually orthogonal.

The definition of $e^{-iI_M^{(l)}}$ [eq. (C.47)] is also consistent with our prior assumption on $I_M^{(l)}$, namely that it acts non-trivially only on memory block $M_{\#l}$. What is more, if $e^{-iI_M^{(l)}}$ is applied once in the time intervals $(t_{l,0}, t_{l,1}), \dots, (t_{l,L-1}, t_{l,L})$, then condition eq. (IV.8) is met. We will see that our idealised solution—the one we wish to approximate—will be consistent with this.

Let the set of pairs $\{(\Omega_{i_l}, |\Omega_{i_l}\rangle_{M_{\#l}})\}_{i_l}$ be the eigenvalues and vectors of $I_M^{(l)}$ respectively:

$$ I_M^{(l)} |\Omega_{i_l}\rangle_{M_{\#l}} = \Omega_{i_l} |\Omega_{i_l}\rangle_{M_{\#l}}, \quad \Omega_{i_l} \in (0, 2\pi], \qquad (C.48) $$

$l = 1, 2, \dots, N_g$.

We can now specify the idealised state on $MC_2$ at times $t_{k,r}$.<fnref n="12" /> For $k = 1, 2, 3, \dots, N_g - 1$; $r = 0, 1, \dots, L$,

$$ |t_{k,r}\rangle_{MC_2} := |t_{k,r}\rangle_{M\setminus\{M_{\#k}, M_{\#k+1}\}} |t_{k,r}\rangle_{M_{\#k}} |t_{k,r}\rangle_{M_{\#k+1}}, \qquad (C.49) $$

$$ |t_{k,r}\rangle_{M_{\#p}} := e^{-irI_M^{(p)}} |0\rangle_{M_{\#p}}, \quad p \in \{k, k+1\} \qquad (C.50) $$

$$ |t_{k,r}\rangle_{M\setminus\{M_{\#k}, M_{\#k+1}\}} C_2 := \prod_{\substack{l=1 \\ l \notin \{k, k+1\}}}^{N_g} \left[ \sum_{i_l} M_{\#l} \langle \Omega_{i_l} |0\rangle_{M_{\#l}} |\Omega_{i_l}\rangle_{M_{\#l}} \right] |\Psi_{\bar{i}_k, \bar{i}_{k+1}}(t_{k,r})\rangle_{C_2}, \qquad (C.51) $$

where $|\Psi_{\bar{i}_k, \bar{i}_{k+1}}(t_{k,r})\rangle_{C_2}$ is a function of indices in the set $\{i_1, i_2, \dots, i_{N_g}\} \setminus \{i_k, i_{k+1}\}$ [defined below in eq. (C.55)] and where recall the definition of the short-hand notation: $|0\rangle_{M_{\#p}} := |\mathfrak{m}_{0,p}\rangle_{M_{0,p}} |\mathfrak{m}_{1,p}\rangle_{M_{1,p}} |\mathfrak{m}_{2,p}\rangle_{M_{2,p}} \cdots |\mathfrak{m}_{L-1,p}\rangle_{M_{L-1,p}}$

<footnote n="12">¹²In this manuscript, we use notation $\prod_{i=1}^n [a_i] := a_1 a_2 \dots a_n$ and where the multiplication operation takes preference over summation, i.e. $\prod_{l=1}^n [\sum_{i_l} h(i_l)] f(i_1, i_2, \dots, i_n) := \sum_{i_1} h(i_1) \sum_{i_2} h(i_2) \dots \sum_{i_n} h(i_n) f(i_1, i_2, \dots, i_n) = \sum_{i_1, i_2, \dots, i_n} h(i_1) h(i_2) \dots h(i_n) f(i_1, i_2, \dots, i_n)$</footnote>
$|\mathfrak{m}_{L,p}\rangle_{M_{L,p}} |0\rangle_{M_{Cntl,p}}$. For the boundary values i.e. $k=0$; $r=0, 1, \dots, L$ we define the state to have periodic boundary conditions except for the case $k=r=0$ since their is no time before $t_{0,0}=0$. Namely, we define

$$|t_{0,r}\rangle_{MC_2} := |t_{0,r}\rangle_{M\setminus\{M_{\#1}, M_{\#N_g}\}} |t_{0,r}\rangle_{M_{\#1}, |t_{0,r-1}\rangle_{M_{\#N_g}}}, \qquad (C.52)$$

$$|t_{0,r}\rangle_{M\setminus\{M_{\#1}, M_{\#N_g}\}} C_2 := \prod_{\substack{l=1 \\ l \notin \{1, N_g\}}}^{N_g} \left[ \sum_{i_l} M_{\#l} \langle \Omega_{i_l} | 0 \rangle_{M_{\#l}} |\Omega_{i_l}\rangle_{M_{\#l}} \right] |\Psi_{\tilde{i}_1, \tilde{i}_{N_g}}(t_{k,r})\rangle_{C_2}, \qquad (C.53)$$

$$|t_{0,r}\rangle_{M_{\#1}} := e^{-irI_M^{(1)}} |0\rangle_{M_{\#1}}, \quad |t_{0,r-1}\rangle_{M_{\#N_g}} := \begin{cases} |0\rangle_{M_{\#N_g}} & \text{for } r=0 \\ e^{-i(r-1)I_M^{(1)}} |0\rangle_{M_{\#1}} & \text{for } r=1, 2, \dots, L. \end{cases} \qquad (C.54)$$

The state on $C_2$ is defined (in slightly more generality) as

$$|\Psi_{\tilde{i}_{n_1}, \tilde{i}_{n_2}, \dots, \tilde{i}_{n_s}}(t)\rangle_{C_2} := \sum_{q \in S_dtd/T_0) \prod_{\substack{l=1 \\ l \notin \{n_1, n_2, \dots, n_s\}}}^{N_g}} \left[ e^{-i \Omega_{i_l}^{(l)} \left( \int_{q-\Theta_l(t)d/T_0}^q dy I_{C_2,d}^{(l)}(y) \right)} \right] \psi_{\text{nor}}^{(2)}(td/T_0, q) |\theta_q\rangle_{C_2} \qquad (C.55)$$

for $n_1, n_2, \dots, n_s \in \{1, 2, \dots, N_g\}$, and where

$$\Theta_l(t) := \begin{cases} 0 & \text{if } t \le t_l \\ t - t_l & \text{if } t > t_l. \end{cases} \qquad (C.56)$$

It readily satisfies the initial condition at $t_{0,0}=0$, namely $|t_{0,0}\rangle_{MC_2} = (\Pi_{l,k} |\mathfrak{m}_{l,k}\rangle_{M_{l,k}}) |\Psi(0)\rangle_{C_2}$. What is more, one can easily verify that this idealised memory state at different times $t_{k,r}$ satisfies the necessary condition in eq. (IV.8). $\psi_{\text{nor}}^{(2)}(\cdot, \cdot)$ is defined analogously to $\psi_{\text{nor}}(\cdot, \cdot)$ for the state on C (see eq. (B.35)). We denote these normalised amplitude with a superscript simply not to confuse it with the state on C which has a different standard deviation:

$$\psi_{\text{nor}}^{(2)}(k_0; k) := A_{\text{nor}}^{(2)} e^{-\frac{\pi}{\sigma_2^2}(k-k_0)^2} e^{i2\pi n_{0,2}(k-k_0)/d}, \qquad (C.57)$$

We define them to be the same as case 1) of section appendix B. In particular, this means that they depend on the dimension$^{13}$ d as follows

$$\sigma_2 = \sqrt{d}, \quad n_{0,2} = \tilde{n}_{0,2} (d-1), \qquad (C.58)$$

where $\tilde{n}_{0,2} \in (0, 1)$ is d-independent by definition. Analogous to the definition of $\alpha_0$ in eq. (B.113), we define $\alpha_{0,2}$ for the clock on C to be

$$\alpha_{0,2} = 1 - \left| 1 - n_{0,2} \left( \frac{2}{d-1} \right) \right| \in (0, 1]. \qquad (C.59)$$

Analogously, to $|A_{\text{nor}}|$, $|A_{\text{nor}}^{(2)}|$ satisfies the upper bound

$$|A_{\text{nor}}^{(2)}|^2 = \left( \frac{2}{\sigma_2^2} \right) + \epsilon(d), \quad \text{as } d \to \infty, \qquad (C.60)$$

where $\epsilon(d) \to 0$ as $d \to \infty$ (see appendix E in [26] for details).

Note that if the $l^{th}$ factor $e^{-i\Omega_{i_l}^{(l)} \int_{q-\Theta_l(t)d/T_0}^q dy I_{C_2,d}^{(l)}(y)}$ in $|\Psi_{\tilde{i}_{n_1}, \tilde{i}_{n_2}, \dots, \tilde{i}_{n_s}}(t)\rangle_{C_2}$ is equal to $e^{-i\Omega_{i_l}^{(l)}r}$, at time $t_{k,r}$, then state $|t_{k,r}\rangle_{MC_2}$ becomes a bi-partite product state between the state on $M_{\#l}$ and the rest of MC$_2$. What is more the state on $M_{\#l}$ is equal to $e^{-irI_M^{(1)}} |0\rangle_{M_{\#l}}$, which in turn is a product state over memory cells, by virtue of eqs. (C.47). This insight will be required in the following two lemmas in the next sections.

<footnote>$^{13}$We have chosen the Hilbert space dimensions of both clocks to be the same, namely d.</footnote>
### 4. Generalization of Theorem 9.1 in [26]

In the proof of Theorem 1 we used the main theorem from [26] (Theorem 9.1) several times. In order to continue in the proof of Theorem 2, we now need to prove a generalization of Theorem 9.1. In order to keep notation close to that used in [26] and to avoid conflicts of notation used in other sections of this manuscript, the definitions and notation used in this section do not apply to other sections of this manuscript.

We start with a definition of a new clock state:

$$|\bar{\Psi}_{\text{nor}}(k_0, \vec{\Delta})\rangle := \sum_{k \in S_d(k_0)} e^{-i \sum_{j=1}^D \int_{k-\vec{\Delta}_j}^k dx V_d^{(j)}(x)} \psi_{\text{nor}}(k_0, k) |\theta_k\rangle, \quad (C.61)$$

with $\vec{\Delta} := (\Delta_1, \Delta_2, \dots, \Delta_D) \in \mathbb{R}^D$, $D \in \mathbb{N}_{>0}$, $k_0 \in \mathbb{R}$ and $\psi_{\text{nor}}(\cdot, \cdot)$ defined in eq. (B.35). The functions $\{V_d^{(j)}(\cdot)\}_j$ are all defined in the same way that $V_d(\cdot)$ is defined in [26], namely

$$V_d^{(j)}(\cdot) := \frac{2\pi}{d} V_0^{(j)}\left(\frac{2\pi}{d}(\cdot)\right), \quad j = 1, 2, \dots, D \quad (C.62)$$

where $V_0^{(j)}: \mathbb{R} \to \mathbb{R} \cup \mathbb{H}^{-}$ (where $\mathbb{H}^{-} := \{a_0 + ib_0: a_0 \in \mathbb{R}, b_0 < 0\}$ denotes the lower-half complex plane) is an infinitely differentiable function of period $2\pi$.

For the following theorem, let us define the following terms. We start with the interaction potentials,

$$\hat{V}_d^{(j)} := \frac{d}{T_0} \sum_{k \in S_d(k_0)} V_d^{(j)}(k) |\theta_k\rangle\langle\theta_k|, \quad (C.63)$$

where $k_0 \in \mathbb{R}$ and is $k_0$-independent due to the periodic nature of $V_0$ and the definition of $S_d$ below B.35. The definition of $b$ from [26, eq. 83] is updated as follows.<fnref n="14" /> $b$ is any real number satisfying:

$$b \ge \max \left\{ 2\pi, \sup_{k \in \mathbb{N}^+} \left( \max_{x \in [0, 2\pi]} \left| \sum_{j=1}^D \frac{d^k}{dx^k} V_0^{(j)}(x) \right| + \max_{y \in [0, 2\pi]} \left| \sum_{j=1}^D \frac{d^k}{dy^k} V_0^{(j)}\left(y - \frac{2\pi\Delta_j}{d}\right) \right| \right)^{1/(k+1)} \right\}. \quad (C.64)$$

Observe that, due to the $2\pi$-periodicity of the functions $\{V_0^{(j)}\}_{j=1}^D$, the r.h.s. is invariant under the mapping $\{\Delta_j\}_{j=1}^D \to \{\Delta_j + a\}_{j=1}^D$, for all $a \in \mathbb{R}$. We further define the rate parameter as

$$\bar{v} = \frac{\pi \alpha_0 \kappa}{\ln(\pi \alpha_0 \sigma^2)} b,$$

where $\kappa = 0.792$ and

$$\alpha_0 = \left(\frac{2}{d-1}\right) \min \{n_0, (d-1) - n_0\} = 1 - \left|1 - n_0\left(\frac{2}{d-1}\right)\right| \in (0, 1], \quad (C.65)$$

where recall $n_0 \in \mathbb{R}$ is a parameter which appears in the definition of $\psi_{\text{nor}}(\cdot, \cdot)$ (eq. (B.35)). (These definitions are analogous to eqs. 85 and 27 in [26].)

In the following Theorem, the free clock Hamiltonian $H_C$, is defined analogously to in the rest of this manuscript (see eq. (B.24)). In this manuscript, we will only use the case $\{V_0^{(j)}: \mathbb{R} \to \mathbb{R}\}_{j=1}^D$ but we write the general case for generality and to be in-keeping with the original theorem.

**Theorem C.1** (Moving the clock through finite time with a generalised potential). Let $k_0 \in \mathbb{R}$, $\vec{\Delta} \in \mathbb{R}^D$, $D \in \mathbb{N}_{>0}$, and $t \in \mathbb{R}$ if $\{V_0^{(j)}: \mathbb{R} \to \mathbb{R}\}_{j=1}^D$ while $t \ge 0$ otherwise. Then the effect of the generator $H_C + \sum_{j=1}^D \hat{V}_d^{(j)}$ for time $t$ on $|\bar{\Psi}_{\text{nor}}(k_0, \vec{\Delta})\rangle$ is approximated by

$$e^{-it(H_C + \sum_{j=1}^D \hat{V}_d^{(j)})} |\bar{\Psi}_{\text{nor}}(k_0, \vec{\Delta})\rangle = |\bar{\Psi}_{\text{nor}}(k_0 + \frac{d}{T_0}t, \vec{\Delta} + \frac{d}{T_0}t)\rangle + |\epsilon\rangle, \quad \|\epsilon\|_2 \le \epsilon_v(t, d)$$

<footnote n="14">¹⁴Note that the definition of $b$ from [26] has a maximization over the function itself (in addition to over its derivatives). In the proof, since the bound for $b$ is resultant from bound on a phase, it can readily be seen that the maximization of the function is at most $2\pi$ due to the invariance of a phase under modulo $2\pi$ arithmetic.</footnote>