# The effect of data encoding on the expressive power of variational quantum
machine learning models

Maria Schuld  Xanadu, Toronto, ON, M5G 2C8, Canada  Ryan Sweke  Dahlem Center
for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany
Johannes Jakob Meyer  Dahlem Center for Complex Quantum Systems, Freie
Universität Berlin, 14195 Berlin, Germany

###### Abstract

Quantum computers can be used for supervised learning by treating parametrised
quantum circuits as models that map data inputs to predictions. While a lot of
work has been done to investigate practical implications of this approach,
many important theoretical properties of these models remain unknown. Here we
investigate how the strategy with which data is encoded into the model
influences the expressive power of parametrised quantum circuits as function
approximators. We show that one can naturally write a quantum model as a
partial Fourier series in the data, where the accessible frequencies are
determined by the nature of the data encoding gates in the circuit. By
repeating simple data encoding gates multiple times, quantum models can access
increasingly rich frequency spectra. We show that there exist quantum models
which can realise all possible sets of Fourier coefficients, and therefore, if
the accessible frequency spectrum is asymptotically rich enough, such models
are universal function approximators.

A popular approach to quantum machine learning uses trainable quantum circuits
as machine learning models similar to neural networks. Quantum gates – the
building blocks of quantum circuits – are used to encode data inputs
$\bm{x}=(x_{1},\dots,x_{N})$ as well as trainable weights
$\bm{\theta}=(\theta_{1},\dots,\theta_{M})$. The circuit is measured multiple
times to estimate the expectation of some observable, and the result is
interpreted as a prediction. The overall computation implements a “quantum
model function” $f_{\bm{\theta}}(\bm{x})$, a machine learning model that is
based on quantum computing. This approach is known by different names such as
variational circuits McClean  _et al._ (2016); Romero and Aspuru-Guzik (2019),
quantum circuit learning Mitarai  _et al._ (2018), quantum neural networks
Farhi and Neven (2018); McClean  _et al._ (2018), or parametrised quantum
circuits Benedetti  _et al._ (2019).

A lot of work has been done to understand the practical details of this
approach, leading to useful training strategies Mitarai  _et al._ (2018);
Ostaszewski  _et al._ (2019); Stokes  _et al._ (2020) and ways to emulate and
extend classical machine learning methods Verdon  _et al._ (2019a, b); Romero
and Aspuru-Guzik (2019); Cong  _et al._ (2019); Liu and Wang (2018). A growing
body of literature, motivated by the dilemma of investigating the performance
of quantum machine learning when only small-scale experiments are physically
possible, tries to understand the potential power of variational circuits from
a theoretical perspective Harrow and Napp (2019); McClean  _et al._ (2018);
Ciliberto  _et al._ (2020); Cerezo  _et al._ (2020). Still, only little is
known about the actual function classes that quantum circuits give rise to.
Can quantum models express any function in the input $\bm{x}$, or are they
limited to a specific class of functions? Can this class of “learnable
functions” be characterised in a meaningful way, and can the characterisation
be used to guide design choices and potential applications for these quantum
models?

Figure 1: Illustration of the main result of this paper, shown for one-
dimensional inputs $x\in\mathbb{R}$: quantum models consisting of layers of
trainable circuit blocks $W=W(\bm{\theta})$ and data encoding circuit blocks
$S(x)$ can be written as a weighed sum $\sum_{\omega}c_{\omega}e^{i\omega x}$.
The data encoding circuit determines the frequencies $\omega$, and the
remainder of the circuit architecture determines the coefficients
$c_{\omega}$. If the $\omega$ are integer-valued (or integer-valued multiples
of a base frequency $\omega_{0}$), the sum becomes a partial Fourier series,
which allows us to systematically study properties of the function class a
given quantum model can learn.

In this paper we investigate these questions in a framework focused on the
role of data encoding. We consider standard models from the literature that
consist of multiple “circuit layers”, each made up of a data encoding
(circuit) block and a trainable (circuit) block, and assume that input
features $x\in\mathbb{R}$ are encoded by gates of the form $e^{ixH}$, where
$H$ is an arbitrary Hamiltonian. Our main tool is the natural representation
of such quantum models as a Fourier-type sum

$f_{\bm{\theta}}(\bm{x})=\sum_{\bm{\omega}\in\Omega}c_{\bm{\omega}}(\bm{\theta})e^{i\bm{\omega}\bm{x}},$
(1)

where $\bm{\omega}\bm{x}$ is the inner product. We show that the _frequency
spectrum_ $\Omega\subset\mathbb{R}^{N}$ is solely determined by the
eigenvalues of the data-encoding Hamiltonians while the design of the entire
circuit controls the coefficients $c_{\bm{\omega}}$ that a quantum model can
realise (see Fig.1). The representation of quantum models as Fourier-type sums
characterises the function families that a given class of quantum models can
learn via two interrelated properties. The first property is the frequency
spectrum $\Omega$, which determines the functions $e^{i\bm{\omega}\bm{x}}$
that the quantum model “has access to”. The second property is the
expressivity of the coefficients $\\{c_{\bm{\omega}}\\}$ that a class of
quantum models can control, which determines how the accessible functions can
be combined. In many natural settings, the frequencies are integers,
$\Omega\subset\mathbb{Z}^{N}$, and the sum becomes a multi-dimensional partial
Fourier series

$f_{\bm{\theta}}(\bm{x})=\sum_{\bm{n}\in\Omega}c_{\bm{n}}(\bm{\theta})e^{i\bm{n}\bm{x}},$
(2)

where the $e^{i\bm{n}\bm{x}}$ are orthogonal basis functions. We use the
nomenclature partial Fourier series to indicate the fact that only a subset of
the Fourier coefficients are non-zero. The Fourier series formalism allows us
to study quantum models using the rich techniques developed in Fourier
analysis.

First, we consider the popular strategy of encoding an input into single-qubit
rotations, and show that repeating the encoding $r$ times either sequentially
or in parallel allows the model to access frequency spectra $\Omega$
consisting of $r$ frequencies. This places into a broader context an
observation made in Ref. Ostaszewski  _et al._ (2019), which states that
encoding a data feature only once into the angle of a single qubit rotation
restricts the function class that quantum models can learn to a simple sine
function (or equivalently, a Fourier series with a single frequency). Second,
we provide bounds for the maximum number of frequencies and Fourier
coefficients a quantum model can control for more general data encoding
strategies. Finally, we study the universality of quantum models. We show that
for sufficiently flexible trainable circuit blocks there exists a quantum
model which can realise any possible set of Fourier coefficients. If,
asymptotically, the accessible frequency spectrum is rich enough, then such
models are universal function approximators. This follows from the fact that
Fourier series with arbitrary coefficients can approximate any square
integrable function on a given interval Carleson (1966).

A few existing studies are related to our work. For example, Pérez-Salinas et
al. Pérez-Salinas  _et al._ (2020) considered quantum models with sequentially
repeated data encodings and conjectured that they are universal function
approximators under a special kind of classical data pre-processing. Killoran
et al. Killoran  _et al._ (2019) have shown that many neural networks can be
naturally emulated on a photonic quantum computer, and point out that such
quantum models therefore inherit universality. The majority of quantum machine
learning papers concerned with questions of expressivity and universality Sim
_et al._ (2019); Chen  _et al._ (2018); Du  _et al._ (2018); Biamonte (2019),
however, interpret these concepts from a quantum information perspective,
which asks whether a circuit can express any quantum computation, not any
function in the inputs. However, in the context of (supervised) machine
learning, quantum universality does not necessarily imply universal function
approximation; a quantum circuit able to realise arbitrary unitary evolutions
may only be able to express a limited class of functions $f(\bm{x})$.111As an
extreme example, consider a parametrised quantum circuit that encodes the data
into gates acting on qubits which are never entangled with the measured qubits
– in which case $f(\bm{x})$ is a constant function, and the resulting machine
learning model trivial. From the function expressivity view-point, Ref. Caro
and Datta (2020) has investigated the pseudo-dimension of a particular class
of quantum models, an expressivity metric which allows one to characterize
learnability and generalization power of the associated model. Also the
essential role of data encoding for quantum machine learning has been
emphasised in previous papers. For example, it was remarked that data encoding
determines the features that quantum models represent Schuld and Killoran
(2019); Havlíček  _et al._ (2019), the decision boundaries they can learn
LaRose and Coyle (2020), as well as the measurements that optimally
distinguish between data classes Lloyd  _et al._ (2020). A central
contribution of this paper is to systematically combine the study of data
encoding with that of the expressivity of quantum models.

We present our results as follows: Section I introduces the basic idea of
writing quantum models as partial Fourier series. Section II puts the tool to
use and analyses the expressivity of quantum models, which leads to a proof
that quantum models are universal in Section III. Section IV discusses
practically relevant implications.

Note: After publishing the preprint of this article, we were made aware that
the connection between Fourier series and quantum machine learning models with
repeated data-encoding has already been established in Ref. Gil Vidal and
Theis (2020). While there is significant overlap between this work and ours,
we provide a novel universality result, as well as a systematic development of
this connection through practically relevant examples.

##  I Quantum models as partial Fourier series

First, we introduce our basic tool: the natural representation of a quantum
model as a partial Fourier series. For simplicity, the majority of our
presentation will focus on the case of univariate functions with inputs
$x\in\mathbb{R}$, but we generalise this to multivariate functions in Appendix
A, which is used for the analysis of universality in Section III.

We define a (univariate) quantum model $f_{\bm{\theta}}(x)$ as the expectation
value of some observable with respect to a state prepared via a parametrised
quantum circuit, i.e.

$f_{\bm{\theta}}(x)=\left\langle
0\right|U^{\dagger}(x,\bm{\theta})MU(x,\bm{\theta})\left|0\right\rangle,$ (3)

where $|0\rangle$ is some initial state of the quantum computer,
$U(x,\bm{\theta})$ is a quantum circuit that depends on the input $x$ and a
(possibly empty) set of parameters $\bm{\theta}$, and $M$ is some observable.
The prediction of the quantum model at a specific point $x$ is estimated in
practice by running the circuit multiple times and averaging over the
measurement results.222Note that the quantum model is a theoretical
construction, since physical measurements will always result in an estimate of
the output expectation, making $f$ a random variable – a complication that we
will ignore here. The quantum circuit itself is constructed from $L$ layers,
each consisting of a data encoding circuit block $S(x)$ and a trainable
circuit block $W(\bm{\theta})$ controlled by the parameters $\bm{\theta}$ (see
Fig. 1). The data encoding block is the same in every layer and consists of
gates of the form $\mathcal{G}(x)=e^{-ixH}$, where $H$ is a Hamiltonian that
generates the “time evolution” used to encode the data. Since we want to focus
on the role of the data encoding, and to avoid further assumptions on how the
trainable circuit blocks are parametrised, we view the trainable circuit
blocks as arbitrary unitary operations, $W(\bm{\theta})=W$, and drop the
subscript of $f_{\bm{\theta}}$ from here on.333Of course, in realistic near-
term settings these unitaries are implemented as short gate sequences and are
by no means universal, and there are many interesting questions around how a
specific parametrisation influences the properties of the resulting quantum
model. With this assumption, the overall quantum circuit has the form

$U(x)=W^{(L+1)}S(x)W^{(L)}\dots W^{(2)}S(x)W^{(1)}.$ (4)

Note that the encoding strategy is very natural, since the physical control
parameters of quantum dynamics usually enter as time evolutions of
Hamiltonians – the most prominent example being Pauli rotations. This model
includes “parallel encodings” that repeat the encoding on different subsystems
Rebentrost  _et al._ (2014), as well as “data reuploading”, where the encoding
is repeated multiple times in sequence Pérez-Salinas  _et al._ (2020) (see
Fig. 2). With a small amount of classical pre-processing this model includes
even many quantum machine learning algorithms that are not based on the
principles of parametrised circuits (see also Section IV.1).

Figure 2: The general quantum model considered in this paper includes qubit-
based circuits where the encoding subroutine consists of a single-qubit gate
$\mathcal{G}(x)$, which is often used in practice. The picture illustrates two
special cases investigated in Section II: (a) shows a circuit where the scalar
input feature $x$ is encoded by one single-qubit gate, which can be repeated
$r=L>1$ times but always acts on the same qubit, and (b) repeats the encoding
gate $r$ times in “parallel” using only one layer. Note that the trainable
blocks $W$ (purple rectangles) represent arbitrary unitaries, which in
practice would be implemented as a sequence of local gates (inset).

Our goal is to write $f$ as a partial Fourier series

$f(x)=\sum_{n\in\Omega}c_{n}e^{inx},$ (5)

with integer-valued frequencies (if $\Omega=\\{-K,\ldots,K\\}$, then we call
(5) a truncated Fourier series). The first step is to note that one can always
find an eigenvalue decomposition of the generator Hamiltonian
$H=V^{\dagger}\Sigma V$ where $\Sigma$ is a diagonal operator containing $H$’s
eigenvalues $\lambda_{1},...,\lambda_{d}$ on its diagonal. The data encoding
unitary becomes $S(x)=V^{\dagger}e^{-ix\Sigma}V$, and we can “absorb” $V$,
$V^{\dagger}$ into the arbitrary unitaries $W^{\prime}=VWV^{\dagger}$. Hence,
without loss of generality we will assume that $H$ is diagonal. This allows us
to separate the data-dependent expressions from the remainder of the circuit
in each component $i$ of the quantum state $U(x)\left|0\right\rangle$,

$\left[U(x)\left|0\right\rangle\right]_{i}=\sum_{j_{1}\dots
j_{L}=1}^{d}e^{-i(\lambda_{j_{1}}+\dots+\lambda_{j_{L}})x}\\\ \times
W_{ij_{L}}^{(L+1)}\dots W_{j_{2}j_{1}}^{(2)}W_{j_{1}1}^{(1)}.$ (6)

For ease of notation we introduce the multi-index
$\bm{j}=\\{j_{1},\dots,j_{L}\\}\in[d]^{L}$, where $[d]^{L}$ denotes the set of
any $L$ integers between $1,\dots,d$. We can then denote the sum of
eigenvalues for a given $\bm{j}$ by
$\Lambda_{\bm{j}}=\lambda_{j_{1}}+\dots+\lambda_{j_{L}}$, and write

$\left[U(x)\left|0\right\rangle\right]_{i}=\sum_{\bm{j}\in[d]^{L}}e^{-i\Lambda_{\bm{j}}x}W_{ij_{L}}^{(L+1)}\dots
W_{j_{2}j_{1}}^{(2)}W_{j_{1}1}^{(1)}.$ (7)

To consider the full quantum model from Eq. (3) we need to take into account
the complex conjugation of this expression as well as the measurement, and get

$f(x)=\sum_{\bm{k},\bm{j}\in[d]^{L}}e^{i(\Lambda_{\bm{k}}-\Lambda_{\bm{j}})x}a_{\bm{k},\bm{j}},$
(8)

where the $a_{\bm{k},\bm{j}}$ contain the terms stemming from the arbitrary
unitaries and measurement,

$a_{\bm{k},\bm{j}}=\sum_{i,i^{\prime}}(W^{*})_{1k_{1}}^{(1)}(W^{*})_{j_{1}j_{2}}^{(2)}\dots(W^{*})_{j_{L}i}^{(L+1)}M_{i,i^{\prime}}\\\
\times W_{i^{\prime}j_{L}}^{(L+1)}\dots W_{j_{2}j_{1}}^{(2)}W_{j_{1}1}^{(1)}.$
(9)

The second step consists of grouping all terms in the sum (8) whose basis
function $e^{i(\Lambda_{\bm{k}}-\Lambda_{\bm{j}})x}$ have the same frequency
$\omega=\Lambda_{\bm{k}}-\Lambda_{\bm{j}}$. All frequencies accessible to the
quantum model are contained in its frequency spectrum

$\Omega=\\{\Lambda_{\bm{k}}-\Lambda_{\bm{j}},\;\bm{k},\bm{j}\in[d]^{L}\\}.$
(10)

This yields

$f(x)=\sum_{\omega\in\Omega}c_{\omega}e^{i\omega x}$ (11)

where the coefficients are obtained by summing over all $a_{\bm{k},\bm{j}}$
contributing to the same frequency

$\displaystyle c_{\omega}=\sum_{\begin{subarray}{c}\bm{k},\bm{j}\in[d]^{L}\\\
\Lambda_{\bm{k}}-\Lambda_{\bm{j}}=\omega\end{subarray}}a_{\bm{k},\bm{j}}.$
(12)

We note that the frequency spectrum $\Omega$ has the following important
properties: $0\in\Omega$, and for every frequency $\omega\in\Omega$, we have
also that $-\omega\in\Omega$. Additionally, since
$c_{\omega}=c^{*}_{-\omega}$, Eq. (11) realises a real-valued function. We
will therefore denote with $K=(|\Omega|-1)/2$ the _size_ of the spectrum, as
it quantifies how many independent non-zero frequencies the model has access
to. The largest available frequency $D=\max(\Omega)$ is called the _degree_ of
the spectrum. Furthermore, the coefficients $c_{\omega}$ are determined by the
arbitrary gates $W^{(1)}\dots W^{(L+1)}$ (which absorbed the $V$,
$V^{\dagger}$ from the encoding Hamiltonians), as well as by the measurement
observable. As a consequence, a quantum model’s frequency spectrum is solely
determined by the eigenvalues of the data encoding gates, while its Fourier
coefficients depend on the entire circuit, as was claimed in Fig. 1. While so
far we have not imposed restrictions on the frequencies $\omega$, one can see
that for integer-valued eigenvalues $\lambda_{1},\dots,\lambda_{d}$, the
frequencies in $\Omega$ are themselves integer-valued, and Eq. (11) yields the
real-valued partial Fourier series from Eq. (5). As we will show in the
following section, common data encoding strategies in near-term quantum
machine learning fulfill the property of an integer-valued frequency spectrum.
Even if the eigenvalues of the encoding gate generators, and therefore the
accessible frequencies $\omega\in\Omega$, are merely integer-valued multiples
of a “base frequency” $\\{n_{1}\omega_{0},n_{2}\omega_{0},\dots\\}$, the
treatment is still analogous to the integer case (see Appendix B). We
therefore focus much of our analysis on this case.

For both integer or non-integer frequencies, the expressivity of a quantum
model is determined by two different properties: the frequency spectrum of the
quantum model, including its size and degree, and the expressivity of the
coefficients controlled by the model. As we will show in the next section,
these two properties give us insights into the function classes that different
quantum models can learn.

##  II The expressivity of quantum models

We proceed to use the Fourier series formalism to investigate the expressivity
of quantum models. We start with an analysis of the popular strategy Mitarai
_et al._ (2018); Schuld  _et al._ (2020); Havlíček  _et al._ (2019);
Hubregtsen  _et al._ (2020); Koide-Majima and Majima (2020); Watabe  _et al._
(2019); Blank  _et al._ (2019); Zhao  _et al._ (2019) of using single-qubit
Pauli rotations in the encoding subroutine $S(x)$ in order to showcase the
practical value of the approach. We then characterise the limits of a quantum
model’s expressivity for a given data encoding gate in more general terms.

###  II.1 A single Pauli-rotation encoding can only learn a sine function

As a “warm-up” application of the Fourier series formalism, we start by
considering a simple quantum model with $L=1$, where we use a single-qubit
gate $\mathcal{G}(x)=e^{-ixH}$ to encode the input $x$ into the circuit (see
also Fig. 2a with $L=1$),

$U(x)=W^{(2)}\mathcal{G}(x)W^{(1)}.$ (13)

As a single-qubit gate generator, $H$ has two distinct eigenvalues
$(\lambda_{1},\lambda_{2})$. We can without loss of generality always rescale
the energy spectrum to $(-\gamma,\gamma)$ because the global phase is
unobservable. We note that the class of such encoding gates includes Pauli
rotations, with $H=(1/2)\sigma$ for
$\sigma\in\\{\sigma_{x},\sigma_{y},\sigma_{z}\\}$, for which
$\gamma=\frac{1}{2}$. We aim to show that models of the type (13) always lead
to functions of the form $f(x)=A\sin(2\gamma x+B)+C$ where $A,B,C$ are
constants determined by the non-encoding part of the variational circuit,
which reproduces the prior observation from Ostaszewski  _et al._ (2019). A
sine function can be described by a truncated Fourier series of degree $1$ –
and in the next section we will go on to show how one can systematically
increase the degree by repeating the encoding gate.

First, since we can absorb the factor $\gamma$ into the data input by re-
scaling it via $\tilde{x}=\gamma x$, we can assume without loss of generality
that the eigenvalues of $H$ are always $\lambda_{1}=-1,\lambda_{2}=1$. From
Eq. (10) we can immediately see that the spectrum of the quantum model is
given by $\Omega=\\{-2,0,2\\}$ (since the possible differences
$\lambda_{k_{1}}-\lambda_{j_{1}}$ for
$\lambda_{k_{1}},\lambda_{j_{1}}\in\\{-1,1\\}$ are $-1-(1)$, $-1-(-1)$,
$1-(1),$ and $1-(-1)$). The Fourier coefficients in Eq. (12) become

$\displaystyle c_{0}$
$\displaystyle=\sum_{i,i^{\prime}}M_{ii^{\prime}}(W^{*})^{(1)}_{12}(W^{*})^{(2)}_{2i}W^{(2)}_{i^{\prime}1}W^{(1)}_{11},$
(14) $\displaystyle c_{2}$
$\displaystyle=\sum_{i,i^{\prime}}M_{ii^{\prime}}(W^{*})^{(1)}_{11}(W^{*})^{(2)}_{1i}W^{(2)}_{i^{\prime}2}W^{(1)}_{21},$
(15) $\displaystyle c_{-2}$ $\displaystyle=c^{*}_{2},$ (16)

and the quantum model’s frequency spectrum consists of a single non-zero
frequency:

$\displaystyle f(x)$
$\displaystyle=c_{-2}e^{i2\tilde{x}}+c_{0}+c_{2}e^{-i2\tilde{x}}$
$\displaystyle=c_{0}+2|c_{2}|\cos(2\tilde{x}-\operatorname{arg}(c_{2})),$

where $\operatorname{arg}(c_{2})$ is the complex phase of $c_{2}$. For Pauli
rotations, one has $\tilde{x}=\gamma x=\frac{x}{2}$, and we recover the result
of Ostaszewski  _et al._ (2019) with
$A=2|c_{2}|,B=-\pi/2-\operatorname{arg}(c_{2}),$ and $C=c_{0}$. Importantly,
we have not assumed anything about the number of qubits, the nature of the
unitaries $W$, or the measurement $M$. This illustrates a key point of this
paper: even with the ability to implement very wide and deep quantum circuits
(which may even be classically intractable to simulate), the expressivity of
the corresponding quantum model is fundamentally limited by the data encoding
strategy.

To support this finding, Fig. 3 shows numerical evidence: encoding data via a
Pauli-X rotation results in a quantum model that can only learn to fit a
Fourier series of a single frequency – and only if that frequency is exactly
matched by how the data is scaled.

Figure 3: A parametrised quantum model is trained with data samples (white
circles) to fit a target function $g(x)=\sum_{n=-1}^{1}c_{n}e^{-nix}$ or
$g^{\prime}(x)=\sum_{n=-2}^{2}c_{n}e^{-nix}$ with coefficients $c_{0}=0.1$,
$c_{1}=c_{2}=0.15-0.15i$. The variational circuit is of the form
$f(x)=\left\langle 0\right|U^{\dagger}(x)\sigma_{z}U(x)\left|0\right\rangle$
where $\left|0\right\rangle$ is a single qubit, and
$U=W^{(2)}R_{x}(x)W^{(1)}$. The $W$ (round blue symbols) are implemented as
general rotation gates parametrised by three learnable weights each, and
$R_{x}$ (square blue symbols) is a single Pauli-X rotation. The left panels
show the quantum model function $f(x)$ and target function
$g(x),g^{\prime}(x)$, while the right panels show the mean squared error
between the data sampled from $g$ and $f$ during a typical training run.
Feeding in the input $x$ as is (top row), the quantum model easily fits the
target of degree $1$. Re-scaling the inputs $x\rightarrow 2x$ causes a
frequency mismatch, and the model cannot learn the target any more (middle
row). However, even with the correct scaling, the variational circuit cannot
fit the target function of degree $2$ (bottom row). The experiments in this
paper were all performed using the PennyLane software library Bergholm  _et
al._ (2018).

###  II.2 Repeated Pauli encodings linearly extend the frequency spectrum

Given the severe limitations exposed in the previous section, a natural
question is how we can extend the accessible frequency spectrum of a quantum
model. To this end, we demonstrate in this section that by using either
single-layer models with $L=1$ where the encoding gate is repeated $r$ times
in parallel (as per Fig. 2b), or multi-layer models with $L>1$ where the
encoding gate is effectively repeated $r=L$ times in series (as per Fig. 2a),
one can systematically increase the degree of the truncated Fourier series to
$r$. We note once again that both of these techniques have been utilised in
prior practical applications Schuld  _et al._ (2020); Mitarai  _et al._
(2018); Hubregtsen  _et al._ (2020); Koide-Majima and Majima (2020); Watabe
_et al._ (2019); Pérez-Salinas  _et al._ (2020), and as such the observations
we make here offer insight into the properties of these models.

Firstly, let us consider the case of single-qubit Pauli rotations repeated in
parallel (Fig. 2b). This is a special case of our base model in Eq. (3), with
$L=1$, and

$\displaystyle S(x)$
$\displaystyle=e^{-i\frac{x}{2}\sigma_{r}}\otimes\ldots\otimes
e^{-i\frac{x}{2}\sigma_{1}},$ (17) $\displaystyle:=e^{-ixH}$ (18)

where $\sigma_{j}\in\\{\sigma_{x},\sigma_{y},\sigma_{z}\\}$. The fact that all
rotation gates commute (as they act on different qubits) allows us to
diagonalise $H$ by diagonalising each rotation gate individually. Doing this,
we find that

$\displaystyle S(x)$
$\displaystyle=V_{r}e^{-i\frac{x}{2}\sigma_{z}}V_{r}^{\dagger}\otimes\ldots\otimes
V_{1}e^{-i\frac{x}{2}\sigma_{z}}V_{1}^{\dagger},$ (19)
$\displaystyle=V\mathrm{exp}\left(-i\frac{x}{2}\sum_{q=1}^{r}\sigma^{(q)}_{z}\right)V^{\dagger},$
(20) $\displaystyle:=Ve^{-ix\Sigma}V^{\dagger},$ (21)

where $\sigma^{(q)}_{z}$ is the (diagonal) $r$-qubit operator which acts non-
trivially, via $\sigma_{z}$, only on the $q$’th qubit. Performing the
calculation yields
$\Sigma=\rm{diag}\left(\lambda_{1},\dots,\lambda_{2^{r}}\right)$, with the
$r+1$ unique entries

$\displaystyle\lambda_{p}=\left(\frac{p}{2}-\frac{r-p}{2}\right)=p-\frac{r}{2},\;p\in\\{0,\dots,r\\},$

which are all possible sums of $r$ values $\pm 1/2$. According to Eq. (10),
the frequency spectrum for $L=1$ contains differences of any two of these
eigenvalues, and we get

$\displaystyle\Omega_{\rm par}$
$\displaystyle=\left\\{\lambda_{k_{1}}-\lambda_{j_{1}}|\;k_{1},j_{1}\in\\{1,\dots,2^{r}\right\\}\\}$
(22)
$\displaystyle=\left\\{\left(p-\frac{r}{2}\right)-\left(p^{\prime}-\frac{r}{2}\right)\right|$
$\displaystyle\phantom{AAAAAAAAAAA}\;p,p^{\prime}\in\\{0,\dots,r\\}\\}$ (23)
$\displaystyle=\left\\{p-p^{\prime}\,|\,p,p^{\prime}\in\\{0,\dots,r\\}\right\\}$
(24) $\displaystyle=\\{-r,-(r-1),\dots,0,\dots,r-1,r\\}.$ (25)

Hence, a univariate quantum model with $r$ parallel Pauli-rotation encodings
can be expressed as a truncated Fourier series of degree $r$.

Interestingly, the same scaling effect is achieved by a single-qubit Pauli
rotation encoding repeated layer-wise (Fig. 2a). Consider the quantum model in
Eqs. (3) and (4), for $L=r>1$ layers, where
$S(x)=\mathrm{exp}(-i(x/2)\sigma_{j})$ is a single-qubit Pauli rotation (i.e.
$\sigma_{j}\in\\{\sigma_{x},\sigma_{y},\sigma_{z}\\}$) which acts on the same
qubit in each layer. The circuit in Eq. (4) becomes

$U(x)=W^{(L+1)}e^{-i\frac{x}{2}\sigma_{L}}W^{(L)}\dots
W^{(2)}e^{-i\frac{x}{2}\sigma_{1}}W^{(1)}.$

Diagonalizing the Pauli rotations as before, then gives us
$\Sigma=(1/2)\sigma_{z}$ for all encoding layers. The frequency spectrum from
Eq. (10) is a sum of $2r$ terms of value $\pm 1/2$,

$\Omega_{\rm
seq}=\\{(\lambda_{k_{1}}+\dots+\lambda_{k_{r}})-(\lambda_{j_{1}}+\dots+\lambda_{j_{r}})\,|\\\
k_{1},\dots,k_{r},j_{1},\dots,j_{r}\in\\{1,2\\}\\}.$ (26)

After a short calculation, one finds that $\Omega_{\rm seq}=\Omega_{\rm par}$.
Again, a quantum model with $r$ sequential repetitions of the single-qubit
Pauli encoding can be expressed as a truncated Fourier series of degree $r$.
The growth mechanism of a quantum model’s frequency spectrum via parallel and
sequential repetitions of single-qubit Pauli encodings is numerically
illustrated in Fig. 4.

Figure 4: Fitting a truncated Fourier series of degree $5$,
$g(x)=\sum_{n=-5}^{5}c_{n}e^{2inx}$ with $c_{n}=0.05-0.05i$ for $n=1,\dots,5$
and $c_{0}=0$, using a quantum model that repeats the encoding $r=1,3,5$ times
in sequence (left) and in parallel (right). Increasing $r$ allows for closer
and closer fits until $r=5$ fits the data almost perfectly in both cases -
illustrating that parallel and sequential repetitions of Pauli encodings
extend the Fourier spectrum in the same manner. All models were trained with
at most 200 steps of an Adam optimiser with learning rate $0.3$ and batch size
$25$. For the “parallel” simulations, the $W$ are not arbitrary unitaries but
implemented by a smaller ansatz of three layers of parametrised rotations as
well as entangling CNOT gates, as per Ref. Schuld  _et al._ (2020), which is
depicted by the hollow rounded gate symbols. The quantum model still easily
fitted the target function, which suggests that the results of this paper are
of relevance for realistic quantum models.

###  II.3 Limits of expressivity

The representation of quantum models as Fourier-type sums immediately allows
us to derive upper bounds on the expressivity of such quantum models when
using $L$ repetitions of an encoding gate of dimension $d$ (which is at most
the size of the overall Hilbert space). Firstly, let us consider the maximum
spectrum size $K(L,d)$ of a quantum model, quantifying the number of
frequencies it can “support” or “has access to”. Since the frequency spectrum
is defined as
$\Omega=\\{(\lambda_{j_{1}}+\dots\lambda_{k_{L}})-(\lambda_{j_{1}}+\dots+\lambda_{k_{L}})\\}$
(where the indices $j_{1},\dots,j_{L}$, $k_{1},\dots,k_{L}$ run over all
dimensions of the encoding gate, from $1$ to $d$), the frequencies are sums of
$2L$ terms, each having $d$ potential values. As a result, they can at most
realise $d^{2L}$ distinct values – irrespective of whether the eigenvalues are
real or integer-valued. Since the size $K$ counts the pairs
$-\omega,\omega\in\Omega$ as one and excludes the “zero frequency”, we get

$K\leq\frac{d^{2L}}{2}-1.$ (27)

As an example, if data is encoded in a single-qubit encoding gate, we recover
the result from the previous sections where the model has degree
$\frac{2^{2}}{2}-1=1$. Using $L$ different encoding gates increases this to
$\frac{2^{2L}}{2}-1$. As we have seen, further assumptions on the eigenvalues
allow us to make this bound a lot tighter; for example when the $L$
repetitions use the same single-qubit encoding gate, $K=L$.

An interesting question is whether there is a single quantum gate which can
encode data into a quantum model that supports the frequency spectrum
$\Omega_{\infty}=\\{-\infty,\dots,-1,0,1,\dots,\infty\\}$ of a full Fourier
series. The answer is yes: the ubiquitous phase shifts in continuous-variable
(CV) quantum systems, which correspond to a free evolution of a harmonic
oscillator, have the number operator
$\hat{n}=\operatorname{diag}(0,1,2,\dots)$ as a generator.

Figure 5: Real and imaginary parts of the first six Fourier coefficients
sampled from $100$ randomly initialised $L=1$ quantum models. The models share
the same encoding strategy of parallel Pauli-X rotations (square symbols) but
vary in the ansatz and number of layers for the trainable unitaries $W$.
Circuit A uses an ansatz of trainable arbitrary single qubit rotations and
layer-dependent entangling structure proposed in Schuld  _et al._ (2020) and
already used in Fig. 4, while Circuit B uses trainable Pauli-X rotations with
a simple entangling structure. The plots suggest that the “expressivity” of
the trainable circuit block – here represented by increasing the number of
times $l$ an ansatz is repeated – has little influence on the distribution of
the Fourier coefficients, as opposed to the type of ansatz.

While the frequency spectrum of a quantum model can directly be derived from
the input encoding gates, the flexibility in the coefficients is a lot harder
to investigate systematically (we will do so for special cases in the
universality proofs in Section III). In principle, every block
$W^{(1)},\dots,W^{(L+1)}$, as well as the measurement observable, contribute
to every Fourier coefficient. This means that only a few degrees of freedom in
the gates may change an exponentially large (or, in the case of continuous-
variable quantum computing, infinite) amount of Fourier coefficients. However,
these Fourier coefficients are not arbitrary, but functions of the limited
degrees of freedom of the quantum circuit, and a quantum circuit of a certain
structure may only be able to realise a small subset of the entire set of all
possible Fourier coefficients $\\{c_{n}\\}$. To arbitrarily control $K+1$
complex Fourier coefficients, we need at least $M\geq 2K+1$ real degrees of
freedom – in other words, parameters
$\bm{\theta}=(\theta_{1},\dots,\theta_{M})$ – in the quantum circuit. As a
special case, we saw that repeating a Pauli encoding $L$ times supports a
spectrum of size $L$, which means that we need at least $2L$ degrees of
freedom in the quantum circuit to control the Fourier coefficients arbitrarily
– a scaling that is realistic for shallow circuits to “utilise the full power”
of the frequency spectrum.

While a systematic analysis of how a parametrised ansatz for the trainable
blocks $W$ impacts the control of a quantum model’s Fourier coefficients
exceeds the scope of this paper, our simulations suggest that even quantum
models with shallow trainable circuit blocks $W$ give rise to rich subsets of
Fourier coefficients (see Fig. 5). However, as the figure shows, an ansatz may
structurally set a certain Fourier coefficient to zero. An interesting further
observation is that the variance of the coefficients decreases with higher
orders. Mathematically, this property stems from the fact that the number of
terms in the sum of Eq. (12) tends to decrease with larger frequencies, since
there are fewer ways to construct those frequencies by the difference
$\Lambda_{\bm{j}}-\Lambda_{\bm{k}}$ of sums of encoding generator eigenvalues.
We note that the Fourier coefficients of square-integrable functions show a
similar behaviour, which contributes to the convergence of such series.

##  III Quantum models are asymptotically universal

In the previous sections we have seen, at least for univariate functions, that
certain quantum models can be written as partial Fourier series, in which the
accessible frequencies are fully determined by the spectra of the Hamiltonians
generating the data-encoding gates. Additionally, by using Pauli rotations as
an explicit example, we have shown that by repeating such encodings, either in
parallel $(L=1)$ or in series ($L>1$), it is possible to realise a truncated
Fourier series, with the number of accessible frequencies determined by the
number of data-encoding gate repetitions. In light of these results, it is
clear that if we allow for sufficiently many repetitions of simple data-
encoding gates (such as Pauli rotations), or for Hamiltonians with large
enough dimension and suitably non-degenerate spectra, then quantum models can
realise arbitrary frequency spectra.

However, as discussed in the previous section, the expressivity of a quantum
model is determined not only by the accessible frequency spectrum, but also by
the flexibility one has in adjusting the contributions of the frequencies,
i.e., with which flexibility the Fourier coefficients can be chosen. In this
section we show that if one allows for trainable circuit blocks which are
flexible enough to realise arbitrary global unitaries, then there exists an
$L=1$ quantum model which can realise all possible sets of Fourier
coefficients. Combined with the observations from the previous sections, this
allows us to show that such quantum models are asymptotically universal, in
the sense that if we allow the global Hilbert space dimension (or the number
of finite dimensional subsystems) to tend to infinity, then such a quantum
model can approximate, to arbitrary accuracy, any square-integrable function
on a suitable domain.

More specifically, we consider the (multivariate) single layer quantum model
$f_{\bm{\theta}}\colon\mathbb{R}^{N}\rightarrow\mathbb{R}$ defined via

$\displaystyle f_{\bm{\theta}}(\bm{x})=\langle
0|U^{\dagger}(\bm{\theta},\bm{x})MU(\bm{\theta},\bm{x})|0\rangle,$ (28)

where

$U(\bm{\theta},\bm{x})=W^{(2)}(\bm{\theta}^{(2)})S(\bm{x})W^{(1)}(\bm{\theta}^{(1)}),$
(29)

with $\bm{\theta}^{(1)},\bm{\theta}^{(2)}\subseteq\bm{\theta}$ and

$S(\bm{x}):=e^{-ix_{1}H_{1}}\otimes\ldots\otimes e^{-ix_{N}H_{N}}.$ (30)

The above model is a natural extension of the univariate $L=1$ model we
explored in previous sections. In Appendix A we show that it naturally
realises a multivariate Fourier series, with the frequency spectrum fully
determined by the spectra of the data-encoding Hamiltonians $\\{H_{l}\\}$, and
the Fourier coefficients determined by the remainder of the circuit.

It is important to emphasise that in practical applications one would
typically consider trainable circuit blocks whose circuit depth scales in a
controlled way with respect to the number of qubits in the circuit. However,
we will in this work assume that the trainable circuit blocks are sufficiently
flexible to realise arbitrary global unitaries, which may require exponential
circuit depth when decomposed into natural primitive gate sets. Given this,
the asymptotic universality of quantum models with either constant,
logarithmic or polynomial circuit depth trainable blocks remains an
interesting open question.

With this assumption on the trainable circuit blocks, we can drop the explicit
dependence on $\bm{\theta}$, and by absorbing $W^{(1)}$ into the initial state
$\left|\Gamma\right\rangle$, and $W^{(2)}$ into the observable $M$, consider
instead the equivalent model

$\displaystyle
f(\bm{x})=\langle\Gamma|S^{\dagger}(\bm{x})MS(\bm{x})|\Gamma\rangle,$ (31)

where the universality of $W^{(1)}$ and $W^{(2)}$ is reinterpreted as the
assumption that $|\Gamma\rangle$ can be an arbitrary state, and $M$ an
arbitrary observable. In order to simplify things further, we will also make
the additional assumption that all data-encoding Hamiltonians are equal –
i.e., that

$\displaystyle S(\bm{x})$ $\displaystyle:=e^{-ix_{1}H}\otimes\ldots\otimes
e^{-ix_{N}H}$ (32) $\displaystyle:=S_{H}(\bm{x}).$ (33)

We are interested in a reasonable notion of universality in the _asymptotic_
regime of infinitely many available subsystems. To formalise this, we
introduce the concept of a _Hamiltonian family_
$\\{H_{m}\,|\,m\in\mathbb{N}\\}$ where $H_{m}$ acts on $m$ subsystems of
dimension $d$. An explicit example of such a family is a simple tensor product
of Pauli rotations, as studied in Section II.2, which corresponds to the
Hamiltonian

$\displaystyle H_{m}=\sum_{i=1}^{m}\sigma_{q}^{(i)}.$ (34)

As illustrated in Fig. 6, such a Hamiltonian family defines a family of models
$\\{f_{m}\\}$ via

$f_{m}(\bm{x})=\langle\Gamma|S_{H_{m}}^{\dagger}(\bm{x})MS_{H_{m}}(\bm{x})|\Gamma\rangle,$
(35)

where for each $m$, the measurement $M$ and the state $|\Gamma\rangle$ (or
equivalently the unitaries $W^{(1)}$ and $W^{(2)}$) are the learnable elements
of the model.

Figure 6: Multivariate $L=1$ quantum model considered for the universality
theorem. Here, $S(\bm{x})$ consists of feature-encoding gates acting on
different subsystems (green boxes). The Hamiltonians that generate these gates
are defined to increase the “richness” of their spectrum with growing
dimension of the subsystems (red arrows). Since we assume that the circuit
depth and structure of the trainable unitaries $W^{(1)}$ and $W^{(2)}$ is
sufficient to allow for the realisation of arbitrary unitary operations, the
trainable circuits grow in dimension along with the total system size.

Now, given some Hamiltonian $H_{m}$ with eigenvalues
$\\{\lambda_{1},\ldots,\lambda_{d^{m}}\\}$, we call

$\Omega_{H_{m}}=\\{\lambda_{j}-\lambda_{k}\,|\,j,k\in\\{1,\ldots,d^{m}\\}\\}$
(36)

the frequency spectrum associated with $H_{m}$. To achieve universality, we
need a Hamiltonian family whose frequency spectrum asymptotically contains any
integer frequency. We formalise this via the following notion: a Hamiltonian
family $\\{H_{m}\\}$ is a _universal Hamiltonian family_ if it has the
property that for all $K\in\mathbb{N}$ there exists some $m\in\mathbb{N}$ such
that

$\mathbb{Z}_{K}=\\{-K,\ldots,0,\ldots,K\\}\subseteq\Omega_{H_{m}}.$ (37)

As we have seen in the previous section, the Hamiltonian family defined by the
Hamiltonians in Eq. (34) is indeed a universal Hamiltonian family, with $m=K$.
As the possible number of frequencies grows exponentially, one could think of
more complicated Hamiltonian families in which the required number of
available subsystems only grows logarithmically $m=O(\log K)$, at the cost of
more complicated, global Hamiltonian terms. With this setup, we can now state
the following universality result:

######  Theorem.

Let $\\{H_{m}\\}$ be a universal Hamiltonian family, and $\\{f_{m}\\}$ the
associated quantum model family, defined via Eq. (35). For all functions $g\in
L_{2}([0,2\pi]^{N})$, and for all $\epsilon>0$, there exists some
$m^{\prime}\in\mathbb{N}$, some state
$|\Gamma\rangle\in\mathbb{C}^{d^{m^{\prime}}}$, and some observable $M$ such
that

$\lvert\rvert f_{m^{\prime}}-g\lvert\rvert_{2}\leq\epsilon.$ (38)

A full proof is given in Appendix C, however in the following we will provide
a sketch of the proof in order to give an outline of the ideas and techniques.
The proof begins by noting that any square-integrable function $g$ on a finite
interval can be approximated by a truncated Fourier series to arbitrary
precision. We therefore reduce the task to finding a quantum model for this
truncated Fourier series. The universality property of the Hamiltonian family
implies that the multivariate models we consider can express all necessary
frequencies to perform that approximation. We then show how to use the freedom
in choosing the initial state and the observable to reproduce the truncated
Fourier series of $g$ exactly, leading to an approximation by a quantum model
with arbitrary precision.

Note that the statement that there exists some state $|\Gamma\rangle$ and some
observable $M$ is equivalent to the statement that the target function can be
learned by the relevant model (under the assumption the trainable circuit
blocks are sufficiently flexible). As any frequency spectrum is asymptotically
accessible, due to the assumption of a universal Hamiltonian family, the
universality theorem is essentially equivalent to the statement that with
sufficiently flexible circuit blocks such quantum models can realise any set
of Fourier coefficients.

##  IV Practical implications for quantum machine learning

In this last section, we discuss the scope and practical relevance of our
results for quantum machine learning. First, we motivate that many quantum
models proposed in the literature that do not immediately fit the base model
from Eq. (3) can still be analysed within our framework under the assumption
that they encode classically pre-processed features $\bm{\phi}(\bm{x})$
instead of the original features $\bm{x}$. Second, we summarise guidelines
that can help with the design of quantum machine learning algorithms.

###  IV.1 Classical pre-processing

The base model used in this paper makes the assumption that a data feature is
encoded into a subroutine $S(x)$ which consists of gates
$\mathcal{G}(x)=e^{-ixH}$. We motivate in this section that many quantum
machine learning algorithms which use other strategies of data encoding
actually perform an implicit pre-processing of the data, and then use the
“time-evolution” encoding studied here. The results of this paper are hence
valid for the new features resulting from the pre-processing step.

For example, the standard encoding procedure of traditional Nielsen and Chuang
(2002) (and some NISQ Farhi and Neven (2018)) quantum algorithms, associates
the $n$-bit binary representation of each (scalar) input feature $x$ with an
$n$-qubit basis state, such as $x\mapsto\left|01011\right\rangle$. The pre-
processing step therefore maps original features $x$ to the angles
$\bm{\phi}(x)=(\phi_{1}(x),\dots,\phi_{n}(x))$ with which the $n$ qubits have
to be rotated to reflect every binary decimal digit of $x$ (i.e., $\pi$ for
$\left|1\right\rangle$ or $0$ for $\left|0\right\rangle$). Our investigation
here states that the quantum model for a single input feature corresponds to a
multi-dimensional Fourier series in the angles, with a frequency spectrum size
of at most $n$. In other words, the pre-processing changed the accessible
Fourier spectrum by changing the features.

Another example is so-called “amplitude encoding” (i.e., Rebentrost  _et al._
(2014); Schuld  _et al._ (2020)), which associates an input vector $\bm{x}$
with the values of the amplitudes of a quantum state. Practically, this
requires $S(\bm{x})$ to be an arbitrary state preparation routine that is
parametrised by some angles computed from $\bm{x}$. The classical pre-
processing therefore maps the original input to the set of angles used in the
state preparation, $\bm{x}\mapsto\bm{\phi}(\bm{x})$.

Pre-processing is also sometimes used in encoding strategies that directly
feed input features into Pauli rotations. One example was used in Figs. 3 and
4, where we re-scaled the inputs by a classical hyperparameter. In Ref. Pérez-
Salinas  _et al._ (2020) it has been proposed to make these hyperparameters
trainable (which in the light of the present analysis would allow for an
adaptive “frequency matching” and may help to increase the expressivity of
small quantum circuits). Another example is to construct higher-order features
that are arithmetic combinations of the original inputs, like
$\phi_{1}(\bm{x})=x_{1}x_{2},\phi_{2}(\bm{x})=x_{2}x_{3},\dots$, as used in
the quantum feature map proposed in Ref. Havlíček  _et al._ (2019).

These examples suggest that implicit pre-processing can extend the function
classes that quantum models can learn even further. However, care needs to be
taken when making theoretical claims about the power of a quantum machine
learning algorithm, which is, strictly speaking, a result of the quantum
algorithm plus the specific pre-processing strategy. In particular,
comparisons to classical machine learning models should identify the pre-
processing strategy and consider feeding the same pre-processed features to
the classical model.

###  IV.2 Practical insights

Finally, we want to summarise how the results of this paper can be used to
understand and evaluate different design decisions of quantum machine learning
models:

_1._ If data is encoded via a Hamiltonian time evolution, we can naturally
describe the class of functions that quantum models can learn as partial
Fourier series. The Hamiltonian defines the available frequencies in the
series, and the gates that do not encode data define the Fourier coefficients.

_2._ If data is encoded into single-qubit Pauli rotations, the number of
rotations used limits the number of frequencies that the model has access to.
Repeating an encoding gate can help to increase the frequency spectrum, and
thereby the expressivity of a quantum model.

_3._ Quantum models naturally learn periodic functions in the data. One should
therefore consider appropriate data re-scaling strategies, to make sure the
data lies within the period of the function class. The natural representation
of quantum models as Fourier series may suggest that time-series learning and
signal processing tasks are particularly suitable applications for quantum
machine learning. It may also hint at inherent regularising properties of
quantum models that exclude higher-order Fourier frequencies.

_4._ Classical pre-processing of the data, such as creating more features, can
give small models more expressivity by enriching the frequency spectrum.

_5._ Adjusting the entries of the observable freely was a key ingredient in
proving universality of quantum circuits in Section III. Fixing the observable
in a quantum model therefore limits its applicability. This fact suggests that
parametrising the observable itself may be a key ingredient for flexible
quantum models.

Ideally, one would hope that our results could provide concrete guidelines for
the design of quantum machine learning models. However, in practical settings
the process of model selection should be guided not purely by model
expressivity, but rather through the expected generalisation performance of
the model function class, as captured by capacity metrics such as the VC-
dimension or Rademacher complexity Shalev-Shwartz and Ben-David (2014). While
such capacities can be calculated for very simple function classes,
calculating such metrics for more complex model classes, such as the quantum
models studied here, is significantly harder. Additionally, in modern over-
parametrised models, which can often fit even randomised training data
perfectly Zhang  _et al._ (2016), more sophisticated approaches are necessary
to understand generalisation capacity Jiang  _et al._ (2019). In light of
this, the insights on how to make models more expressive should not be
misinterpreted as recommendations for how to design good quantum models – a
question which is much more complex and whose answer depends strongly on the
context.

##  V Conclusion

In this work we presented a systematic mapping between a large class of
quantum machine learning models and partial Fourier series, which has allowed
us to explore and quantify the effect of commonly used data-encoding
mechanisms on the expressivity of these quantum models. We believe that this
framework both lays a foundation for further theoretical analysis, and can
serve as a useful guide in the search for suitable applications of such
models. Additionally, this work provides a connection between quantum machine
learning and ideas from the classical machine learning literature, such as
neural networks with periodic activation functions Sitzmann  _et al._ (2020),
and parametrised Fourier series as an alternative to neural networks
Zhumekenov  _et al._ (2019); Wahls  _et al._ (2014).

As mentioned throughout the paper, a variety of interesting questions remain.
Firstly, can the framework developed here help us to understand and quantify
the generalisation capacity of quantum models, and therefore guide model
selection in a meaningful way? In particular, by using the representation of a
quantum model as a partial Fourier series, can one calculate meaningful modern
generalisation measures Jiang  _et al._ (2019) and use these for the
development of model-selection guidelines? Secondly, we have proven our
universality result under the assumption of exponential depth trainable
circuit blocks (which provides a reasonable notion of asymptotic universality
with respect to circuit depth). In practical settings however one is
interested in trainable circuit blocks with depth restrictions. Can one prove
universality of such quantum models with either constant, logarithmic or
polynomial depth trainable circuit blocks? In order to answer this question
our toolbox needs to be developed further to understand how the structure of
the trainable circuit blocks influences the set of accessible Fourier
coefficients. Finally, it is currently unclear for which concrete applications
quantum models may be naturally suited, or offer any sort of advantage over
classical techniques, such as neural networks. Another question is therefore
whether one can use knowledge of the function class expressed by quantum
models, as developed in this work, to suggest natural applications for quantum
machine learning.

## Code

Code to reproduce the figures and explore further settings can be found in the
following GitHub repository:
https://github.com/XanaduAI/expressive_power_of_quantum_models.

## Acknowledgements

MS wants to thank Nathan Killoran, Nicolas Quesada and Josh Izaac for helpful
discussions. RS and JJM acknowledge funding from the BMWi under the PlanQK
initiative. The authors endorse Scientific CO2nduct con  and provide a CO2
emission table in Appendix D.

## References

  * McClean  _et al._ (2016) Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik, “The theory of variational hybrid quantum-classical algorithms,” New Journal of Physics 18, 023023 (2016).
  * Romero and Aspuru-Guzik (2019) Jonathan Romero and Alan Aspuru-Guzik, “Variational quantum generators: Generative adversarial quantum machine learning for continuous distributions,” arXiv preprint arXiv:1901.00848 (2019).
  * Mitarai  _et al._ (2018) Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii, “Quantum circuit learning,” Physical Review A 98, 032309 (2018).
  * Farhi and Neven (2018) Edward Farhi and Hartmut Neven, “Classification with quantum neural networks on near term processors,” arXiv preprint arXiv:1802.06002 (2018).
  * McClean  _et al._ (2018) Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven, “Barren plateaus in quantum neural network training landscapes,” Nature Communications 9, 1–6 (2018).
  * Benedetti  _et al._ (2019) Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini, “Parameterized quantum circuits as machine learning models,” Quantum Science and Technology 4, 043001 (2019).
  * Ostaszewski  _et al._ (2019) Mateusz Ostaszewski, Edward Grant, and Marcello Benedetti, “Quantum circuit structure learning,” arXiv preprint arXiv:1905.09692 (2019).
  * Stokes  _et al._ (2020) James Stokes, Josh Izaac, Nathan Killoran, and Giuseppe Carleo, “Quantum natural gradient,” Quantum 4, 269 (2020).
  * Verdon  _et al._ (2019a) Guillaume Verdon, Jacob Marks, Sasha Nanda, Stefan Leichenauer, and Jack Hidary, “Quantum hamiltonian-based models and the variational quantum thermalizer algorithm,” (2019a), arXiv:1910.02071 [quant-ph] .
  * Verdon  _et al._ (2019b) Guillaume Verdon, Trevor McCourt, Enxhell Luzhnica, Vikash Singh, Stefan Leichenauer, and Jack Hidary, “Quantum graph neural networks,” (2019b), arXiv:1909.12264 [quant-ph] .
  * Cong  _et al._ (2019) Iris Cong, Soonwon Choi, and Mikhail D Lukin, “Quantum convolutional neural networks,” Nature Physics 15, 1273–1278 (2019).
  * Liu and Wang (2018) Jin-Guo Liu and Lei Wang, “Differentiable learning of quantum circuit born machines,” Physical Review A 98, 062324 (2018).
  * Harrow and Napp (2019) Aram Harrow and John Napp, “Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms,” arXiv preprint arXiv:1901.05374 (2019).
  * Ciliberto  _et al._ (2020) Carlo Ciliberto, Andrea Rocchetto, Alessandro Rudi, and Leonard Wossnig, “Fast quantum learning with statistical guarantees,” arXiv preprint arXiv:2001.10477 (2020).
  * Cerezo  _et al._ (2020) M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles, “Cost-function-dependent barren plateaus in shallow quantum neural networks,” (2020), arXiv:2001.00550 [quant-ph] .
  * Carleson (1966) Lennart Carleson, “On convergence and growth of partial sums of Fourier series,” Acta Mathematica 116, 135–157 (1966).
  * Pérez-Salinas  _et al._ (2020) Adrián Pérez-Salinas, Alba Cervera-Lierta, Elies Gil-Fuster, and José I Latorre, “Data re-uploading for a universal quantum classifier,” Quantum 4, 226 (2020).
  * Killoran  _et al._ (2019) Nathan Killoran, Thomas R Bromley, Juan Miguel Arrazola, Maria Schuld, Nicolás Quesada, and Seth Lloyd, “Continuous-variable quantum neural networks,” Physical Review Research 1, 033063 (2019).
  * Sim  _et al._ (2019) Sukin Sim, Peter D Johnson, and Alán Aspuru-Guzik, “Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms,” Advanced Quantum Technologies 2, 1900070 (2019).
  * Chen  _et al._ (2018) Hongxiang Chen, Leonard Wossnig, Simone Severini, Hartmut Neven, and Masoud Mohseni, “Universal discriminative quantum neural networks,” arXiv preprint arXiv:1805.08654 (2018).
  * Du  _et al._ (2018) Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao, “The expressive power of parameterized quantum circuits,” arXiv preprint arXiv:1810.11922 (2018).
  * Biamonte (2019) Jacob Biamonte, “Universal variational quantum computation,” arXiv preprint arXiv:1903.04500 (2019).
  * Caro and Datta (2020) Matthias C Caro and Ishaun Datta, “Pseudo-dimension of quantum circuits,” arXiv preprint arXiv:2002.01490 (2020).
  * Schuld and Killoran (2019) Maria Schuld and Nathan Killoran, “Quantum machine learning in feature Hilbert spaces,” Physical Review Letters 122, 040504 (2019).
  * Havlíček  _et al._ (2019) Vojtěch Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta, “Supervised learning with quantum-enhanced feature spaces,” Nature 567, 209–212 (2019).
  * LaRose and Coyle (2020) Ryan LaRose and Brian Coyle, “Robust data encodings for quantum classifiers,” arXiv preprint arXiv:2003.01695 (2020).
  * Lloyd  _et al._ (2020) Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Izaac, and Nathan Killoran, “Quantum embeddings for machine learning,” arXiv preprint arXiv:2001.03622 (2020).
  * Gil Vidal and Theis (2020) Francisco Javier Gil Vidal and Dirk Oliver Theis, “Input redundancy for parameterized quantum circuits,” Frontiers in Physics 8, 297 (2020).
  * Rebentrost  _et al._ (2014) Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd, “Quantum support vector machine for big data classification,” Physical Review Letters 113, 130503 (2014).
  * Schuld  _et al._ (2020) Maria Schuld, Alex Bocharov, Krysta M Svore, and Nathan Wiebe, “Circuit-centric quantum classifiers,” Physical Review A 101, 032308 (2020).
  * Hubregtsen  _et al._ (2020) Thomas Hubregtsen, Josef Pichlmeier, and Koen Bertels, “Evaluation of parameterized quantum circuits: on the design, and the relation between classification accuracy, expressibility and entangling capability,” arXiv preprint arXiv:2003.09887 (2020).
  * Koide-Majima and Majima (2020) Naoko Koide-Majima and Kei Majima, “Quantum circuit-like learning: A fast and scalable classical machine-learning algorithm with similar performance to quantum circuit learning,” arXiv preprint arXiv:2003.10667 (2020).
  * Watabe  _et al._ (2019) Masaya Watabe, Kodai Shiba, Masaru Sogabe, Katsuyoshi Sakamoto, and Tomah Sogabe, “Quantum circuit parameters learning with gradient descent using backpropagation,” arXiv preprint arXiv:1910.14266 (2019).
  * Blank  _et al._ (2019) Carsten Blank, Daniel K Park, June-Koo Kevin Rhee, and Francesco Petruccione, “Quantum classifier with tailored quantum kernel,” arXiv preprint arXiv:1909.02611 (2019).
  * Zhao  _et al._ (2019) Jian Zhao, Yuan-Hang Zhang, Chang-Peng Shao, Yu-Chun Wu, Guang-Can Guo, and Guo-Ping Guo, “Building quantum neural networks based on a SWAP test,” Physical Review A 100, 012334 (2019).
  * Bergholm  _et al._ (2018) Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, M. Sohaib Alam, Shahnawaz Ahmed, Juan Miguel Arrazola, Carsten Blank, Alain Delgado, Soran Jahangiri, Keri McKiernan, Johannes Jakob Meyer, Zeyue Niu, Antal Száva, and Nathan Killoran, “PennyLane: Automatic differentiation of hybrid quantum-classical computations,” arXiv preprint arXiv:1811.04968 (2018).
  * Nielsen and Chuang (2002) Michael A Nielsen and Isaac Chuang, “Quantum computation and quantum information,” (2002).
  * Shalev-Shwartz and Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David,  _Understanding machine learning: From theory to algorithms_ (Cambridge university press, 2014).
  * Zhang  _et al._ (2016) Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals, “Understanding deep learning requires rethinking generalization,” (2016), arXiv:1611.03530 [cs.LG] .
  * Jiang  _et al._ (2019) Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio, “Fantastic generalization measures and where to find them,” (2019), arXiv:1912.02178 [cs.LG] .
  * Sitzmann  _et al._ (2020) Vincent Sitzmann, Julien NP Martel, Alexander W Bergman, David B Lindell, and Gordon Wetzstein, “Implicit neural representations with periodic activation functions,” arXiv preprint arXiv:2006.09661 (2020).
  * Zhumekenov  _et al._ (2019) Abylay Zhumekenov, Malika Uteuliyeva, Olzhas Kabdolov, Rustem Takhanov, Zhenisbek Assylbekov, and Alejandro J Castro, “Fourier neural networks: A comparative study,” arXiv preprint arXiv:1902.03011 (2019).
  * Wahls  _et al._ (2014) Sander Wahls, Visa Koivunen, H Vincent Poor, and Michel Verhaegen, “Learning multidimensional fourier series with tensor trains,” in  _2014 IEEE Global Conference on Signal and Information Processing (GlobalSIP)_ (IEEE, 2014) pp. 394–398.
  * (44) “Scientific co2nduct,” online.
  * Weisz (2012) Ferenc Weisz, “Summability of multi-dimensional trigonometric fourier series,” (2012), arXiv:1206.1789 [math.CA] .

##  Appendix A Partial Fourier Series Representation of Multivariate Functions

In this section we show how a certain class of $L=1$ quantum models naturally
realise multivariate Fourier series. On the one hand, this shows a way in
which the univariate case analysed in the paper can easily generalise to
multivariate models by encoding the features into different quantum
subsystems. On the other hand, the multivariate model described in this
section is a quantum model whose asymptotic universality is stated and
discussed in Section III, and proven in Appendix C.

More specifically, we consider a quantum model of the form

$\displaystyle f(\bm{x})=\langle
0|\left((W^{(1)})^{\dagger}S^{\dagger}(\bm{x})(W^{(2)})^{\dagger}\right)M\left(W^{(2)}S(\bm{x})W^{(1)}\right)|0\rangle,$
(39)

where

$S(\bm{x}):=e^{-ix_{1}H_{1}}\otimes\ldots\otimes e^{-ix_{N}H_{N}}.$ (40)

Without loss of generality, instead of explicitly considering arbitrary
unitaries $W^{(1)}$ and $W^{(2)}$, we can “absorb” the unitaries into the
initial state and measurement and consider the equivalent model

$\displaystyle
f(\bm{x})=\langle\Gamma|S^{\dagger}(\bm{x})MS(\bm{x})|\Gamma\rangle,$ (41)

where

$\displaystyle|\Gamma\rangle$
$\displaystyle=\sum_{j_{1},\ldots,j_{N}=1}^{2^{d}}\gamma_{j_{1},\ldots,j_{N}}^{\vphantom{*}}|j_{1}\rangle\otimes\ldots\otimes|j_{N}\rangle$
(42)

is some arbitrary state, and $M$ is some arbitrary observable. To simplify the
index handling, we introduce the multi-indices $\bm{j}\in[2^{d}]^{N}$ with
which we can rewrite

$\displaystyle|\Gamma\rangle:=\sum_{\bm{j}}^{\vphantom{*}}\gamma_{\bm{j}}|\bm{j}\rangle.$
(43)

Additionally, as argued before we can without loss of generality assume that
all Hamiltonians are diagonal, i.e., that

$H_{k}=\mathrm{diag}(\lambda^{(k)}_{1},\ldots,\lambda^{(k)}_{2^{d}}).$ (44)

With this assumption, we note that $S(\bm{x})$ is diagonal with entries

$[S(\bm{x})]_{\bm{j},\bm{j}}=e^{-i\bm{x}\cdot\bm{\lambda}_{\bm{j}}},$ (45)

where we have defined

$\bm{\lambda}_{\bm{j}}=(\lambda^{(1)}_{j_{1}},\ldots,\lambda^{(N)}_{j_{N}}).$
(46)

Given this, we see that

$\displaystyle f(\bm{x})$
$\displaystyle=\sum_{\bm{j}}\sum_{\bm{k}}\gamma^{*}_{\bm{j}}\gamma_{\bm{k}}^{\vphantom{*}}[S^{\dagger}(\bm{x})MS(\bm{x})]_{\bm{j},\bm{k}}^{\vphantom{*}}$
(47)
$\displaystyle=\sum_{\bm{j}}\sum_{\bm{k}}\gamma^{*}_{\bm{j}}\gamma_{\bm{k}}^{\vphantom{*}}M_{\bm{j},\bm{k}}^{\vphantom{*}}e^{i\bm{x}\cdot(\bm{\lambda}_{\bm{k}}-\bm{\lambda}_{\bm{j}})},$
(48)

which is indeed a partial multivariate Fourier series, with the accessible
frequencies fully determined by the spectra of the encoding Hamiltonians
$\\{H_{k}\\}$, and the Fourier coefficients determined by the trainable
unitaries (or equivalently, the state and observable).

##  Appendix B Non-integer frequencies

In the main text, we put our focus on quantum models with integer-valued
frequency spectra, as they naturally arise when using Pauli rotation gates and
allow for analysis with the techniques of Fourier series. Here we will briefly
discuss why many quantum models with non-integer-valued frequency spectra can
be treated similarly.

First, note that we can always decompose functions of the form $e^{i\omega x}$
into a Fourier series of integer-valued frequencies, i.e.,

$\displaystyle e^{i\omega
x}=\sum_{n=-\infty}^{\infty}\frac{(-1)^{n}\sin\omega\pi}{(\omega-n)\pi}e^{inx}=\sum_{n=-\infty}^{\infty}\operatorname{sinc}(\omega-n)e^{inx},$
(49)

with $\operatorname{sinc}(z)=\sin(\pi z)/\pi z$. However, as we can see from
this expression, any non-integer frequency in general “contributes” to
_infinitely many_ Fourier coefficients. It turns out that a rather general
case of quantum models with non-integer frequencies can be handled
equivalently, namely if the frequencies are integer multiples of some basic
frequency $\omega_{0}$,

$\displaystyle\Omega=\\{0,\pm n_{1}\omega_{0},\pm n_{2}\omega_{0},\dots\\}.$
(50)

This condition is equivalent to all frequencies in $\Omega$ being mutually
commensurable, i.e., the ratio of any two frequencies is a rational number.
This is the case in many natural settings, for example if encodings with non-
integer frequencies are repeated in parallel alike to the Pauli encodings in
Section II.

Basis functions of the form $e^{ixn\omega_{0}}$ are periodic functions on the
interval $[0,2\pi/\omega_{0}]$. This means that the generated Fourier-type sum
in Eq. (11) can be understood like the partial Fourier series in Eq. (5), but
on a different interval. Alternatively, one can imagine re-scaling the data by
$\tilde{x}=x/\omega_{0}$, with which

$\displaystyle e^{i\frac{x}{\omega_{0}}\omega}=e^{i\tilde{x}n}.$ (51)

While this strategy could in principle be applied to any frequency spectrum
where the frequencies are mutually commensurable, one has to be aware that
$\omega_{0}$ is as least as small as the smallest difference between
frequencies in $\Omega$. If very close frequencies are present in the
spectrum, the data will have to be re-scaled by a very large factor to an
interval where the generated Fourier coefficients may be sparse and the
approximation quality poor.

##  Appendix C Proof of the universality theorem

We provide in this section a proof of the universality theorem stated in
Section III, which we restate for completeness:

######  Theorem.

Let $\\{H_{m}\\}$ be a universal Hamiltonian family, and $\\{f_{m}\\}$ the
associated quantum model family, defined via Eq. (35). For all functions $g\in
L_{2}([0,2\pi]^{N})$, and for all $\epsilon>0$, there exists some
$m^{\prime}\in\mathbb{N}$, some state
$|\Gamma\rangle\in\mathbb{C}^{d^{m^{\prime}}}$, and some observable $M$ such
that

$\lvert\rvert f_{m^{\prime}}-g\lvert\rvert_{2}\leq\epsilon.$ (52)

###### Proof.

To begin with, we note that we can approximate any given $g\in
L_{2}([0,2\pi]^{N})$, up to an arbitrarily small error in $L_{2}$ norm, by
using a truncated Fourier series Weisz (2012). More specifically, for any
given $\epsilon>0$, there exists some $K\in\mathbb{N}$ and some set of
coefficients $\\{c_{\bm{n}}\,|\,\bm{n}\in\mathbb{Z}^{N}_{K}\\}$, with
$c_{\bm{n}}=c^{*}_{-\bm{n}}$, such that

$\displaystyle\tilde{g}(\bm{x})$
$\displaystyle=\sum_{n_{1}=-K}^{K}\ldots\sum_{n_{N}=-K}^{K}c_{\bm{n}}e^{i\bm{x}\cdot\bm{n}}$
(53)
$\displaystyle:=\sum_{\bm{n}\in\mathbb{Z}^{N}_{K}}c_{\bm{n}}e^{i\bm{x}\cdot\bm{n}}$
(54)

satisfies

$\lvert\rvert\tilde{g}-g\lvert\rvert\leq\epsilon.$ (55)

In order to prove the theorem we therefore only need to show that there exists
an $m^{\prime}\in\mathbb{N}$, some state $|\Gamma\rangle$ and some observable
$M$ so that the associated quantum model $f_{m^{\prime}}$ generates the
Fourier series $\tilde{g}$. Recall that the quantum model was defined as

$\displaystyle
f_{m}(\bm{x})=\langle\Gamma|S^{\dagger}_{H_{m}}(\bm{x})MS_{H_{m}}(\bm{x})|\Gamma\rangle,$
(56)

with

$S_{H_{m}}(\bm{x}):=e^{-ix_{1}H_{m}}\otimes\ldots\otimes e^{-ix_{N}H_{m}}.$
(57)

In Appendix A, we have seen that we can express the output of the model as

$\displaystyle f_{m}(\bm{x})$
$\displaystyle=\sum_{\bm{j}}\sum_{\bm{k}}\gamma^{*}_{\bm{j}}\gamma_{\bm{k}}^{\vphantom{*}}M_{\bm{j},\bm{k}}^{\vphantom{*}}e^{i\bm{x}\cdot(\bm{\lambda}_{\bm{k}}-\bm{\lambda}_{\bm{j}})},$
(58)

where the multi-indices $\bm{j}$ and $\bm{k}$ have $N$ entries that iterate
over all $2^{d}$ basis states of the $d$ qubit subsystems. Let
$\Omega_{H_{m}}$ be the frequency spectrum of $H_{m}$, as defined in Eq. (36).
As the $\\{H_{m}\\}$ form a universal family of Hamiltonians by assumption, we
can choose an $m^{\prime}\in\mathbb{N}$ so that

$\displaystyle\mathbb{Z}_{K}=\\{-K,\dots,0,\dots,K\\}\subseteq\Omega_{H_{m^{\prime}}}.$
(59)

The accessible frequency vectors $\bm{\lambda}_{\bm{j}}-\bm{\lambda}_{\bm{k}}$
independently contain all possible combinations of the frequencies in
$\Omega_{H_{m^{\prime}}}$. The vector-valued frequency spectrum for the
multivariate case is therefore the Cartesian product of $N$ copies of
$\Omega_{H_{m^{\prime}}}$:

$\displaystyle\Omega=\underbrace{\Omega_{H_{m^{\prime}}}\times\dots\times\Omega_{H_{m^{\prime}}}}_{N\text{
times}}.$ (60)

As $\mathbb{Z}_{K}\subseteq\Omega_{H_{m^{\prime}}}$ we naturally have that
$\mathbb{Z}_{K}^{N}\subseteq\Omega$, which means that the Fourier series
generated by the chosen model contains all terms that are necessary to
construct the Fourier series $\tilde{g}$.

We can now revisit Eq. (58) and show that we can leverage the freedom of
choosing both the initial state $\left|\Gamma\right\rangle$ and the observable
$M$ arbitrarily to adjust all terms in the sum of Eq. (58) freely up to the
complex-conjugation symmetry that guarantees that the model output is a real-
valued function. To this end, we first observe that an exchange of the multi-
indices $\bm{j}$ and $\bm{k}$ yields the complex conjugate of the original
term:

$\displaystyle\left[\gamma^{*}_{\bm{j}}\gamma_{\bm{k}}^{\vphantom{*}}M_{\bm{j},\bm{k}}^{\vphantom{*}}e^{i\bm{x}\cdot(\bm{\lambda}_{\bm{k}}-\bm{\lambda}_{\bm{j}})}\right]^{*}$
$\displaystyle=\gamma^{*}_{\bm{k}}\gamma_{\bm{j}}^{\vphantom{*}}M_{\bm{j},\bm{k}}^{*}e^{i\bm{x}\cdot(\bm{\lambda}_{\bm{j}}-\bm{\lambda}_{\bm{k}})}$
(61)
$\displaystyle=\gamma^{*}_{\bm{k}}\gamma_{\bm{j}}^{\vphantom{*}}M_{\bm{k},\bm{j}}^{\vphantom{*}}e^{-i\bm{x}\cdot(\bm{\lambda}_{\bm{k}}-\bm{\lambda}_{\bm{j}})}.$
(62)

Other than that, the coefficients can be freely chosen. To this end, we fix
our initial state as the equal superposition state which can be prepared by
applying a Hadamard gate to every qubit in the system. This gives
$\gamma_{\bm{j}}=1/\sqrt{2^{Nd}}$ and results in the model

$\displaystyle f_{m^{\prime}}(\bm{x})$
$\displaystyle=2^{-Nd}\sum_{\bm{j}}\sum_{\bm{k}}M_{\bm{j},\bm{k}}^{\vphantom{*}}e^{i\bm{x}\cdot(\bm{\lambda}_{\bm{k}}-\bm{\lambda}_{\bm{j}})}.$
(63)

With this choice, we see that the coefficients are directly proportional to
the different entries of the observable $M$. Recall that our initial goal was
to construct the Fourier series $\tilde{g}$ with coefficients
$\\{c_{\bm{n}}\\}$ where $\bm{n}\in\mathbb{Z}_{K}^{N}$. We already argued that
all those are accessible in the frequency spectrum of our model because of the
universal nature of the Hamiltonian family $\\{H_{m}\\}$. As any frequency
corresponds to one or more pairings of multi-indices $\bm{j}$ and $\bm{k}$, we
can always select a set of these multi-indices such that it is in one to one
correspondence with the frequencies present in the Fourier series $\tilde{g}$:

$\displaystyle
I=\\{(\bm{j},\bm{k})\in[2^{d}]^{N}\times[2^{d}]^{N}\,|\,\text{for all
}\bm{n}\in\mathbb{Z}_{K}^{N}\text{ there is exactly one pair
}(\bm{j},\bm{k})\text{ so that
}\bm{\lambda}_{\bm{j}}-\bm{\lambda}_{\bm{k}}=\bm{n}\\}.$ (64)

With this it is now straightforward to use the freedom to choose our
observable to fix $f_{m^{\prime}}=\tilde{g}$ by choosing the diagonal and
upper-triangular elements of $M$ via

$\displaystyle
M_{\bm{j},\bm{k}}^{\vphantom{*}}=\begin{cases}2^{Nd}c_{\bm{n}}\text{ if
}\bm{\lambda}_{\bm{j}}-\bm{\lambda}_{\bm{k}}=\bm{n}\text{ and
}(\bm{j},\bm{k})\in I\\\ 0\text{ otherwise}\end{cases}$ (65)

after which the lower-triangular elements are fixed by the constraint that the
observable is Hermitian. ∎

##  Appendix D CO2 Emission Table

Numerical simulations |
---|---
Total Kernel Hours [$\mathrm{h}$] | $\approx 100$
Thermal Design Power Per Kernel [$\mathrm{W}$] | $\approx 50$
Total Energy Consumption Simulations [$\mathrm{kWh}$] | $\approx 5$
Average Emission Of CO2 In South Africa [$\mathrm{kg/kWh}$] | $\approx 1.5$
Total CO2 Emission For Numerical Simulations [$\mathrm{kg}$] | $\approx 7.5$
Transport |
Total CO2 Emission For Transport [$\mathrm{kg}$] | 0
Total CO2 Emission [$\mathrm{kg}$] | $\approx 7.5$
Were The Emissions Offset? | Yes


Noise-Resilient Designs for Optical Neural Networks
1,2]Gianluca Kosmellacor
[cor]Corresponding author
1]Ripalta Stabile
2]Jaron Sanders

[1]organization=Department of Electrical Engineering, Eindhoven University of Technology,
addressline=PO Box 513,
postcode=5600 MB,
country=The Netherlands

[2]organization=Department of Mathematics and Computer Science, Eindhoven University of Technology,
addressline=PO Box 513,
postcode=5600 MB,
country=The Netherlands

Optical Neural Networks, Law of Large Numbers, Universal Approximation

§ INTRODUCTION

§ MODEL

§ SIMULATIONS

§ DISCUSSION & CONCLUSION

§ ACKNOWLEDGMENTS