# Power and limitations of single-qubit
native quantum neural networks

Zhan Yu &Hongshun Yao &Mujin Li &Xin Wang
Institute for Quantum Computing, Baidu Research, Beijing 100193, China
<EMAIL_ADDRESS>Y., H. Y., M. L. contributed equally to this work.

###### Abstract

Quantum neural networks (QNNs) have emerged as a leading strategy to establish
applications in machine learning, chemistry, and optimization. While the
applications of QNN have been widely investigated, its theoretical foundation
remains less understood. In this paper, we formulate a theoretical framework
for the expressive ability of data re-uploading quantum neural networks that
consist of interleaved encoding circuit blocks and trainable circuit blocks.
First, we prove that single-qubit quantum neural networks can approximate any
univariate function by mapping the model to a partial Fourier series. We in
particular establish the exact correlations between the parameters of the
trainable gates and the Fourier coefficients, resolving an open problem on the
universal approximation property of QNN. Second, we discuss the limitations of
single-qubit native QNNs on approximating multivariate functions by analyzing
the frequency spectrum and the flexibility of Fourier coefficients. We further
demonstrate the expressivity and limitations of single-qubit native QNNs via
numerical experiments. We believe these results would improve our
understanding of QNNs and provide a helpful guideline for designing powerful
QNNs for machine learning tasks.

##  1 Introduction

Quantum computing is a technology that exploits the laws of quantum mechanics
to solve complicated problems much faster than classical computers. It has
been applied in areas such as breaking cryptographic systems [1], searching
databases [2], and quantum simulation [3, 4], in which it gives a quantum
speedup over the best known classical algorithms. With the fast development of
quantum hardware, recent results [5, 6, 7] have shown quantum advantages in
specific tasks. An emerging direction is to investigate if quantum computing
can offer quantum advantages in artificial intelligence, giving rise to an
interdisciplinary area called _quantum machine learning_ [8].

A leading strategy to quantum machine learning uses _quantum neural networks_
(QNNs), which are quantum analogs of artificial neural networks (NNs). Much
progress has been made in applications of QNN in various topics [9, 10, 11],
including quantum autoencoder [12, 13], supervised learning [14, 15, 16, 17],
dynamic learning [18, 19, 20], quantum chemistry [21], and quantum metrology
[22, 23, 24]. Similar to the field of machine learning, a crucial challenge of
quantum machine learning is to design powerful and efficient QNN models for
quantum learning tasks, which requires a theoretical understanding of how
structural properties of QNN may affect its expressive power.

The expressive power of a QNN model can be characterized by the function
classes that it can approximate. Recently, the universal approximation
property (UAP) of QNN models has been investigated, which is similar to the
universal approximation theorem [25, 26] in machine learning theory. The
authors of [27] suggested that a QNN model can be written as a partial Fourier
series in the data and proved the existence of a multi-qubit QNN model that
can realize a universal function approximator. The UAP of single-qubit models
remains an open conjecture, due to the difficulties in analyzing the
flexibility of Fourier coefficients. Another work [28] considered hybrid
classical-quantum neural networks and obtained the UAP by using the Stone-
Weierstrass theorem. Ref. [29] proved that even a single-qubit hybrid QNN can
approximate any bounded function.

The above results of UAP show that the expressivity of QNNs is strong, but it
does not reveal the relationship between the structural properties of a QNN
and its expressive ability. Therefore the UAP may not be a good guide for
constructing QNN models with practical interests. In particular, it is worth
noting that the existence proof in Ref. [27] is under the assumption of multi-
qubit systems, exponential circuit depth, and arbitrary observables, which
does not explicitly give the structure of QNNs. Meanwhile, Refs. [28, 29]
demonstrated the construction of QNNs in detail, but it is unclear whether the
powerful expressivity comes from the classical part or the quantum part of
hybrid models. Moreover, a systematic analysis of how parameters in the QNN
affect the classes of functions that it can approximate is missing. The
absence of these theoretical foundations hinders the understanding on the
expressive power and limitation of QNNs, which makes it highly necessary but
challenging to design effective and efficient QNNs.

To theoretically investigate the expressivity of QNNs, it is important to
study the simplest case of single-qubit QNNs, just like the celebrated
universal approximation theorem first showing the expressivity of depth-2 NNs
[25, 26]. In this paper, we formulate an analytical framework that correlates
the structural properties of a single-qubit native QNN and its expressive
power. We consider data re-uploading models that consist of interleaved data
encoding circuit blocks and trainable circuit blocks [30]. First, we prove
that there exists a single-qubit native QNN that can express any Fourier
series, which is a universal approximator for any square-integrable univariate
function. It solves the open problem on the UAP of single-qubit QNNs in Ref.
[27]. Second, we systematically analyze how parameters in trainable circuit
blocks affect the Fourier coefficients. The main results on the expressivity
of QNNs are summarized as in Fig. 1. Third, we discuss potential difficulties
for single-qubit native QNNs to approximate multivariate functions.
Additionally, we compare native QNNs with the hybrid version and show the
fundamental difference in their expressive power. We also demonstrate the
expressivity and limitations of single-qubit native QNNs via numerical
experiments on approximating univariate and multivariate functions. Our
analysis, beyond the UAP of QNNs, improves the understanding of the
relationship between the expressive power and the structure of QNNs. This
fundamental framework provides a theoretical foundation for data re-uploading
QNN models, which is helpful to construct effective and efficient QNNs for
quantum machine learning tasks.

Figure 1: A schematic diagram of the main results. A single-qubit data re-
uploading QNN model consisting of interleaved trainable blocks (in blue) and
encoding blocks (in orange) corresponds to a partial Fourier series. The
encoding blocks decide the frequency spectrum of the Fourier series and the
trainable blocks control the Fourier coefficients. By the summability and
convergence of the Fourier series, the QNN model can approximate any square-
integrable target function.

We will start by giving some background and defining the native QNN models in
the next section, and then analyze the expressivity of single-qubit native
QNNs in Section 3. In Section 4, we discuss the limitation of single-qubit
native QNNs and compare native QNNs with hybrid QNNs, which shows the
fundamental difference between their expressive power. The numerical
experiments on the expressivity and limitations of single-qubit native QNNs
are described in Section 5.

##  2 Preliminaries

###  2.1 A primer on quantum computing

#### Quantum state

The basic unit of information in quantum computation is one _quantum bit_ , or
_qubit_ for short. Just like a classical bit has a state in either $0$ or $1$,
a qubit also has a state. A single-qubit state is a unit vector in a
2-dimensional Hilbert space ${{\mathbb{C}}}^{2}$, which is commonly denoted in
Dirac notation $\ket{\psi}=\alpha\ket{0}+\beta\ket{1}$, where
$\ket{0}=(1,0)^{T}$ and $\ket{1}=(0,1)^{T}$ are known as computational basis
states. Here $\ket{\psi}$ denotes a column vector and its conjugate transpose
$\bra{\psi}\coloneqq\ket{\psi}^{\dagger}$ is a row vector. Then the inner
product $\innerproduct{\psi}{\psi}=\norm{\psi}^{2}$ denotes the square of
$L^{2}$-norm of $\ket{\psi}$. Note that $\ket{\psi}$ is a normalized state so
$\innerproduct{\psi}{\psi}=\absolutevalue{\alpha}^{2}+\absolutevalue{\beta}^{2}=1$.
Having this constraint, a single-qubit state can be represented as a point at
surface of a _Bloch sphere_ , written as
$\ket{\psi}=\cos(\theta/2)\ket{0}+e^{i\phi}\sin(\theta/2)\ket{1}$, where
$\theta$ and $\phi$ are re-interpreted as azimuthal angle and polar angle in
spherical coordinates. More generally, a quantum state of $n$ qubits can be
represented as a normalized vector in the $n$-fold tensor product Hilbert
space ${{\mathbb{C}}}^{2^{n}}$.

#### Quantum gate

Quantum gates are basic operations used to manipulate qubits. Unlike some
classical logical gates, quantum gates are reversible, so they can be
represented as _unitary transformations_ in the Hilbert space. A unitary
matrix $U$ satisfies $U^{\dagger}U=UU^{\dagger}=I$. A commonly used group of
single-qubit quantum gates is the _Pauli gates_ , which can be written as
Pauli matrices:

$X=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix},\qquad Y=\begin{bmatrix}0&-i\\\
i&0\end{bmatrix},\qquad Z=\begin{bmatrix}1&0\\\ 0&-1\end{bmatrix}.$ (1)

The Pauli $X$, $Y$, and $Z$ gates are equivalent to a rotation around the $x$,
$y$, and $z$ axes of the Bloch sphere by $\pi$ radians, respectively. A group
of more general gates is the _rotation operator gates_
$\\{R_{P}(\theta)=e^{-i\frac{\theta}{2}P}\mid P\in\\{X,Y,Z\\}\\}$, which
allows the rotating angle around the $x$, $y$ and $z$ axes of the Bloch sphere
to be customized. They can be written in the matrix form as

$R_{X}(\theta)=\begin{bmatrix}\cos\frac{\theta}{2}&-i\sin\frac{\theta}{2}\\\\[4.30554pt]
-i\sin\frac{\theta}{2}&\cos\frac{\theta}{2}\end{bmatrix},\quad
R_{Y}(\theta)=\begin{bmatrix}\cos\frac{\theta}{2}&-\sin\frac{\theta}{2}\\\\[4.30554pt]
\sin\frac{\theta}{2}&\cos\frac{\theta}{2}\end{bmatrix},\quad
R_{Z}(\theta)=\begin{bmatrix}e^{-i\frac{\theta}{2}}&0\\\\[4.30554pt]
0&e^{i\frac{\theta}{2}}\end{bmatrix}.$ (2)

#### Quantum measurement

A measurement is a quantum operation to retrieve classical information from a
quantum state. The simplest measurement is the computational basis
measurement; for a single-qubit state $\ket{\psi}=\alpha\ket{0}+\beta\ket{1}$,
the outcome of such a measurement is either $\ket{0}$ with probability
$\absolutevalue{\alpha}^{2}$ or $\ket{1}$ with probability
$\absolutevalue{\beta}^{2}$. Computational basis measurements can be
generalized to _Pauli measurements_ , where Pauli matrices are _observables_
that we can measure. For example, measuring Pauli $Z$ is equivalent to the
computational basis measurement, since $\ket{0}$ and $\ket{1}$ are
eigenvectors of $Z$ with corresponding eigenvalues $\pm 1$. Pauli $Z$
measurement returns $+1$ if the resulting state is $\ket{0}$ and returns $-1$
if the resulting state is $\ket{1}$. We can calculate the expected value of
Pauli $Z$ measurement when the state is $\ket{\psi}$:

$\bra{\psi}Z\ket{\psi}=(\alpha^{*}\bra{0}+\beta^{*}\bra{1})Z(\alpha\ket{0}+\beta\ket{1})=\absolutevalue{\alpha}^{2}-\absolutevalue{\beta}^{2}.$
(3)

Pauli measurements can be extended to the case of multiple qubits by a tensor
product of Pauli matrices.

###  2.2 Data re-uploading quantum neural networks

We consider the data re-uploading QNN model [30], which is a generalized
framework of quantum machine learning models based on parameterized quantum
circuits [31]. A data re-uploading QNN is a quantum circuit that consists of
interleaved data encoding circuit blocks $S(\cdot)$ and trainable circuit
blocks $V(\cdot)$,

$\displaystyle
U_{\bm{\theta},L}(\bm{x})=V(\bm{\theta_{0}})\prod_{j=1}^{L}S(\bm{x})V(\bm{\theta_{j}}),$
(4)

where $\bm{x}$ is the input data,
$\bm{\theta}=(\bm{\theta_{0}},\ldots,\bm{\theta_{L}})$ is a set of trainable
parameters, and $L$ denotes the number of layers. It is common to build the
data encoding blocks and trainable blocks using the most prevalent
parameterized quantum operators $\\{R_{X},R_{Y},R_{Z}\\}$. We define the
output of this model as the expectation value of measuring some observable
$M$,

$f_{\bm{\theta},L}(\bm{x})=\bra{0}U^{\dagger}_{\bm{\theta},L}(\bm{x})MU_{\bm{\theta},L}(\bm{x})\ket{0}.$
(5)

Note that some data re-uploading QNNs introduce trainable weights in data pre-
processing or post-processing, which are considered as hybrid QNNs. For
example, the data encoding block defined as $S(\bm{w}\cdot\bm{x})$ is
essentially equivalent to feeding data $\bm{x}$ into a neuron with weight
$\bm{w}$ and then uploading the output to an encoding block $S(\cdot)$. Such a
mixing structure makes it hard to tell whether the expressive power comes from
the classical or quantum part. To solely study the expressive power of QNNs,
we define the concept of _native QNN_ , where all trainable weights are
introduced by parameters of tunable quantum gates so that they can be
distinguished from a hybrid QNN. Throughout this paper, we simply refer to the
native QNN as QNN for short unless specified otherwise.

##  3 Expressivity of single-qubit QNNs

To better understand the expressive power of QNNs, we start investigating the
simplest case of single-qubit models. Ref. [27] investigated the expressive
power of QNNs using the Fourier series formalism. In this section, we
establish an exact correlation between the single-qubit QNN and the Fourier
series in terms of both the frequency spectrum and Fourier coefficients. Note
that we consider one-dimensional input data for now, which corresponds to the
class of univariate functions.

A Fourier series is an expansion of a periodic function $f(x)$ in infinite
terms of a sum of sines and cosines which can be written in the exponential
form as

$f(x)=\sum_{n=-\infty}^{\infty}c_{n}e^{i\frac{2\pi}{T}nx},$ (6)

where

$c_{n}=\frac{1}{T}\int_{T}f(x)e^{i\frac{2\pi}{T}nx}dx$ (7)

are the Fourier coefficients. Here $T$ is the period of function $f(x)$. The
quantities $n\frac{2\pi}{T}$ are called the _frequencies_ , which are
multiples of the base frequency $\frac{2\pi}{T}$. The set of frequency
$\\{n\frac{2\pi}{T}\\}_{n}$ is called the _frequency spectrum_ of Fourier
series.

In approximation theory, a partial Fourier series (or truncated Fourier
series)

$s_{N}(x)=\sum_{n=-N}^{N}c_{n}e^{i\frac{\pi}{T}nx}$ (8)

is commonly used to approximate the function $f(x)$. A partial Fourier series
can be transformed to a Laurent polynomial $P\in{{\mathbb{C}}}[z,z^{-1}]$ by
the substitution $z=e^{i\frac{2\pi}{T}x}$, i.e.,

$P(z)=\sum_{n=-N}^{N}c_{n}z^{n}.$ (9)

A Laurent polynomial $P\in{{\mathbb{F}}}[z,z^{-1}]$ is a linear combination of
positive and negative powers of the variable $z$ with coefficients in
${{\mathbb{F}}}$. The _degree_ of a Laurent polynomial $P$ is the maximum
absolute value of any exponent of $z$ with non-zero coefficients, denoted by
$\deg(P)$. We say that a Laurent polynomial $P$ has _parity_ $0$ if all
coefficients corresponding to odd powers of $z$ are $0$, and similarly $P$ has
parity $1$ if all coefficients corresponding to even powers of $z$ are $0$.

Following the pattern of Fourier series, we first consider using
$R_{Z}(x)=e^{-ixZ/2}$ to encode the input $x$ and let $R_{Y}(\cdot)$ be the
trainable gate. We can write the QNN as

$U_{\bm{\theta},L}^{\textit{YZY}}(x)=R_{Y}(\theta_{0})\prod_{j=1}^{L}R_{Z}(x)R_{Y}(\theta_{j}),$
(10)

and the quantum circuit is shown in Fig. 3.

Figure 2: Circuit of $U_{\bm{\theta},L}^{\textit{YZY}}(x)$, where the
trainable block is $R_{Y}(\cdot)$ and the encoding block is $R_{Z}(\cdot)$.

To characterize the expressivity of this kind of basic QNN, we first
rigorously show that the QNN $U_{\bm{\theta},L}^{\textit{YZY}}(x)$ can be
represented in the form of a partial Fourier series with real coefficients.

###### Lemma 1

There exist
$\bm{\theta}=(\theta_{0},\theta_{1},\ldots,\theta_{L})\in{{\mathbb{R}}}^{L+1}$
such that $U_{\bm{\theta},L}^{\textit{YZY}}(x)=\begin{bmatrix}P(x)&-Q(x)\\\
Q^{*}(x)&P^{*}(x)\end{bmatrix}$ (11) if and only if real Laurent polynomials
$P,Q\in{{\mathbb{R}}}[e^{ix/2},e^{-ix/2}]$ satisfy 1. $\deg(P)\leq L$ and
$\deg(Q)\leq L$, 2. $P$ and $Q$ have parity $L\bmod 2$, 3. $\forall
x\in{{\mathbb{R}}}$, $\absolutevalue{P(x)}^{2}+\absolutevalue{Q(x)}^{2}=1$.

Lemma 1 decomposes the unitary matrix of the QNN
$U_{\bm{\theta},L}^{\textit{YZY}}(x)$ into Laurent polynomials with real
coefficients, which can be used to represent a partial Fourier series with
real coefficients. The proof of Lemma 1 uses a method of mathematical
induction that is in the similar spirit of the proof of quantum signal
processing [32, 33, 34, 35], which is a powerful subroutine in Hamiltonian
simulation [4] and quantum singular value transformation [34]. The forward
direction is straightforward by the definition of
$U_{\bm{\theta},L}^{\textit{YZY}}(x)$ in Eq. (10). The proof of the backward
direction is by induction in $L$ where the base case $L=0$ holds trivially.
For $L>0$, we prove that for any $U_{\bm{\theta},L}^{\textit{YZY}}(x)$ where
$P,Q$ satisfy the three conditions, there exists a unique block
$R_{Y}^{\dagger}(\theta_{k})R_{Z}^{\dagger}(x)$ such that polynomials
$\hat{P}$ and $\hat{Q}$ in
$U_{\bm{\theta},L}^{\textit{YZY}}(x)R_{Y}^{\dagger}(\theta_{k})R_{Z}^{\dagger}(x)$
satisfy the three conditions for $L-1$. Lemma 1 explicitly correlates the
frequency spectrum of the Fourier series and the number of layers $L$ of the
QNN. The proof of Lemma 1 also illustrates the exact correspondence between
the Fourier coefficients and parameters of trainable gates. A detailed proof
can be found in Appendix A.1.

Other than characterizing the QNN with Laurent polynomials, we also need to
specify the achievable Laurent polynomials $P(x)$ for which there exists a
corresponding $Q(x)$ satisfying the three conditions in Lemma 1. It has been
proved in Refs. [33, 36, 37] that the only constraint is
$\absolutevalue{P(x)}\leq 1$ for all $x\in{{\mathbb{R}}}$. That is, for any
$P\in{{\mathbb{R}}}[e^{ix/2},e^{-ix/2}]$ with $\deg(P)\leq L$ and parity
$L\bmod 2$, if $\absolutevalue{P(x)}\leq 1$ for all $x\in{{\mathbb{R}}}$,
there exists a $Q\in{{\mathbb{R}}}[e^{ix/2},e^{-ix/2}]$ with $\deg(P)\leq L$
and parity $L\bmod 2$ such that
$\absolutevalue{P(x)}^{2}+\absolutevalue{Q(x)}^{2}=1$ for all
$x\in{{\mathbb{R}}}$.

By Lemma 1, the partial Fourier series corresponding to the QNN
$U_{\bm{\theta},L}^{\textit{YZY}}(x)$ only has real coefficients. With the
exponential form of Eq. (6), a Fourier series with real coefficients only has
$\cos(nx)$ terms, which means $U_{\bm{\theta},L}^{\textit{YZY}}(x)$ can be
used to approximate any even function on the interval $[-\pi,\pi]$. Thus we
establish the following proposition, whose proof is deferred to Appendix A.2.

###### Proposition 2

For any even square-integrable function $f:[-\pi,\pi]\to[-1,1]$ and for all
$\epsilon>0$, there exists a QNN $U_{\bm{\theta},L}^{\textit{YZY}}(x)$ such
that $\ket{\psi(x)}=U_{\bm{\theta},L}^{\textit{YZY}}(x)\ket{0}$ satisfies

$\norm{\expectationvalue{Z}{\psi(x)}-f(x)}\leq\epsilon.$ (12)

Although the above result states that the QNN
$U_{\bm{\theta},L}^{\textit{YZY}}(x)\ket{0}$ is able to approximate a class of
even functions within arbitrary precision, we can see that the main limitation
of the expressive power of QNN $U_{\bm{\theta},L}^{\textit{YZY}}(x)$ is the
real Fourier coefficients, which may restrict its universal approximation
capability.

To tackle this issue, our idea is to introduce complex coefficients to the
corresponding Laurent polynomials, which can be implemented by adding a
trainable Pauli $Z$ rotation operator in each layer. Specifically, we consider
the QNN

$U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)=R_{Z}(\varphi)W(\theta_{0},\phi_{0})\prod_{j=1}^{L}R_{Z}(x)W(\theta_{j},\phi_{j}),$
(13)

where each trainable block is $W(\theta_{j},\phi_{j})\coloneqq
R_{Y}(\theta_{j})R_{Z}(\phi_{j})$. Here we add an extra $R_{Z}(\varphi)$ gate
to adjust the relative phase between $P$ and $Q$. The quantum circuit of
$U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)$ is illustrated in Fig. 3.

Figure 3: Circuit of $U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)$, where
the trainable block is composed of $R_{Y}(\cdot)$ and $R_{Z}(\cdot)$, and the
encoding block is $R_{Z}(\cdot)$.

To characterize the capability of this QNN, we establish the following Lemma
which implies $U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)$ can express any
Fourier partial sum with complex Fourier coefficients.

###### Lemma 3

There exist
$\bm{\theta}=(\theta_{0},\theta_{1},\ldots,\theta_{L})\in{{\mathbb{R}}}^{L+1}$
and
$\bm{\phi}=(\varphi,\phi_{0},\phi_{1},\ldots,\phi_{L})\in{{\mathbb{R}}}^{L+2}$
such that
$U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)=\begin{bmatrix}P(x)&-Q(x)\\\
Q^{*}(x)&P^{*}(x)\end{bmatrix}$ (14) if and only if Laurent polynomials
$P,Q\in{{\mathbb{C}}}[e^{ix/2},e^{-ix/2}]$ satisfy 1. $\deg(P)\leq L$ and
$\deg(Q)\leq L$, 2. $P$ and $Q$ have parity $L\bmod 2$, 3. $\forall
x\in{{\mathbb{R}}}$, $\absolutevalue{P(x)}^{2}+\absolutevalue{Q(x)}^{2}=1$.

Lemma 3 demonstrates a decomposition of the QNN
$U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)$ into Laurent polynomials with
complex coefficients, which can be used to represent a partial Fourier series
with complex coefficients in form of Eq. (8). The proof of Lemma 3 is similar
to the proof of Lemma 1 and its details are provided in Appendix A.3. Again,
the proof demonstrates the effect of parameterized gates on the control of
Fourier coefficients. Similarly, the constraint for the achievable Laurent
polynomials $P(x)$ in $U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)$ is that
$\absolutevalue{P(x)}\leq 1$ for all $x\in{{\mathbb{R}}}$ [36, 37].

We then prove in the following Theorem 4 that
$U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)$ is able to approximate any
square-integrable function within arbitrary precision, using the well-
established result in Fourier analysis. The detailed proof is deferred to
Appendix A.4.

######  Theorem 4 (Univariate approximation properties of single-qubit QNNs.)

For any univariate square-integrable function $f:[-\pi,\pi]\to[-1,1]$ and for
all $\epsilon>0$, there exists a QNN
$U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)$ such that
$\ket{\psi(x)}=U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)\ket{0}$ satisfies

$\norm{\expectationvalue{Z}{\psi(x)}-f(x)}\leq\epsilon.$ (15)

Up till now we only let the encoding gate be the $R_{Z}(x)$ gate, what if we
use other rotation operator gates to encode the data? It actually does not
matter which one we choose as the encoding gate if the trainable gates are
universal. Note that Pauli rotation operators $R_{X}(x),R_{Y}(x),R_{Z}(x)$
have two eigenvalues $\cos(x/2)\pm i\sin(x/2)$, and they can be diagonalized
as $Q^{\dagger}R_{Z}(x)Q$. Merging unitaries $Q^{\dagger}$ and $Q$ to
universal trainable gates gives the QNN that uses $R_{Z}(x)$ as the encoding
gate. We hereby define the generic single-qubit QNNs as

$U_{\bm{\theta},\bm{\phi},\bm{\lambda},L}^{\textit{UZU}}(x)=U_{3}(\theta_{0},\phi_{0},\lambda_{0})\prod_{j=1}^{L}R_{Z}(x)U_{3}(\theta_{j},\phi_{j},\lambda_{j}),$
(16)

where each trainable block is the generic rotation gate

$U_{3}(\theta,\phi,\lambda)=\begin{bmatrix}\cos\frac{\theta}{2}&-e^{i\lambda}\sin\frac{\theta}{2}\\\
e^{i\phi}\sin\frac{\theta}{2}&e^{i(\phi+\lambda)}\cos\frac{\theta}{2}\end{bmatrix}.$
(17)

By definition, any $L$-layer single-qubit QNN, including
$U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}$, can be expressed as
$U_{\bm{\theta},\bm{\phi},\bm{\lambda},L}^{\textit{UZU}}$. Thus
$U_{\bm{\theta},\bm{\phi},\bm{\lambda},L}^{\textit{UZU}}$ is surely a
universal approximator.

##  4 Limitations of single-qubit QNNs

We have proved that a single-qubit QNN is a universal approximator for
univariate functions, it is natural to consider its limitations. Is there a
single-qubit QNN that can approximate arbitrary multivariate functions? We
answer this question from the perspective of multivariate Fourier series.
Specifically, we consider the generic form of single-qubit QNNs defined in Eq.
(16) and upload the classical data
$\bm{x}\coloneqq(x^{(1)},x^{(2)},\cdots,x^{(d)})\in{{\mathbb{R}}}^{d}$ as

$\displaystyle
U_{\bm{\theta},L}(\bm{x})=U_{3}(\theta_{0},\phi_{0},\lambda_{0})\prod_{j=1}^{L}R_{Z}(x_{j})U_{3}(\theta_{j},\phi_{j},\lambda_{j}),$
(18)

where each $x_{j}\in\bm{x}$ and $L\in{{\mathbb{N}}}^{+}$. Without loss of
generality, assume that each dimension $x^{(i)}$ is uploaded the same number
of times, denoted by $K$. Naturally, we have $Kd=L$. Further, we rewrite the
output of QNNs defined in Eq. (5) as the following form.

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

where $\Omega=\\{-K,\cdots,0,\cdots,K\\}^{d}$, and the $c_{\bm{\omega}}$ is
determined by parameters $\bm{\theta}$ and the observable $M$. A detailed
analysis can be found in Appendix B. We can see that Eq. (19) cannot be
represented as a $K$-truncated multivariate Fourier series. Specifically, by
the curse of dimensionality, it requires exponentially many terms in $d$ to
approximate a function in $d$ dimensions. However, for
$f_{\bm{\theta},L}(\bm{x})$, the degrees of freedom grow linearly with the
number of layers $L$. It implies that single-qubit native QNNs potentially
lack the capability to universally approximate arbitrary multivariate
functions from the perspective of the Fourier series.

Despite the potential limitation of native QNNs in multivariate approximation,
it has been proved that a single-qubit hybrid QNN can approximate arbitrary
multivariate functions [28, 29]. However, the UAP of hybrid QNNs is
fundamentally different from the native model that we investigated. Those
hybrid models involve trainable weights either in data pre-processing or post-
processing. Specifically, introducing trainable weights in data pre-processing
is equivalent to multiplying each frequency of the Fourier series by an
arbitrary real coefficient, i.e.

$S(wx)=R_{Z}(wx)=e^{-iw\frac{x}{2}Z}.$ (20)

Therefore it enriches the frequency spectrum of native QNNs, which only
contain integer multiples of the fundamental frequency. It can also be readily
extended to the encoding of multi-dimensional data
$\bm{x}\coloneqq(x^{(1)},x^{(2)},\cdots,x^{(d)})$ as

$R_{Z}(w_{1}x^{(1)})R_{Z}(w_{2}x^{(2)})\cdots
R_{Z}(w_{d}x^{(d)})=R_{Z}(\bm{w}\cdot\bm{x})=e^{-\frac{1}{2}i\bm{w}\cdot\bm{x}Z},$
(21)

where $\bm{w}=(w_{1},\ldots,w_{d})$ is a vector of trainable weights. Using
such an encoding method enables a single-qubit QNN to approximate any
continuous multivariate function [29]. We notice that, although the trainable
weights enrich the frequency spectrum of the Fourier series, the capability of
hybrid QNNs to approximate arbitrary multivariate functions is not obtained
using the multivariate Fourier series, but the universal approximation theorem
[25, 26] in machine learning theory. In another word, the multivariate UAP of
a hybrid QNN mostly comes from the classical structure, and the QNN serves as
an activation function $\sigma(x)=e^{-ix}$ in the universal approximation
theorem. This fact might be able to shed some light on the reason why a hybrid
QNN does not provide quantum advantages over the classical NN.

##  5 Numerical experiments

In order to better illustrate the expressive power of single-qubit native
QNNs, we supplement the theoretical results with numerical experiments.
Specifically, we demonstrate the flexibility and approximation capability of
single-qubit native QNNs in Section 5.1. The limitations of single-qubit QNNs
are illustrated in Section 5.2 through the numerical experiments on
approximating multivariate functions. All simulations are carried out with the
Paddle Quantum toolkit on the PaddlePaddle Deep Learning Platform, using a
desktop with an 8-core i7 CPU and 32GB RAM.

###  5.1 Univariate function approximation

A damping function $f(x)=\frac{\sin{(5x)}}{5x}$ is used to demonstrate the
approximation performance of single-qubit native QNN models. The dataset
consists of 300 data points uniformly sampled from the interval $[0,\pi]$,
from which 200 are selected for the training set and 100 for the test set.
Since the function $f(x)$ is an even function, we use the QNN model as defined
in Eq. (10). The parameters of trainable gates are initialized from the
uniform distribution on $[0,2\pi]$. We adopt a variational quantum algorithm,
where a gradient-based optimizer is used to search and update parameters in
the QNN. The mean squared error (MSE) serves as the loss function. Here the
Adam optimizer is used with a learning rate of 0.1. We set the training
iterations to be 100 with a batch size of 20 for all experiments.

While approximating a function $f(x)$ by a truncated Fourier series, the
approximation error decreases as the number of expansion terms increases. As
shown in Lemma 3, the frequency spectrum and Fourier coefficients will be
extended by consecutive repetitions of the encoding gate and trainable gate.
The numerical results in Fig. 4 illustrate that the approximation error
decreases as the number of layers increases, which are consistent with our
theoretical analysis.

Figure 4: Panel (a) is the approximation results of
$U^{\textit{YZY}}_{\bm{\theta},L}$ with different $L$. Panel (b) shows the
approximation error. Here the theoretical truncation error is calculated using
the uniform norm $\norm{f_{N}(x)-f(x)}_{\infty}$, where $f_{N}(x)$ is the
truncated Fourier series of $f(x)$ with $N$ terms.

To further show the flexibility and capability of single-qubit QNNs, we pick a
square wave function as the target function. The training set contains 400
data points sampled from the interval $[0,20]$. The numerical results are
illustrated in Fig. 5. By simply repeating 45 layers, the single-qubit QNN
$U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)$ learns the function hidden
beneath the training data. In particular, the approximation works well not
only for input variables located between the training data but also outside of
the region, because the Fourier series has a natural capability in dealing
with periodic functions.

Figure 5: The result of approximating the square wave function by a $45$-layer
QNN $U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)$. For showing periodic
extrapolation, and the test region is extend to $[0,30]$.

###  5.2 Multivariate function approximation

We numerically demonstrate the limitations of single-qubit native QNNs in
approximate multivariate functions. We examine the convergence of the loss as
the number of layers of the circuit increases and compare the outcome with the
target function. Specifically, we consider a bivariate function
$f(x,y)=(x^{2}+y-1.5\pi)^{2}+(x+y^{2}-\pi)^{2}$ as the target function. Note
that $f(x,y)$ is normalized on the interval $[-\pi,\pi]^{2}$, i.e., $-1\leq
f(x,y)\leq 1$.

The training set consists of 400 data points sampled from interval
$[-\pi,\pi]^{2}$. We use the single-qubit QNN with various numbers of layers
defined as Eq. (18) to learn the target function. The experimental setting is
the same as in the univariate function approximation. In order to reduce the
effect of randomness, the experimental results are averaged over 5 independent
training instances.

Fig. 6 shows that the single-qubit native QNN has difficulty in approximating
bivariate functions. The approximation result of QNN as shown in Fig. 6(b) is
quite different from the target function, even for a very deep circuit of $40$
layers. Also, the training loss in Fig. 6(c) does not decrease as the number
of layers increases. Note that the target function is only bivariate here, the
limitations of single-qubit native QNNs will be more obvious in the case of
higher dimensions. We further propose a possible strategy that extends single-
qubit QNNs to multiple qubits, which could potentially overcome the
limitations and handle practical classification tasks, see Appendix C for
details.

((a))

((b))

((c))

Figure 6: Panel (a) is the plot of target function $f(x,y)$. Panel (b) shows
the approximation result of a $40$-layer QNN. Panel (c) is the plot of
training loss for QNNs with different numbers of layers during the
optimization.

##  6 Conclusion and outlook

In this work, we presented a systematic investigation of the expressive power
of single-qubit native QNNs, which are capable to approximate any square-
integrable univariate function with arbitrary precision. We not only give an
existence proof but also analytically show an exact mapping between native
QNNs and the partial Fourier series from perspectives of both frequency
spectrum and Fourier coefficients, which solves an open problem on the UAP of
single-qubit QNNs in Ref. [27]. Our proof, inspired by quantum signal
processing, explicitly illustrates the correlation between parameters of
trainable gates and the Fourier coefficients. Other than the expressivity, we
also discuss the limitation of single-qubit QNNs from the perspective of
multivariate Fourier series. Both the expressivity and limitation of single-
qubit QNNs are validated by numerical simulations. We expect our results
provide a fundamental framework to the class of data re-uploading QNNs, which
serves as insightful guidance on the design of such QNN models.

Although the expressive power of a single-qubit QNN have been well
investigated, it may not be an ideal model in practice due to the potential
limitations on approximating multivariate functions. Moreover, single-qubit
models can be efficiently simulated by classical computers and hence cannot
bring any quantum advantage. Therefore one future step is to generalize the
framework of single-qubit QNNs to multivariate function approximators. The
multi-qubit QNNs with UAP as shown in Ref. [27] require exponential circuit
depth, which is impractical to implement and also does not imply quantum
advantage. It is of great interest to investigate the efficient implementation
of QNNs with universal approximation properties for multivariate functions. A
recent paper presents a method that extends quantum signal processing to
multivariable [38], which might be applicable to single-qubit QNNs.

## Acknowledgments and Disclosure of Funding

We would like to thank Runyao Duan for helpful suggestions on quantum signal
processing. We also thank Guangxi Li, Geng Liu, Youle Wang, Haokai Zhang, Lei
Zhang, and Chengkai Zhu for useful comments. Z. Y., H. Y., and M. L.
contributed equally to this work. Part of this work was done when Z. Y., H.
Y., and M. L. were research interns at Baidu Research.

## References

  * Shor [1997] Peter W. Shor.  Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.  _SIAM Journal on Computing_ , 26(5):1484–1509, oct 1997.  ISSN 0097-5397.  doi: 10.1137/S0097539795293172.  URL http://epubs.siam.org/doi/10.1137/S0097539795293172.
  * Grover [1996] Lov K Grover.  A fast quantum mechanical algorithm for database search.  In _Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC ’96_ , pages 212–219, New York, New York, USA, 1996\. ACM Press.  ISBN 0897917855.  doi: 10.1145/237814.237866.  URL http://portal.acm.org/citation.cfm?doid=237814.237866.
  * Lloyd [1996] Seth Lloyd.  Universal Quantum Simulators.  _Science_ , 273(5278):1073–1078, aug 1996.  ISSN 0036-8075.  doi: 10.1126/science.273.5278.1073.  URL http://www.sciencemag.org/cgi/doi/10.1126/science.273.5278.1073.
  * Childs et al. [2018] Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su.  Toward the first quantum simulation with quantum speedup.  _Proceedings of the National Academy of Sciences_ , 115(38):9456–9461, sep 2018.  ISSN 0027-8424.  doi: 10.1073/pnas.1801723115.  URL http://arxiv.org/abs/1711.10980http://www.pnas.org/lookup/doi/10.1073/pnas.1801723115.
  * Arute et al. [2019] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al.  Quantum supremacy using a programmable superconducting processor.  _Nature_ , 574(7779):505–510, 2019.
  * Wu et al. [2021] Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan.  Strong Quantum Computational Advantage Using a Superconducting Quantum Processor.  _Physical Review Letters_ , 127(18):180501, oct 2021.  ISSN 0031-9007.  doi: 10.1103/PhysRevLett.127.180501.  URL https://link.aps.org/doi/10.1103/PhysRevLett.127.180501.
  * Zhong et al. [2020] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan.  Quantum computational advantage using photons.  _Science_ , 370(6523):1460–1463, dec 2020.  ISSN 0036-8075.  doi: 10.1126/science.abe8770.  URL https://www.science.org/doi/10.1126/science.abe8770.
  * Biamonte et al. [2017] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd.  Quantum machine learning.  _Nature_ , 549(7671):195–202, sep 2017.  ISSN 0028-0836.  doi: 10.1038/nature23474.  URL http://dx.doi.org/10.1038/nature23474http://www.nature.com/articles/nature23474.
  * Cerezo et al. [2021] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles.  Variational quantum algorithms.  _Nature Reviews Physics_ , aug 2021.  ISSN 2522-5820.  doi: 10.1038/s42254-021-00348-9.  URL https://www.nature.com/articles/s42254-021-00348-9.
  * Bharti et al. [2021] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik.  Noisy intermediate-scale quantum (NISQ) algorithms.  _arXiv:2101.08448_ , pages 1–82, jan 2021.  URL http://arxiv.org/abs/2101.08448.
  * Endo et al. [2021] Suguru Endo, Zhenyu Cai, Simon C Benjamin, and Xiao Yuan.  Hybrid Quantum-Classical Algorithms and Quantum Error Mitigation.  _Journal of the Physical Society of Japan_ , 90(3):032001, mar 2021.  ISSN 0031-9015.  doi: 10.7566/JPSJ.90.032001.  URL http://arxiv.org/abs/2011.01382https://journals.jps.jp/doi/10.7566/JPSJ.90.032001.
  * Romero et al. [2017] Jonathan Romero, Jonathan P. Olson, and Alan Aspuru-Guzik.  Quantum autoencoders for efficient compression of quantum data.  _Quantum Science and Technology_ , 2(4):045001, dec 2017.  ISSN 2058-9565.  doi: 10.1088/2058-9565/aa8072.  URL http://stacks.iop.org/2058-9565/2/i=4/a=045001?key=crossref.03b058bfdad4fe46f9a2bc5ffae3961e.
  * Cao and Wang [2021] Chenfeng Cao and Xin Wang.  Noise-Assisted Quantum Autoencoder.  _Physical Review Applied_ , 15(5):054012, may 2021\.  ISSN 2331-7019.  doi: 10.1103/PhysRevApplied.15.054012.  URL http://arxiv.org/abs/2012.08331https://link.aps.org/doi/10.1103/PhysRevApplied.15.054012.
  * Cong et al. [2019] Iris Cong, Soonwon Choi, and Mikhail D. Lukin.  Quantum convolutional neural networks.  _Nature Physics_ , 15(12):1273–1278, dec 2019\.  ISSN 1745-2473.  doi: 10.1038/s41567-019-0648-8.  URL http://arxiv.org/abs/1810.03787http://www.nature.com/articles/s41567-019-0648-8.
  * Li and Deng [2021] Weikang Li and Dong-Ling Deng.  Recent advances for quantum classifiers.  _arXiv:2108.13421_ , aug 2021.  URL http://arxiv.org/abs/2108.13421.
  * Schuld and Petruccione [2021] Maria Schuld and Francesco Petruccione.  _Machine Learning with Quantum Computers_.  Springer, 2021.
  * Li et al. [2021] G. Li, Z. Song, and X. Wang.  VSQL: Variational shadow quantum learning for classification.  In _Proceedings of the AAAI Conference on Artificial Intelligence, 35(9), 8357-8365_ , 2021.
  * Khatri et al. [2018] Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cincio, Andrew T. Sornborger, and Patrick J. Coles.  Quantum-assisted quantum compiling.  _Quantum_ , 3:140, jul 2018.  ISSN 2521-327X.  doi: 10.22331/q-2019-05-13-140.  URL https://quantum-journal.org/papers/q-2019-05-13-140/http://arxiv.org/abs/1807.00800http://dx.doi.org/10.22331/q-2019-05-13-140.
  * Yu et al. [2022] Zhan Yu, Xuanqiang Zhao, Benchi Zhao, and Xin Wang.  Optimal quantum dataset for learning a unitary transformation.  _arXiv preprint arXiv:2203.00546_ , mar 2022.  URL http://arxiv.org/abs/2203.00546.
  * Caro et al. [2022] Matthias C Caro, Hsin-Yuan Huang, Nicholas Ezzell, Joe Gibbs, Andrew T Sornborger, Lukasz Cincio, Patrick J Coles, and Zoë Holmes.  Out-of-distribution generalization for learning quantum dynamics.  _arXiv preprint arXiv:2204.10268_ , apr 2022.  URL http://arxiv.org/abs/2204.10268.
  * McArdle et al. [2020] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan.  Quantum computational chemistry.  _Reviews of Modern Physics_ , 92(1):015003, mar 2020.  ISSN 0034-6861.  doi: 10.1103/RevModPhys.92.015003.  URL https://link.aps.org/doi/10.1103/RevModPhys.92.015003.
  * Koczor et al. [2020] Bálint Koczor, Suguru Endo, Tyson Jones, Yuichiro Matsuzaki, and Simon C Benjamin.  Variational-state quantum metrology.  _New Journal of Physics_ , 22(8):083038, aug 2020\.  ISSN 1367-2630.  doi: 10.1088/1367-2630/ab965e.  URL https://iopscience.iop.org/article/10.1088/1367-2630/ab965e.
  * Beckey et al. [2022] Jacob L. Beckey, M. Cerezo, Akira Sone, and Patrick J. Coles.  Variational quantum algorithm for estimating the quantum Fisher information.  _Physical Review Research_ , 4(1):013083, feb 2022\.  ISSN 2643-1564.  doi: 10.1103/PhysRevResearch.4.013083.  URL https://link.aps.org/doi/10.1103/PhysRevResearch.4.013083.
  * Meyer et al. [2021] Johannes Jakob Meyer, Johannes Borregaard, and Jens Eisert.  A variational toolbox for quantum multi-parameter estimation.  _npj Quantum Information_ , 7(1):89, dec 2021\.  ISSN 2056-6387.  doi: 10.1038/s41534-021-00425-y.  URL http://dx.doi.org/10.1038/s41534-021-00425-yhttp://www.nature.com/articles/s41534-021-00425-y.
  * Cybenko [1989] George Cybenko.  Approximation by superpositions of a sigmoidal function.  _Mathematics of control, signals and systems_ , 2(4):303–314, 1989.  URL https://link.springer.com/article/10.1007/BF02551274.
  * Hornik [1991] Kurt Hornik.  Approximation capabilities of multilayer feedforward networks.  _Neural networks_ , 4(2):251–257, 1991.  URL https://www.sciencedirect.com/science/article/abs/pii/089360809190009T.
  * Schuld et al. [2021] Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer.  Effect of data encoding on the expressive power of variational quantum-machine-learning models.  _Physical Review A_ , 103(3):032430, 2021.  URL https://doi.org/10.1103/PhysRevA.103.032430.
  * Goto et al. [2021] Takahiro Goto, Quoc Hoan Tran, and Kohei Nakajima.  Universal approximation property of quantum machine learning models in quantum-enhanced feature spaces.  _Physical Review Letters_ , 127(9):090506, 2021\.  URL https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.127.090506.
  * Pérez-Salinas et al. [2021] Adrián Pérez-Salinas, David López-Núñez, Artur Garc\́mathbf{i}a-Sáez, Pol Forn-D\́mathbf{i}az, and José I Latorre.  One qubit as a universal approximant.  _Physical Review A_ , 104(1):012405, 2021.  URL https://journals.aps.org/pra/abstract/10.1103/PhysRevA.104.012405.
  * 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, February 2020.  doi: 10.22331/q-2020-02-06-226.
  * Jerbi et al. [2022] Sofiene Jerbi, Lukas J. Fiderer, Hendrik Poulsen Nautrup, Jonas M. Kübler, Hans J. Briegel, and Vedran Dunjko.  Quantum machine learning beyond kernel methods.  _arXiv:2110.13162 [quant-ph, stat]_ , February 2022.
  * Low and Chuang [2017] Guang Hao Low and Isaac L. Chuang.  Optimal hamiltonian simulation by quantum signal processing.  _Physical Review Letters_ , 118(1):010501, January 2017.  doi: 10.1103/PhysRevLett.118.010501.
  * Haah [2019] Jeongwan Haah.  Product decomposition of periodic functions in quantum signal processing.  _Quantum_ , 3:190, October 2019.  ISSN 2521-327X.  doi: 10.22331/q-2019-10-07-190.
  * Gilyén et al. [2019] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.  Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics.  _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , pages 193–204, June 2019.  doi: 10.1145/3313276.3316366.
  * Chao et al. [2020] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, and Mario Szegedy.  Finding Angles for Quantum Signal Processing with Machine Precision, March 2020.
  * Silva et al. [2022] Thais de Lima Silva, Lucas Borges, and Leandro Aolita.  Fourier-based quantum signal processing.  June 2022.  doi: 10.48550/arXiv.2206.02826.
  * Wang et al. [2022] Xin Wang, Youle Wang, Zhan Yu, and Lei Zhang.  Quantum Phase Processing: Transform and Extract Eigen-Information of Quantum Systems, September 2022.
  * Rossi and Chuang [2022] Zane M. Rossi and Isaac L. Chuang.  Multivariable quantum signal processing (m-qsp): Prophecies of the two-headed oracle.  (arXiv:2205.06261), May 2022.
  * Weisz [2012] Ferenc Weisz.  Summability of multi-dimensional trigonometric fourier series.  _arXiv preprint arXiv:1206.1789_ , 2012.
  * Zhang et al. [2003] Jun Zhang, Jiri Vala, Shankar Sastry, and K. Birgitta Whaley.  Exact Two-Qubit Universal Quantum Circuit.  _Physical Review Letters_ , 91(2):027903, July 2003.  doi: 10.1103/PhysRevLett.91.027903.
  * Vidal and Dawson [2004] G. Vidal and C. M. Dawson.  Universal quantum circuit for two-qubit transformations with three controlled-NOT gates.  _Physical Review A_ , 69(1):010301, January 2004\.  doi: 10.1103/PhysRevA.69.010301.
  * Fisher [1936] Ronald A Fisher.  The use of multiple measurements in taxonomic problems.  _Annals of eugenics_ , 7(2):179–188, 1936.
  * Michalski et al. [1986] Ryszard S Michalski, Igor Mozetic, Jiarong Hong, and Nada Lavrac.  The multi-purpose incremental learning system aq15 and its testing application to three medical domains.  In _Proc. AAAI_ , volume 1986, pages 1–041, 1986.
  * Lyon et al. [2016] Robert J Lyon, BW Stappers, Sally Cooper, John Martin Brooke, and Joshua D Knowles.  Fifty years of pulsar candidate selection: from simple filters to a new principled real-time classification approach.  _Monthly Notices of the Royal Astronomical Society_ , 459(1):1104–1123, 2016.

Appendix for Power and limitations of single-qubit native quantum neural
networks

##  Appendix A Detailed Proofs

###  A.1 Proof of Lemma 1

###### Lemma S1

There exist
$\bm{\theta}=(\theta_{0},\theta_{1},\ldots,\theta_{L})\in{{\mathbb{R}}}^{L+1}$
such that

$U_{\bm{\theta},L}^{\textit{YZY}}(x)=\begin{bmatrix}P(x)&-Q(x)\\\
Q^{*}(x)&P^{*}(x)\end{bmatrix}$ (S1)

if and only if real Laurent polynomials
$P,Q\in{{\mathbb{R}}}[e^{ix/2},e^{-ix/2}]$ satisfy

  1. 1.

$\deg(P)\leq L$ and $\deg(Q)\leq L$,

  2. 2.

$P$ and $Q$ have parity $L\bmod 2$,

  3. 3.

$\forall x\in{{\mathbb{R}}}$,
$\absolutevalue{P(x)}^{2}+\absolutevalue{Q(x)}^{2}=1$.

###### Proof.

First we prove the forward direction, i.e. Eq. (S1) implies the three
conditions, by induction on $L$. For the base case, if $L=0$, then
$R_{Y}(\theta_{0})$ gives $P=\cos(\theta_{0}/2)$ and $Q=\sin(\theta_{0}/2)$,
which clearly satisfies the conditions.

For the induction step, suppose Eq. (S1) satisfies the three conditions. Then

$\displaystyle\begin{bmatrix}P&-Q\\\
Q^{*}&P^{*}\end{bmatrix}R_{Z}(x)R_{Y}(\theta_{k})$ (S2)
$\displaystyle=\begin{bmatrix}P&-Q\\\
Q^{*}&P^{*}\end{bmatrix}\begin{bmatrix}\cos(\theta_{k}/2)e^{-ix/2}&-\sin(\theta_{k}/2)e^{-ix/2}\\\
\sin(\theta_{k}/2)e^{ix/2}&\cos(\theta_{k}/2)e^{ix/2}\end{bmatrix}$ (S3)
$\displaystyle=\begin{bmatrix}\cos\frac{\theta_{k}}{2}e^{-ix/2}P-\sin\frac{\theta_{k}}{2}e^{ix/2}Q&-\sin\frac{\theta_{k}}{2}e^{-ix/2}P-\cos\frac{\theta_{k}}{2}e^{ix/2}Q\\\
\cos\frac{\theta_{k}}{2}e^{-ix/2}Q^{*}+\sin\frac{\theta_{k}}{2}e^{ix/2}P^{*}&\cos\frac{\theta_{k}}{2}e^{ix/2}P^{*}-\sin\frac{\theta_{k}}{2}e^{-ix/2}Q^{*}\end{bmatrix}$
(S4) $\displaystyle=\begin{bmatrix}\bar{P}&-\bar{Q}\\\
\bar{Q}^{*}&\bar{P}^{*}\end{bmatrix}$ (S5)

where

$\displaystyle\bar{P}$
$\displaystyle=\cos\frac{\theta_{k}}{2}e^{-ix/2}P-\sin\frac{\theta_{k}}{2}e^{ix/2}Q,$
(S6) $\displaystyle\bar{Q}$
$\displaystyle=\sin\frac{\theta_{k}}{2}e^{-ix/2}P+\cos\frac{\theta_{k}}{2}e^{ix/2}Q$
(S7)

clearly satisfy the first condition: $\deg(\bar{P})\leq L+1$ and
$\deg(\bar{Q})\leq L+1$. They also satisfy the second condition since
multiplying by $e^{-ix/2}$ or $e^{ix/2}$ alters the parity. The third
condition follows from unitarity.

Next we show the reverse by induction on $L$ that the three conditions suffice
to construct the QNN in Eq. (S1). For the base case, we have $L=0$ and
$\deg(P)=\deg(Q)=0$. Note that $P$ and $Q$ are real polynomials, i.e. the
coefficients must be real numbers, so condition 3 implies that
$P=\cos(\theta_{0}/2)$ and $Q=\sin(\theta_{0}/2)$ for some
$\theta_{0}\in{{\mathbb{R}}}$. Thus the matrix

$\begin{bmatrix}P&-Q,\\\ Q^{*}&P^{*}\end{bmatrix}$ (S8)

can be written as a QNN
$U_{\bm{\theta},0}^{\textit{YZY}}(x)=R_{Y}(\theta_{0})$.

For the induction step, suppose Laurent polynomials $P$ and $Q$ satisfy the
three conditions for some $L>0$. We first observe that condition 3 implies

$\absolutevalue{P}^{2}+\absolutevalue{Q}^{2}=PP^{*}+QQ^{*}=1,$ (S9)

where $PP^{*}+QQ^{*}$ is a Laurent polynomial of $e^{ix/2}$ with parity
$2n\pmod{2}\equiv 0$. We denote $d\coloneqq\max(\deg(P),\deg(Q))$, then $d\leq
L$ by the first condition. Since Eq. (S9) holds for all $x\in{{\mathbb{R}}}$,
the leading coefficients must satisfy $p_{d}p_{-d}+q_{d}q_{-d}=0$ so they
cancel. We choose $\theta_{k}\in{{\mathbb{R}}}$ so that

$\displaystyle\cos\frac{\theta_{k}}{2}p_{d}+\sin\frac{\theta_{k}}{2}q_{d}$
$\displaystyle=0,$ (S10)
$\displaystyle-\sin\frac{\theta_{k}}{2}p_{-d}+\cos\frac{\theta_{k}}{2}q_{-d}$
$\displaystyle=0.$ (S11)

Now we briefly argue that there always exists a $\theta_{k}$ satisfies
equations above. If all $p_{d},p_{-d},q_{d},q_{-d}$ are not $0$, simply let
$\tan\frac{\theta_{k}}{2}=-\frac{p_{d}}{q_{d}}$. Then consider the case of
zero coefficients. Since $d=\max(\deg(P),\deg(Q))$, at most two of
$p_{d},p_{-d},q_{d},q_{-d}$ could be $0$. The fact $p_{d}p_{-d}+q_{d}q_{-d}=0$
implies that one of $p_{d},p_{-d}$ is $0$ if and only if one of $q_{d},q_{-d}$
is $0$. If $p_{d}=q_{d}=0$ (or $p_{-d}=q_{-d}=0$), pick $\theta_{k}$ so that
$\tan\frac{\theta_{k}}{2}=\frac{q_{-d}}{p_{-d}}$ (or
$\tan\frac{\theta_{k}}{2}=-\frac{p_{d}}{q_{d}}$). If $p_{d}=q_{-d}=0$ (or
$p_{-d}=q_{d}=0$), pick $\theta_{k}$ so that $\sin\frac{\theta_{k}}{2}=0$ (or
$\cos\frac{\theta_{k}}{2}=0$).

Next, for the $\theta_{k}$ that satisfies Eq. (S10) and Eq. (S11)
simultaneously, we consider

$\displaystyle\begin{bmatrix}P&-Q\\\
Q^{*}&P^{*}\end{bmatrix}R_{Y}^{\dagger}(\theta_{k})R_{Z}^{\dagger}(x)$ (S12)
$\displaystyle=\begin{bmatrix}\cos\frac{\theta_{k}}{2}e^{ix/2}P+\sin\frac{\theta_{k}}{2}e^{ix/2}Q&-\cos\frac{\theta_{k}}{2}e^{-ix/2}Q+\sin\frac{\theta_{k}}{2}e^{-ix/2}P\\\
\cos\frac{\theta_{k}}{2}e^{ix/2}Q^{*}-\sin\frac{\theta_{k}}{2}e^{ix/2}P^{*}&\cos\frac{\theta_{k}}{2}e^{-ix/2}P^{*}+\sin\frac{\theta_{k}}{2}e^{-ix/2}Q\end{bmatrix}$
(S13) $\displaystyle=\begin{bmatrix}\hat{P}&-\hat{Q}\\\
\hat{Q}^{*}&\hat{P}^{*}\end{bmatrix}$ (S14)

where

$\displaystyle\hat{P}$
$\displaystyle=\cos\frac{\theta_{k}}{2}e^{ix/2}P+\sin\frac{\theta_{k}}{2}e^{ix/2}Q,$
(S15) $\displaystyle\hat{Q}$
$\displaystyle=\cos\frac{\theta_{k}}{2}e^{-ix/2}Q-\sin\frac{\theta_{k}}{2}e^{-ix/2}P.$
(S16)

Since $P,Q\in{{\mathbb{R}}}[e^{ix/2},e^{-ix/2}]$ are Laurent polynomials with
degree at most $d$, $\hat{P}\in{{\mathbb{R}}}[e^{ix/2},e^{-ix/2}]$ might
appear to be a Laurent polynomial with degree $d+1$. In fact it has degree
$\deg(\hat{P})\leq d-1$, because the coefficient of $(e^{ix/2})^{d+1}$ term in
$\hat{P}$ is $\cos\frac{\theta_{k}}{2}p_{d}+\sin\frac{\theta_{k}}{2}q_{d}=0$
by the choice of $\theta_{k}$, and the coefficient of $(e^{ix/2})^{d}$ term is
0 by condition 2. Similarly, $\hat{Q}$ has leading coefficient
$\cos\frac{\theta_{k}}{2}q_{-d}-\sin\frac{\theta_{k}}{2}p_{-d}=0$ and has
degree $\deg(\hat{Q})\leq d-1$. Since $d\leq L$, we have $\deg(\hat{P})\leq
L-1$ and $\deg(\hat{Q})\leq L-1$, hence condition 1 is satisfied. From the
parity of $P$ and $Q$, it is easy to see that $\hat{P}$ and $\hat{Q}$ have
parity $L-1\bmod 2$, thus condition 2 is satisfied. Condition 3 follows from
unitarity. By the induction hypothesis, Eq. (S14) can be written as a QNN in
the form of $U_{\bm{\theta},L-1}^{\textit{YZY}}(x)$, and therefore the matrix

$\begin{bmatrix}P&-Q\\\ Q^{*}&P^{*}\end{bmatrix}$ (S17)

can be written as a QNN in the form of $U_{\bm{\theta},L}^{\textit{YZY}}(x)$.
∎

We note that the above proof is in a similar spirit of the proof of quantum
signal processing [32, 33, 34, 35].

###  A.2 Proof of Proposition 2

###### Proposition 2

For any even square-integrable function $f:[-\pi,\pi]\to[-1,1]$ and for all
$\epsilon>0$, there exists a QNN $U_{\bm{\theta},L}^{\textit{YZY}}(x)$ such
that $\ket{\psi(x)}=U_{\bm{\theta},L}^{\textit{YZY}}(x)\ket{0}$ satisfies

$\norm{\expectationvalue{Z}{\psi(x)}-f(x)}\leq\epsilon.$ (S18)

###### Proof.

First, it is known that any even square-integrable function $f(x)$ can be
approximated by a truncated Fourier series [39]. For any $\epsilon>0$, there
exists a $K\in{{\mathbb{N}}}^{+}$ such that

$\displaystyle\norm{f_{K}(x)-f(x)}\leq\frac{\epsilon}{2},$ (S19)

where $f_{K}(x)$ is the $K$-term partial Fourier series of even function
$f(x)$. Consider the function $\sqrt{\frac{1+f_{K}(x)}{2}}$, using the
property of square-integrable functions again, there exists an
$L\in{{\mathbb{N}}}^{+}$ such that

$\displaystyle\norm{g_{L}(x)-\sqrt{\frac{1+f_{K}(x)}{2}}}\leq\frac{\epsilon}{8},$
(S20)

where

$\displaystyle g_{L}(x)=a_{0}+\sum_{n=1}^{L/2}a_{n}\cos{(nx)}$ (S21)

is the partial Fourier series of the even function
$\sqrt{\frac{1+f_{K}(x)}{2}}$ and $L\pmod{2}\equiv 0$. Next we need to prove

$\displaystyle\expectationvalue{U_{\bm{\theta},L}^{\textit{YZY}}(x)}{0}=g_{L}(x).$
(S22)

Specifically, $g_{L}(x)$ can be written as follows,

$\displaystyle
g_{L}(x)=\sum_{n=-L/2}^{L/2}c_{n}e^{inx}=\sum_{n=-L/2}^{L/2}c_{n}(e^{ix/2})^{2n},$
(S23)

where $c_{n}=c_{-n}=a_{n}/2$. Obviously,
$g_{L}\in{{\mathbb{R}}}[e^{ix/2},e^{-ix/2}]$ and conditions of Lemma 1 are
satisfied, so Eq. (S22) holds. Further, we have

$\displaystyle\norm{\expectationvalue{Z}{\psi(x)}-f_{K}(x)}$
$\displaystyle=2\norm{g^{2}_{L}(x)-\frac{1+f_{K}(x)}{2}},$ (S24)
$\displaystyle\leq 4\norm{g_{L}(x)-\sqrt{\frac{1+f_{K}(x)}{2}}},$ (S25)
$\displaystyle\leq\frac{\epsilon}{2},$ (S26)

where $\norm{g_{L}(x)}\leq 1$ and $\norm{\sqrt{\frac{1+f_{K}(x)}{2}}}\leq 1$.
Finally, combined with inequality (S19), inequality (S18) holds. ∎

###  A.3 Proof of Lemma 3

###### Lemma 2

There exist
$\bm{\theta}=(\theta_{0},\theta_{1},\ldots,\theta_{L})\in{{\mathbb{R}}}^{L+1}$
and
$\bm{\phi}=(\varphi,\phi_{0},\phi_{1},\ldots,\phi_{L})\in{{\mathbb{R}}}^{L+2}$
such that

$U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)=\begin{bmatrix}P(x)&-Q(x)\\\
Q^{*}(x)&P^{*}(x)\end{bmatrix}$ (S27)

if and only if Laurent polynomials $P,Q\in{{\mathbb{C}}}[e^{ix/2},e^{-ix/2}]$
satisfy

  1. 1.

$\deg(P)\leq L$ and $\deg(Q)\leq L$,

  2. 2.

$P$ and $Q$ have parity $L\bmod 2$,

  3. 3.

$\forall x\in{{\mathbb{R}}}$,
$\absolutevalue{P(x)}^{2}+\absolutevalue{Q(x)}^{2}=1$.

###### Proof.

The entire proof is similar as the proof of Lemma 1, and the only difference
is that the coefficients of Laurent polynomials could be complex rather than
real. First we prove the forward direction by induction on $L$. For the base
case, if $L=0$, then
$U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)=R_{Z}(\varphi)R_{Y}(\theta_{0})R_{Z}(\phi_{0})$
gives $P=e^{-i(\varphi+\phi_{0})/2}\cos(\theta_{0}/2)$ and
$Q=e^{-i(\varphi-\phi_{0})/2}\sin(\theta_{0}/2)$, which clearly satisfies the
three conditions.

For the induction step, suppose Eq. (S27) satisfies the three conditions. Then

$\displaystyle\begin{bmatrix}P&-Q\\\
Q^{*}&P^{*}\end{bmatrix}R_{Z}(x)R_{Y}(\theta_{k})R_{Z}(\phi_{k})$ (S28)
$\displaystyle=\begin{bmatrix}P&-Q\\\
Q^{*}&P^{*}\end{bmatrix}\begin{bmatrix}\cos\frac{\theta_{k}}{2}e^{-i\frac{\phi_{k}}{2}}e^{-i\frac{x}{2}}&-\sin\frac{\theta_{k}}{2}e^{i\frac{\phi_{k}}{2}}e^{-i\frac{x}{2}}\\\
\sin\frac{\theta_{k}}{2}e^{-i\frac{\phi_{k}}{2}}e^{i\frac{x}{2}}&\cos\frac{\theta_{k}}{2}e^{i\frac{\phi_{k}}{2}}e^{i\frac{x}{2}}\end{bmatrix}$
(S29)
$\displaystyle=\begin{bmatrix}\cos\frac{\theta_{k}}{2}e^{-i\frac{\phi_{k}}{2}}e^{-i\frac{x}{2}}P-\sin\frac{\theta_{k}}{2}e^{-i\frac{\phi_{k}}{2}}e^{i\frac{x}{2}}Q&-\sin\frac{\theta_{k}}{2}e^{i\frac{\phi_{k}}{2}}e^{-i\frac{x}{2}}P-\cos\frac{\theta_{k}}{2}e^{i\frac{\phi_{k}}{2}}e^{i\frac{x}{2}}Q\\\
\cos\frac{\theta_{k}}{2}e^{-i\frac{\phi_{k}}{2}}e^{-i\frac{x}{2}}Q^{*}+\sin\frac{\theta_{k}}{2}e^{-i\frac{\phi_{k}}{2}}e^{i\frac{x}{2}}P^{*}&\cos\frac{\theta_{k}}{2}e^{i\frac{\phi_{k}}{2}}e^{i\frac{x}{2}}P^{*}-\sin\frac{\theta_{k}}{2}e^{i\frac{\phi_{k}}{2}}e^{-i\frac{x}{2}}Q^{*}\end{bmatrix}$
(S30) $\displaystyle=\begin{bmatrix}\bar{P}&-\bar{Q}\\\
\bar{Q}^{*}&\bar{P}^{*}\end{bmatrix}$ (S31)

where

$\displaystyle\bar{P}$
$\displaystyle=\cos\frac{\theta_{k}}{2}e^{-i\frac{\phi_{k}}{2}}e^{-i\frac{x}{2}}P-\sin\frac{\theta_{k}}{2}e^{-i\frac{\phi_{k}}{2}}e^{i\frac{x}{2}}Q,$
(S32) $\displaystyle\bar{Q}$
$\displaystyle=\sin\frac{\theta_{k}}{2}e^{i\frac{\phi_{k}}{2}}e^{-i\frac{x}{2}}P+\cos\frac{\theta_{k}}{2}e^{i\frac{\phi_{k}}{2}}e^{i\frac{x}{2}}Q$
(S33)

clearly satisfy the first condition: $\deg(\bar{P})\leq L+1$ and
$\deg(\bar{Q})\leq L+1$. They also satisfy the second condition since
multiplying by $e^{-ix/2}$ or $e^{ix/2}$ alters the parity. The third
condition is satisfied because of unitarity.

Next we show the backward direction by induction on $L$ that the three
conditions suffice to construct the QNN in Eq. (S27). First we consider the
base case of $L=0$, we have $\deg(P)=\deg(Q)=0$, the above condition implies
that $P=e^{-i(\varphi+\phi_{0})/2}\cos(\theta_{0}/2)$ and
$Q=e^{-i(\varphi-\phi_{0})/2}\sin(\theta_{0}/2)$ for some
$\varphi,\theta_{0},\phi_{0}\in{{\mathbb{R}}}$. Thus the matrix

$\begin{bmatrix}P&-Q,\\\ Q^{*}&P^{*}\end{bmatrix}$ (S34)

can be written as a QNN
$U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)=R_{Z}(\varphi)R_{Y}(\theta_{0})R_{Z}(\phi_{0})$.

For the induction step, suppose Laurent polynomials $P$ and $Q$ satisfy the
three conditions for some $L>0$. We first observe that condition 3 implies

$\absolutevalue{P}^{2}+\absolutevalue{Q}^{2}=PP^{*}+QQ^{*}=1,$ (S35)

where $PP^{*}+QQ^{*}$ is a Laurent polynomial of $e^{ix/2}$ with parity
$2n\pmod{2}\equiv 0$. Since Eq. (S35) holds for all $x\in{{\mathbb{R}}}$, the
leading coefficients must satisfy $p_{d}p_{-d}^{*}+q_{d}q_{-d}^{*}=0$ and
$p_{d}^{*}p_{-d}+q_{d}^{*}q_{-d}=0$, where $d\coloneqq\max(\deg(P),\deg(Q))$.
By the first condition, we have $d\leq L$. We choose
$\theta_{k},\phi_{k}\in\mathbb{R}$ so that

$\displaystyle\cos{\frac{\theta_{k}}{2}}e^{i\frac{\phi_{k}}{2}}p_{d}+\sin{\frac{\theta_{k}}{2}}e^{-i\frac{\phi_{k}}{2}}q_{d}$
$\displaystyle=0,$ (S36)
$\displaystyle-\sin{\frac{\theta_{k}}{2}}e^{i\frac{\phi_{k}}{2}}p_{-d}+\cos{\frac{\theta_{k}}{2}}e^{-i\frac{\phi_{k}}{2}}q_{-d}$
$\displaystyle=0.$ (S37)

Now we briefly argue that there always exists $\theta_{k}$ and $\phi_{k}$
satisfy equations above. If all $p_{d},p_{-d},q_{d},q_{-d}$ are not zero,
simply let $\tan(\frac{\theta_{k}}{2})e^{-i\phi_{k}}=-\frac{p_{d}}{q_{d}}$.
Then consider the case of zero coefficients. Since $\deg(P)=\deg(Q)=d$, at
most two of $p_{d},p_{-d},q_{d},q_{-d}$ could be 0. The fact
$p_{d}p_{-d}^{*}+q_{d}q_{-d}^{*}=0$ implies that one of one of $p_{d},p_{-d}$
is 0 if and only if one of $q_{d},q_{-d}$ is 0. If $p_{d}=q_{d}=0$ (or
$p_{-d}=q_{-d}=0$), pick $\theta_{k}$ and $\phi_{k}$ so that
$\tan{(\frac{\theta_{k}}{2})}e^{i\phi_{k}}=\frac{q_{-d}}{p_{-d}}$. If
$p_{d}=q_{-d}=0$ or ($p_{-d}=q_{d}=0$), pick $\theta_{k}$ so that
$\sin{(\frac{\theta_{k}}{2})}=0$ (or $\cos{(\frac{\theta_{k}}{2})}=0$).

Next, for the $\theta_{k}$ that we pick, consider

$\displaystyle\begin{bmatrix}P&-Q\\\
Q^{*}&P^{*}\end{bmatrix}W^{\dagger}(\theta_{k},\phi_{k})R_{Z}^{\dagger}(x)$
(S38)
$\displaystyle=\begin{bmatrix}e^{i\frac{\phi_{k}}{2}}\cos\frac{\theta_{k}}{2}e^{i\frac{x}{2}}P+e^{-i\frac{\phi_{k}}{2}}\sin\frac{\theta_{k}}{2}e^{i\frac{x}{2}}Q&e^{i\frac{\phi_{k}}{2}}\sin\frac{\theta_{k}}{2}e^{-i\frac{x}{2}}P-e^{-i\frac{\phi_{k}}{2}}\cos\frac{\theta_{k}}{2}e^{-i\frac{x}{2}}Q\\\
e^{i\frac{\phi_{k}}{2}}\cos\frac{\theta_{k}}{2}e^{i\frac{x}{2}}Q^{*}-e^{-i\frac{\phi_{k}}{2}}\sin\frac{\theta_{k}}{2}e^{i\frac{x}{2}}P^{*}&e^{-i\frac{\phi_{k}}{2}}\cos\frac{\theta_{k}}{2}e^{-i\frac{x}{2}}P^{*}+e^{i\frac{\phi_{k}}{2}}\sin\frac{\theta_{k}}{2}e^{-i\frac{x}{2}}Q^{*}\end{bmatrix}$
(S39) $\displaystyle=\begin{bmatrix}\hat{P}&-\hat{Q}\\\
\hat{Q}^{*}&\hat{P}^{*}\end{bmatrix}$ (S40)

where

$\displaystyle\hat{P}$
$\displaystyle=e^{i\frac{\phi_{k}}{2}}\cos\frac{\theta_{k}}{2}e^{i\frac{x}{2}}P+e^{-i\frac{\phi_{k}}{2}}\sin\frac{\theta_{k}}{2}e^{i\frac{x}{2}}Q,$
(S41) $\displaystyle\hat{Q}$
$\displaystyle=e^{-i\frac{\phi_{k}}{2}}\cos\frac{\theta_{k}}{2}e^{-i\frac{x}{2}}Q-e^{i\frac{\phi_{k}}{2}}\sin\frac{\theta_{k}}{2}e^{-i\frac{x}{2}}P.$
(S42)

Since $P,Q\in{{\mathbb{C}}}[e^{ix/2},e^{-ix/2}]$ are Laurent polynomials with
degree at most $d$, $\hat{P}\in{{\mathbb{R}}}[e^{ix/2},e^{-ix/2}]$ might
appear to be a Laurent polynomial with degree at most $d+1$. In fact it has
degree $\deg(\hat{P})\leq d-1$, because the coefficient of
$(e^{i\frac{x}{2}})^{d+1}$ term in $\hat{P}$ is
$\cos{\frac{\theta_{k}}{2}}e^{i\frac{\phi_{k}}{2}}p_{d}+\sin{\frac{\theta_{k}}{2}}e^{-i\frac{\phi_{k}}{2}}q_{d}=0$
by the selected $\theta_{k}$ and $\phi_{k}$, and the coefficients of
$(e^{\frac{ix}{2}})^{d}$ term is 0 by condition 2. Similarly, $\hat{Q}$ has
leading coefficient
$-\sin{\frac{\theta_{k}}{2}}e^{i\frac{\phi_{k}}{2}}p_{-d}+\cos{\frac{\theta_{k}}{2}}e^{-i\frac{\phi_{k}}{2}}q_{-d}=0$
and has degree $\deg(\hat{Q})\leq d-1$. Since $d\leq L$, we have
$\deg(\hat{P})\leq L-1$ and $\deg(\hat{Q})\leq L-1$, hence condition 1 is
satisfied. From the parity of $P$ and $Q$, it is easy to see that $\hat{P}$
and $\hat{Q}$ have parity $L-1\bmod{2}$, thus condition 2 is satisfied.
Condition 3 follows from unitarity. Thus by the induction hypothesis, Eq.
(S40) can be written as a QNN in the form of
$U_{\bm{\theta},\bm{\phi},L-1}^{\textit{WZW}}(x)$, and therefore the matrix

$\begin{bmatrix}P&-Q\\\ Q^{*}&P^{*}\end{bmatrix}$ (S43)

can be written as a QNN in the form of
$U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)$. ∎

###  A.4 Proof of Theorem 4

######  Theorem 2 (Univariate approximation properties of single-qubit QNNs.)

For any univariate square-integrable function $f:[-\pi,\pi]\to[-1,1]$ and for
all $\epsilon>0$, there exists a QNN
$U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)$ such that
$\ket{\psi(x)}=U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)\ket{0}$ satisfies

$\norm{\expectationvalue{Z}{\psi(x)}-f(x)}\leq\epsilon.$ (S44)

###### Proof.

Similar as in the proof of Proposition 2, we use the fact that square-
integrable functions $f$ can be approximated by a truncated Fourier series.
Then, there exists a $K\in{{\mathbb{N}}}^{+}$ such that

$\displaystyle\norm{f_{K}(x)-f(x)}\leq\frac{\epsilon}{2},$ (S45)

where $f_{K}(x)$ is the $K$-term truncated Fourier series of $f(x)$. Consider
the function $\sqrt{\frac{1+f_{K}(x)}{2}}$, using the property of square-
integrable functions again, there exists an $L\in{{\mathbb{N}}}^{+}$ such that

$\displaystyle\norm{g_{L}(x)-\sqrt{\frac{1+f_{K}(x)}{2}}}\leq\frac{\epsilon}{8},$
(S46)

where

$\displaystyle g_{L}(x)=\sum_{n=-L/2}^{L/2}c_{n}e^{inx}$ (S47)

is the partial Fourier series of function $\sqrt{\frac{1+f_{K}(x)}{2}}$ and
$L\pmod{2}\equiv 0$. Next we need to prove

$\displaystyle\expectationvalue{U_{\bm{\theta},\bm{\phi},L}^{\textit{WZW}}(x)}{0}=g_{L}(x).$
(S48)

Specifically, $g_{L}(x)$ can be written as follows

$\displaystyle g_{L}(x)=\sum_{n=-L/2}^{L/2}c_{n}(e^{ix/2})^{2n}.$ (S49)

Obviously, $g_{L}\in{{\mathbb{C}}}[e^{ix/2},e^{-ix/2}]$ and conditions of
Lemma 3 are satisfied, thus Eq. (S48) holds. Further, we have

$\displaystyle\norm{\expectationvalue{Z}{\psi(x)}-f_{K}(x)}\leq\frac{\epsilon}{2}.$
(S50)

Finally, combined with inequality (S45), the inequality (S44) holds. ∎

##  Appendix B Limitations on representing multivariate Fourier series

In this section, we show that if the single-qubit native QNN is written in the
form of a $K$-truncated multivariate Fourier series, it has a rich Fourier
frequency set $\Omega$, but it cannot meet the requirements of the
corresponding Fourier coefficients set $C_{\Omega}$ due to the curse of
dimensionality. Specifically, let
$\bm{x}\coloneqq(x^{(1)},x^{(2)},\ldots,x^{(d)})\in{{\mathbb{R}}}^{d}$ and the
single-qubit native QNN is defined as follows:

$\displaystyle
U_{\bm{\theta},L}(\bm{x})=U_{3}(\theta_{0},\phi_{0},\lambda_{0})\prod_{j=1}^{L}R_{Z}(x_{j})U_{3}(\theta_{j},\phi_{j},\lambda_{j}),$
(S51)

where $x_{j}$ is a one-dimensional data of $\bm{x}$, i.e.,
$x_{j}\in\\{x^{(m)}\mid m=1,\cdots,d\\}$. The quantum circuit is shown in Fig.
B.

Figure S1: Circuit of $U_{\bm{\theta},L}(\bm{x})$, where the trainable block
is composed of $U_{3}(\cdot)$, and the encoding block is $R_{Z}(\cdot)$. Note
that there is no restriction on the encoding order of $x^{(m)}$.

Without loss of generality, assume that each one-dimensional data $x^{(m)}$ is
uploaded the same number of times, denoted by $K$, then we have $Kd=L$.
Further, we write $V_{j}\coloneqq U_{3}(\theta_{j},\phi_{j},\lambda_{j})$ for
short, that is

$\displaystyle
U_{\bm{\theta},L}(\bm{x})=V_{0}\prod_{j=1}^{L}\begin{bmatrix}e^{-ix_{j}\lambda_{0}}&0\\\
0&e^{-ix_{j}\lambda_{1}}\end{bmatrix}V_{j},$ (S52)

where $\lambda_{0}=\frac{1}{2}$ and $\lambda_{1}=-\frac{1}{2}$. More
generally, we have

$\displaystyle
U_{\bm{\theta},L}(\bm{x})=\sum_{j_{1},\cdots,j_{L}=0}^{1}e^{-i(\lambda_{j_{1}}x_{1}+\cdots+\lambda_{j_{L}}x_{L})}\,V_{0}\outerproduct{j_{1}}{j_{1}}V_{1}\cdots\outerproduct{j_{L}}{j_{L}}V_{L}.$
(S53)

Next, we reformulate the above equation using $x^{(m)}$ instead of $x_{j}$. We
denote $I_{m}\subset\\{1,\cdots,L\\}$ as the index set of encoding block
$R_{Z}(x^{(m)})$ and $I^{\prime}_{m}=\\{\lambda_{j_{k}}\mid k\in I_{m}\\}$,
then

$\displaystyle
U_{\bm{\theta},L}(\bm{x})=\sum_{\bm{j}\in\\{0,1\\}^{L}}e^{-i(\Lambda_{\bm{j}}^{(1)}x^{(1)}+\cdots+\Lambda_{\bm{j}}^{(d)}x^{(d)})}\,V_{0}\outerproduct{j_{1}}{j_{1}}V_{1}\cdots\outerproduct{j_{L}}{j_{L}}V_{L},$
(S54)

where $\bm{j}$ is bit-strings composed of $j_{l}$, $l=1,\cdots,L$ and
$\Lambda_{\bm{j}}^{(m)}=\sum\lambda$, $\lambda\in I^{\prime}_{m}$. Further,
for the initial state $\ket{0}$ and some observable $M$, we have

$\displaystyle
f_{\bm{\theta},L}(\bm{x})=\bra{0}U_{\bm{\theta},L}^{\dagger}(\bm{x})MU_{\bm{\theta},L}(\bm{x})\ket{0}=\sum_{\bm{\omega}\in\Omega}c_{\bm{\omega}}e^{i\bm{\omega}\cdot\bm{x}},$
(S55)

where
$\Omega=\\{h_{\bm{j,k}}\coloneqq(\Lambda_{\bm{k}}^{(1)}-\Lambda_{\bm{j}}^{(1)},\cdots,\Lambda_{\bm{k}}^{(d)}-\Lambda_{\bm{j}}^{(d)})\mid\bm{j,k}\in\\{0,1\\}^{L}\\}$.
We consider the $m$-th dimension,

$\displaystyle\Lambda_{\bm{k}}^{(m)}-\Lambda_{\bm{j}}^{(m)}=\\{(\lambda_{k_{1}}+\cdots+\lambda_{k_{K}})-(\lambda_{j_{1}}+\cdots+\lambda_{j_{K}})\mid\lambda_{k_{1}}\cdots\lambda_{k_{K}},\lambda_{j_{1}}\cdots\lambda_{j_{K}}\in
I^{\prime}_{m}\\}.$ (S56)

Since $\lambda=\pm\frac{1}{2}$, for all $\lambda\in I_{m}^{\prime}$, we can
derive

$\displaystyle\\{\Lambda_{\bm{k}}^{(m)}-\Lambda_{\bm{j}}^{(m)}\mid\bm{j,k}\in\\{0,1\\}^{L}\\}=\\{-K,\cdots,0,\cdots,K\\}.$
(S57)

Then the Fourier frequency spectrum is
$\Omega=\\{-K,\cdots,0,\cdots,K\\}^{d}$. For the Fourier coefficient set
$C_{\Omega}=\\{c_{\bm{\omega}}\mid\bm{\omega}\in\Omega\\}$, we have

$\displaystyle
c_{\bm{\omega}}=\sum_{\bm{j,k}\in\\{0,1\\}^{L},\bm{\omega}=h_{\bm{j,k}}}C_{\bm{j,k}},$
(S58)

and

$\displaystyle
C_{\bm{j,k}}=\bra{0}V^{\dagger}_{L}\outerproduct{k_{L}}{k_{L}}V^{\dagger}_{L-1}\cdots\outerproduct{k_{1}}{k_{1}}V^{\dagger}_{1}MV_{1}\outerproduct{j_{1}}{j_{1}}\cdots
V_{L-1}\outerproduct{j_{L}}{j_{L}}V_{L}\ket{0}.$ (S59)

If the number of truncation terms $K$ is fixed, as the dimension $d$
increases, the degrees of freedom of the set $C_{\Omega}$ increase with
$O(d)$, so it cannot represent any exponential size Fourier coefficients set.
Thus for all $\bm{\theta}\in{{\mathbb{R}}}^{3(L+1)}$, the Eq. (S55) cannot
express an arbitrary $k$-truncated multivariate Fourier series.

##  Appendix C Extension to multi-qubit QNNs

We have already shown that single-qubit native QNNs are able to approximate
any univariate function but possibly could not approximate arbitrary
multivariate functions by Fourier series in Section 3 and Section 4. To
address this limitation, research into the extension approach of single-qubit
native QNNs is crucial. For classical NNs, a common approach toward overcoming
such limitations is to increase the width or depth of the networks. We
conjecture that QNNs have similar characteristics. We hereby provide a multi-
qubit extension strategy as shown in Fig. C, called _Parallel-Entanglement_ ,
introducing quantum entanglement by multi-qubit gates such as CNOT gates.
Similar to classical NNs in which different neurons are connected by trainable
parameters to form deep NNs, QNNs can establish the connection between
different qubits through quantum entanglement.

Figure S2: The Parallel-Entanglement model of $d$ qubits and $L$ layers. Each
layer consists of a trainable block and an encoding block in the dashed box.
Each trainable block is composed of repeated sub-blocks of $U_{3}$ rotation
gates and CNOT gates, as shown in the dotted box. The number of sub-blocks in
each trainable block is denoted by $D_{tr}$. The encoding block is a
$d$-tensor of $R_{Z}(x^{(m)})$ gates for a $d$-dimensional data
$\bm{x}\coloneqq(x^{(1)},\ldots,x^{(d)})$.

We numerically show that the multi-qubit extension as shown in Fig. C could
improve the expressivity of single-qubit QNNs. Consider the same bivariate
function $f(x,y)=(x^{2}+y-1.5\pi)^{2}+(x+y^{2}-\pi)^{2}$ used in Section 5.2,
we use a two-qubit QNN of $L=10$ and $D_{tr}=3$ to approximate the target
function $f(x,y)$ with the same training setting. The experimental results are
shown in Fig. S3. Compared with the approximation results of single-qubit QNNs
in Fig. 6, we can see that the two-qubit QNN has stronger expressive power
than single-qubit models. Moreover, we could build the _universal trainable
block_ (UTB) using a universal two-qubit quantum gate [40, 41] consisting of
$U_{3}$ and CNOT gates. Specifically, a two-qubit universal trainable block
can express any two-qubit unitary matrix. Using a two-qubit QNN with UTBs
yields a better approximation result which is shown in Fig. S4. From the
numerical results, we could see that the multi-qubit extension could
potentially overcome the limitations of single-qubit QNNs on approximating
multivariate functions as illustrated in Section 4.

((a))

((b))

((c))

Figure S3: Panel (a) is the plot of target function $f(x,y)$. Panel (b) shows
the approximation result of a two-qubit QNN of $L=10$ and $D_{tr}=3$. Panel
(c) is the plot of training loss during the optimization.

((a))

((b))

Figure S4: Panel (a) shows the approximation result of a two-qubit QNN of
$L=10$ with UTB. Panel (b) is the plot of training loss during the
optimization.

We further illustrate the ability of Parallel-Entanglement models to address
practical problems through experiments on the classification task. The public
benchmark data sets are used to demonstrate the capabilities of Parallel-
Entanglement models to tackle classification tasks.

Table 1: The performance of the Parallel-Entanglement model. Dataset | # of qubits | $L$ | $D_{tr}$ | # of parameters | Average accuracy
---|---|---|---|---|---
Iris | 4 | 1 | 1 | 16 | $0.990\pm 0.01$
HTRU2 | 8 | 1 | 1 | 32 | $0.910\pm 0.09$
|  | 3 | 1 | 64 | $0.970\pm 0.03$
|  | 3 | 2 | 128 | $0.980\pm 0.02$
Breast Cancer | 4 | 1 | 1 | 16 | $0.780\pm 0.06$
|  | 3 | 1 | 32 | $0.840\pm 0.02$
|  | 3 | 2 | 64 | $0.845\pm 0.04$

The performance of the Parallel-Entanglement model on classifying Iris [42],
Breast Cancer [43], and HTRU2 [44] data sets are summarized in Table 1.
Specifically, 100 pieces of data are sampled from the dataset, with $80\%$ of
them serving as the training set and $20\%$ serving as the test set. We use
the Adam optimizer with a learning rate of 0.1 and a batch size of 40 to train
the multi-qubit QNNs. In order to reduce the effect of randomness, the results
of classification accuracy are averaged over 10 independent training
instances.

The Iris data set contains 3 different classes, each class only has four
attributes. Obviously, the 4-qubit model easily obtains an average accuracy of
over $99\%$ with only 1 layer on Iris data. The HTRU2 data set only has two
categories, and each example has 8 attributes. As a result, an 8-qubit QNN is
required to complete this task. The average accuracy for binary classification
with 1 layer achieves above $91\%$. We can see that adding the number of
layers to 3 and the depth of each layer to 2 increases the average accuracy to
$98\%$. Since the Breast Cancer data contains 30 features for binary
classification, the principal component analysis (PCA) is used to reduce
feature dimension. Here the numerical results of a 4-qubit model are given to
illustrate the power of the QNN. Compared to the model using complete
information, the QNN model does not perform perfectly. But increasing the
number of layers and the depth may improve the test accuracy. Based on the
finding of the preceding experiments, it is clear that the Parallel-
Entanglement model is capable of handling practical classification problems.