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

Mischa P. Woods  University Grenoble Alpes, Inria, Grenoble, France

###### Abstract

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 run time 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 run time
advantage. As with classical and conventional quantum computers, quantum
frequential computers also generate heat and require cooling. We also
characterise these requirements.

##  I Introduction

Conventional quantum computers are desirable because there exist algorithms
which offer speedups in the run time when compared to the best classical
algorithm for the same problem. Grover’s search algorithm [1], which offers a
quadratic run time speedup over the theoretically optimal classical algorithm,
and Shor’s factoring algorithm [2], which offers an almost exponential speedup
over the best known classical algorithm, are perhaps the most well-known
examples.

These run time 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 run time speedup. Namely, rather than
using quantum properties to reduce the gate count itself, we will aim to
reduce the run time 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.

Figure 1: A puck, depicted by a back rectangle, moves from left to right. In
the snapshot of the dynamics depicted, the 1st two gates of the algorithm have
been implemented.

Denoting by $T_{0}$ the total run time and solving the Liouvillian for this
setup leads to a frequency

$\displaystyle f=\frac{V}{\Delta x_{0}}=\sqrt{\frac{2\,T_{0}}{m\Delta
x_{0}^{2}}}\sqrt{P},$ (II.1)

where $P$ is the total power (initial energy over run time $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 run time $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_{\textup{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}$, $\ldots,$ $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 run time $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,\ldots,N_{g}-1\\}$ such
that the pair of states
$\rho_{\textup{Com}}(t_{l}),\rho_{\textup{Com}}(t_{l+1})$ are non-squeezed
states with respect to the measurement basis and the Hamiltonian
$H_{\textup{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

$\displaystyle f\leq C_{\textit{SQL}}\sqrt{P},$ (II.2)

where $C_{\text{SQL}}$ is independent of
$P=(\textup{tr}[\rho_{0}H_{\textup{Com}}]-E^{0}_{\textup{Com}})/T_{0}$, with
$E^{0}_{\textup{Com}}$ the ground state energy of $H_{\textup{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

$\displaystyle f\leq C_{\textit{HL}}P,$ (II.3)

where $C_{\text{HL}}$ is independent of $P$. See section VI.0.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 abound 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

$\displaystyle f$ $\displaystyle\geq C_{a}P^{a},\qquad a\in(1/2,1],\,\,\,P\geq
P_{a}$ (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
$\textup{M}_{0}$ which stores the gate sequence
$(\mathbb{m}_{1},\mathbb{m}_{2},\ldots,\mathbb{m}_{N_{g}})$, where each
element belongs to an alphabet $\mathcal{G}$111To 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.. 3) the control
space C, which will encode the degrees of freedom of the system which
implements the gate sequence.

For every element $\mathbb{m}\in\mathcal{G}$, there is a corresponding unitary
$U(\mathbb{m})$ on S. The set of these
$\\{U(\mathbb{m})\,|\,\mathbb{m}\in\mathcal{G}\\}=:\mathcal{U}_{\mathcal{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, have referred to both $\mathcal{G}$ and
$\mathcal{U}_{\mathcal{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, $\textup{M}_{0}$, is formed by
$N_{g}\in{\mathbbm{N}_{>0}}$ local memory cells, i.e.
$\mathcal{C}_{\textup{M}_{0}}=\mathcal{C}_{\textup{Cell}}^{\otimes N_{g}}$,
where each cell is of the dimension of the gate set:
$\textup{Dim}(\mathcal{H}_{\textup{Cell}})=\big{|}\mathcal{G}\big{|}$. Its
initial state, $\ket{0}_{\textup{M}_{0}}$, belongs to the set representing the
memory states corresponding to all possible gate sequences the computer can
implement:222We 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_{\textup{B}}:\neq\textup{tr}_{\textup{A}}O_{\textup{AB}}$ for operators
$O_{\textup{AB}}$ over a bipartite system.

$\displaystyle\mathcal{C}_{\textup{M}_{0}}:=\big{\\{}\ket{\mathbb{m}_{1}}_{\textup{M}_{0,1}}\ket{\mathbb{m}_{2}}_{\textup{M}_{0,2}}\ket{\mathbb{m}_{3}}_{\textup{M}_{0,3}}\ldots\ket{\mathbb{m}_{N_{g}}}_{\textup{M}_{0,N_{g}}}\,\,\big{|}\,\,\mathbb{m}_{1},\mathbb{m}_{2},\ldots,\mathbb{m}_{N_{g}}\in\mathcal{G}\big{\\}}$
(III.1)

where
$\\{\ket{\mathbb{m}_{l}}_{\textup{M}_{0,l}}\\}_{\mathbb{m}_{l}\in\mathcal{G}}$
forms an orthonormal basis for the $l^{\text{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 2: Diagram of the different systems involved: the memory
$\textup{M}_{0}$, the logical space S, and control C.

Let $t_{j}:=jT_{0}/N_{g}$, $(j=0,1,2,\ldots,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

$\displaystyle\ket{t_{j}}_{\textup{S}}:=U(\mathbb{m}_{j})U(\mathbb{m}_{j-1})\ldots
U(\mathbb{m}_{1})\ket{0}_{\textup{S}},$ (III.2)

where the initial state,
$\ket{0}_{\textup{S}}\in\mathcal{P}(\mathcal{H}_{\textup{S}})$, with
$\mathcal{P}(\mathcal{H}_{\textup{S}})$ the set of normalised pure states on
$\mathcal{H}_{\textup{S}}$. The corresponding gate frequency is

$\displaystyle f:=\frac{N_{g}}{T_{0}}.$ (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,\ldots,N_{g}$) is

$\displaystyle\ket{0}_{\textup{M}_{0}}\ket{t_{j}}_{\textup{S}}\ket{t_{j}}_{\textup{C}}.$
(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 $\textup{S},\textup{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

$\displaystyle
H_{{\textup{M}_{0}}\textup{S}\textup{C}}=H_{\textup{C}}+\sum_{l=1}^{N_{g}}I_{{\textup{M}_{0}}\textup{S}}^{(l)}\otimes
I_{\textup{C}}^{(l)},$ (III.5)

where we use subscripts ${\textup{M}_{0}}$, S, C to indicate which subsystems
the individual terms act upon. $H_{{\textup{M}_{0}}\textup{S}\textup{C}}$ is
self-adjoint and has a ground state energy of zero. While the Hamiltonians
$H_{{\textup{M}_{0}}\textup{S}\textup{C}}$ can depend on $\mathcal{G}$, they
cannot depend on the initial memory state
$\ket{0}_{\textup{M}_{0}}\in\mathcal{C}_{\textup{M}_{0}}$. This is because we
want the gate sequence to be encoded in $\ket{0}_{\textup{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_{\textup{C}}$
since the control state is permitted to freely evolve. Conversely, the initial
state of the memory, $\ket{0}_{\textup{M}_{0}}$, does not evolve—hence the
absence of a term of the form $H_{\textup{M}_{0}}$. It does however require
interaction terms with the physical space,
$\\{I_{{\textup{M}_{0}}\textup{S}}^{(l)}\\}_{l}$ 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}_{\mathcal{G}}$.
The $l^{\text{th}}$ interaction term, $I_{\textup{M}_{0}\textup{S}}^{(l)}$,
only acts non-trivially on S and $\textup{M}_{0,l}$. As such, we can associate
the presence of $I_{\textup{M}_{0}\textup{S}}^{(l)}$ with the application of
$U(\mathbb{m}_{l})$ on S.

The Hamiltonians $H_{\textup{C}}$ have a discrete spectrum which forms a basis
$\\{\ket{E_{n}}_{\textup{C}}\\}_{n}$. The terms
$\\{I_{\textup{C}}^{(l)}\\}_{l=1}^{N_{g}}$ are diagonal in the discrete
Fourier transform basis generated from $\\{\ket{E_{n}}_{\textup{C}}\\}_{n}$.

As before, we define the power for this model as

$\displaystyle P:=\frac{E_{0}}{T_{0}},\qquad
E_{0}:=\textup{tr}[\rho^{0}_{{\textup{M}_{0}}\textup{S}\textup{C}}H_{{\textup{M}_{0}}\textup{S}\textup{C}}],$
(III.6)

where $\rho^{0}_{{\textup{M}_{0}}\textup{S}\textup{C}}$ is the density matrix
for the initial state,
$\ket{0}_{\textup{M}_{0}}\ket{0}_{\textup{S}}\ket{0}_{\textup{C}}$. For the
following theorems, it is convenient to introduce the set of classical states
of the control $\mathcal{C}_{\textup{C}}$: this is the class of non-squeezed
states with respect to the free control Hamiltonian $H_{\textup{C}}$ and its
conjugate Hermitian operator $t_{\textup{C}}$ (which is diagonal in the same
basis as operators $\\{I_{\textup{C}}^{(l)}\\}_{l=1}^{N_{g}}$ ). In other
words, the control states in $\mathcal{C}_{\textup{C}}$ have equal uncertainty
with respect to both operators (up to normalization and vanishing corrections
in the large $P$ limit.) See section A.2 for their full definitions.

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

We use $T(\ket{A},\ket{B})$ to denote the trace distance between two
normalised kets $\ket{A}$, $\ket{B}$. As such, in the following the term
$T\big{(}\mathrm{e}^{-\mathrm{i}t_{j}H_{{\textup{M}_{0}}\textup{S}\textup{C}}}\ket{0}_{\textup{M}_{0}}\ket{0}_{\textup{S}}\ket{0}_{\textup{C}},\,\,\ket{0}_{\textup{M}_{0}}\ket{t_{j}}_{\textup{S}}\ket{t_{j}}_{\textup{C}}\big{)}$
can be understood colloquially as the error in running the computer up to time
$t_{j}$.

######  Theorem III.1 (Optimal classical and quantum frequential computers
exist).

For all gate sets $\mathcal{U}_{\mathcal{G}}$, initial memory states
$\ket{0}_{\textup{M}_{0}}\in\mathcal{C}_{\textup{M}_{0}}$ and initial logical
states $\ket{0}_{\textup{S}}\in\mathcal{P}(\mathcal{H}_{\textup{S}})$, there
exists triplets $\\{\ket{t_{j}}_{\textup{C}}\\}_{j=0}^{N_{g}}$, $N_{g}$,
$H_{\textup{M}_{0}\textup{S}\textup{C}}$ parametrised by the power $P>0$ and a
dimensionless parameter $\bar{\epsilon}$, such that for all
$j=1,2,\ldots,N_{g}$ and fixed $\bar{\varepsilon}>0$ the large-$P$ scaling is
as follows

$\displaystyle
T\Big{(}\mathrm{e}^{-\mathrm{i}t_{j}H_{{\textup{M}_{0}}\textup{S}\textup{C}}}\ket{0}_{\textup{M}_{0}}\ket{0}_{\textup{S}}\ket{0}_{\textup{C}},\,\,\ket{0}_{\textup{M}_{0}}\ket{t_{j}}_{\textup{S}}\ket{t_{j}}_{\textup{C}}\Big{)}\leq\left(\sum_{k=1}^{j}\tilde{d}(\mathbb{m}_{k})\right)g(\bar{\varepsilon})\,\textup{poly}(P)\,P^{-1/\sqrt{\bar{\varepsilon}}},$
(III.7)

for the following two cases:
Case 1):

$\displaystyle
f=\frac{1}{T_{0}}\left({T_{0}^{2}}P\right)^{1/2-\bar{\varepsilon}}+\delta
f,\qquad|\delta
f|\leq\frac{1}{T_{0}}+\mathcal{O}\left(\textup{poly}(P)P^{-1/\sqrt{\bar{\varepsilon}}}\right)\text{
as }P\to\infty,$ (III.8)

and $\ket{t_{j}}_{\textup{C}}\in\mathcal{C}_{\textup{C}}$,
$j=0,1,2,\ldots,N_{g}$.
Case 2):

$\displaystyle
f=\frac{1}{T_{0}}\left(T_{0}^{2}P\right)^{1-\bar{\varepsilon}}+\delta
f^{\prime},\qquad|\delta
f^{\prime}|\leq\frac{1}{T_{0}}+\mathcal{O}\left(\textup{poly}(P)P^{-1/\sqrt{\bar{\varepsilon}}}\right)\text{
as }P\to\infty.$ (III.9)

The proof can be found in appendix B. It is by construction. In the proof, the
parametrization of triplets $\\{\ket{t_{j}}_{\textup{C}}\\}_{j=0}^{N_{g}}$,
$N_{g}$, $H_{\textup{M}_{0}\textup{S}\textup{C}}$ is defined explicitly in
terms of $\bar{\varepsilon}$, 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 III.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.4 and II.3 can both be saturated.

The coefficients $\tilde{d}(\mathbb{m}_{k})$ are related to the number of
qubits in S which the gate $U(\mathbb{m}_{k})$ acts non-trivially on. E.g. if
$U(\mathbb{m}_{k})$ is a 2-bit/qubit gate, then $\tilde{d}(\mathbb{m}_{k})\leq
4$. It is important that the error only grows with the number of qubits the
gates act upon, rather than the total dimension $d_{\textup{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 III.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_{\textup{M}_{0}\textup{S}}^{(l)}\otimes
I_{\textup{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 $\mathbb{m}_{1},\mathbb{m}_{2},\mathbb{m}_{3},\ldots$ one wishes to
implement into sequences of length $N_{g}$, run the computer with the 1st
partition in the initial memory state $\ket{0}_{\textup{M}_{0}}$ and then
reset the control state to its initial state $\ket{0}_{\textup{C}}$ at time
$t_{N_{g}}$ and $\ket{0}_{\textup{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 $\textup{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 III.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.0.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 run time of the computer of
$(L+1)T_{0}$, $L\in{\mathbbm{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}_{\mathcal{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,\ldots,N_{g};\,l=0,1,2,\ldots,L$), $L\in{\mathbbm{N}_{\geq 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

$\displaystyle\ket{t_{j,l}}_{\textup{C}}=\ket{t_{j,m}}_{\textup{C}},$ (IV.1)

for all $l,m=0,1,2,\ldots,L$ and $j=0,1,\ldots,N_{g}$.

With the exception of the 1st cycle, the computer will run analogously to that
of the previous section, but with the memory $\textup{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}_{\mathcal{G}}$, according to the sequence $(\mathbb{m}_{1,1}$,
$\mathbb{m}_{1,2}$,$\ldots$, $\mathbb{m}_{1,N_{g}}$,
$\mathbb{m}_{2,1}$,$\mathbb{m}_{2,2}$,$\ldots,$ $\mathbb{m}_{2,N_{g}}$,
$\mathbb{m}_{3,1}$, $\ldots$, $\mathbb{m}_{3,N_{g}}$, $\ldots,$
$\mathbb{m}_{L,1},$ $\mathbb{m}_{L,2}$,$\ldots$, $\mathbb{m}_{L,N_{g}})$ with
elements in $\mathcal{G}$. The logical space will remain unchanged during the
first cycle: $\ket{0}_{\textup{S}}=\ket{t_{k,0}}_{\textup{S}}$,
$k=1,2,3,\ldots,N_{g}$, and the gate sequence is fully implemented on it over
the subsequent cycles: For $k=1,2,\ldots,N_{g}$; $l=1,2,\ldots,L$

$\displaystyle\ket{t_{k,l}}_{\textup{S}}=U(\mathbb{m}_{l,k})U(\mathbb{m}_{l,k-1})U(\mathbb{m}_{l,k-2})\ldots
U(\mathbb{m}_{2,2})U(\mathbb{m}_{2,1})U(\mathbb{m}_{1,N_{g}})\ldots
U(\mathbb{m}_{1,3})U(\mathbb{m}_{1,2})U(\mathbb{m}_{1,1})\ket{0}_{\textup{S}}.$
(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 $\textup{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}$ :

$\displaystyle\ket{t_{k,l}}_{\textup{W}}:=\ket{t_{k,l}}_{\textup{W}_{1}}\ket{t_{k,l}}_{\textup{W}_{2}}\ldots\ket{t_{k,l}}_{\textup{W}_{N_{g}}},\qquad\ket{t_{k,l}}_{\textup{W}_{j}}\in\mathcal{C}_{\textup{W}_{j}}:=\\{\ket{\textup{off}}_{\textup{W}_{j}},\ket{\textup{on}}_{\textup{W}_{j}}\\},$
(IV.3)

where $\ket{\textup{off}}_{\textup{W}_{j}}$,
$\ket{\textup{on}}_{\textup{W}_{j}}$ form an orthonormal basis for the Hilbert
space $\mathcal{H}_{\textup{W}_{j}}$. The switches are initiated to the all-
off state:
$\ket{0}_{\textup{W}}:=\ket{\textup{off}}_{\textup{W}_{1}}\ket{\textup{off}}_{\textup{W}_{2}}\ldots\ket{\textup{off}}_{\textup{W}_{N_{g}}}$.
Similarly, the memory cells on $\textup{M}_{0}$ are initialised to a state
${\bf 0}\notin\mathcal{G}$,

$\displaystyle\ket{0}_{\textup{M}_{0}}:=\ket{{\bf
0}}_{\textup{M}_{0,1}}\ket{{\bf 0}}_{\textup{M}_{0,2}}\ldots\ket{{\bf
0}}_{\textup{M}_{0,N_{g}}},$ (IV.4)

where $\ket{0}_{\textup{M}_{0}}$ is orthogonal to all states in
$\mathcal{C}_{\textup{M}_{0}}$. At later times, some of the memory cells in
$\textup{M}_{0}$ will have changed to take on values in $\mathcal{G}$, and as
such the elements of $\big{\\{}\ket{t_{j,l}}_{\textup{M}_{0}}\big{\\}}_{j,l}$
belong to
$\mathcal{C}_{\textup{M}_{0}}^{\prime}:={\mathcal{C}_{\textup{Cell}}^{\prime}}^{\\!\\!\\!\\!\\!\otimes
N_{g}}$,
$\mathcal{C}_{\textup{Cell}}^{\prime}=\big{\\{}\ket{\mathbb{m}}\big{\\}}_{\mathbb{m}\in\mathcal{G}\cup\\{{\bf
0}\\}}$. We want to describe a scenario where the state $\ket{{\bf
0}}_{\textup{M}_{0,k}}$ informs the control on C to turn the $k$th switch from
the off state, $\ket{\textup{off}}_{\textup{W}_{k}}$, to the on state
$\ket{\textup{on}}_{\textup{W}_{k}}$. Moreover, we will now assume that the
control system on C reads memory cell ${\textup{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 $\ket{t_{k,0}}_{\textup{W}}$ as the state of
the switch at time $t_{k,0}$:

$\displaystyle\ket{t_{k,0}}_{\textup{W}}:=\left[\ket{\textup{on}}_{\textup{W}_{1}}\ket{\textup{on}}_{\textup{W}_{2}}\ldots\ket{\textup{on}}_{\textup{W}_{k}}\ket{\textup{off}}_{\textup{W}_{k+1}}\ket{\textup{off}}_{\textup{W}_{k+2}}\ket{\textup{off}}_{\textup{W}_{k+3}}\ldots\right]_{N_{g}},$
(IV.5)

for $k=1,2,\ldots,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,\ldots,N_{g}$; $r=1,2,\ldots,L$

$\displaystyle\ket{t_{N_{g},0}}_{\textup{W}}=\ket{t_{k,r}}_{\textup{W}}:=\ket{\textup{on}}_{\textup{W}_{1}}\ket{\textup{on}}_{\textup{W}_{2}}\ldots\ket{\textup{on}}_{\textup{W}_{k}}\ket{\textup{on}}_{\textup{W}_{N_{g}}}.$
(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 $\textup{C}_{2}$, to exchange the
state on $\textup{M}_{0}$ in eq. IV.4 for one containing the instructions for
the 1st $N_{g}$ logical gates, namely
$\mathbb{m}_{1,1},\mathbb{m}_{1,2},\mathbb{m}_{1,3},\ldots,\mathbb{m}_{1,N_{g}}$.
Similarly, in the $l$th cycle, the control on C should implement the gates
corresponding to the sequence
$\mathbb{m}_{l,1},\mathbb{m}_{l,2},\mathbb{m}_{l,3},\ldots,\mathbb{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,
$\ket{0}_{\textup{M}_{\scriptscriptstyle{\\#},l}}$, is a tensor-product state
encoding a partition of the to-be-implemented gate sequence and thus belongs
to the set:

$\displaystyle\mathcal{C}_{\textup{M}_{\scriptscriptstyle{\\#},l}}:=\big{\\{}\ket{{\bf
0}}_{\textup{M}_{0,l}}\ket{\mathbb{m}_{1,l}}_{\textup{M}_{1,l}}\ket{\mathbb{m}_{2,l}}_{\textup{M}_{2,l}}\ldots\ket{\mathbb{m}_{L,l}}_{\textup{M}_{L,l}}\,\big{|}\,\mathbb{m}_{1,l},\mathbb{m}_{2,l},\ldots,\mathbb{m}_{L,l}\in\mathcal{G}\,\big{\\}},$
(IV.7)

$l=1,2,\ldots,N_{g}$. Thus collectively, the initial state of the entire
memory,
$\ket{0}_{\textup{M}}:=\ket{0}_{\textup{M}_{\scriptscriptstyle{\\#},1}}\ket{0}_{\textup{M}_{\scriptscriptstyle{\\#},2}}\ket{0}_{\textup{M}_{\scriptscriptstyle{\\#},3}}\ldots\ket{0}_{\textup{M}_{\scriptscriptstyle{\\#},N_{g}}}\in\mathcal{C}_{\textup{M}_{\scriptscriptstyle{\\#},1}}\otimes\mathcal{C}_{\textup{M}_{\scriptscriptstyle{\\#},2}}\otimes\ldots\otimes\mathcal{C}_{\textup{M}_{\scriptscriptstyle{\\#},N_{g}}}=:\mathcal{C}_{\textup{M}}$
encodes the entire logical gate sequence which is to be implemented on S. See
footnote 4 for an illustration of the subsystems involved in their initial-
state configuration.

While the memory $\textup{M}_{0}$ is initially in a product state over the
distinct memory cells, since the control on $\textup{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
$\\{\mathbb{m}_{k,l}\\}_{k,l}$ which are in the process of being read/written
to. Consequently, while initially the memory and control on $\textup{C}_{2}$
will be in product-state form, $\ket{0}_{\textup{M}}\ket{0}_{\textup{C}_{2}}$,
they will be describe by a non-product state a later times:
$\\{\ket{t_{j,l}}_{\textup{M}\textup{C}_{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
$\ket{t}_{\textup{M}_{l,k}}$ the state of the cell $\textup{M}_{l,k}$ at time
$t$; we thus require,

$\displaystyle\ket{t}_{\textup{M}_{0,k}}=\ket{\mathbb{m}_{l,k}}_{\textup{M}_{0,k}},$
(IV.8)

for all $t\in[t_{k-1,l},t_{k,l}]$, and $l=1,2,3,\ldots,L$;
$k=1,2,\ldots,N_{g}$. Note that this condition also necessitates that the
state of the memory cell on $\textup{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_{\textup{bus}}$ as the frequency
at which each bus lane re-freshens the memory $\textup{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
$\textup{M}_{0,k}$) is bus-lane independent (i.e. $k$-independent), and given
by

$\displaystyle f_{\textup{bus}}=\frac{1}{T_{0}}.$ (IV.9)

Figure 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}({\mathbb{m}})$,
$\mathbb{m}\in\mathcal{G}$ in this work). It is convenient to think of the
dynamics induced via the Hamiltonian on states in $\mathcal{C}_{\textup{M}}$
as the the result of a bus whose control emanates from a system
$\textup{C}_{2}$. It is also convenient to think of this bus as consisting in
a number $N_{g}$ of lanes.444The “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. The
$l^{\text{th}}$ bus lane can copy and write to memory cells in memory block
$\textup{M}_{\scriptscriptstyle{\\#},l}$ and can be turned on or off via
changing the state of the switch in $\mathcal{C}_{\textup{W}_{l}}$ (which is
located directly above the bus lane in the figure). The control system C can
only read memory cells in $\textup{M}_{0}$ sequentially from left to right,
once per cycle and apply logical operations from $\mathcal{U}_{\mathcal{G}}$
to S sequentially and turn switches in W on or off. (Each cycle is of duration
$T_{0}$.)

As in section IV, we aim to mimic this behaviour up to a small error with a
time-independent Hamiltonian and at particular gate frequency and power. The
locality structure of our new Hamiltonian is

$\displaystyle H_{\textup{M}\textup{W}\textup{S}\textup{C}\textup{C}_{2}}$
$\displaystyle:=H_{{\textup{M}_{0}}\textup{W}\textup{S}\textup{C}}+H_{\textup{M}\textup{W}\textup{C}_{2}},\quad
H_{\textup{M}\textup{W}\textup{C}_{2}}:=H_{\textup{C}_{2}}+\sum_{l=1}^{N_{g}}I_{\textup{M}\textup{W}}^{(l)}\otimes
I_{\textup{C}_{2}}^{(l)},\quad
H_{{\textup{M}_{0}}\textup{W}\textup{S}\textup{C}}:=H_{\textup{C}}+\sum_{l=1}^{N_{g}}I_{\textup{M}_{0}\textup{W}\textup{S}}^{(l)}\otimes
I_{\textup{C}}^{(l)},$ (IV.10)

where $I_{\textup{M}\textup{W}}^{(l)}$ only acts non-trivially on memory cells
and switch states on $\textup{M}_{\scriptscriptstyle{\\#},l}\textup{W}_{l}$
i.e.—the $l$th bus lane and its corresponding on/off switch. The Hamiltonian
$H_{{\textup{M}_{0}}\textup{W}\textup{S}\textup{C}}$ is identical to those
described in eq. III.5 up to the interaction terms
$\\{I_{\textup{M}_{0}\textup{W}\textup{S}}^{(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_{\textup{M}\textup{W}\textup{S}\textup{C}\textup{C}_{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}_{\textup{M}}$. This constraint is
motivated analogously to the reasons given before in section III.

Analogously to the $H_{\textup{C}}$, $\\{I_{\textup{C}}^{(l)}\\}_{l}$ pair,
the terms $\\{I_{\textup{C}_{2}}^{(l)}\\}_{l}$ are diagonal in the discrete
Fourier Transform basis generated from the energy-eigenbasis of
$H_{\textup{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:

$\displaystyle P^{\prime}:=\frac{E_{0}^{\prime}}{T_{0}(L+1)},\qquad
E_{0}^{\prime}:=\textup{tr}[\rho^{0}_{\textup{M}\textup{W}\textup{S}\textup{C}\textup{C}_{2}}H_{\textup{M}\textup{W}\textup{S}\textup{C}\textup{C}_{2}}],$
(IV.11)

where $\rho^{0}_{\textup{M}\textup{W}\textup{S}\textup{C}\textup{C}_{2}}$ is
the density matrix for state
$\ket{0}_{\textup{M}}\ket{0}_{\textup{W}}\ket{0}_{\textup{S}}\ket{0}_{\textup{C}}\ket{0}_{\textup{C}_{2}}$.
Analogously to how we defined the set of classical states for the control on
C, we need to define the set of classical states for the control of the bus on
$\textup{C}_{2}$ as the set of non-squeezed states: the set
$\mathcal{C}_{\textup{C}_{2}}$ is the set of minimum-uncertainty states which
share the same standard deviation with respect to $H_{\textup{C}_{2}}$ and a
canonically conjugate operator $t_{\textup{C}_{2}}$ (up to normalization and
vanishing corrections in the large $P$ limit). See section A.2 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_{{\textup{M}_{0}}\textup{W}\textup{S}\textup{C}}$ and
$H_{\textup{M}\textup{W}\textup{C}_{2}}$ do not commute in general since they
both act non-trivially on memory cells $\textup{M}_{0}$ and switches W.
Physical speaking, this is because
$H_{{\textup{M}_{0}}\textup{W}\textup{S}\textup{C}}$ generates the dynamics
for performing gates on S and W controlled on the state of $\textup{M}_{0}$,
while $H_{\textup{M}\textup{W}\textup{C}_{2}}$ generates the dynamics to write
to $\textup{M}_{0}$ the necessary memory cells from
$\textup{M}_{\scriptscriptstyle{\\#},1},\textup{M}_{\scriptscriptstyle{\\#},2},\ldots,\textup{M}_{\scriptscriptstyle{\\#},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
$\textup{W}_{j}$ for turning on/off the control of the memory block on
$\textup{M}_{\scriptscriptstyle{\\#},j}$, is because of initial-condition
requirements. In particular, in our construction, we need to turn on the
memory blocks $\\{\textup{M}_{\scriptscriptstyle{\\#},j}\\}_{j}$ sequentially
to avoid malfunction. It is expected (we will not prove this here) that if the
states on $\textup{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.0.3 for a longer discussion.

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

######  Theorem IV.1 (Optimal quantum frequential computers only require a
classical internal bus).

For all gate sets $\mathcal{U}_{\mathcal{G}}$, initial memory states
$\ket{0}_{\textup{M}}\in\mathcal{C}_{\textup{M}}$ and initial logical states
$\ket{0}_{\textup{S}}\in\mathcal{P}(\mathcal{H}_{\textup{S}})$, there exists
$\ket{0}_{\textup{C}}$, $\ket{0}_{\textup{C}_{2}}$,
$\\{\ket{t_{j,l}}_{\textup{C}},\ket{t_{j,l}}_{\textup{M}\textup{C}_{2}}\\}_{j=1,2,\ldots,N_{g};\,l=0,1,\ldots,L}$,
$N_{g}$, $H_{\textup{M}_{0}\textup{S}\textup{C}}$ parametrised by the power
$P>0$ and a dimensionless parameter $\bar{\varepsilon}$ (where elements
$\ket{t_{j,l}}_{\textup{C}}$, $\ket{t_{j,l}}_{\textup{M}\textup{C}_{2}}$
satisfy eqs. IV.1 and IV.8 respectively), such that for all
$j=1,2,3,\ldots,N_{g}$; $l=0,1,2,\ldots,L$ and fixed $\bar{\varepsilon}>0$,
the large-$P$ scaling is as follows

$\displaystyle
T\Big{(}\mathrm{e}^{-\mathrm{i}t_{j,l}H_{\textup{M}\textup{W}\textup{S}\textup{C}\textup{C}_{2}}}\ket{0}_{\textup{M}}\ket{0}_{\textup{C}_{2}}\ket{0}_{\textup{W}}\ket{0}_{\textup{S}}\ket{0}_{\textup{C}},\,\,\ket{t_{j,l}}_{\textup{M}\textup{C}_{2}}\ket{t_{j,l}}_{\textup{W}}\ket{t_{j,l}}_{\textup{S}}\ket{t_{j,l}}_{\textup{C}}\Big{)}$
(IV.12)
$\displaystyle\leq\left(\sum_{r=0}^{l}\sum_{k=1}^{j}\tilde{d}(\mathbb{m}_{r,k})\right)h(\bar{\varepsilon})\,\textup{poly}\big{(}(L+1)P^{\prime}\big{)}\,\,\big{(}(L+1)P^{\prime}\big{)}^{-1/\sqrt{\bar{\varepsilon}}},$
(IV.13)

where $\ket{0}\\!\\!\bra{0}_{\textup{C}_{2}}$,
$\textup{tr}_{\textup{M}}\big{[}\ket{t_{j,l}}\\!\\!\bra{t_{j,l}}_{\textup{M}\textup{C}_{2}}\big{]}\in\mathcal{C}_{\textup{C}_{2}}$
and

$\displaystyle
f=\frac{1}{T_{0}}\left({T_{0}^{2}(L+1)}\,P^{\prime}\right)^{1-\bar{\varepsilon}}+\delta
f^{\prime\prime},\qquad|\delta
f^{\prime\prime}|\leq\frac{1}{T_{0}}+\mathcal{O}\left(\textup{poly}\big{(}(L+1)P^{\prime}\big{)}\big{(}(L+1)P^{\prime}\big{)}^{-1/\sqrt{\bar{\varepsilon}}}\,\right)\text{
as }P^{\prime}\to\infty.$ (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 III.1, the gate frequency increase achieved by
increasing $1/T_{0}$ results in only a classical scaling with power. However,
since $E_{0}^{\prime}$ is $L$-independent, the combination $(L+1)P^{\prime}$
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
$\left(\sum_{r=0}^{l}\sum_{k=1}^{j}\tilde{d}(\mathbb{m}_{r,k})\right)$ scales,
at most, linearly in $L$ (since $\mathcal{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^{\prime}$. As such, the
quantum frequential computer can run over many cycles before errors become
intolerable. More precisely, by setting $\bar{\varepsilon}$ small enough, the
number of cycles can increase arbitrarily fast as a function of energy:
$L\sim{E_{0}^{\prime}}^{1/\sqrt{2\bar{\varepsilon}}}$, and the r.h.s. of eq.
IV.12 still converges to zero for large $E_{0}^{\prime}$.

Note that the power $P^{\prime}$ 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 run time 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 III.1 and IV.1 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, 6, 7, 8, 9, 10, 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 III.1 and IV.1) since
this ratio is zero because the run time 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).

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

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 IV.1.
However, since we have already proved in Theorem IV.1 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,
$\ket{0}_{\textup{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 when the interaction terms responsible for gate implementation,
$\\{I_{\textup{M}_{0}\textup{W}\textup{S}}^{(l)}\otimes
I_{\textup{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
$\ket{0}_{\textup{C}}$ at times $t_{0,l}=lT_{0}$, $l\in{\mathbbm{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_{\scriptscriptstyle{\\#},N_{g}}$ is removed).555As we will see, this change
will not affect the synoptics since $N_{g}-1\sim N_{g}$ for large $N_{g}$.
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,
$\mathcal{C}_{\textup{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

$\displaystyle\mathcal{L}_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}(\cdot)=-\mathrm{i}\big{[}H^{\prime}_{{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}},\,\cdot\,\big{]}+\mathcal{D}_{\textup{C}}(\cdot),$
(V.1)

where $\mathcal{D}_{\textup{C}}$ is a dynamical semigroup dissipater on C. In
our case, it can be further decomposed as
$\mathcal{D}_{\textup{C}}=\mathcal{D}_{\textup{C}}^{\textup{re}}+\mathcal{D}_{\textup{C}}^{\textup{no
re}}$, where $\mathcal{D}_{\textup{C}}^{\textup{re}}$ generates the renewal
process: it maps all input states to one unique output state
$\ket{0}\\!\\!\bra{0}_{\textup{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

$\displaystyle
H^{\prime}_{{\textup{M}_{0}}\textup{S}\textup{W}\textup{C}}=H_{\textup{C}}+\sum_{l=1}^{N_{g}-1}I_{{\textup{M}_{0}}\textup{S}\textup{W}}^{(l)}\otimes
I_{\textup{C}}^{(l)},$ (V.2)

and bloque-diagonal in the $\mathcal{C}_{\textup{M}_{0}}$ basis.

The initial state of the computer we will consider in the theorem in this
section are pure states of the form
$\ket{0}_{\textup{S}}\ket{0}_{\textup{W}}\ket{0}_{\textup{M}_{0}}\ket{0}_{\textup{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
$(\mathbb{m}_{l,k})_{l,k}$ encoded into the initial state
$\ket{0}_{\textup{M}}$. The reason for imposing this constraint is the same as
that explained in section III.

Let us denote by $\rho_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}(\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{\mathbbm{N}_{\geq 0}}$ of times:
$\rho_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}(\tau)=\sum_{l=0}^{\infty}P(t|\tau_{l})\,\rho_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}(t|\tau_{l})$,
where $\rho_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}{(t|\tau_{l})}$ is
the state in the ensemble at time $\tau=\tau_{l}+t$, which has passed through
the state $\ket{0}_{\textup{C}}$ (due to the application of the renewal map
$\mathcal{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$.666We use the convention $\tau_{0}:=0$, such that
$P(t,+1|\tau_{0})$ is the probability associated with the 1st renewal.

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

$\displaystyle\ket{t}_{\textup{M}_{0,k}}=\ket{\mathbb{m}_{l,k}}_{\textup{M}_{0,k}},$
(V.3)

for all $t\in[t_{k-1},t_{k})$, $k=1,2,\ldots,N_{g}-1$. Since we will be
operating in a steady-state, eq. V.3 must hold for all $l\in{\mathbbm{N}_{\geq
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 III.1 and IV.1, it is useful to introduce states which
correspond to the state of the quantum frequential computer during its
computational run time 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
$\\{\ket{[t_{j}|\tau_{l}]}_{\textup{M}_{0}\textup{S}\textup{W}\textup{A}}\ket{[t_{j}|\tau_{l}]}_{\textup{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:

$\displaystyle\ket{[0|\tau_{l}]}_{\textup{M}_{0}\textup{S}\textup{W}\textup{A}}=\ket{\rho(0|\tau_{l})}_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}\textup{A}}=\ket{\rho(0|\tau_{l})}_{\textup{M}_{0}\textup{S}\textup{W}\textup{A}}\ket{0}_{\textup{C}},$
(V.4)

where
$\textup{tr}_{\textup{A}}[\ket{\rho(0|\tau_{l})}\\!\\!\bra{\rho(0|\tau_{l})}_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}\textup{A}}]=\rho_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}{(0|\tau_{l})}$
and the last equality is due to the fact that the renewal process maps the
state on C to $\ket{0}_{\textup{C}}$ at time $\tau_{l}$. The idealised states
$\ket{[t_{k}|\tau_{l}]}_{\textup{M}_{0}\textup{S}\textup{W}\textup{A}}$ update
via the exact application of the logical gates
$\\{U(\mathbb{m}_{l,j})\\}_{j=1}^{k}$ on S or W and a set of local unitaries
on the memory $\\{U_{\textup{M}_{0}\textup{A}}^{(l,j)}\\}_{j=1}^{k}$ to
guarantee the fulfilment of eq. V.3:

$\displaystyle\ket{[t_{k}|\tau_{l}]}_{\textup{M}_{0}\textup{S}\textup{W}\textup{A}}=U_{\textup{M}_{0}\textup{A}}^{(l,k)}\ldots
U_{\textup{M}_{0}\textup{A}}^{(l,2)}U_{\textup{M}_{0}\textup{A}}^{(l,1)}U(\mathbb{m}_{l,k})\ldots
U(\mathbb{m}_{l,2})U(\mathbb{m}_{l,1})\ket{\rho(0|\tau_{l})}_{\textup{M}_{0}\textup{S}\textup{W}\textup{A}}.$
(V.5)

Since we assume this for all $l\in{\mathbbm{N}_{\geq 0}}$, this assumption is
implicitly assuming that the oscillator on $\textup{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 $\textup{M}_{0}\backslash\textup{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 III.1 and IV.1,
defining power as initial energy over run time 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+\mathrm{d}\tau]$ is
$\textup{tr}[H^{\prime}_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}\mathcal{D}_{\textup{C}}\left(\rho_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}(\tau)\right)]\mathrm{d}\tau$,
where $\rho_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}(\tau)$ is the
solution to eq. V.5 at time $\tau$. We however are interested in the energy
flow per cycle. We can break the energy flow of the $l$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

$\displaystyle\braket{E^{\text{re}}}:=-\int_{0}^{\infty}\mathrm{d}s\,\textup{tr}[H_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}^{\prime}\,\mathcal{D}_{\textup{C}}^{\text{re}}(\rho_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}(s|\tau_{l-1}))]$
(V.6)

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

$\displaystyle\braket{E^{\text{after
re}}}:=-\int_{0}^{\infty}\mathrm{d}t\,P({t},+1|\tau_{l})\int_{0}^{t}\mathrm{d}s\,\textup{tr}[H_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}^{\prime}\,\mathcal{D}_{\textup{C}}^{\text{no
re}}(\rho_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}(s|\tau_{l}))],$ (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 irrecuperable and so in a worst-
case scenario can be completely associated with heat. As we show in the the
proof of theorem V.1, $\braket{E^{\text{re}}}$ and $\braket{E^{\text{after
re}}}$ 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}_{\textup{C}}^{\text{re}}$ what stabilises
the oscillator, the term
$\mathcal{D}_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}^{\text{no re}}$ is
necessary in order for the sum 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

$\displaystyle P^{\prime\prime}:=P^{\text{re}}+P^{\text{after re}},\quad
P^{\text{re}}:=\frac{|\braket{E^{\text{re}}}|}{T_{0}},\quad P^{\text{after
re}}:=\frac{\braket{E^{\text{after re}}}}{T_{0}}.$ (V.8)

As before, we assume $T_{0}$ to be constant, so that an increase in
$P^{\prime\prime}$ 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 V.1). Some of the energy flowing
out of the system, $\braket{E^{\text{after re}}}$, will come from the energy
flowing into the system, $\braket{E^{\text{re}}}$, 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 V.1 that $\braket{E^{\text{after
re}}}\leq-\braket{E^{\text{re}}}+\delta E$, where $\delta E$ vanishes as
$\braket{E^{\text{re}}}$ becomes large. As such the inclusion of
$\braket{E^{\text{before re}}}$ in the definition does not change how
quantities scale with increasing $P^{\prime\prime}$, which is what we are
interest 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 $\\{\mathbb{m}_{l,N_{g}}\\}_{l}$ do not exist, and
we make the association $\tilde{d}(\mathbb{m}_{l,N_{g}})=1$. Like before,
$g(\bar{\varepsilon})>0$ is a $P$-independent function of $\varepsilon>0$,
while $\textup{poly}(P)$ is an $\bar{\varepsilon}$-independent polynomial in
$P$. They are both $l$ independent.

######  Theorem V.1 (Nonequilibrium steady-state optimal quantum frequential
computers exist).

For all gate sets $\mathcal{U}_{\mathcal{G}}$, initial gate sequences
$(\mathbb{m}_{l,k})_{l,k}$ with elements in $\mathcal{G}$, and initial logical
states $\ket{0}_{\textup{S}}\in\mathcal{P}(\mathcal{H}_{\textup{S}})$, there
exists $\ket{0}_{\textup{C}}$,
$\\{\ket{t_{j}|\tau_{l}}_{\textup{C}}\\}_{j=1,2,\ldots,N_{g};l\in{\mathbbm{N}_{\geq
0}}}$, $N_{g}$, $\mathcal{L}_{\textup{M}_{0}\textup{S}\textup{W}\textup{C}}$
parametrised by the power $P^{\prime\prime}>0$ and a dimensionless parameter
$\bar{\varepsilon}$ (where elements $\ket{[t_{j}|\tau_{l}]}_{\textup{C}}$,
satisfy eq. V.5), such that for all $j=1,2,3,\ldots,N_{g}$;
$l\in{\mathbbm{N}_{\geq 0}}$ and fixed $\bar{\varepsilon}>0$, the following
large-$P^{\prime\prime}$ scaling hold simultaneously

Given that $l\in{\mathbbm{N}_{\geq 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:

$\displaystyle\int_{\tau_{l}+T_{0}-t_{1}}^{\tau_{l}+T_{0}}\mathrm{d}t\,{P}(t,+1|\tau_{l})=1-\varepsilon_{r},\qquad
0<\varepsilon_{r}\leq\left(\sum_{k=1}^{N_{g}}\tilde{d}(\mathbb{m}_{l,k})\right)g(\bar{\varepsilon})\,\textup{poly}({P^{\prime\prime}})\,{P^{\prime\prime}}^{-1/(2\sqrt{\bar{\varepsilon}})},$
(V.9)

The deviations in the state between renewals are small: For
$j=1,2,\ldots,N_{g}$,

$\displaystyle
T\Big{(}\rho_{\textup{M}_{0}\textup{S}\textup{C}}(t_{j}|\tau_{l}),\,\,\ket{[t_{j}|\tau_{l}]}_{\textup{M}_{0}\textup{S}\textup{W}\textup{A}}\ket{[t_{j}|\tau_{l}]}_{\textup{C}}\Big{)}\leq\left(\sum_{k=1}^{j}\tilde{d}(\mathbb{m}_{l,k})\right)g(\bar{\varepsilon})\,\textup{poly}({P^{\prime\prime}})\,{P^{\prime\prime}}^{-1/\sqrt{\bar{\varepsilon}}},$
(V.10)

The gate frequency has the asymptomatically optimal scaling in terms of power:

$\displaystyle
f=\frac{1}{T_{0}}\left({T_{0}^{2}}\,{P^{\prime\prime}}\right)^{1-\bar{\varepsilon}}+\delta
f^{\prime},\qquad|\delta
f^{\prime}|\leq\frac{1}{T_{0}}+\mathcal{O}\left(\textup{poly}({P^{\prime\prime}}){P^{\prime\prime}}^{-1/(2\sqrt{\bar{\varepsilon}})}\right)\text{
as }{P^{\prime\prime}}\to\infty.$ (V.11)

A few important observations: First note that, the bus width $N_{g}-1$ is give
by $T_{0}f-1$ and thus grows defectively linearly in the power [analogously to
as in Theorem IV.1]. 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}(\mathbb{m}_{l,k})$. However, since $\mathcal{G}$ is a finite set,
$\sum_{k=1}^{N_{g}}\tilde{d}(\mathbb{m}_{l,k})$ is upper bounded by a linear-
in-$P^{\prime\prime}$ function which is $l$ and $\bar{\varepsilon}$
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
$\left(\sum_{r=0}^{l}\sum_{k=1}^{j}\tilde{d}(\mathbb{m}_{r,k})\right)$ from
eq. IV.13 in Theorem IV.1, 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 III.1
which can readily be seen to apply equally well to Theorem V.1].

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^{\prime\prime}$ 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 $\textup{C}_{2}$ driving
the bus implicitly via the assumption eq. V.3, the power consumption,
$P^{\prime\prime}$, 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 $\textup{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 $\textup{C}_{2}$ should be less than that required
to stabilise the oscillator on $\textup{C}_{2}$. As such, at most, the power
requirements for the oscillator on $\textup{C}_{2}$ should be proportional to
those of C, namely $P^{\prime\prime}$. Therefore, the total power requirements
$P_{\text{tot}}$ should scale as $P_{\text{tot}}\sim P^{\prime\prime}$ 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 inline with the
results obtained in Theorem IV.1, where both oscillators (the one on C and
$\textup{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

####  VI.0.1 Pure vs mixed states

Pure states are arguably an idealisation of mixed states. In our formalism, in
the main, we have used a pure state formalization 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.

####  VI.0.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 run
time. 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 $\mathcal{G}$ and
insert sequences ($id$, $id$, $\ldots$, $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_{\text{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.

####  VI.0.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 $\textup{C}_{2}$ responsible for updating the memory cells on
$\textup{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 $\textup{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 footnote 4), 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
$\textup{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 $\textup{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.0.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.

####  VI.0.4 Oscillator synchronization

In the context of Theorem V.1 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 (eqs.
V.3 and 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_{\textup{bus}}$ with high probability. Indeed, this is
actually the case for the classical oscillator on $\textup{C}_{2}$ in the case
of the oscillator used in the proof of Theorem IV.1 (as can be seen in
appendix C). As such, the classical oscillator on $\textup{C}_{2}$ controlling
the bus only needs to be in sync with the oscillator on C within a constant
fraction of the frequency $f_{\textup{bus}}$, which is a far fry from the much
faster gate frequency $f$. Therefore, in order to keep the oscillator on
$\textup{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
section D.3 we show how the renewal process can easily generate this classical
bit in the setting of Theorem V.1.

####  VI.0.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.

####  VI.0.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.

####  VI.0.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.0.2.

####  VI.0.8 Classical control states

In this manuscript, we have used the term “classical states” to refer to
quantum systems on C or $\textup{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
manuscriptcan 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.0.2 for more
details.

####  VI.0.9 Coupling terms in the Hamiltonian

We have explained that the state on C is non-classical in the case of a
quantum frequential computer. It is worth remarking that the nature of the
interaction terms $\\{I_{\textup{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_{\textup{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^{(l)}_{\textup{C}}\mapsto I^{(l)\prime}_{\textup{C}}(\hat{x})$,
$I^{(l)\prime}_{\textup{C}}(\cdot):{\mathbbm{R}}\to{\mathbbm{R}_{\geq 0}}$)
are capable of producing quantum frequential computers—We suspect not.
Interaction terms of the form $\\{I_{\textup{C}}^{(l)}\\}_{l}$ can be
constructed in physical settings, as shown theoretically in [17].

####  VI.0.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.3 and II.2, followed by Theorems
III.1 and IV.1.

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
III.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 C in the proofs of Theorems III.1, IV.1 and V.1
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 III.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 IV.1. When phrased in
the language of quantum speed limits, Theorem IV.1 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 III.1
and IV.1. See discussion following Theorem IV.1 on this topic and how it was
used to motivate section V.

####  VI.0.11 Technicalities

From a technical standpoint, the main tools for the deriving the upper bounds
from section II came from the Cramér-Rao bound and [4]. While Theorems III.1,
IV.1 and V.1 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 $\text{poly}(\cdot)$ in Theorems III.1, IV.1 and V.1, can
be calculated exactly if desired. It is expected that they will be of low
order.

##  VII Conclusion

####  VII.0.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 run time
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 run time 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 run time 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 run time
advantage for said problems.

####  VII.0.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.

###### Acknowledgements.

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

###### Contents

  1. I Introduction
  2. II Classical and quantum upper limits to computation
  3. III Existence of Optimal Type-1 and type-2 Quantum frequential computers
  4. IV Quantum frequential computers only require a classical internal bus
  5. V Nonequilibrium steady-state dynamics, power consumption and heat dissipation
  6. VI Discussion
    1. VI.0.1 Pure vs mixed states
    2. VI.0.2 Error correction
    3. VI.0.3 Intuitive explanation to why the internal bus of a quantum frequential computer can be classical
    4. VI.0.4 Oscillator synchronization
    5. VI.0.5 Heat generation and cooling requirements
    6. VI.0.6 Irreversible computing
    7. VI.0.7 Nature of the logical space in a type-1 quantum frequential computer
    8. VI.0.8 Classical control states
    9. VI.0.9 Coupling terms in the Hamiltonian
    10. VI.0.10 Quantum speed limits
    11. VI.0.11 Technicalities
  7. VII Conclusion
    1. VII.0.1 Summary
    2. VII.0.2 Outlook
  8. A Classical limit and quantum upper bounds
    1. A.1 Proof for upper classical and quantum bounds based on metrology
    2. A.2 Definition for sets $\mathcal{C}_{\textup{C}}$ and $\mathcal{C}_{\textup{C}_{2}}$ of classical states of the control
  9. B Proof of Theorem III.1: Attaining the quantum limit
    1. B.1 Main structural technical lemma
    2. B.2 Some additional definitions required for the lemmas of section B.3
    3. B.3 Final technical lemmas
    4. B.4 Proof of the theorem
    5. B.5 Generic known useful technical lemmas
  10. C Proof of Theorem IV.1: Attaining the quantum limit with a classical bus
    1. C.1 Main technical lemma: A decoupling of error contributions
    2. C.2 Lemmas bounding error contributions from control on C
    3. C.3 Description of the control on $\textup{C}_{2}$
    4. C.4 Generalization of Theorem 9.1 in [26]
    5. C.5 Lemmas bounding error contributions from control on $\textup{C}_{2}$
  11. D Nonequilibrium steady-state dynamics
    1. D.1 Setup of the dynamical semigroup
    2. D.2 Proof of Theorem V.1
    3. D.3 Generation of a classical signal when each renewal process occurs

##  Appendix A Classical limit and quantum upper bounds

###  A.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]

$\displaystyle\braket{(t_{\text{est}}(\xi)-t)^{2}}=\int_{\xi}\textup{d}\xi\,P(\xi|t)(t_{\text{est}}-t)^{2},$
(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{\mathbbm{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 $\ket{0}$ and then passes
though a sequence $\big{(}\ket{l}_{\textup{Lo}}\big{)}_{l=1}^{N_{g}}$ of
states after the application of the first $l$ gates: the logical state is
$\ket{l}_{\textup{Lo}}$ for $t=t_{l}$ for $l=0,1,2,\ldots,N_{g}-1$. The
conditional probability $P(\xi|t)$ can be written as
$P(\xi|t)=\textup{tr}[M(\xi)\rho_{\textup{Com}}(t)]$ where
$\\{M(\xi)\\}_{\xi}$ is a complete set of POVM elements and
$\rho_{\textup{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

$\displaystyle
M(\xi)=\sum_{l=0}^{N_{g}-1}\ket{l}\\!\\!\bra{l}_{\textup{Lo}}\,\delta(l-\xi),$
(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:777Other 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 Crameŕ-Rao bound has a singular point at
$t=t_{\textup{est}}$ so this choice is not valid.

$\displaystyle
t_{\text{est}}(\xi)=\left(\xi+\Delta_{0}\right)\frac{T_{0}}{N_{g}},$ (A.3)

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

$\displaystyle\Delta
t_{\text{est}}(t_{l}):=\sqrt{\braket{(t_{\text{est}}-t_{l})^{2}}}=\Delta_{0}\frac{T_{0}}{N_{g}},$
(A.4)

for $l=0,1,\ldots,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{\mathbbm{R}}$ with a mean-squared-error $\Delta X(x)$ for which there
exist $x,x^{\prime}$ such that:

$\displaystyle 1)$ $\displaystyle\qquad\Delta(x)>0,\qquad\Delta(x^{\prime})>0$
(A.5) $\displaystyle 2)$
$\displaystyle\qquad|x-x^{\prime}|=(\lambda+1)\big{(}\Delta X(x)+\Delta
X(x^{\prime})\big{)}$ (A.6) $\displaystyle 3)$
$\displaystyle\qquad\Delta(x)=\Delta(x^{\prime})$ (A.7)

where $\lambda=4.64$, then

$\displaystyle\Delta X(x)\leq\frac{\kappa}{\textup{tr}[H\rho_{0}]-E_{0}},$
(A.8)

where $\kappa$ is a numerical constant $\kappa\approx 0.091$, $\rho_{0}$ the
initial probe state,
$\rho(x)=\mathrm{e}^{x\mathrm{i}H}\rho_{0}\mathrm{e}^{-x\mathrm{i}H}$ 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^{\prime}=t_{l}$, such that $|t-t^{\prime}|=T_{0}/N_{g}$, and $\Delta
t_{\textup{est}}(t_{l})+\Delta
t_{\textup{est}}(t_{l+1})=2\Delta_{0}T_{0}/N_{g}$. Therefore, by choosing
$\Delta_{0}=1/\big{(}2(\lambda+1)\big{)}\approx 0.0887$ it follows that

$\displaystyle\Delta
t_{\text{est}}(t_{l})\leq\frac{\kappa}{\textup{tr}[H_{\textup{Com}}\rho_{0}]-E^{0}_{\textup{Com}}},$
(A.9)

where we have denoted the ground state of $H_{\textup{Com}}$ by
$E^{0}_{\textup{Com}}$. Therefore, by recalling that $f=N_{g}/T_{0}$ with no
restrictions of the probe state nor the Hamiltonian, from eqs. A.8 and A.4 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=\textup{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,\ldots,N_{g}-1$:

$\displaystyle\Delta
t_{\textup{est}}\leq\frac{c_{0}}{\sqrt{\textup{tr}[H_{\textup{Com}}\rho_{0}]-E^{0}_{\textup{Com}}}}$
(A.10)

if $\rho_{\textup{Com}}(t_{l})$ and $\rho_{\textup{Com}}(t_{l+1})$ [where
$\rho_{\textup{Com}}(t):=\mathrm{e}^{\mathrm{i}tH_{\textup{Com}}}\rho_{\textup{Com}}(0)\mathrm{e}^{-\mathrm{i}tH_{\textup{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^{\prime}+\mathrm{i}H_{\textup{Com}}$, with
$|\lambda|=1$ and where
$M^{\prime}=\sum_{l=0}^{N_{g}-1}\ket{l}\\!\\!\bra{l}_{\textup{Lo}}$. (When
$|\lambda|>1$, the eigenstates of $L(\lambda)$ are said to be squeezed in
$H_{\textup{Com}}$ and anti-squeezed in $M^{\prime}$; and vice versa when
$|\lambda|<1$.)

###  A.2 Definition for sets $\mathcal{C}_{\textup{C}}$ and
$\mathcal{C}_{\textup{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 section 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_{\textup{C}}$, and the basis which diagonalises
the interaction terms $\\{I_{\textup{C}}^{(l)}\\}_{l=1}^{N_{g}}$. The
Hamiltonian $H_{\textup{C}}$ we use in the proof of Theorem III.1 is
$H_{\textup{C}}=\sum_{n=0}^{d-1}n\ket{E_{n}}\\!\\!\bra{E_{n}}_{\textup{C}}$,888Up
to a constant factor with units of energy. while the basis which diagonalises
the terms $\\{I_{\textup{C}}^{(l)}\\}_{l}$ is the discrete Fourier transform
basis of the orthonormal basis $\\{\ket{E_{n}}_{\textup{C}}\\}_{n}$, namely
$\bigg{\\{}\ket{\theta_{k}}=\frac{1}{\sqrt{d}}\sum_{n=0}^{d-1}\mathrm{e}^{-\mathrm{i}2\pi
nk/d}\ket{E_{n}}\bigg{\\}}_{k=0}^{d-1}.$ One thus defines the “time
observable” by
$t_{\textup{C}}:=\sum_{k=0}^{d-1}k\ket{\theta_{k}}\\!\\!\bra{\theta_{k}}_{\textup{C}}$.999Up
to a constant factor with units of time—See [26] for more insights into
$t_{\textup{C}}$ and $H_{\textup{C}}$. Thus defining the operator
$L_{\textup{C}}:=\lambda t_{\textup{C}}+\mathrm{i}H_{\textup{C}}$, we say that
a pure state $\ket{\psi}_{\textup{C}}$ on C is classical (non-squeezed) if it
is an eigenstate of $L_{\textup{C}}$ for which $|\lambda|=1$ up to vanishingly
small additive corrections in the large $d$ limit, i.e. if
$L_{\textup{C}}\ket{\psi(d)}_{\textup{C}}=E(\psi)\ket{\psi(d)}_{\textup{C}}+\ket{\epsilon(d)}_{\textup{C}}$
for $|\lambda|=1$, $E(\psi)\in{\mathbbm{C}}$ and where
$\braket{\epsilon(d)}{\epsilon(d)}_{\textup{C}}=0$ as $d\to\infty$. We denote
the set of such states by $\mathcal{C}_{\textup{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 III.1.

For the case of Theorem IV.1, in section IV, the classical states on
$\textup{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 $\textup{C}_{2}$, as the set of minimum-uncertainty states which
share the same standard deviation with respect to $t_{\textup{C}_{2}}$ and
$H_{\textup{C}_{2}}$ as the non-squeezed pure states for
$L_{\textup{C}_{2}}=\lambda t_{\textup{C}_{2}}+\mathrm{i}H_{\textup{C}_{2}}$.

More formally, one can define this set as follows. In eq. IV.10, the
Hamiltonian $H_{\textup{C}_{2}}$ is defined identically to $H_{\textup{C}}$ up
to the change of Hilbert space $\textup{C}\to\textup{C}_{2}$. We can thus
define the discrete Fourier transform basis
$\\{\ket{\theta_{k}}_{\textup{C}_{2}}\\}_{k}$ analogously to above but for
$\textup{C}_{2}$. (The interaction terms
$\\{I_{\textup{C}_{2}}^{(l)}\\}_{l=1}^{N_{g}}$ are also diagonal in this
basis.) The operator $t_{\textup{C}_{2}}$ can thus be defined as
$t_{\textup{C}_{2}}:=\sum_{k=0}^{d-1}k\ket{\theta_{k}}\\!\\!\bra{\theta_{k}}_{\textup{C}_{2}}$,
and the non-squeezed pure states on $\textup{C}_{2}$, by solving
$L_{\textup{C}_{2}}\ket{\psi(d)}_{\textup{C}_{2}}=E(\psi)\ket{\psi(d)}_{\textup{C}_{2}}+\ket{\epsilon(d)}_{\textup{C}_{2}}$
for $|\lambda|=1$, $E(\psi)\in{\mathbbm{C}}$ and where
$\braket{\epsilon(d)}{\epsilon(d)}_{\textup{C}_{2}}=0$ as $d\to\infty$. We
define $\rho_{\textup{C}_{2}}$ as classical (non-squeezed) if there exists
$\ket{\psi(d)}_{\textup{C}_{2}}$ such that $\Delta
t_{\textup{C}_{2}}(\rho_{\textup{C}_{2}}):=\textup{tr}[t_{\textup{C}_{2}}^{2}\rho_{\textup{C}_{2}}]-(\textup{tr}[t_{\textup{C}_{2}}\rho_{\textup{C}_{2}}])^{2}$
and $\Delta
H_{\textup{C}_{2}}(\rho_{\textup{C}_{2}}):=\textup{tr}[H_{\textup{C}_{2}}^{2}\rho_{\textup{C}_{2}}]-(\textup{tr}[H_{\textup{C}_{2}}\rho_{\textup{C}_{2}}])^{2}$
are equal to
${\mathstrut}_{\textup{C}_{2}}\\!\\!\bra{\psi(d)}t_{\textup{C}_{2}}^{2}\ket{\psi(d)}_{\textup{C}_{2}}-\left({\mathstrut}_{\textup{C}_{2}}\\!\\!\bra{\psi(d)}t_{\textup{C}_{2}}\ket{\psi(d)}_{\textup{C}_{2}}\right)^{2}$
and
${\mathstrut}_{\textup{C}_{2}}\\!\\!\bra{\psi(d)}H_{\textup{C}_{2}}^{2}\ket{\psi(d)}_{\textup{C}_{2}}-\left({\mathstrut}_{\textup{C}_{2}}\\!\\!\bra{\psi(d)}H_{\textup{C}_{2}}\ket{\psi(d)}_{\textup{C}_{2}}\right)^{2}$
respectively. We denote the set of all such states by
$\mathcal{C}_{\textup{C}_{2}}$.

##  Appendix B Proof of Theorem III.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.

###  B.1 Main structural technical lemma

Let us introduce hamiltonians of the form

$\displaystyle
H_{\textup{S}\textup{C}}:=H_{\textup{C}}+\sum_{\begin{subarray}{c}l=1\end{subarray}}^{N_{g}}I_{\textup{S}}^{(l)}\otimes
I_{\textup{C}}^{(l)}.$ (B.1)

In the following lemma, we assume that the states
$\\{\ket{t_{j}}_{\textup{S}},\ket{t_{j}}_{\textup{C}}\\}_{j=0}^{N_{g}}$ are
normalised and $H_{\textup{S}\textup{C}}$ in eq. B.1 is finite-
dimensional.101010This last assumption is overkill; indeed under minimal
assumptions it can be extended to the infinite-dimensional case. However, for
our purposes this will suffice.

######  Lemma B.1.

For $j=1,2,3,\ldots,N_{g}$

$\displaystyle\big{\|}\mathrm{e}^{-\mathrm{i}t_{j}H_{\textup{S}\textup{C}}}\ket{0}_{\textup{S}}\ket{0}_{\textup{C}}-\ket{t_{j}}_{\textup{S}}\ket{t_{j}}_{\textup{C}}\big{\|}_{2}\leq$
$\displaystyle\sum_{k=1}^{j}\big{\|}\ket{t_{k}}_{\textup{S}}\ket{t_{k}}_{\textup{C}}-\mathrm{e}^{-\mathrm{i}t_{1}H_{\textup{S}\textup{C}}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}\big{\|}_{2}$
(B.2) $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{j}\bigg{(}\big{\|}\ket{t_{k}}_{\textup{S}}\ket{t_{k}}_{\textup{C}}-\mathrm{e}^{-\mathrm{i}t_{1}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}\big{\|}_{2}$
(B.3)
$\displaystyle+t_{1}\max_{x\in[0,t_{1}]}\big{\|}\bar{H}_{\textup{S}\textup{C}}^{(k)}\mathrm{e}^{-\mathrm{i}xH_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}\big{\|}_{2}\bigg{)},$
(B.4)

where

$\displaystyle
H_{\textup{S}\textup{C}}^{(k)}:=H_{\textup{C}}+I_{\textup{S}}^{(k)}\otimes
I_{\textup{C}}^{(k)},\qquad\bar{H}_{\textup{S}\textup{C}}^{(k)}:=H_{\textup{S}\textup{C}}-H_{\textup{S}\textup{C}}^{(k)}=\sum_{\begin{subarray}{c}l=1\\\
l\neq k\end{subarray}}^{N_{g}}I_{\textup{S}}^{(l)}\otimes
I_{\textup{C}}^{(l)}.$ (B.5)

The Lemma is useful because it permits us to compute the error by only
computing unitary evolution w.r.t. $H_{\textup{S}\textup{C}}^{(k)}$ rather
than $H_{\textup{S}\textup{C}}$. 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
$\ket{\Phi_{m}}=\ket{t_{m}}_{\textup{S}}\ket{t_{m}}_{\textup{C}}$ and
$\Delta_{m}=\mathrm{e}^{-\mathrm{i}t_{1}H_{\textup{S}\textup{C}}}$ and note
$t_{j}=jt_{1}$. We can now add and subtract an appropriately-chosen term and
apply the triangle inequality to achieve

$\displaystyle\big{\|}\mathrm{e}^{-\mathrm{i}t_{j}H_{\textup{S}\textup{C}}}\ket{0}_{\textup{S}}\ket{0}_{\textup{C}}-\ket{t_{j}}_{\textup{S}}\ket{t_{j}}_{\textup{C}}\big{\|}_{2}$
(B.6)
$\displaystyle\leq\sum_{k=1}^{j}\big{\|}\ket{t_{k}}_{\textup{S}}\ket{t_{k}}_{\textup{C}}-\mathrm{e}^{-\mathrm{i}t_{1}H_{\textup{S}\textup{C}}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}\big{\|}_{2}$
(B.7)
$\displaystyle\leq\sum_{k=1}^{j}\Big{(}\big{\|}\ket{t_{k}}_{\textup{S}}\ket{t_{k}}_{\textup{C}}-\mathrm{e}^{-\mathrm{i}t_{1}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}\big{\|}_{2}$
(B.8)
$\displaystyle\;\;\;\,+\big{\|}\mathrm{e}^{-\mathrm{i}t_{1}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}-\mathrm{e}^{-\mathrm{i}t_{1}H_{\textup{S}\textup{C}}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}\big{\|}_{2}\Big{)}.$
(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
$\ket{\Phi_{m}}=\mathrm{e}^{-\mathrm{i}\delta_{n}H_{\textup{S}\textup{C}}^{(k)}}\ket{\Phi_{m-1}}=\mathrm{e}^{-\mathrm{i}\delta_{n}(m-1)H_{\textup{S}\textup{C}}^{(k)}}\ket{\Phi_{0}}$,
$\Delta_{m}=\mathrm{e}^{-\mathrm{i}\delta_{n}H_{\textup{S}\textup{C}}}$, with
$\delta_{n}=t_{1}/n$. Thus applying Lemma B.4 , we have for all
$n\in{\mathbbm{N}_{>0}}$

$\displaystyle\big{\|}\mathrm{e}^{-\mathrm{i}t_{1}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}-\mathrm{e}^{-\mathrm{i}t_{1}H_{\textup{S}\textup{C}}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}\big{\|}_{2}$
(B.10)
$\displaystyle\leq\sum_{m=1}^{n}\big{\|}\mathrm{e}^{-\mathrm{i}m\delta_{n}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}-\mathrm{e}^{-\mathrm{i}\delta_{n}H_{\textup{S}\textup{C}}}\mathrm{e}^{-\mathrm{i}(m-1)\delta_{n}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}\big{\|}_{2}$
(B.11)
$\displaystyle=\sum_{m=1}^{n}\big{\|}\Big{(}\mathrm{e}^{-\mathrm{i}\delta_{n}H_{\textup{S}\textup{C}}^{(k)}}-\mathrm{e}^{-\mathrm{i}\delta_{n}H_{\textup{S}\textup{C}}}\Big{)}\mathrm{e}^{-\mathrm{i}(m-1)\delta_{n}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{j-1}}_{\textup{C}}\big{\|}_{2}$
(B.12)
$\displaystyle\leq\sum_{m=1}^{n}\max_{x_{n}\in[0,t_{1}]}\big{\|}\Big{(}\mathrm{e}^{-\mathrm{i}\delta_{n}H_{\textup{S}\textup{C}}^{(k)}}-\mathrm{e}^{-\mathrm{i}\delta_{n}H_{\textup{S}\textup{C}}}\Big{)}\mathrm{e}^{-\mathrm{i}x_{n}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{j-1}}_{\textup{C}}\big{\|}_{2}$
(B.13)
$\displaystyle=n\max_{x_{n}\in[0,t_{1}]}\sqrt{{}_{\textup{S}}\\!\bra{t_{k-1}}\\!{}_{\textup{C}}\\!\bra{t_{k-1}}\mathrm{e}^{\mathrm{i}x_{n}H_{\textup{S}\textup{C}}^{(k)}}A^{\dagger}(\delta_{n})A(\delta_{n})\mathrm{e}^{-\mathrm{i}x_{n}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}},$
(B.14)

where
$A(y):=\Big{(}\mathrm{e}^{-\mathrm{i}yH_{\textup{S}\textup{C}}^{(k)}}-\mathrm{e}^{-\mathrm{i}yH_{\textup{S}\textup{C}}}\Big{)}$.
Applying Taylor’s remainder theorem to the real function
$f:{\mathbbm{R}}\to{\mathbbm{R}}$

$\displaystyle
f(y):={}_{\textup{S}}\\!\bra{t_{k-1}}\\!{}_{\textup{C}}\\!\bra{t_{k-1}}\mathrm{e}^{\mathrm{i}x_{n}H_{\textup{S}\textup{C}}^{(k)}}A^{\dagger}(y)A(y)\mathrm{e}^{-\mathrm{i}x_{n}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}$
(B.15)

about the point $y=0$, we find

$\displaystyle
f(y)=\,{}_{\textup{S}}\\!\bra{t_{k-1}}\\!{}_{\textup{C}}\\!\bra{t_{k-1}}\big{[}\dot{A}^{\dagger}(y)\dot{A}(y)\big{]}_{y=0}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}\,y^{2}+R(y)\,y^{3},$
(B.16)

where dots represent derivatives w.r.t. $y$ and $R:\Re\to\Re$ 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

$\displaystyle\big{\|}\mathrm{e}^{-\mathrm{i}t_{1}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}-\mathrm{e}^{-\mathrm{i}t_{1}H_{\textup{S}\textup{C}}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}\big{\|}_{2}$
(B.17)
$\displaystyle\leq\max_{x_{n}\in[0,t_{1}]}\sqrt{{}_{\textup{S}}\\!\bra{t_{k-1}}\\!{}_{\textup{C}}\\!\bra{t_{k-1}}\mathrm{e}^{\mathrm{i}x_{n}H_{\textup{S}\textup{C}}^{(k)}}\Big{(}\bar{H}_{\textup{S}\textup{C}}^{(k)}\Big{)}^{2}\mathrm{e}^{-\mathrm{i}x_{n}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}t_{1}^{2}+R(t_{1}/n)t_{1}^{3}/n},$
(B.18)

for all $n\in{\mathbbm{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

$\displaystyle\big{\|}\mathrm{e}^{-\mathrm{i}t_{1}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}-\mathrm{e}^{-\mathrm{i}t_{1}H_{\textup{S}\textup{C}}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}\big{\|}_{2}$
(B.19)
$\displaystyle\leq\lim_{n\to\infty}\max_{x_{n}\in[0,t_{1}]}\sqrt{{}_{\textup{S}}\\!\bra{t_{k-1}}\\!{}_{\textup{C}}\\!\bra{t_{k-1}}\mathrm{e}^{\mathrm{i}x_{n}H_{\textup{S}\textup{C}}^{(k)}}\Big{(}\bar{H}_{\textup{S}\textup{C}}^{(k)}\Big{)}^{2}\mathrm{e}^{-\mathrm{i}x_{n}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}t_{1}^{2}+R(t_{1}/n)t_{1}^{3}/n},$
(B.20)
$\displaystyle\leq\sqrt{\left(\lim_{n\to\infty}\max_{x_{n}\in[0,t_{1}]}{}_{\textup{S}}\\!\bra{t_{k-1}}\\!{}_{\textup{C}}\\!\bra{t_{k-1}}\mathrm{e}^{\mathrm{i}x_{n}H_{\textup{S}\textup{C}}^{(k)}}\Big{(}\bar{H}_{\textup{S}\textup{C}}^{(k)}\Big{)}^{2}\mathrm{e}^{-\mathrm{i}x_{n}H_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}t_{1}^{2}\right)+}$
(B.21)
$\displaystyle\qquad\overline{+\left(\lim_{n\to\infty}\max_{x_{n}\in[0,t_{1}]}R(t_{1}/n)\frac{t_{1}^{3}}{n}\right)},$
(B.22)
$\displaystyle=\max_{x\in[0,t_{1}]}t_{1}\sqrt{{}_{\textup{S}}\\!\bra{t_{k-1}}\\!{}_{\textup{C}}\\!\bra{t_{k-1}}\mathrm{e}^{\mathrm{i}xH_{\textup{S}\textup{C}}^{(k)}}\Big{(}\bar{H}_{\textup{S}\textup{C}}^{(k)}\Big{)}^{2}\mathrm{e}^{-\mathrm{i}xH_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{t_{k-1}}_{\textup{C}}}.$
(B.23)

Thus identifying the last line with the corresponding 2-norm, we conclude the
proof. ∎

###  B.2 Some additional definitions required for the lemmas of section 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_{\textup{C}}$, is chosen identically to that of
[26], namely:

$\displaystyle{H}_{\textup{C}}=\sum_{n=0}^{d-1}n\omega_{0}\ket{E_{n}}\\!\\!\bra{E_{n}},$
(B.24)

where $\\{\ket{E_{n}}\\}_{n=0}^{d-1}$ forms an orthonormal basis for the
Hilbert space of the control, $\mathcal{H}_{\textup{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
$\mathrm{e}^{-\mathrm{i}\hat{H}_{\textup{C}}T_{0}}={\mathbbm{1}}_{\textup{C}}$.

The states $\\{\ket{\theta_{k}}\\}$ are the discrete Fourier Transform basis
of the energy basis: For $k\in{\mathbbm{Z}}$

$\displaystyle\ket{\theta_{k}}=\frac{1}{\sqrt{d}}\sum_{n=0}^{d-1}\mathrm{e}^{-\mathrm{i}2\pi
nk/d}\ket{E_{n}}.$ (B.25)

Note that any subset of $d$ consecutive terms forms an orthonormal basis for
$\mathcal{H}_{\textup{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,\ldots,N_{g}$

$\displaystyle
I_{\textup{C}}^{(l)}:=\frac{d}{T_{0}}\sum_{k\in\mathcal{S}_{d}(k_{0})}I_{\textup{C},d}^{(l)}(k)\ket{\theta_{k}}\\!\\!\bra{\theta_{k}},\qquad
I_{\textup{C},d}^{(l)}(x):=\frac{2\pi}{d}\bar{V}_{0}\left(\frac{2\pi}{d}x\right)\Bigg{|}_{x_{0}=x_{0}^{(l)}},$
(B.26)

with $\mathcal{S}_{d}(k_{0}):=\\{k\,|\,k\in{\mathbbm{Z}}\text{ and }-d/2\leq
k_{0}-k<d/2\\}$ and where $x_{0}^{(l)}:=2\pi(l-1/2)/N_{g}$. The function
$\bar{V}_{0}:{\mathbbm{R}}\to{\mathbbm{R}}$ is defined in [27]. It has
$x_{0}\in{\mathbbm{R}}$ as a parameter in its definition, which
is111111Technically, $\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.

$\displaystyle\bar{V}_{0}(x)=nA_{0}\sum_{p=-\infty}^{+\infty}V_{B}(n(x-x_{0}+2\pi
p)),$ (B.27)

where $n>0$, $x_{0}\in{\mathbbm{R}}$ and $A_{0}$ is a normalization constant
such that

$\displaystyle\int_{0}^{2\pi}\bar{V}_{0}(x)dx=1,$ (B.28)

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

$\displaystyle A_{0}=\frac{1}{\int_{-\infty}^{\infty}\textup{d}xV_{B}(x)},$
(B.29)

where

$\displaystyle
V_{B}(\cdot)=\textup{sinc}^{2N}(\cdot)=(\sin(\pi\,\cdot)/(\pi\,\cdot))^{2N},\qquad
N\in{\mathbbm{N}_{>0}}.$ (B.30)

Notice that $\bar{V}_{0}(\cdot)$ is $2\pi$ periodic and as such, the summation
in $I_{\textup{C}}^{(l)}$ is independent of $k_{0}\in{\mathbbm{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

$\displaystyle\int_{a}^{b}\mathrm{d}x\bar{V}_{0}(x)=nA_{0}\sum_{p=-\infty}^{+\infty}\int_{a}^{b}\mathrm{d}x\,V_{B}(n(x-x_{0}+2\pi
p)),\qquad\forall a,b,x_{0}\in{\mathbbm{R}},n>0.$ (B.31)

We will use this property extensively in proofs in this manuscript.

Let

$\displaystyle\ket{t_{j}}_{\textup{S}}:=\mathrm{e}^{\mathrm{i}I_{\textup{S}}^{(j)}}\ket{t_{j-1}}_{\textup{S}},\quad
j=1,2,\ldots,N_{g},$ (B.32)

where we assume w.l.o.g. that the spectrum of $I_{\textup{S}}^{(j)}$ lies in
the interval $(0,2\pi]$. Its eigenvalues are arbitrary so that states
$\ket{t_{j}}_{\textup{S}}$ and $\ket{t_{j-1}}_{\textup{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,
$\ket{0}_{\textup{S}}$ is any pure state in $\mathcal{H}_{\textup{S}}$.

Since the memory is fixed in this section, the definition of
$\tilde{d}(\mathbb{m}_{l})$ corresponds to the number of non-identical
eigenvalues of $I_{\textup{S}}^{(l)}$ and

$\displaystyle t_{j}:=jT_{0}/N_{g},$ (B.33)

for $j=1,2,3,\ldots,N_{g}$.

As for the states of the control, we use so-called quasi-ideal clock states
coming from [26]. In particular, we define
$\ket{t_{j}}_{\textup{C}}:=\ket{\Psi(t_{j}d/T_{0})}_{\textup{C}}$ for
$j=0,1,2,\ldots,N_{g}$, where for $t\in{\mathbbm{R}}$ , $T_{0}>0$,
$d\in{\mathbbm{N}_{>0}}$,

$\displaystyle\ket{\Psi(td/T_{0})}_{\textup{C}}:=\sum_{k\in\mathcal{S}_{d}(td/T_{0})}\psi_{\textup{nor}}\big{(}td/T_{0},k\big{)}\ket{\theta_{k}},$
(B.34)

where

$\displaystyle\psi_{\textup{nor}}\big{(}k_{0};k\big{)}:=A_{\textup{nor}}\,\mathrm{e}^{-\frac{\pi}{\sigma^{2}}(k-k_{0})^{2}}\mathrm{e}^{\mathrm{i}2\pi
n_{0}(k-k_{0})/d}.$ (B.35)

with $\sigma>0$, $n_{0}\in(0,d-1)$. The amplitude $A_{\textup{nor}}$ is
defined such that $\ket{\Psi(td/T_{0})}_{\textup{C}}$ is normalised. Its
large-$d$ scaling is

$\displaystyle|A_{\textup{nor}}|^{2}=\left(\frac{2}{\sigma^{2}}\right)+\epsilon(d),$
(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).

###  B.3 Final technical lemmas

######  Lemma B.2.

For all $k\in 1,2,3,\ldots,N_{g}$, the last terms in lemma B.1 are upper
bounded by

$\displaystyle
t_{1}\max_{x\in[0,t_{1}]}\big{\|}\bar{H}_{\textup{S}\textup{C}}^{(k)}\mathrm{e}^{-\mathrm{i}xH_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{\Psi(t_{k-1}d/T_{0})}_{\textup{C}}\big{\|}_{2}\leq$
(B.37)
$\displaystyle\frac{\tilde{d}(\mathbb{m}_{k})4\pi^{2}nA_{0}}{T_{0}}\Biggl{(}3A_{\textup{nor}}d\,N_{g}\bigg{(}\mathrm{e}^{-{\pi}{\frac{d^{2}}{\sigma^{2}(4N_{g})^{2}}}}+\Big{(}\frac{2N_{g}}{\pi^{2}n}\Big{)}^{2N}\,\bigg{)}$
(B.38)
$\displaystyle\quad+A_{\textup{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)\varepsilon_{v}(t_{1},d)\Biggr{)},$
(B.39)

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

$\displaystyle\begin{split}\varepsilon_{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)\mathrm{e}^{-\frac{\pi}{4}\frac{d^{2}}{\sigma^{2}}}+\mathcal{O}\left(\mathrm{e}^{-\frac{\pi}{2}\sigma^{2}}\right)\text{
as }d\to\infty,\quad(0,d)\ni\sigma\to\infty\end{split}$ (B.40)

where $C_{0}>0$, $\alpha_{0}>0$ , $\epsilon_{5}>0$ are fixed constants and

$\displaystyle
A_{\textup{nor}}\leq\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)}},$
(B.41)

with

$\displaystyle\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^{-\frac{2\pi d}{\sigma^{2}}}}.$ (B.42)

###### Proof.

For all $x\in[0,t_{1}]$

$\displaystyle\big{\|}\bar{H}_{\textup{S}\textup{C}}^{(k)}\mathrm{e}^{-\mathrm{i}xH_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{\Psi(t_{k-1}d/T_{0})}_{\textup{C}}\big{\|}_{2}$
(B.43) $\displaystyle\leq\sum_{\begin{subarray}{c}l=1\\\ l\neq
k\end{subarray}}^{N_{g}}\big{\|}I_{\textup{S}}^{(l)}\otimes
I_{\textup{C}}^{(l)}\mathrm{e}^{-\mathrm{i}xH_{\textup{S}\textup{C}}^{(k)}}\ket{t_{k-1}}_{\textup{S}}\ket{\Psi(t_{k-1}d/T_{0})}_{\textup{C}}\big{\|}_{2}$
(B.44)
$\displaystyle\leq\sum_{j=1}^{\tilde{d}(\mathbb{m}_{k})}\sum_{\begin{subarray}{c}l=1\\\
l\neq
k\end{subarray}}^{N_{g}}\big{|}A_{j}^{(k-1)}\big{|}\big{\|}I_{\textup{S}}^{(l)}\otimes
I_{\textup{C}}^{(l)}\ket{\theta_{j}^{(k-1)}}_{\textup{S}}\mathrm{e}^{-\mathrm{i}xH_{\textup{C}}^{(k)}\big{(}\theta_{j}^{(k)}\big{)}}\ket{\Psi(t_{k-1}d/T_{0})}_{\textup{C}}\big{\|}_{2}$
(B.45)
$\displaystyle=\sum_{j=1}^{\tilde{d}(\mathbb{m}_{k})}\sum_{\begin{subarray}{c}l=1\\\
l\neq
k\end{subarray}}^{N_{g}}\big{|}A_{j}^{(k-1)}\big{|}\big{\|}I_{\textup{S}}^{(l)}\ket{\theta_{j}^{(k-1)}}_{\textup{S}}\big{\|}_{2}\big{\|}I_{\textup{C}}^{(l)}\mathrm{e}^{-\mathrm{i}xH_{\textup{C}}^{(k)}\big{(}\theta_{j}^{(k)}\big{)}}\ket{\Psi(t_{k-1}d/T_{0})}_{\textup{C}}\big{\|}_{2}$
(B.46) $\displaystyle\leq\sum_{\begin{subarray}{c}l=1\\\ l\neq
k\end{subarray}}^{N_{g}}\sum_{j=1}^{\tilde{d}(\mathbb{m}_{k})}\big{|}A_{j}^{(k-1)}\big{|}\big{\|}I_{\textup{S}}^{(l)}\big{\|}_{2}\max_{\vartheta\in[-\pi,\pi]}\big{\|}I_{\textup{C}}^{(l)}\mathrm{e}^{-\mathrm{i}xH_{\textup{C}}^{(k)}(\vartheta)}\ket{\Psi(t_{k-1}d/T_{0})}_{\textup{C}}\big{\|}_{2}$
(B.47) $\displaystyle\leq
2\pi\tilde{d}(\mathbb{m}_{k})\sum_{\begin{subarray}{c}l=1\\\ l\neq