# Concentration of Data Encoding in Parameterized Quantum Circuits

Guangxi Li  Institute for Quantum Computing, Baidu Research, China  Centre for
Quantum Software and Information, University of Technology Sydney, Australia
Ruilin Ye  Institute for Quantum Computing, Baidu Research, China  Institute
of Remote Sensing and Geographical Information Systems, Peking University,
China  Xuanqiang Zhao  Institute for Quantum Computing, Baidu Research, China
Xin Wang  Institute for Quantum Computing, Baidu Research, China

###### Abstract

Variational quantum algorithms have been acknowledged as a leading strategy to
realize near-term quantum advantages in meaningful tasks, including machine
learning and combinatorial optimization. When applied to tasks involving
classical data, such algorithms generally begin with quantum circuits for data
encoding and then train quantum neural networks (QNNs) to minimize target
functions. Although QNNs have been widely studied to improve these algorithms’
performance on practical tasks, there is a gap in systematically understanding
the influence of data encoding on the eventual performance. In this paper, we
make progress in filling this gap by considering the common data encoding
strategies based on parameterized quantum circuits. We prove that, under
reasonable assumptions, the distance between the average encoded state and the
maximally mixed state could be explicitly upper-bounded with respect to the
width and depth of the encoding circuit. This result in particular implies
that the average encoded state will concentrate on the maximally mixed state
at an exponential speed on depth. Such concentration seriously limits the
capabilities of quantum classifiers, and strictly restricts the
distinguishability of encoded states from a quantum information perspective.
We further support our findings by numerically verifying these results on both
synthetic and public data sets. Our results highlight the significance of
quantum data encoding in machine learning tasks and may shed light on future
encoding strategies.

##  1 Introduction

Quantum machine learning [1, 2, 3, 4] is an emerging and promising
interdisciplinary research direction in the fields of quantum computing and
artificial intelligence. In this area, quantum computers are expected to
enhance machine learning algorithms through their inherent parallel
characteristics, thus demonstrating quantum advantages over classical
algorithms [5].

With the increasing enormous efforts from academia and industry, current
quantum devices (usually acknowledged as the noisy intermediate-scale quantum
(NISQ) devices [6]) already can show quantum advantages on certain carefully
designed tasks [7, 8] despite their limitations in quantum circuit width and
depth. A timely direction is to explore quantum advantages with near-term
quantum devices in practical machine learning tasks, and a leading strategy is
the hybrid quantum-classical algorithms, also known as the variational quantum
algorithms [9, 10]. Such algorithms usually use a classical optimizer to train
quantum neural networks (QNNs). They in particular hand over relatively
intractable tasks to quantum computers while those rather ordinary tasks to
classical computers.

For usual quantum machine learning tasks, a quantum circuit used in the
variational quantum algorithms is generally divided into two parts: a data
encoding circuit and a QNN. On the one hand, developing various QNN
architectures is the most popular way to improve these algorithms’ ability to
deal with practical tasks. Numerous architectures such as strongly entangling
circuit architectures [11], quantum convolutional neural networks [12], tree-
tensor networks [13], and even automatically searched architectures [14, 15,
16, 17] have been proposed. On the other hand, one has to carefully design the
encoding circuit, which could significantly influence the generalization
performance of these algorithms [18, 19]. Consider an extreme case. If all
classical inputs are encoded into the same quantum state, these algorithms
will fail to do any machine learning tasks. In addition, the kernel’s
perspective [20, 21, 22, 23] also suggests that data encoding strategy plays a
vital or even leading role in quantum machine learning algorithms [24, 25,
26]. However, there is much less literature on data encoding strategies, which
urgently requires to be studied.

Encoding classical information into quantum data is nontrivial [1], and it is
even more difficult on near-term quantum devices. One of the most feasible and
popular encoding strategies on NISQ devices is based on parameterized quantum
circuits (PQCs) [27], such as the empirically designed angle encoding [24,
28], IQP encoding [29], etc. It is natural to ask how to choose these encoding
strategies and whether there are theoretical guarantees of using them. More
specifically, it is necessary to systematically understand the impact of such
PQC-based encoding strategies on the performance of QNNs in quantum machine
learning tasks.

Figure 1: Illustration of the concentration of PQC-based data encoding. The
average encoded quantum states concentrate on the maximally mixed state at an
exponential rate on the encoding depth. This concentration implies the
theoretical indistinguishability of the encoded quantum data.

In this work, we present results from the perspective of average encoded
quantum state with respect to the width and depth of the encoding PQCs. A
cartoon illustration summarizing our main result is depicted in Fig. 1. We
show that for the usual PQC-based encoding strategies with a fixed width, the
average encoded state is close to the maximally mixed state at an exponential
speed on depth. In particular, we establish the following:

  * •

We theoretically give the upper bound of the quantum divergence between the
average encoded state and the maximally mixed state, which depends explicitly
on the hyper-parameters (e.g., qubit number and encoding depth) of PQCs. From
this bound, we find that for a fixed qubit number, the average encoded state
concentrates on the maximally mixed state exponentially on the encoding depth.

  * •

We show that the quantum states encoded by deep PQCs will seriously limit the
trainability of a quantum classifier and further limit its classification
ability.

  * •

We show that the quantum states encoded by deep PQCs are indistinguishable
from a quantum information perspective.

  * •

We support the above findings by numerical experiments on both synthetic and
public data sets.

#### Related Work

Ref. [18] derived generalization bounds of PQC-based data encoding, which
mainly depends on the total number of circuit gates. While we derive quantum
divergence bound that depends on the width and depth of PQCs. The works [26,
30] explored the effects of data encoding from the perspective of data re-
uploading. [31] studied the robustness of data encoding for quantum
classifiers. Data encoding strategies with discrete features were proposed for
variational quantum classifiers [32].

###  1.1 Background

#### Quantum Basics

We first provide basic concepts about quantum computing [33]. In general,
quantum information is described by quantum states. An $n$-qubit quantum state
is mathematically represented by a positive semi-definite matrix (a.k.a. a
density matrix) $\rho\in\mathbb{C}^{2^{n}\times 2^{n}}$ with property
$\operatorname{Tr}(\rho)=1$. If $\operatorname{Rank}(\rho)=1$, it is called a
pure state; otherwise, it is a mixed state. A pure state can also be
represented by a unit column vector $\ket{\phi}\in\mathbb{C}^{2^{n}}$, where
$\rho=\op{\phi}{\phi}$ and $\bra{\phi}=\ket{\phi}^{\dagger}$. A mixed state
can be regarded as a weighted sum of pure states, i.e.,
$\rho=\sum_{i}q_{i}\op{\phi_{i}}{\phi_{i}}$, where $q_{i}\geq 0$ and
$\sum_{i}q_{i}=1$. Specifically, a mixed state whose density matrix is
proportional to the identity matrix is called the maximally mixed state
$\mathbbm{1}\equiv\frac{I}{2^{n}}$.

A quantum state $\rho$ could be evolved to another state $\rho^{\prime}$
through a quantum circuit (or gate) mathematically represented by a unitary
matrix $U$, i.e., $\rho^{\prime}=U\rho U^{\dagger}$. Typical single-qubit
gates include Pauli gates, $\tiny X\equiv[\begin{array}[]{cc}0&1\\\
1&0\end{array}],Y\equiv[\begin{array}[]{cc}0&-i\\\
i&0\end{array}],Z\equiv[\begin{array}[]{cc}1&0\\\ 0&-1\end{array}]$, and their
corresponding rotation gates $R_{P}(\theta)\equiv\mathrm{e}^{-i\theta P/2}$
with a parameter $\theta$ and $P\in\\{X,Y,Z\\}$. Another commonly used gate
$U3$ in this paper is defined as $U3(\theta_{1},\theta_{2},\theta_{3})\equiv
R_{z}(\theta_{3})R_{y}(\theta_{2})R_{z}(\theta_{1})$, which can implement an
arbitrary single-qubit unitary transformation with appropriate parameters. In
this paper, $R_{z},R_{y}$ are equivalent to $R_{Z},R_{Y}$ without specified. A
multi-qubit gate can be either an individual gate (e.g., CNOT) or a tensor
product of single-qubit gates. To get classical information from a quantum
state $\rho^{\prime}$, one needs to perform quantum measurements, e.g.,
calculating the expectation value $\langle
H\rangle=\operatorname{Tr}(H\rho^{\prime})$ of a Hermitian matrix $H$, and we
often call $H$ an observable.

#### Quantum Divergence

Similar to Kullback-Leibler divergence in machine learning, we use quantum
divergence to quantify the difference between quantum states or quantum data.
Two widely-used quantum divergences are quantum sandwiched Rényi divergence
[34, 35]
$\widetilde{D}_{\alpha}(\rho\|\sigma)\equiv\frac{1}{\alpha-1}\log\operatorname{Tr}\left[\sigma^{\frac{1-\alpha}{2\alpha}}\rho\sigma^{\frac{1-\alpha}{2\alpha}}\right]^{\alpha}$
and the Petz-Rényi divergence [36]
${D}_{\alpha}(\rho\|\sigma)\equiv\frac{1}{\alpha-1}\log\operatorname{Tr}\left[\rho^{\alpha}\sigma^{1-\alpha}\right]$,
where $\alpha\in(0,1)\cup(1,\infty)$ and the latter has an operational
significance in quantum hypothesis testing [37, 38, 39]. In this work, for the
purposes of analyzing quantum encoding, we focus on the Petz-Rényi divergence
with $\alpha=2$, i.e.,

$\displaystyle{D}_{2}(\rho\|\sigma)=\log\operatorname{Tr}\left[\rho^{2}\sigma^{-1}\right],$
(1)

which also plays an important role in training quantum neural networks [40] as
well as quantum communication [41]. Throughout this paper, when we mention the
quantum divergence, we mean the Petz-Rényi divergence ${D}_{2}$ if not
specified and $\log$ denotes $\log_{2}$ if not specified.

#### Parameterized Quantum Circuit

In general, a parameterized quantum circuit [27] has the form
$U({\bm{\theta}})=\prod_{j}U_{j}(\theta_{j})V_{j},$ where ${\bm{\theta}}$ is
its parameter vector, $U_{j}(\theta_{j})=\mathrm{e}^{-i\theta_{j}P_{j}/2}$
with $P_{j}$ denoting a Pauli gate, and $V_{j}$ denotes a fixed gate such as
Identity, CNOT and so on. In this paper, PQCs are utilized as both data
encoding strategies and quantum neural networks. Specifically, when used for
data encoding, an $n$-qubit PQC takes a classical input vector $\bm{x}$ as its
parameters and acts on an initial state $\ket{0}^{\otimes n}$ to obtain the
encoded state $\ket{\bm{x}}$. Here, $\ket{0}^{\otimes n}$ is a
$2^{n}$-dimensional vector whose first element is $1$ and all other elements
are $0$.

##  2 Main Results

$\Qcircuit@C=0.5em@R=1em{\lstick{\ket{0}}&\gate{R_{y}(x_{1,1})}\gate{R_{y}(x_{1,2})}\qw\cdots\gate{R_{y}(x_{1,D})}\qw\\\
\lstick{\ket{0}}\gate{R_{y}(x_{2,1})}\gate{R_{y}(x_{2,2})}\qw\cdots\gate{R_{y}(x_{2,D})}\qw\\\
\cdots\cdots\cdots\\\
\lstick{\ket{0}}\gate{R_{y}(x_{n,1})}\gate{R_{y}(x_{n,2})}\qw\cdots\gate{R_{y}(x_{n,D})}\qw}$

(a) Circuit with $R_{y}$ rotations only

(b) Assumption of IGD

Figure 2: (a) Circuit for the data encoding strategy with $R_{y}$ rotations
only; (b) An example of a binary data set with two classes of $t$-dimensional
vectors $\bm{x}$ and $\bm{y}$. Here, it is assumed that each $x_{j}$ (or
$y_{j}$) obeys an independent Gaussian distribution (IGD), i.e.,
$x_{j}\sim\mathcal{N}(\mu_{x,j},\sigma^{2}_{x,j})$ (or
$y_{j}\sim\mathcal{N}(\mu_{y,j},\sigma^{2}_{y,j})$), where these mean values
(small red cross symbols) range in $[0,2\pi)$ and form the green dotted lines.
Note that the difference between these two lines determines that they belong
to different classes.

###  2.1 A Warm-up Case

For a quick access, we first consider one of the most straightforward PQC-
based data encoding strategies, i.e., consisting of $R_{y}$ rotations only,
cf. Fig. 2(a). It can be viewed as a generalized angle encoding. For a
classical input vector $\bm{x}$ with $nD$ components, the output of this data
encoding circuit is a pure state $\ket{\bm{x}}\in\mathbb{C}^{2^{n}}$ expanded
in a $2^{n}$-dimensional Hilbert space. We denote the density matrix of the
output state by $\rho(\bm{x})=\op{\bm{x}}{\bm{x}}$. If we assume each element
of the input vector obeys an independent Gaussian distribution (IGD, see Fig.
2(b) for an intuitive illustration), then we have the following theorem.

######  Theorem 1.

Assume each element of an $nD$-dimensional vector $\bm{x}$ obeys an IGD, i.e.,
$x_{j,d}\sim\mathcal{N}(\mu_{j,d},\sigma^{2}_{j,d})$, where
$\sigma_{j,d}\geq\sigma$ for some constant $\sigma$ and $1\leq j\leq n,1\leq
d\leq D$. If $\bm{x}$ is encoded into an $n$-qubit pure state $\rho(\bm{x})$
according to the circuit in Fig. 2(a), then the quantum divergence between the
average encoded state $\bar{\rho}$ and the maximally mixed state
$\mathbbm{1}={I}/{2^{n}}$ is upper-bounded by

$\displaystyle D_{2}\left(\bar{\rho}\|\mathbbm{1}\right)\leq
n\log\left(1+\mathrm{e}^{-D\sigma^{2}}\right),$ (2)

where $\bar{\rho}$ is defined as
$\bar{\rho}\equiv\mathbb{E}\left[\rho(\bm{x})\right]$.

This theorem shows that the upper bound of the quantum divergence between
$\bar{\rho}$ and $\mathbbm{1}$ explicitly depends on the qubit number $n$ and
the encoding depth $D$ under certain conditions. Further by approximating Eq.
(2) as

$\displaystyle D_{2}\left(\bar{\rho}\|\mathbbm{1}\right)\leq
n\log(1+\mathrm{e}^{-D\sigma^{2}})\approx\begin{cases}n\left(1-\frac{\sigma^{2}}{2\ln
2}D\right),&D\in O(1),\\\
n\mathrm{e}^{-D\sigma^{2}},&D\in\Omega(\text{poly}\log(n)).\end{cases}$ (3)

We easily find that for a fixed $n$, the upper bound decays exponentially with
$D$ growing in $\Omega(\text{poly}\log(n))$. This means that the average
encoded state will quickly approach the maximally mixed state with an
arbitrarily small distance under reasonable depths.

#### Sketch of Proof.

For the $j$-th qubit, let $x_{j,{\rm sum}}=\sum_{d}x_{j,d}$ and $\mu_{j,{\rm
sum}}=\sum_{d}\mu_{j,d}$, we get $x_{j,{\rm sum}}\sim\mathcal{N}(\mu_{j,{\rm
sum}},\sum_{d}\sigma^{2}_{j,d})$. From the fact that
$R_{y}(x_{1})R_{y}(x_{2})=R_{y}(x_{1}+x_{2})$, we have

$\displaystyle\rho\left(\bm{x}_{j}\right)=R_{y}\left(x_{j,{\rm
sum}}\right)\op{0}{0}R_{y}^{\dagger}\left(x_{j,{\rm
sum}}\right)=\frac{1}{2}\left[I+\cos\left(x_{j,{\rm
sum}}\right)Z+\sin\left(x_{j,{\rm sum}}\right)X\right].$ (4)

Further from the fact that if a variable $x\sim\mathcal{N}(\mu,\sigma^{2})$,
then
$\mathbb{E}\left[\cos(x)\right]=\mathrm{e}^{-\frac{\sigma^{2}}{2}}\cos(\mu)$
and $\mathbb{E}\left[\sin(x)\right]$
$=\mathrm{e}^{-\frac{\sigma^{2}}{2}}\sin(\mu)$, together with the condition
$\sigma_{j,d}\geq\sigma$, we bound
$D_{2}\left(\mathbb{E}\left[\rho\left(\bm{x}_{j}\right)\right]\|\mathbbm{1}\right)$
via calculating

$\displaystyle\operatorname{Tr}\left(\mathbb{E}^{2}\left[\rho\left(\bm{x}_{j}\right)\right]\right)=\frac{1}{2}\left(1+\mathrm{e}^{-\sum_{d}\sigma^{2}_{j,d}}\right)\leq\frac{1}{2}\left(1+\mathrm{e}^{-D\sigma^{2}}\right).$
(5)

Finally we generalize Eq. (5) to multi-qubit cases, and complete the proof of
Theorem 1. The detailed proof is deferred to Appendix A.

###  2.2 General Case

Next, we consider the general PQC-based data encoding strategies shown in Fig.
3, where a column of $U3$ gates and a column of entangled gates spread out
alternately.

######  Theorem 2.

(Data Encoding Concentration) Assume each element of a $3nD$-dimensional
vector $\bm{x}$ obeys an IGD, i.e.,
$x_{j,d,k}\sim\mathcal{N}(\mu_{j,d,k},\sigma^{2}_{j,d,k})$, where
$\sigma_{j,d,k}\geq\sigma$ for some constant $\sigma$ and $1\leq j\leq n,1\leq
d\leq D,1\leq k\leq 3$. If $\bm{x}$ is encoded into an $n$-qubit pure state
$\rho(\bm{x})$ according to the circuit in Fig. 3, the quantum divergence
between the average encoded state $\bar{\rho}$ and the maximally mixed state
$\mathbbm{1}={I}/{2^{n}}$ is upper-bounded by

$\displaystyle
D_{2}\left(\bar{\rho}\|\mathbbm{1}\right)\leq\log(1+(2^{n}-1)\mathrm{e}^{-D\sigma^{2}}).$
(6)

$\Qcircuit@C=0.5em@R=1.0em{\lstick{\ket{0}}&\gate{U3(\bm{x}_{1,1})}\multigate{3}{Etg_{1}}\gate{U3(\bm{x}_{1,2})}\multigate{3}{Etg_{2}}\qw\cdots\gate{U3(\bm{x}_{1,D-1})}\multigate{3}{Etg_{D-1}}\gate{U3(\bm{x}_{1,D})}\qw\\\
\lstick{\ket{0}}\gate{U3(\bm{x}_{2,1})}\ghost{Etg_{1}}\gate{U3(\bm{x}_{2,2})}\ghost{Etg_{2}}\qw\cdots\gate{U3(\bm{x}_{2,D-1})}\ghost{Etg_{D-1}}\gate{U3(\bm{x}_{2,D})}\qw\\\
\cdots\cdots\cdots\cdots\\\
\lstick{\ket{0}}\gate{U3(\bm{x}_{n,1})}\ghost{Etg_{1}}\gate{U3(\bm{x}_{n,2})}\ghost{Etg_{2}}\qw\cdots\gate{U3(\bm{x}_{n,D-1})}\ghost{Etg_{D-1}}\gate{U3(\bm{x}_{n,D})}\qw}$
Figure 3: Circuit for the data encoding strategy with $D$ layers of $U3$ gates
and $D-1$ layers of entanglements. Here, each $\bm{x}_{j,d}$ represents three
elements $x_{j,d,1},x_{j,d,2},x_{j,d,3}$, and each $Etg_{i}$ denotes an
arbitrary group of entangled two-qubit gates, such as CNOT or CZ, where $1\leq
j\leq n,1\leq d\leq D,1\leq i\leq D-1$.

This theorem shows that, when employing general PQC-based encoding strategies,
we could also have an upper bound of the quantum divergence
$D_{2}\left(\bar{\rho}\|\mathbbm{1}\right)$ which explicitly depends on $n$
and $D$. By approximating the upper bound in Eq. (6) as follows

$\displaystyle
D_{2}\left(\bar{\rho}\|\mathbbm{1}\right)\leq\log\left(1+(2^{n}-1)\mathrm{e}^{-D\sigma^{2}}\right)\approx\begin{cases}n-\frac{\sigma^{2}}{\ln
2}D,&D\in O(\text{poly}\log(n)),\\\
(2^{n}-1)\mathrm{e}^{-D\sigma^{2}},&D\in\Omega(\text{poly}(n)).\end{cases}$
(7)

We observe similarly that for some fixed $n$, the upper bound decays at an
exponential speed as $D$ grows in $\Omega(\text{poly}(n))$. In addition,
according to our proof analysis, even if each $U3$ gate is replaced by a $U2$
gate containing only two different kinds of Pauli rotations or even a $U1$
gate with only one proper Pauli rotation, we still get a similar bound as Eq.
(6). Therefore, we conclude that as long as $D$ grows within a reasonable
scope, the average of the quantum states encoded by a wide family of PQCs will
quickly concentrates on the maximally mixed state. Unlike the warm-up case,
the proof for this theorem is quite non-straightforward due to the tricky
entangled gates. For smooth reading, we defer the complete proof in Appendix
B.

The average encoded state $\bar{\rho}$ in Theorem 2 is built on infinite data
samples, but in practice we do not have infinite ones. Therefore, we provide
the following helpful corollary.

######  Corollary 2.1.

Assume there are $M$ classical vectors $\\{\bm{x}^{(m)}\\}^{M}_{m=1}$ sampled
from the distributions described in Theorem 2 and define
$\bar{\rho}_{M}\equiv\frac{1}{M}\sum_{m=1}^{M}\rho(\bm{x}^{(m)})$. Let $H$ be
a Hermitian matrix with its eigenvalues ranging in $[-1,1]$, then given an
arbitrary $\epsilon\in(0,1)$, as long as the encoding depth
$D\geq\frac{1}{\sigma^{2}}\left[(n+4)\ln{2}+2\ln\left(1/\epsilon\right)\right]$,
we have

$\displaystyle\Big{|}\operatorname{Tr}\left[H\left(\bar{\rho}_{M}-\mathbbm{1}\right)\right]\Big{|}\leq\epsilon$
(8)

with a probability of at least $1-2\mathrm{e}^{-M\epsilon^{2}/8}$.

This corollary implies that for a reasonable encoding depth $D$ and number of
samples $M$, the practical average encoded state $\bar{\rho}_{M}$ will also be
infinitely close to the maximally mixed state with a high probability. The
proof is mainly derived from Hoeffding’s inequality [42] and the relations
between quantum divergence and trace norm. The proof details are deferred to
Appendix C.

##  3 Applications in Quantum Supervised Learning

In this section, we will show that the concentrated quantum states encoded by
the above PQC-based data encoding strategies will severely limit the
performances of quantum supervised learning tasks. Before beginning, let’s
define the following necessary data set.

######  Definition 3.

(Data Set) The $K$-class data set
$\mathcal{D}\equiv\\{(\bm{x}^{(m)},\bm{y}^{(m)})\\}^{KM}_{m=1}\subset\mathbb{R}^{3nD}\times\mathbb{R}^{K}$
totally has $KM$ data samples, including $M$ samples in each category. Here,
suppose elements in the same entry of all input vectors from the same category
are sampled from the same IGD with a variance of at least $\sigma^{2}$ and
each $\bm{x}^{(m)}$ is encoded into the corresponding pure state
$\rho(\bm{x}^{(m)})$ according to the circuit in Fig. 3 with $n$ qubits and
$D$ layers of $U3$ gates. The label $\bm{y}^{(m)}$ is a one-hot vector that
indicates which of the $K$ classes $\bm{x}^{(m)}$ belongs to.

###  3.1 In the Scenario of Quantum Classification

Quantum classification, as one of the most significant branches in quantum
machine learning, is widely studied nowadays, where quantum-enhanced
classification models are expected to achieve quantum advantages against the
classical ones in solving classification tasks [29, 43]. Specifically, in the
NISQ era, plenty of variational quantum classifiers based on parameterized
quantum circuits are developed to make full usage of NISQ devices [9, 44, 11,
12, 13, 45, 46]. See [47] for a review on the recent advances of quantum
classifiers .

In general, a quantum classifier aims to learn a map from input to label by
optimizing a loss function constructed through QNNs to predict the label of an
unseen input as accurately as possible. Now, we demonstrate the performance of
a quantum classifier on the data set $\mathcal{D}$ defined in Def. 3.

In this paper, the loss function is defined from the cross-entropy loss with
softmax function [48]:

$\displaystyle
L\left(\bm{\theta};\mathcal{D}\right)\equiv\frac{1}{KM}\sum_{m=1}^{KM}L^{(m)}\quad\text{with}\quad
L^{(m)}\left(\bm{\theta};(\bm{x}^{(m)},\bm{y}^{(m)})\right)\equiv-\sum_{k=1}^{K}y^{(m)}_{k}\ln\frac{\mathrm{e}^{h_{k}}}{\sum_{j=1}^{K}\mathrm{e}^{h_{j}}},$
(9)

where $y^{(m)}_{k}$ denotes the $k$-th element of the label $\bm{y}^{(m)}$ and

$\displaystyle
h_{k}\left(\bm{x}^{(m)},\bm{\theta}\right)=\operatorname{Tr}\left[H_{k}U(\bm{\theta})\rho(\bm{x}^{(m)})U^{\dagger}(\bm{\theta})\right],$
(10)

which means the Hermitian operator $H_{k}$ is finally measured after the
quantum neural network $U(\bm{\theta})$. Here, each $H_{k}$ is chosen from
tensor products of various Pauli matrices, such as $Z\otimes I$, $X\otimes
Y\otimes Z$ and so on. By minimizing the loss function with a gradient descent
method, we could obtain the final trained model $U(\bm{\theta}^{*})$ with the
optimal or sub-optimal parameters $\bm{\theta}^{*}$. After that, when provided
a new input quantum state $\rho(\bm{x}^{\prime})$, we compute each
$h_{k}^{\prime}$ with parameters $\bm{\theta}^{*}$ according to Eq. (10), and
the index of the largest $h_{k}^{\prime}$ is exactly our designated label.

However, all these graceful expectations can only be established on gradients
with relatively large absolute values. On the contrary, gradients with
significantly small absolute values will cause a severe training problem, for
example the barren plateau issue [49]. Therefore, in the following we
investigate the partial gradient of the cost defined in Eq. (9) with regard to
its parameters. The results are exhibited in Proposition 4.

######  Proposition 4.

Consider a $K$-classification task with the data set $\mathcal{D}$ defined in
Def. 3. If the encoding depth
$D\geq\frac{1}{\sigma^{2}}\left[(n+4)\ln{2}+2\ln\left(1/\epsilon\right)\right]$
for some $\epsilon\in(0,1)$, then the partial gradient of the loss function
defined in Eq. (9) with respect to each parameter $\theta_{i}$ of the employed
QNN is bounded by

$\displaystyle\Big{|}\frac{\partial
L\left(\bm{\theta};\mathcal{D}\right)}{\partial\theta_{i}}\Big{|}\leq
K\epsilon$ (11)

with a probability of at least $1-2\mathrm{e}^{-M\epsilon^{2}/8}$.

From this proposition, we observe that no matter what QNN structures are
selected, the absolute gradient value can be arbitrarily small with a very
high probability for the above data set $\mathcal{D}$, provided that the
encoding depth $D$ and the number of data samples $M$ are sufficiently large.
This vanishing of the gradients will severely restrict the trainability of
QNNs. Moreover, if before training $U(\bm{\theta})$ is initialized to satisfy
a certain randomness, such as unitary 2-design [50], then each $h_{k}$ in Eq.
(10) will concentrate on 0 with a high probability, thus the loss in Eq. (9)
will concentrate on $\ln K$. This concentration of loss is also verified
through numerical simulations, as presented in Sec. 4. This phenomenon,
together with Proposition 4, implies that large encoding depth will
significantly hinder the training of a quantum classifier and probably lead to
poor classification accuracy. Please refer to Appendix D for the proof of
Proposition 4.

###  3.2 In the Scenario of Quantum State Discrimination

Quantum state discrimination [51] is a central information-theoretic task in
quantum information and finds applications in various topics such as quantum
cryptography [52], quantum error mitigation [53], and quantum data hiding
[54]. It aims to distinguish quantum states using a positive operator-valued
measure (POVM), a set of positive semi-definite operators that sum to the
identity operator. Here, we have to seriously note that in quantum state
discrimination, we can only measure each quantum state once, instead of
measuring repeatedly and calculating the expectations as shown in quantum
classification.

In general, a perfect discrimination (i.e., a perfect POVM) can not be
achieved if quantum states are non-orthogonal. A natural alternative option is
by adopting some metrics such as the success probability so that the optimal
POVM could be obtained via various kinds of optimization ways, e.g., Helstrom
bound [55] and semi-definite programming (SDP) [56]. Recently, researchers
also try to train QNNs as substitutions for optimal POVMs [57, 58].

Next, we demonstrate the impact of the encoded quantum states from the data
set $\mathcal{D}$ defined in Def. 3 on quantum state discrimination. Our goal
is to obtain the maximum success probability $p_{\rm succ}$ by maximizing the
success probability over all POVMs with $K$ operators:

$\displaystyle p_{\rm
succ}\equiv\max_{\left\\{\Pi_{k}\right\\}_{k}}\frac{1}{K}\sum_{k=1}^{K}\operatorname{Tr}\left[\Pi_{k}\bar{\rho}_{k,M}\right]\quad\text{with}\quad\bar{\rho}_{k,M}\equiv\frac{1}{M}\sum_{m=1}^{KM}y^{(m)}_{k}\rho(\bm{x}^{(m)}),$
(12)

where $y^{(m)}_{k}$ denotes the $k$-th element of the label $\bm{y}^{(m)}$ and
$\left\\{\Pi_{k}\right\\}_{k=1}^{K}$ denotes a POVM, which satisfies
$\sum_{k=1}^{K}\Pi_{k}=I$.

######  Proposition 5.

Consider a $K$-class discrimination task with the data set $\mathcal{D}$
defined in Def. 3. If the encoding depth
$D\geq\frac{1}{\sigma^{2}}\left[(n+4)\ln{2}+2\ln\left(1/\epsilon\right)\right]$
for a given $\epsilon\in(0,1)$, then with a probability of at least
$1-2\mathrm{e}^{-M\epsilon^{2}/8}$, the maximum success probability $p_{\rm
succ}$ is bounded as

$\displaystyle p_{\rm succ}\leq{1}/{K}+\epsilon.$ (13)

This proposition implies that as long as the encoding depth $D$ and the data
numbers $M$ are large enough, the optimal success probability $p_{\rm succ}$
could be arbitrarily close to $\frac{1}{K}$ with a remarkably high probability
for the data set $\mathcal{D}$. This nearly blind-guessing success probability
shows that the concentration of the encoded quantum states in the data set
$\mathcal{D}$ will lead to the failure of state discrimination via POVM. As
POVMs are the most general kind of measurements one can implement to extract
classical information from quantum systems [33], we conclude that the above
different classes of encoded states are indistinguishable from the perspective
of quantum information. The proof of Proposition 5 could be derived
straightforwardly by combining Eq. (12) with Corollary 2.1.

$\Qcircuit@C=0.5em@R=1em{\lstick{\ket{0}}&\gate{R_{y}(x_{1})}\ctrl{1}\qw\qw\targ\gate{R_{y}(x_{4d+1})}\qw\barrier[-0.5em]{3}\cdots\gate{U3(\theta_{1,5,9})}\ctrl{1}\qw\qw\targ\gate{R_{y}(\theta_{4l+9})}\qw\rstick{\langle
H_{k}\rangle}\\\
\lstick{\ket{0}}\gate{R_{y}(x_{2})}\targ\ctrl{1}\qw\qw\gate{R_{y}(x_{4d+2})}\qw\cdots\gate{U3(\theta_{2,6,10})}\targ\ctrl{1}\qw\qw\gate{R_{y}(\theta_{4l+10})}\qw\\\
\lstick{\ket{0}}\gate{R_{y}(x_{3})}\qw\targ\ctrl{1}\qw\gate{R_{y}(x_{4d+3})}\qw\cdots\gate{U3(\theta_{3,7,11})}\qw\targ\ctrl{1}\qw\gate{R_{y}(\theta_{4l+11})}\qw\\\
\lstick{\ket{0}}\gate{R_{y}(x_{4})}\qw\qw\targ\ctrl{-3}\gate{R_{y}(x_{4d+4})}\qw\cdots\gate{U3(\theta_{4,8,12})}\qw\qw\targ\ctrl{-3}\gate{R_{y}(\theta_{4l+12})}\qw\gategroup{1}{3}{4}{7}{0.5em}{--}\gategroup{1}{12}{4}{16}{0.5em}{--}\\\
\times(D-1)\times L_{\rm QNN}}$ Figure 4: Circuits for data encoding (before
the barrier line) and quantum neural network (after the barrier line) in the
4-qubit case. Here the input $\bm{x}\in\mathbb{R}^{4D}$ and $d\in[1,D-1]$. The
QNN totally has $L_{\rm QNN}+1$ layers with parameters
$\bm{\theta}\in\mathbb{R}^{4L_{\rm QNN}+12}$, where the first layer $U3$ gates
consists of 12 parameters. After QNN, there are $K$ expectations
$\left\\{\langle H_{k}\rangle\right\\}_{k=1}^{K}$ for $K$-classification
tasks.

##  4 Numerical Experiments

Previous sections demonstrate that the average encoded state will concentrate
on the maximally mixed state under PQC-based data encoding strategies with
large depth. These encoded states theoretically cannot be utilized to train
QNNs or distinguished by POVMs. In this section, we verify these results on
both synthetic and public data sets by choosing a commonly employed strongly
entangling circuit [11], which helps to understand the concentration rate
intuitively for realistic encoding circuits. All the simulations and
optimization loop are implemented via Paddle
Quantum111https://github.com/paddlepaddle/Quantum on the PaddlePaddle Deep
Learning Platform [59].

(a) Encoding Strategy in Fig. 2(a)

(b) Encoding Strategy in Fig. 4

Figure 5: Exponential decay of quantum divergence
$D_{2}(\bar{\rho}_{0}||\mathbbm{1})$ vs. encoding depth under different qubit
cases for synthetic data set. Here, there are one million data samples for
calculating average encoded state $\bar{\rho}_{0}$ for class 0 at each point
in numerical lines. And the upper-bounds come from (a) Theorem 1, (b) Theorem
2, respectively.

###  4.1 On Synthetic Data Set

#### Data Set

The synthetic two-class data set
$\left\\{(\bm{x}^{(m)},\bm{y}^{(m)})\right\\}_{m=1}^{M}$ is generated
following the distributions depicted in Fig. 2(b), where each
$x^{(m)}_{j}\sim\mathcal{N}(\mu_{j},\sigma^{2}_{j})$ for $1\leq j\leq t$ and
$\bm{y}^{(m)}$ denotes a one-hot label. Here, we assume all means come from
two lines, i.e., $\mu_{j}=\frac{2\pi}{16}(j-1)\ {\rm mod}\ 2\pi$ for class 0
and $\mu_{j}=\frac{2\pi}{16}(16-j)\ {\rm mod}\ 2\pi$ for class 1, and all
$\sigma_{j}$’s are set as 0.8. Note that the same variance is selected for
both classes to facilitate the demonstration of the experiment. Other choices
of $\sigma_{j}$’s would have similar effects.

We first verify our two main upper bounds given in Theorems 1 and 2 by
encoding the $nD$-dimensional inputs that belong to the same class into
$n$-qubit quantum states with $D$ encoding depths under the encoding
strategies illustrated in Figs. 2(a) and 4, respectively. Here, $n$ is set as
$2,4,6$ and $D\in[1,14]$. The results are displayed in Fig. 5, from which we
can intuitively see that the divergences decrease exponentially on depth.
Specifically, from Fig. 5(a), we know the upper bound in Theorem 2(a) is
tight, which is also easily verified from our proof. From Fig. 5(b), we learn
that the upper bound in Theorem 2 is quite loose, which suggests that the real
situation is much worse than our theoretical analysis. We also notice in Fig.
5(b) that for this strongly entangling encoding strategy, the larger the qubit
number is, the faster the divergence decreases. This unexpected phenomenon
reveals the possibility that specific structures of encoding circuits may lead
to more severe concentrations for larger numbers of qubits and is worthy of
further studies.

Figure 6: Numerical results for synthetic data sets under the encoding
strategy in Fig. 4. In all qubit cases, (a) the test accuracy of QNN (or (b)
the maximum success probability of POVM) will eventually decay to 50% or so
with the depth growing; (c) In the 4 qubit case, for instance, the training
losses of QNN do not decrease and stay at about $\ln 2$ in the training
process when the depth becomes large enough.

Next, we examine the performance of QNNs and POVMs by generating 20k data
samples for training and 4k for testing under the encoding strategy in Fig. 4,
where half of the data belong to class 0, and the others belong to class 1.
The QNNs are designed according to the right hand side of Fig. 4, where the
number of layers $L_{\rm QNN}$ is set as $n+2$, the finally measured Hermitian
operators are set as $H_{1}=Z$ and $H_{2}=X$ on the first qubit, and all
parameters $\bm{\theta}$ are initialized randomly in $[0,2\pi]$. During the
optimization, we adopt the Adam optimizer [60] with a batch size of 200 and a
learning rate of $0.02$. In the POVM setting, we directly employ semi-definite
programming [56] to obtain the maximum success probability $P_{\rm succ}$ on
the training data samples. The results are illustrated in Fig. 6. We observe
that both the test accuracy of the QNNs and the maximum success probability
$P_{\rm succ}$ of the POVMs eventually decay to about $0.5$ as the encoding
depth grows, indicating that the classification abilities of both the QNNs and
the POVMs are no better than random guessing. In addition, the training losses
of QNNs in Fig. 6 gradually approach $\ln 2$ as the depth grows and finally do
not go down anymore during the whole training process, which implies that the
concentration of this data set on the maximally mixed state would limit the
trainability of QNNs as we predicted in Sec. 3.1. All these results are in
line with our theoretical expectations.

###  4.2 On Public Data Set

#### Data Set and Preprocessing

The handwritten digit data set MNIST [61] consists of 70k images labeled from
‘0’ to ‘9’, each of which contains $28\times 28$ gray scale pixels valued in
$[0,255]$. In order to facilitate encoding, these images are first resized to
$4\times 4$ and then normalized to values between $0$ and $\pi$. Finally, we
select all images corresponding to two pairs of labels, i.e., $(2,9)$ and
$(3,6)$, for two binary classification tasks. For each task, there are about
12k training samples and 2k testing samples, and each category accounts for
half or so.

Figure 7: Numerical results of QNN for MNIST data set under the encoding
strategy in Fig. 4. (a) The curves for the quantum divergence between the
averaged encoded state $\bar{\rho}$ of each handwritten digit and the
maximally mixed state $\mathbbm{1}$ decrease exponentially on depth. (b) The
test accuracy reduce rapidly with a larger encoding depth; (c) In the case of
classifying digits 3 and 6, when the depth is large (e.g., 8), it is difficult
to keep the training loss away from $\ln 2$ in the training process.

Here we mainly consider the performance of QNN on this data set because POVMs
are generally not suitable for prediction. These 16-dimensional preprocessed
images are first encoded into $n$-qubit quantum states with encoding depth $D$
and then fed into a QNN (cf. Fig. 4). We set $n$ as 2,3,4,6,8 and $D$ as
8,6,4,3,2 accordingly. The settings of QNN are almost the same as those used
in the synthetic case, except for a new learning rate of $0.05$. From Fig. 7,
we see that the average state of each digit class concentrates on the
maximally mixed state at an approximately exponential speed on depth, which is
consistent with our main result. Furthermore, the outcomes in Figs. 7 and 7
also confirm the incapability of training of QNNs, provided that the classical
inputs are encoded by a higher depth PQC.

##  5 Discussion

We have witnessed both theoretically and experimentally that for usual PQC-
based data encoding strategies with higher depth, the average encoded state
concentrates on the maximally mixed state. We further show that such
concentration severely limits the capabilities of quantum classifiers for
practical tasks. Such limitation indicates that we should pay more attention
to methods encoding classical data into PQCs in quantum supervised learning.

Our work suggests that the distance between the average encoded state and the
maximally mixed state may be a reasonable metric to quantify how well the
quantum encoding preserves the features in quantum supervised learning. The
result on the encoding concentration also motivates us to consider how to
design PQC-based encoding strategies better to avoid the exponentially decayed
distance. An obvious way this paper implies might be to keep the depth shallow
while accompanied by a higher width. Still, it will render poor generalization
performance [19] as well as the notorious barren plateau issue [49].
Therefore, it will be desirable to develop nontrivial quantum encoding
strategies to guarantee the effectiveness and efficiency of quantum supervised
learning as well as quantum kernel methods [24, 20, 28]. Recent works on data
re-uploading [26, 30, 62] and pooling [19, 25] of quantum neural networks may
also provide potential methods for improving the quantum encoding efficiency.

## Acknowledgements

We would like to thank Sanjiang Li, Yuan Feng, Hongshun Yao, and Zhan Yu for
helpful discussions. G. L. acknowledges the support from the Baidu-UTS AI
Meets Quantum project, the China Scholarship Council (No. 201806070139), and
the Australian Research Council project (Grant No: DP180100691). Part of this
work was done when R. Y. and X. Z. were research interns at Baidu Research.

## References

  * [1] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd.  Quantum machine learning.  Nature, 549(7671):195–202, sep 2017.
  * [2] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione.  An introduction to quantum machine learning.  Contemporary Physics, 56(2):172–185, apr 2015.
  * [3] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig.  Quantum machine learning: a classical perspective.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, jan 2018.
  * [4] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost.  Quantum algorithms for supervised and unsupervised machine learning.  arXiv:1307.0411, jul 2013.
  * [5] Aram W Harrow and Ashley Montanaro.  Quantum computational supremacy.  Nature, 549(7671):203–209, 2017.
  * [6] John Preskill.  Quantum Computing in the NISQ era and beyond.  Quantum, 2:79, aug 2018.
  * [7] 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.
  * [8] 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, et al.  Quantum computational advantage using photons.  Science, 370(6523):1460–1463, 2020.
  * [9] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S Kottmann, Tim Menke, et al.  Noisy intermediate-scale quantum algorithms.  Reviews of Modern Physics, 94(1):015004, 2022.
  * [10] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al.  Variational quantum algorithms.  Nature Reviews Physics, 3(9):625–644, 2021.
  * [11] Maria Schuld, Alex Bocharov, Krysta M. Svore, and Nathan Wiebe.  Circuit-centric quantum classifiers.  Physical Review A, 101(3):032308, mar 2020.
  * [12] Iris Cong, Soonwon Choi, and Mikhail D. Lukin.  Quantum convolutional neural networks.  Nature Physics, 15(12):1273–1278, dec 2019.
  * [13] Edward Grant, Marcello Benedetti, Shuxiang Cao, Andrew Hallam, Joshua Lockhart, Vid Stojevic, Andrew G. Green, and Simone Severini.  Hierarchical quantum classifiers.  npj Quantum Information, 4(1):65, dec 2018.
  * [14] Mateusz Ostaszewski, Lea M Trenkwalder, Wojciech Masarczyk, Eleanor Scerri, and Vedran Dunjko.  Reinforcement learning for optimization of variational quantum circuit architectures.  Advances in Neural Information Processing Systems, 34:18182–18194, 2021.
  * [15] Mateusz Ostaszewski, Edward Grant, and Marcello Benedetti.  Structure optimization for parameterized quantum circuits.  Quantum, 5:391, 2021.
  * [16] Shi-Xin Zhang, Chang-Yu Hsieh, Shengyu Zhang, and Hong Yao.  Differentiable Quantum Architecture Search.  arXiv:2010.08561, oct 2020.
  * [17] Yuxuan Du, Tao Huang, Shan You, Min-Hsiu Hsieh, and Dacheng Tao.  Quantum circuit architecture search: error mitigation and trainability enhancement for variational quantum solvers.  arXiv preprint arXiv:2010.10217, 2020.
  * [18] Matthias C Caro, Elies Gil-Fuster, Johannes Jakob Meyer, Jens Eisert, and Ryan Sweke.  Encoding-dependent generalization bounds for parametrized quantum circuits.  Quantum, 5:582, 2021.
  * [19] Leonardo Banchi, Jason Pereira, and Stefano Pirandola.  Generalization in quantum machine learning: A quantum information standpoint.  PRX Quantum, 2(4):040321, 2021.
  * [20] Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R. McClean.  Power of data in quantum machine learning.  Nature Communications, 12(1):2631, dec 2021.
  * [21] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme.  A rigorous and robust quantum speed-up in supervised machine learning.  Nature Physics, 17(9):1013–1017, 2021.
  * [22] Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu.  Sublinear quantum algorithms for training linear and kernel-based classifiers.  In International Conference on Machine Learning, pages 3815–3824. PMLR, 2019.
  * [23] Jonas Kübler, Simon Buchholz, and Bernhard Schölkopf.  The inductive bias of quantum kernels.  Advances in Neural Information Processing Systems, 34, 2021.
  * [24] Maria Schuld.  Quantum machine learning models are kernel methods.  arXiv:2101.11020, pages 1–26, jan 2021.
  * [25] Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Izaac, and Nathan Killoran.  Quantum embeddings for machine learning.  arXiv:2002.08953, pages 1–11, jan 2020.
  * [26] 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.
  * [27] Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini.  Parameterized quantum circuits as machine learning models.  Quantum Science and Technology, 4(4):043001, jun 2019.
  * [28] Evan Peters, João Caldeira, Alan Ho, Stefan Leichenauer, Masoud Mohseni, Hartmut Neven, Panagiotis Spentzouris, Doug Strain, and Gabriel N. Perdue.  Machine learning of high dimensional data on a noisy quantum processor.  arXiv:2101.09581, pages 1–20, jan 2021.
  * [29] 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(7747):209–212, mar 2019.
  * [30] 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.
  * [31] Ryan LaRose and Brian Coyle.  Robust data encodings for quantum classifiers.  Physical Review A, 102(3):032420, 2020.
  * [32] Hiroshi Yano, Yudai Suzuki, Rudy Raymond, and Naoki Yamamoto.  Efficient discrete feature encoding for variational quantum classifier.  In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 11–21. IEEE, 2020.
  * [33] Michael A. Nielsen and Isaac Chuang.  Quantum Computation and Quantum Information.  American Journal of Physics, 70(5):558–559, may 2002.
  * [34] Martin Müller-Lennert, Frédéric Dupuis, Oleg Szehr, Serge Fehr, and Marco Tomamichel.  On quantum Rényi entropies: A new generalization and some properties.  Journal of Mathematical Physics, 54(12):122203, dec 2013.
  * [35] Mark M Wilde, Andreas Winter, and Dong Yang.  Strong Converse for the Classical Capacity of Entanglement-Breaking and Hadamard Channels via a Sandwiched Rényi Relative Entropy.  Communications in Mathematical Physics, 331(2):593–622, oct 2014\.
  * [36] Dénes Petz.  Quasi-entropies for finite quantum systems.  Reports on Mathematical Physics, 23(1):57–65, feb 1986.
  * [37] Koenraad M R Audenaert.  A sharp continuity estimate for the von Neumann entropy.  Journal of Physics A: Mathematical and Theoretical, 40(28):8127–8136, jul 2007.
  * [38] Michael Nussbaum and Arleta Szkoła.  The Chernoff lower bound for symmetric quantum hypothesis testing.  The Annals of Statistics, 37(2):1040–1057, 2009.
  * [39] Robert Salzmann, Nilanjana Datta, Gilad Gour, Xin Wang, and Mark M. Wilde.  Symmetric distinguishability as a quantum resource.  New Journal of Physics, 23(8):083016, aug 2021.
  * [40] Maria Kieferova, Ortiz Marrero Carlos, and Nathan Wiebe.  Quantum Generative Training Using Rényi Divergences.  arXiv:2106.09567, jun 2021.
  * [41] Kun Fang and Hamza Fawzi.  Geometric Rényi Divergence and its Applications in Quantum Channel Capacities.  Communications in Mathematical Physics, 384(3):1615–1677, jun 2021\.
  * [42] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  In The collected works of Wassily Hoeffding, pages 409–426. Springer, 1994.
  * [43] Maria Schuld and Nathan Killoran.  Quantum Machine Learning in Feature Hilbert Spaces.  Physical Review Letters, 122(4):040504, feb 2019.
  * [44] Edward Farhi and Hartmut Neven.  Classification with Quantum Neural Networks on Near Term Processors.  arXiv:1802.06002, pages 1–21, feb 2018.
  * [45] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii.  Quantum circuit learning.  Physical Review A, 98(3):032309, sep 2018.
  * [46] Guangxi Li, Zhixin Song, and Xin Wang.  Vsql: variational shadow quantum learning for classification.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8357–8365, 2021.
  * [47] Weikang Li and Dong-Ling Deng.  Recent advances for quantum classifiers.  Science China Physics, Mechanics & Astronomy, 65(2):1–23, 2022\.
  * [48] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  Deep learning.  MIT press, 2016.
  * [49] 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):4812, dec 2018.
  * [50] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine.  Exact and approximate unitary 2-designs and their application to fidelity estimation.  Physical Review A, 80(1):012304, jul 2009.
  * [51] Joonwoo Bae and Leong Chuan Kwek.  Quantum state discrimination and its applications.  Journal of Physics A: Mathematical and Theoretical, 48(8):083001, feb 2015.
  * [52] Ran Canetti.  Universally composable security: A new paradigm for cryptographic protocols.  In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 136–145. IEEE, 2001.
  * [53] Ryuji Takagi, Suguru Endo, Shintaro Minagawa, and Mile Gu.  Fundamental limits of quantum error mitigation.  arXiv preprint arXiv:2109.04457, 2021.
  * [54] DP DiVincenzo, DW Leung, and BM Terhal.  Quantum data hiding.  IEEE Transactions on Information Theory, 48(3):580–598, 2002.
  * [55] Carl W Helstrom.  Quantum detection and estimation theory.  Journal of Statistical Physics, 1(2):231–252, 1969.
  * [56] Joonwoo Bae and Won-Young Hwang.  Minimum-error discrimination of qubit states: Methods, solutions, and properties.  Phys. Rev. A, 87:012334, Jan 2013.
  * [57] Hongxiang Chen, Leonard Wossnig, Simone Severini, Hartmut Neven, and Masoud Mohseni.  Universal discriminative quantum neural networks.  Quantum Machine Intelligence, 3(1):1–11, 2021.
  * [58] Andrew Patterson, Hongxiang Chen, Leonard Wossnig, Simone Severini, Dan Browne, and Ivan Rungger.  Quantum state discrimination using noisy quantum neural networks.  Physical Review Research, 3(1):013063, 2021.
  * [59] Yanjun Ma, Dianhai Yu, Tian Wu, and Haifeng Wang.  PaddlePaddle: An Open-Source Deep Learning Platform from Industrial Practice.  Frontiers of Data and Domputing, 1(1):105–115, 2019.
  * [60] Diederik P. Kingma and Jimmy Lei Ba.  Adam: A method for stochastic optimization.  3rd International Conference on Learning Representations, ICLR 2015 - Conference Track Proceedings, dec 2015.
  * [61] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [62] 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, pages 1–13, 2021.
  * [63] Christopher A Fuchs and Jeroen Van De Graaf.  Cryptographic distinguishability measures for quantum-mechanical states.  IEEE Transactions on Information Theory, 45(4):1216–1227, 1999\.

Supplementary Material for
Concentration of Data Encoding in Parameterized Quantum Circuits

##  Appendix A Proof of Theorem 1

######  Theorem 1.

Assume each element of an $nD$-dimensional vector $\bm{x}$ obeys an IGD, i.e.,
$x_{j,d}\sim\mathcal{N}(\mu_{j,d},\sigma^{2}_{j,d})$, where
$\sigma_{j,d}\geq\sigma$ for some constant $\sigma$ and $1\leq j\leq n,1\leq
d\leq D$. If $\bm{x}$ is encoded into an $n$-qubit pure state $\rho(\bm{x})$
according to the circuit in Fig. S1, then the quantum divergence between the
average encoded state $\bar{\rho}=\mathbb{E}\left[\rho(\bm{x})\right]$ and the
maximally mixed state $\mathbbm{1}=\frac{I}{2^{n}}$ is upper bounded as

$\displaystyle
D_{2}\left(\bar{\rho}\|\mathbbm{1}\right)\equiv\log\operatorname{Tr}\left(\bar{\rho}^{2}\cdot\mathbbm{1}^{-1}\right)\leq
n\log\left(1+\mathrm{e}^{-D\sigma^{2}}\right).$ (S1)

$\Qcircuit@C=1.5em@R=1em{\lstick{\ket{0}}&\gate{R_{y}(x_{1,1})}\gate{R_{y}(x_{1,2})}\qw\cdots\gate{R_{y}(x_{1,D})}\qw\\\
\lstick{\ket{0}}\gate{R_{y}(x_{2,1})}\gate{R_{y}(x_{2,2})}\qw\cdots\gate{R_{y}(x_{2,D})}\qw\\\
\cdots\cdots\cdots\\\
\lstick{\ket{0}}\gate{R_{y}(x_{n,1})}\gate{R_{y}(x_{n,2})}\qw\cdots\gate{R_{y}(x_{n,D})}\qw}$
Figure S1: Circuit for the data encoding strategy with $R_{y}$ rotations only.

###### Proof.

Let $\rho(\bm{x}_{j})\equiv
R_{y}(x_{j,1}+\cdots+x_{j,D})\op{0}{0}R_{y}^{\dagger}(x_{j,1}+\cdots+x_{j,D})$,
then

$\displaystyle\rho(\bm{x})=\rho(\bm{x}_{1})\otimes\rho(\bm{x}_{2})\otimes\cdots\otimes\rho(\bm{x}_{n}).$
(S2)

Due to the independence of each $\rho(\bm{x}_{j})$, we have

$\displaystyle\bar{\rho}=\mathbb{E}\left[\rho(\bm{x})\right]=\mathbb{E}\left[\rho(\bm{x}_{1})\right]\otimes\mathbb{E}\left[\rho(\bm{x}_{2})\right]\otimes\cdots\otimes\mathbb{E}\left[\rho(\bm{x}_{n})\right].$
(S3)

What’s more, for $j=1,\ldots,n$,

$\displaystyle\mathbb{E}\left[\rho(\bm{x}_{j})\right]$
$\displaystyle=\frac{1}{2}\mathbb{E}\begin{bmatrix}1+\cos{(\sum_{d}x_{j,d})}&\sin{(\sum_{d}x_{j,d})}\\\
\sin{(\sum_{d}x_{j,d})}&1-\cos{(\sum_{d}x_{j,d})}\end{bmatrix}$ (S4)
$\displaystyle=\frac{1}{2}\begin{bmatrix}1+\mathbb{E}\left[\cos{(\sum_{d}x_{j,d})}\right]&\mathbb{E}\left[\sin{(\sum_{d}x_{j,d})}\right]\\\
\mathbb{E}\left[\sin{(\sum_{d}x_{j,d})}\right]&1-\mathbb{E}\left[\cos{(\sum_{d}x_{j,d})}\right]\end{bmatrix}.$
(S5)

######  Lemma S1.

Assume a variable $x\sim\mathcal{N}(\mu,\sigma^{2})$, then

$\displaystyle\mathbb{E}\left[\cos(x)\right]=\mathrm{e}^{-\frac{\sigma^{2}}{2}}\cos(\mu);\qquad\mathbb{E}\left[\sin(x)\right]=\mathrm{e}^{-\frac{\sigma^{2}}{2}}\sin(\mu).$
(S6)

We know
$\sum_{d}x_{j,d}\sim\mathcal{N}(\sum_{d}\mu_{j,d},\sqrt{\sum_{d}\sigma^{2}_{j,d}})$,
and combining Eq. (S5) with Lemma S1, we have

$\displaystyle\Big{|}\Big{|}\mathbb{E}\left[\rho(\bm{x}_{j})\right]\Big{|}\Big{|}_{F}^{2}$
$\displaystyle=\frac{1}{2}+\frac{1}{2}\mathbb{E}^{2}\left[\cos{(\sum_{d}x_{j,d})}\right]+\frac{1}{2}\mathbb{E}^{2}\left[\sin{(\sum_{d}x_{j,d})}\right]$
(S7)
$\displaystyle=\frac{1}{2}+\frac{1}{2}\left(\mathrm{e}^{-\frac{\sum_{d}\sigma^{2}_{j,d}}{2}}\cos(\sum_{d}\mu_{j,d})\right)^{2}+\frac{1}{2}\left(\mathrm{e}^{-\frac{\sum_{d}\sigma^{2}_{j,d}}{2}}\sin(\sum_{d}\mu_{j,d})\right)^{2}$
(S8)
$\displaystyle=\frac{1}{2}+\frac{1}{2}\mathrm{e}^{-\sum_{d}\sigma^{2}_{j,d}}$
(S9) $\displaystyle\leq\frac{1}{2}+\frac{1}{2}\mathrm{e}^{-D\sigma^{2}}.$
(S10)

Finally, from Eq. (S3), we have

$\displaystyle\log\operatorname{Tr}\left(\bar{\rho}^{2}\cdot\left(\frac{I}{2^{n}}\right)^{-1}\right)$
$\displaystyle=\log\left(2^{n}\|\bar{\rho}\|_{F}^{2}\right)$ (S11)
$\displaystyle=\log\left(2^{n}\prod_{j=1}^{n}\Big{|}\Big{|}\mathbb{E}\left[\rho(\bm{x}_{j})\right]\Big{|}\Big{|}_{F}^{2}\right)\leq\log\left(2^{n}\left(\frac{1+\mathrm{e}^{-D\sigma^{2}}}{2}\right)^{n}\right)$
(S12) $\displaystyle=n\log(1+\mathrm{e}^{-D\sigma^{2}}).$ (S13)

This completes the proof. ∎

##  Appendix B Proof of Theorem 2

######  Theorem 2.

(Data Encoding Concentration) Assume each element of a $3nD$-dimensional
vector $\bm{x}$ obeys an IGD, i.e.,
$x_{j,d,k}\sim\mathcal{N}(\mu_{j,d,k},\sigma^{2}_{j,d,k})$, where
$\sigma_{j,d,k}\geq\sigma$ for some constant $\sigma$ and $1\leq j\leq n,1\leq
d\leq D,1\leq k\leq 3$. If $\bm{x}$ is encoded into an $n$-qubit pure state
$\rho(\bm{x})$ according to the circuit in Fig. S2, the quantum divergence
between the average encoded state $\bar{\rho}$ and the maximally mixed state
$\mathbbm{1}$ is upper bounded as

$\displaystyle
D_{2}\left(\bar{\rho}\|\mathbbm{1}\right)\equiv\log\operatorname{Tr}\left(\bar{\rho}^{2}\cdot\mathbbm{1}^{-1}\right)\leq\log\left(1+(2^{n}-1)\mathrm{e}^{-D\sigma^{2}}\right).$
(S14)

$\Qcircuit@C=0.5em@R=1em{\lstick{\ket{0}}&\gate{U3(\bm{x}_{1,1})}\multigate{3}{Etg_{1}}\gate{U3(\bm{x}_{1,2})}\multigate{3}{Etg_{2}}\qw\cdots\gate{U3(\bm{x}_{1,D-1})}\multigate{3}{Etg_{D-1}}\gate{U3(\bm{x}_{1,D})}\qw\\\
\lstick{\ket{0}}\gate{U3(\bm{x}_{2,1})}\ghost{Etg_{1}}\gate{U3(\bm{x}_{2,2})}\ghost{Etg_{2}}\qw\cdots\gate{U3(\bm{x}_{2,D-1})}\ghost{Etg_{D-1}}\gate{U3(\bm{x}_{2,D})}\qw\\\
\cdots\cdots\cdots\cdots\\\
\lstick{\ket{0}}\gate{U3(\bm{x}_{n,1})}\ghost{Etg_{1}}\gate{U3(\bm{x}_{n,2})}\ghost{Etg_{2}}\qw\cdots\gate{U3(\bm{x}_{n,D-1})}\ghost{Etg_{D-1}}\gate{U3(\bm{x}_{n,D})}\qw}$
Figure S2: Circuit for the data encoding strategy with $D$ layers of $U3$
gates and $D-1$ layers of entanglements. Here, each $\bm{x}_{j,d}$ represents
three elements $x_{j,d,1},x_{j,d,2},x_{j,d,3}$, and each $Etg_{i}$ denotes an
arbitrary group of entangled two-qubit gates, such as CNOT or CZ, where $1\leq
j\leq n,1\leq d\leq D,1\leq i\leq D-1$.

###### Proof.

In this proof, we consider the $U3(x_{j,d,1},x_{j,d,2},x_{j,d,3})$ gate as
$R_{z}(x_{j,d,3})\cdot R_{y}(x_{j,d,2})\cdot R_{z}(x_{j,d,1})$, which is one
of the most commonly used ones. Of course, other forms of U3 gate are similar.

#### Outline of Proof.

1) Decomposing initial state. Firstly, we decompose the initial state
according to Pauli bases; 2) Vectors transition. Then by taking the
corresponding coefficients as a row vector, we state that each action of a
group of entangled gates $Etg_{i}$ or a column of $U3$ gates is equivalent to
multiplying the previous coefficient vector by a transition matrix; 3) Bound
by singular value. Finally, we get the upper bound by investigating the
singular values of these transition matrices.

1) Decomposing initial state. The state after the first column of $U3$ gates
becomes

$\displaystyle\rho_{1}=\frac{1}{2}\begin{bmatrix}1+\cos(x_{1,1,2})&\mathrm{e}^{-ix_{1,1,3}}\sin(x_{1,1,2})\\\
\mathrm{e}^{ix_{1,1,3}}\sin(x_{1,1,2})&1-\cos(x_{1,1,2})\end{bmatrix}$
$\displaystyle\otimes\frac{1}{2}\begin{bmatrix}1+\cos(x_{2,1,2})&\mathrm{e}^{-ix_{2,1,3}}\sin(x_{2,1,2})\\\
\mathrm{e}^{ix_{2,1,3}}\sin(x_{2,1,2})&1-\cos(x_{2,1,2})\end{bmatrix}$
$\displaystyle\otimes\cdots\cdots\otimes\frac{1}{2}$
$\displaystyle\begin{bmatrix}1+\cos(x_{n,1,2})&\mathrm{e}^{-ix_{n,1,3}}\sin(x_{n,1,2})\\\
\mathrm{e}^{ix_{n,1,3}}\sin(x_{n,1,2})&1-\cos(x_{n,1,2})\end{bmatrix}.$ (S15)

Now we define
$\rho_{1}\equiv\rho_{1,1}\otimes\rho_{1,2}\otimes\cdots\otimes\rho_{1,n}$,
where

$\displaystyle\rho_{1,j}\equiv\frac{1}{2}\begin{bmatrix}1+\cos(x_{j,1,2})&\mathrm{e}^{-ix_{j,1,3}}\sin(x_{j,1,2})\\\
\mathrm{e}^{ix_{j,1,3}}\sin(x_{j,1,2})&1-\cos(x_{j,1,2})\end{bmatrix}.$ (S16)

And from Lemma S1, we have

$\displaystyle\mathbb{E}\left[\rho_{1,j}\right]=\frac{1}{2}\begin{bmatrix}1+A_{j,1,2}\cos(\mu_{j,1,2})&A_{j,1,3}\mathrm{e}^{-i\mu_{j,1,3}}A_{j,1,2}\sin(\mu_{j,1,2})\\\
A_{j,1,3}\mathrm{e}^{i\mu_{j,1,3}}A_{j,1,2}\sin(\mu_{j,1,2})&1-A_{j,1,2}\cos(\mu_{j,1,2})\end{bmatrix},$
(S17)

where we define $A_{j,d,k}=\mathrm{e}^{-\frac{\sigma_{j,d,k}^{2}}{2}}$ for
writing convenience. Here we note that due to all $x_{j,d,k}$’s being
independent of each other, calculating the expectation of $\rho_{1,j}$ in
advance does not affect the following computations. Next we decompose
$\mathbb{E}\left[\rho_{1,j}\right]$ according to the Pauli bases, i.e.,
$I,Z,X,Y$,

$\displaystyle\mathbb{E}\left[\rho_{1,j}\right]=\frac{1}{2}I+\frac{A_{j,1,2}\cos(\mu_{j,1,2})}{2}Z$
$\displaystyle+\frac{A_{j,1,3}\cos(\mu_{j,1,3})A_{j,1,2}\sin(\mu_{j,1,2})}{2}X$
$\displaystyle+\frac{A_{j,1,3}\sin(\mu_{j,1,3})A_{j,1,2}\sin(\mu_{j,1,2})}{2}Y.$
(S18)

Then from Eq. (B), we could derive that
$\mathbb{E}\left[\rho_{1}\right]=\bigotimes_{j=1}^{n}\mathbb{E}\left[\rho_{1,j}\right]$
can also be decomposed in accordance with various tensor products of Pauli
bases. Therefore, studying the state after the gate $Etg_{1}$ could be
transferred to what performance it will be when entangled two-qubit gates act
on the tensor products of Pauli bases.

2) Vectors transition. Here, we focus on the two widely employed two-qubit
entangled gates CNOT and CZ, and the calculations are concluded in Table 1.
The results in the table show that the transitions are closed for tensor
products of Pauli bases. Here we note that other entangled two-qubit gates
will have a similar effect.

Table 1: The transition table for tensor products of Pauli bases when applying CNOT or CZ gates. Pauli bases | Apply CNOT | Apply CZ
---|---|---
$I\otimes I$ | $I\otimes I$ | $I\otimes I$
$I\otimes Z$ | $Z\otimes Z$ | $I\otimes Z$
$I\otimes X$ | $I\otimes X$ | $Z\otimes X$
$I\otimes Y$ | $Z\otimes Y$ | $Z\otimes Y$
$Z\otimes I$ | $Z\otimes I$ | $Z\otimes I$
$Z\otimes Z$ | $I\otimes Z$ | $Z\otimes Z$
$Z\otimes X$ | $Z\otimes X$ | $I\otimes X$
$Z\otimes Y$ | $I\otimes Y$ | $I\otimes Y$
$X\otimes I$ | $X\otimes X$ | $X\otimes Z$
$X\otimes Z$ | -$Y\otimes Y$ | $X\otimes I$
$X\otimes X$ | $X\otimes I$ | $Y\otimes Y$
$X\otimes Y$ | $Y\otimes Z$ | -$Y\otimes X$
$Y\otimes I$ | $Y\otimes X$ | $Y\otimes Z$
$Y\otimes Z$ | $X\otimes Y$ | $Y\otimes I$
$Y\otimes X$ | $Y\otimes I$ | -$X\otimes Y$
$Y\otimes Y$ | -$X\otimes Z$ | $X\otimes X$

Next, we consider the effects of applying the gate
$U3(x_{1},x_{2},x_{3})=R_{z}(x_{3})R_{y}(x_{2})R_{z}(x_{1})$ to four Pauli
matrices. And the results of the calculations are as follows:

$\displaystyle\mathbb{E}\left[U3\cdot I\cdot U3^{\dagger}\right]$
$\displaystyle=I$ (S19) $\displaystyle\mathbb{E}\left[U3\cdot Z\cdot
U3^{\dagger}\right]$ $\displaystyle=p_{zz}Z+p_{zx}X+p_{zy}Y$ (S20)
$\displaystyle\mathbb{E}\left[U3\cdot X\cdot U3^{\dagger}\right]$
$\displaystyle=p_{xz}Z+p_{xx}X+p_{xy}Y$ (S21)
$\displaystyle\mathbb{E}\left[U3\cdot Y\cdot U3^{\dagger}\right]$
$\displaystyle=p_{yz}Z+p_{yx}X+p_{yy}Y,$ (S22)

where

$\displaystyle p_{zz}$ $\displaystyle=A_{2}\cos(\mu_{2})$ (S23) $\displaystyle
p_{zx}$ $\displaystyle=A_{2}\sin(\mu_{2})A_{3}\cos(\mu_{3})$ (S24)
$\displaystyle p_{zy}$ $\displaystyle=A_{2}\sin(\mu_{2})A_{3}\sin(\mu_{3})$
(S25) $\displaystyle p_{xz}$
$\displaystyle=-A_{2}\sin(\mu_{2})A_{1}\cos(\mu_{1})$ (S26) $\displaystyle
p_{xx}$
$\displaystyle=A_{2}\cos(\mu_{2})A_{1}\cos(\mu_{1})A_{3}\cos(\mu_{3})-A_{1}\sin(\mu_{1})A_{3}\sin(\mu_{3})$
(S27) $\displaystyle p_{xy}$
$\displaystyle=A_{2}\cos(\mu_{2})A_{1}\cos(\mu_{1})A_{3}\sin(\mu_{3})+A_{1}\sin(\mu_{1})A_{3}\cos(\mu_{3})$
(S28) $\displaystyle p_{yz}$
$\displaystyle=A_{2}\sin(\mu_{2})A_{1}\sin(\mu_{1})$ (S29) $\displaystyle
p_{yx}$
$\displaystyle=-A_{2}\cos(\mu_{2})A_{1}\sin(\mu_{1})A_{3}\cos(\mu_{3})-A_{1}\cos(\mu_{1})A_{3}\sin(\mu_{3})$
(S30) $\displaystyle p_{yy}$
$\displaystyle=-A_{2}\cos(\mu_{2})A_{1}\sin(\mu_{1})A_{3}\sin(\mu_{3})+A_{1}\cos(\mu_{1})A_{3}\cos(\mu_{3}).$
(S31)

Here, $x_{k},A_{k},\mu_{k}$ are the abbreviations for
$x_{j,d,k},A_{j,d,k},\mu_{j,d,k}$, respectively.

Now we record Eqs. (S19)-(S22) as a matrix $T$, which we call transition
matrix, i.e.,

$\displaystyle T\equiv\begin{bmatrix}1&0&0&0\\\ 0&p_{zz}&p_{zx}&p_{zy}\\\
0&p_{xz}&p_{xx}&p_{xy}\\\ 0&p_{yz}&p_{yx}&p_{yy}\end{bmatrix}.$ (S32)

By carefully calculating Eqs. (S19)-(S32) again, we also have

$\displaystyle\tiny T\tiny=\begin{bmatrix}1&0&0&0\\\ 0&1&0&0\\\
0&0&A_{1}\cos(\mu_{1})&A_{1}\sin(\mu_{1})\\\
0&0&-A_{1}\sin(\mu_{1})&A_{1}\cos(\mu_{1})\end{bmatrix}\begin{bmatrix}1&0&0&0\\\
0&A_{2}\cos(\mu_{2})&A_{2}\sin(\mu_{2})&0\\\
0&-A_{2}\sin(\mu_{2})&A_{2}\cos(\mu_{2})&0\\\
0&0&0&1\end{bmatrix}\begin{bmatrix}1&0&0&0\\\ 0&1&0&0\\\
0&0&A_{3}\cos(\mu_{3})&A_{3}\sin(\mu_{3})\\\
0&0&-A_{3}\sin(\mu_{3})&A_{3}\cos(\mu_{3})\end{bmatrix},$ (S33)

where the three matrices correspond to the effects of applying $R_{z}(x_{1})$,
$R_{y}(x_{2})$ and $R_{z}(x_{3})$, respectively.

If we further record an arbitrary input
$\rho_{in}\equiv\alpha_{1}I+\alpha_{2}Z+\alpha_{3}X+\alpha_{4}Y$ as a row
vector
$\pi_{in}=\begin{bmatrix}\alpha_{1}&\alpha_{2}&\alpha_{3}&\alpha_{4}\end{bmatrix}$,
then applying the gate $U3(x_{1},x_{2},x_{3})$ to $\rho_{in}$ will result in
the output $\rho_{out}\equiv\beta_{1}I+\beta_{2}Z+\beta_{3}X+\beta_{4}Y$,
where

$\displaystyle\pi_{out}\equiv\begin{bmatrix}\beta_{1}&\beta_{2}&\beta_{3}&\beta_{4}\end{bmatrix}=\begin{bmatrix}\alpha_{1}&\alpha_{2}&\alpha_{3}&\alpha_{4}\end{bmatrix}\begin{bmatrix}1&0&0&0\\\
0&p_{zz}&p_{zx}&p_{zy}\\\ 0&p_{xz}&p_{xx}&p_{xy}\\\
0&p_{yz}&p_{yx}&p_{yy}\end{bmatrix}=\pi_{in}T.$ (S34)

This is a fundamental relationship in this proof, which can be easily verified
in multi-qubit and multi-depth cases. Hence, we could rewrite each
$\mathbb{E}\left[\rho_{d}\right]$, $0\leq d\leq D$, as follows

$\displaystyle\mathbb{E}\left[\rho_{0}\right]\qquad$
$\displaystyle\longleftrightarrow\qquad\pi_{0}=\otimes_{j=1}^{n}\begin{bmatrix}\frac{1}{2}&\frac{1}{2}&0&0\end{bmatrix}$
(S35) $\displaystyle\mathbb{E}\left[\rho_{1}\right]\qquad$
$\displaystyle\longleftrightarrow\qquad\pi_{1}=\pi_{0}\cdot\otimes_{j=1}^{n}T_{j,1}\cdot\widetilde{Etg_{1}}$
(S36) $\displaystyle\cdots$
$\displaystyle\mathbb{E}\left[\rho_{d}\right]\qquad$
$\displaystyle\longleftrightarrow\qquad\pi_{d}=\pi_{d-1}\cdot\otimes_{j=1}^{n}T_{j,d}\cdot\widetilde{Etg_{d}}$
(S37) $\displaystyle\cdots$
$\displaystyle\mathbb{E}\left[\rho_{D-1}\right]\qquad$
$\displaystyle\longleftrightarrow\qquad\pi_{D-1}=\pi_{D-2}\cdot\otimes_{j=1}^{n}T_{j,D-1}\cdot\widetilde{Etg_{D-1}}$
(S38) $\displaystyle\mathbb{E}\left[\rho_{D}\right]\qquad$
$\displaystyle\longleftrightarrow\qquad\pi_{D}=\pi_{D-1}\cdot\otimes_{j=1}^{n}T_{j,D},$
(S39)

where each $T_{j,d}$ represents that this transition matrix is constructed
based on the gate $U3(x_{j,d,1}$, $x_{j,d,2}$, $x_{j,d,3})$ and each
$\widetilde{Etg_{i}}$ means rearranging the elements of the previously
multiplied row vector, which is equivalent to the effect after applying
$Etg_{i}$, $1\leq i\leq D-1$. Here, please note that we omit the possible
negative sign described in Table 1, because in the following proof, it has no
influence.

From the fact that $\operatorname{Tr}\left(P_{i}^{2}\right)=2$,
$\operatorname{Tr}\left(P_{i}P_{j}\right)=0$, where $P_{i},P_{j}$ denote
different Pauli matrices, and combining the relationship in Eq. (S39), we have

$\displaystyle\operatorname{Tr}\left(\mathbb{E}\left[\rho_{D}\right]\right)^{2}=2^{n}\cdot\pi_{D}\left(\pi_{D}\right)^{\top}.$
(S40)

What’s more, we also find that every $\otimes_{j=1}^{n}T_{j,d}$ and
$\widetilde{Etg_{i}}$ always have an element 1 in the top left corner, i.e.,

$\displaystyle\otimes_{j=1}^{n}T_{j,d}\equiv\begin{bmatrix}1&\\\
&\mathcal{T}_{d}\end{bmatrix},\qquad\widetilde{Etg_{i}}\equiv\begin{bmatrix}1&\\\
&\mathcal{E}_{i}\end{bmatrix},$ (S41)

where
$\mathcal{T}_{d},\mathcal{E}_{i}\in\mathbb{R}^{(4^{n}-1)\times(4^{n}-1)}$ and
$1\leq d\leq D,1\leq i\leq D-1$. Therefore,

$\displaystyle\operatorname{Tr}\left(\mathbb{E}\left[\rho_{D}\right]\right)^{2}$
$\displaystyle=2^{n}\cdot\pi_{D}\left(\pi_{D}\right)^{\top}$ (S42)
$\displaystyle=2^{n}\cdot\pi_{0}\begin{bmatrix}1&\\\
&\mathcal{T}_{1}\mathcal{E}_{1}\mathcal{T}_{2}\mathcal{E}_{2}\cdots\mathcal{T}_{D}\end{bmatrix}\begin{bmatrix}1&\\\
&\mathcal{T}_{D}^{\top}\cdots\mathcal{E}_{2}^{\top}\mathcal{T}_{2}^{\top}\mathcal{E}_{1}^{\top}\mathcal{T}_{1}^{\top}\end{bmatrix}\left(\pi_{0}\right)^{\top}$
(S43)
$\displaystyle=2^{n}\cdot\begin{bmatrix}\frac{1}{2^{n}}&\mathring{\pi}_{0}\end{bmatrix}\begin{bmatrix}1&\\\
&\mathcal{T}_{1}\mathcal{E}_{1}\mathcal{T}_{2}\mathcal{E}_{2}\cdots\mathcal{T}_{D}\mathcal{T}_{D}^{\top}\cdots\mathcal{E}_{2}^{\top}\mathcal{T}_{2}^{\top}\mathcal{E}_{1}^{\top}\mathcal{T}_{1}^{\top}\end{bmatrix}\begin{bmatrix}\frac{1}{2^{n}}\\\
\mathring{\pi}_{0}^{\top}\end{bmatrix}$ (S44)
$\displaystyle=\frac{1}{2^{n}}+2^{n}\cdot\mathring{\pi}_{0}\mathcal{T}_{1}\mathcal{E}_{1}\cdots\mathcal{T}_{D-1}\mathcal{E}_{D-1}\mathcal{T}_{D}\mathcal{T}_{D}^{\top}\mathcal{E}_{D-1}^{\top}\mathcal{T}_{D-1}^{\top}\cdots\mathcal{E}_{1}^{\top}\mathcal{T}_{1}^{\top}\mathring{\pi}_{0}^{\top},$
(S45)

where $\mathring{\pi}_{0}$ means that the row vector $\pi_{0}$ removes the
first element.

3) Bound by singular value. Next, in order to further calculate it, we need to
prove first the following two Lemmas.

######  Lemma S2.

Given a Hermitian matrix $H\in\mathbb{C}^{n\times n}$ with all its eigenvalues
no larger than $\lambda$, and an $n$-dimensional vector $\bm{x}$, then

$\displaystyle\bm{x}^{\dagger}H\bm{x}\leq\|\bm{x}\|_{2}^{2}\lambda,$ (S46)

where $\|\cdot\|_{2}$ denotes the $l_{2}$-norm.

###### Proof.

Assume $H$ has the spectral decomposition

$\displaystyle H=\sum_{i=1}^{n}\lambda_{i}\bm{u}_{i}\bm{u}_{i}^{\dagger},$
(S47)

then $\bm{x}$ can be uniquely decomposed as
$\bm{x}=\sum_{i=1}^{n}\alpha_{i}\bm{u}_{i}$ with
$\sum_{i=1}^{n}|\alpha_{i}|^{2}=\|\bm{x}\|_{2}^{2}$. Finally we have

$\displaystyle\bm{x}^{\dagger}H\bm{x}=\sum_{i=1}^{n}|\alpha_{i}|^{2}\lambda_{i}\leq\sum_{i}^{n}|\alpha_{i}|^{2}\lambda=\|\bm{x}\|_{2}^{2}\lambda.$
(S48)

∎

######  Lemma S3.

Given a Hermitian matrix $H\in\mathbb{C}^{n\times n}$ with all its eigenvalues
no larger than $\lambda$, and an arbitrary matrix $Q\in\mathbb{C}^{n\times n}$
with all its singular values no larger than $s$, then the largest eigenvalue
of $QHQ^{\dagger}$ is no larger than $s^{2}\lambda$.

###### Proof.

The largest eigenvalue of $QHQ^{\dagger}$ can be computed as
$\lambda_{max}\equiv\max_{\bm{x}}\bm{x}^{\dagger}QHQ^{\dagger}\bm{x}$, where
$\bm{x}$ denotes a unit vector. Assume $Q$ has the singular value
decomposition

$\displaystyle
Q=USV^{\dagger}=\sum_{i=1}^{n}s_{i}\bm{u}_{i}\bm{v}_{i}^{\dagger}=\begin{bmatrix}\bm{u}_{1}&\bm{u}_{2}&\cdots&\bm{u}_{n}\end{bmatrix}\begin{bmatrix}s_{1}&0&0&0\\\
0&s_{2}&0&0\\\ 0&0&\ddots&0\\\
0&0&0&s_{n}\end{bmatrix}\begin{bmatrix}\bm{v}_{1}^{\dagger}\\\
\bm{v}_{2}^{\dagger}\\\ \vdots\\\ \bm{v}_{n}^{\dagger}\end{bmatrix}$ (S49)

and $\bm{x}=\sum_{i=1}^{n}\alpha_{i}\bm{u}_{i}$ with
$\sum_{i=1}^{n}|\alpha_{i}|^{2}=1$, then

$\displaystyle\bm{x}^{\dagger}QHQ^{\dagger}\bm{x}=\bm{x}^{\dagger}USV^{\dagger}HVSU^{\dagger}\bm{x}=\begin{bmatrix}\alpha_{1}^{\dagger}s_{1}&\alpha_{2}^{\dagger}s_{2}&\cdots&\alpha_{n}^{\dagger}s_{n}\end{bmatrix}V^{\dagger}HV\begin{bmatrix}\alpha_{1}s_{1}\\\
\alpha_{2}s_{2}\\\ \cdots\\\ \alpha_{n}s_{n}\end{bmatrix}.$ (S50)

Consider $V^{\dagger}HV$ as a new Hermitian matrix and $SU^{\dagger}\bm{x}$ as
a new vector $\tilde{\bm{x}}$, then all the eigenvalues of $V^{\dagger}HV$ are
still no larger than $\lambda$ and the square of the $l_{2}$-norm of
$\tilde{\bm{x}}$ is computed as

$\displaystyle\|\tilde{\bm{x}}\|_{2}^{2}=\sum_{i=1}^{n}|\alpha_{i}|^{2}s_{i}^{2}\leq\sum_{i=1}^{n}|\alpha_{i}|^{2}s^{2}=s^{2}.$
(S51)

From Lemma S2, we have

$\displaystyle\bm{x}^{\dagger}QHQ^{\dagger}\bm{x}\leq\|\tilde{\bm{x}}\|_{2}^{2}\lambda\leq
s^{2}\lambda.$ (S52)

As $\bm{x}$ is arbitrary, we can obtain that
$\lambda_{max}\equiv\max_{\bm{x}}\bm{x}^{\dagger}QHQ^{\dagger}\bm{x}$ is no
larger than $s^{2}\lambda$ as well. ∎

Now, let us investigate the singular values of $T_{j,d}$. From Eq. (S32), we
know it always has the trivial biggest singular value 1. The second-biggest
singular value $s_{m}$ can be derived from

$\displaystyle
s_{m}^{2}=\max_{\bm{u}}\bm{u}^{\dagger}\begin{bmatrix}p_{zz}&p_{zx}&p_{zy}\\\
p_{xz}&p_{xx}&p_{xy}\\\
p_{yz}&p_{yx}&p_{yy}\end{bmatrix}\begin{bmatrix}p_{zz}&p_{xz}&p_{yz}\\\
p_{zx}&p_{xx}&p_{yx}\\\ p_{zy}&p_{xy}&p_{yy}\end{bmatrix}\bm{u},$ (S53)

where $\bm{u}\in\mathbb{C}^{3}$ denotes a unit column vector. From Eq. (S33),
we derive that

$\displaystyle\tiny\begin{bmatrix}p_{zz}&p_{zx}&p_{zy}\\\
p_{xz}&p_{xx}&p_{xy}\\\ p_{yz}&p_{yx}&p_{yy}\end{bmatrix}$
$\displaystyle\tiny=\begin{bmatrix}1&0&0\\\
0&A_{1}\cos(\mu_{1})&A_{1}\sin(\mu_{1})\\\
0&-A_{1}\sin(\mu_{1})&A_{1}\cos(\mu_{1})\end{bmatrix}\begin{bmatrix}A_{2}\cos(\mu_{2})&A_{2}\sin(\mu_{2})&0\\\
-A_{2}\sin(\mu_{2})&A_{2}\cos(\mu_{2})&0\\\
0&0&1\end{bmatrix}\begin{bmatrix}1&0&0\\\
0&A_{3}\cos(\mu_{3})&A_{3}\sin(\mu_{3})\\\
0&-A_{3}\sin(\mu_{3})&A_{3}\cos(\mu_{3})\end{bmatrix}$ (S54)
$\displaystyle\tiny=\begin{bmatrix}1&0&0\\\
0&A_{1}\cos(\mu_{1})&A_{1}\sin(\mu_{1})\\\
0&-A_{1}\sin(\mu_{1})&A_{1}\cos(\mu_{1})\end{bmatrix}\begin{bmatrix}\cos(\mu_{2})&\sin(\mu_{2})&0\\\
-\sin(\mu_{2})&\cos(\mu_{2})&0\\\ 0&0&1\end{bmatrix}\begin{bmatrix}A_{2}&&\\\
&A_{2}A_{3}&0\\\ 0&0&A_{3}\end{bmatrix}\begin{bmatrix}1&0&0\\\
0&\cos(\mu_{3})&\sin(\mu_{3})\\\ 0&-\sin(\mu_{3})&\cos(\mu_{3})\end{bmatrix},$
(S55)

hence,

$\displaystyle\scriptsize\begin{bmatrix}p_{zz}&p_{zx}&p_{zy}\\\
p_{xz}&p_{xx}&p_{xy}\\\
p_{yz}&p_{yx}&p_{yy}\end{bmatrix}\begin{bmatrix}p_{zz}&p_{xz}&p_{yz}\\\
p_{zx}&p_{xx}&p_{yx}\\\
p_{zy}&p_{xy}&p_{yy}\end{bmatrix}=Q\begin{bmatrix}\cos(\mu_{2})&\sin(\mu_{2})&0\\\
-\sin(\mu_{2})&\cos(\mu_{2})&0\\\
0&0&1\end{bmatrix}\begin{bmatrix}A_{2}^{2}&&\\\
&\left(A_{2}A_{3}\right)^{2}&0\\\
0&0&A_{3}^{2}\end{bmatrix}\begin{bmatrix}\cos(\mu_{2})&-\sin(\mu_{2})&0\\\
\sin(\mu_{2})&\cos(\mu_{2})&0\\\ 0&0&1\end{bmatrix}Q^{\top},$ (S56)

where $Q\equiv\tiny\begin{bmatrix}1&0&0\\\
0&A_{1}\cos(\mu_{1})&A_{1}\sin(\mu_{1})\\\
0&-A_{1}\sin(\mu_{1})&A_{1}\cos(\mu_{1})\end{bmatrix}$ has the largest
singular value 1.

From Lemma S3, we deduce that the largest eigenvalue of the matrix in Eq.
(S56) is $\max\left\\{A_{2}^{2},A_{3}^{2}\right\\}$, which is no larger than
$\mathrm{e}^{-\sigma^{2}}$. Further combining Eq. (S53), we infer that $s_{m}$
is no larger than $\mathrm{e}^{-\frac{\sigma^{2}}{2}}$, i.e., the second-
biggest singular value of each $T_{j,d}$ is no larger than
$\mathrm{e}^{-\frac{\sigma^{2}}{2}}$. What’s more, we could derive that their
tensor product $\otimes_{j=1}^{n}T_{j,d}$ also has the trivial largest
singular value 1 and the second-largest singular value which is no larger than
$\mathrm{e}^{-\frac{\sigma^{2}}{2}}$.

From the definition of $\mathcal{T}_{d}$ in Eq. (S41), we declare that the
largest singular value of each $\mathcal{T}_{d}$ is no larger than
$\mathrm{e}^{-\frac{\sigma^{2}}{2}}$. Let’s go back to the following formula
in Eq. (S45) to continue estimating
$\operatorname{Tr}\left(\mathbb{E}\left[\rho_{D}\right]\right)^{2}$, i.e.,

$\displaystyle\mathring{\pi}_{0}\mathcal{T}_{1}\mathcal{E}_{1}\cdots\mathcal{T}_{D-1}\mathcal{E}_{D-1}\mathcal{T}_{D}\mathcal{T}_{D}^{\top}\mathcal{E}_{D-1}^{\top}\mathcal{T}_{D-1}^{\top}\cdots\mathcal{E}_{1}^{\top}\mathcal{T}_{1}^{\top}\mathring{\pi}_{0}^{\top}.$
(S57)

Since the largest eigenvalue of $\mathcal{T}_{D}\mathcal{T}_{D}^{\top}$ is no
larger than $\mathrm{e}^{-\sigma^{2}}$, and each $\mathcal{E}_{i}$, defined in
Eq. (S41), is a unitary matrix, by repeatedly applying Lemma S3, we obtain
that largest eigenvalue of $\mathcal{T}_{1}\mathcal{E}_{1}\cdots$
$\mathcal{T}_{D}\mathcal{T}_{D}^{\top}\cdots$
$\mathcal{E}_{1}^{\top}\mathcal{T}_{1}^{\top}$ is no larger than
$\mathrm{e}^{-D\sigma^{2}}$. Furthermore, from Eq. (S35) and the definition of
$\mathring{\pi}_{0}$, we know $\mathring{\pi}_{0}$ has $4^{n}-1$ dimensions,
where $2^{n}-1$ elements are $\frac{1}{2^{n}}$ and the others are $0$. Hence,
$\|\mathring{\pi}_{0}\|^{2}_{2}=\frac{2^{n}-1}{2^{2n}}$. Combining these with
Lemma S2, we have

$\displaystyle\mathring{\pi}_{0}\mathcal{T}_{1}\mathcal{E}_{1}\cdots\mathcal{T}_{D-1}\mathcal{E}_{D-1}\mathcal{T}_{D}\mathcal{T}_{D}^{\top}\mathcal{E}_{D-1}^{\top}\mathcal{T}_{D-1}^{\top}\cdots\mathcal{E}_{1}^{\top}\mathcal{T}_{1}^{\top}\mathring{\pi}_{0}^{\top}\leq\|\mathring{\pi}_{0}\|^{2}_{2}\mathrm{e}^{-D\sigma^{2}}=\frac{2^{n}-1}{2^{2n}}\mathrm{e}^{-D\sigma^{2}}.$
(S58)

Go further, and we have, together with Eq. (S45),

$\displaystyle\operatorname{Tr}\left(\mathbb{E}\left[\rho_{D}\right]\right)^{2}$
$\displaystyle=\frac{1}{2^{n}}+2^{n}\cdot\mathring{\pi}_{0}\mathcal{T}_{1}\mathcal{E}_{1}\cdots\mathcal{T}_{D-1}\mathcal{E}_{D-1}\mathcal{T}_{D}\mathcal{T}_{D}^{\top}\mathcal{E}_{D-1}^{\top}\mathcal{T}_{D-1}^{\top}\cdots\mathcal{E}_{1}^{\top}\mathcal{T}_{1}^{\top}\mathring{\pi}_{0}^{\top}$
(S59)
$\displaystyle\leq\frac{1}{2^{n}}+2^{n}\cdot\frac{2^{n}-1}{2^{2n}}\mathrm{e}^{-D\sigma^{2}}=\frac{1+\left(2^{n}-1\right)\mathrm{e}^{-D\sigma^{2}}}{2^{n}}.$
(S60)

Finally, we have

$\displaystyle\log\operatorname{Tr}\left(\bar{\rho}^{2}\cdot\left(\frac{I}{2^{n}}\right)^{-1}\right)$
$\displaystyle=\log\left(2^{n}\cdot\operatorname{Tr}\left(\mathbb{E}\left[\rho_{D}\right]\right)^{2}\right)\leq\log\left(1+(2^{n}-1)\mathrm{e}^{-D\sigma^{2}}\right).$
(S61)

This completes the proof of Theorem 2.

Without stopping here, we also analyse some generalizations of Theorem 2.

(I) From Eqs. (S53)-(S56), we find that removing the matrix $Q$ will have no
influence on the final result. Hence, we directly generalize that if there is
only one column of $R_{z}R_{y}$ or $R_{y}R_{z}$ gates in each layer, we will
get the same upper bound. In fact, according to our proof method, we infer
that as long as there are two different kinds of rotation gates in each
encoding layer, this upper bound is valid.

(II) What is the result for the case with only $R_{y}$ rotation gates in each
encoding layer? Since each $\mathcal{T}_{d}$ has the largest singular value 1,
it is not suitable for the above proof. However, through analyzing the
transition rule in Table 1, we find that the largest singular value of
$\mathcal{T}_{d-1}\mathcal{E}_{d-1}\mathcal{T}_{d}$ is still no larger than
$\mathrm{e}^{-\frac{\sigma^{2}}{2}}$, which means every two encoding layers
have the same effect as above with one layer. Therefore, the final upper bound
can be changed to
$\log\left(1+(2^{n}-1)\mathrm{e}^{-\lfloor\frac{D}{2}\rfloor\sigma^{2}}\right)$.
Since it has the same trend as the original bound, it has no impact on our
final analysis. ∎

##  Appendix C Proof of Corollary 2.1

######  Corollary 2.1.

Assume there are $M$ classical vectors $\\{\bm{x}^{(m)}\\}^{M}_{m=1}$ sampled
from the distributions described in Theorem 2 and define
$\bar{\rho}_{M}\equiv\frac{1}{M}\sum_{m=1}^{M}\rho(\bm{x}^{(m)})$. Let $H$ be
a Hermitian matrix with its eigenvalues ranging in $[-1,1]$, then given an
arbitrary $\epsilon\in(0,1)$, as long as the depth
$D\geq\frac{1}{\sigma^{2}}\left[(n+4)\ln{2}+2\ln\left(1/\epsilon\right)\right]$,
we have
$\Big{|}\operatorname{Tr}\left[H\left(\bar{\rho}_{M}-\mathbbm{1}\right)\right]\Big{|}\leq\epsilon$
with a probability of at least $1-2\mathrm{e}^{-M\epsilon^{2}/8}$.

###### Proof.

Let $\bar{\rho}\equiv\mathbb{E}\left[\rho\left(\bm{x}^{(m)}\right)\right]$,
then we have

$\displaystyle\Big{|}\operatorname{Tr}\left[H\left(\bar{\rho}_{M}-\frac{I}{2^{n}}\right)\right]\Big{|}$
$\displaystyle=\Big{|}\operatorname{Tr}\left[H\left(\bar{\rho}_{M}-\bar{\rho}+\bar{\rho}-\frac{I}{2^{n}}\right)\right]\Big{|}$
(S62)
$\displaystyle\leq\Big{|}\operatorname{Tr}\left[H\left(\bar{\rho}_{M}-\bar{\rho}\right)\right]\Big{|}+\Big{|}\operatorname{Tr}\left[H\left(\bar{\rho}-\frac{I}{2^{n}}\right)\right]\Big{|},$
(S63)

where the inequality is due to triangle inequality.

Now we first consider the first term in Eq. (S63). Since
$\frac{1}{M}\operatorname{Tr}\left(H\rho(\bm{x}^{(1)})\right)$, $\ldots$,
$\frac{1}{M}\operatorname{Tr}\left(H\rho(\bm{x}^{(M)})\right)$ are i.i.d. and
$\frac{-1}{M}\leq\frac{1}{M}\operatorname{Tr}\left(H\rho(\bm{x}^{(m)})\right)\leq\frac{1}{M}$,
through Hoeffding’s inequality [42], we have

$\displaystyle
P\left(\Big{|}\sum_{m=1}^{M}\frac{1}{M}\operatorname{Tr}\left(H\rho(\bm{x}^{(m)})\right)-\mathbb{E}\left[\operatorname{Tr}\left(H\rho(\bm{x}^{(m)})\right)\right]\Big{|}\leq
t\right)\geq 1-2\mathrm{e}^{-\frac{Mt^{2}}{2}}.$ (S64)

From the fact that
$\sum_{m=1}^{M}\frac{1}{M}\operatorname{Tr}\left(H\rho(\bm{x}^{(m)})\right)=\operatorname{Tr}\left(H\bar{\rho}_{M}\right)$
and
$\mathbb{E}\left[\operatorname{Tr}\left(H\rho(\bm{x}^{(m)})\right)\right]=\operatorname{Tr}\left(H\bar{\rho}\right)$,
we obtain

$\displaystyle\Big{|}\operatorname{Tr}\left(H\bar{\rho}_{M}\right)-\operatorname{Tr}\left(H\bar{\rho}\right)\Big{|}\leq\frac{\epsilon}{2}$
(S65)

with a probability of at least $1-2\mathrm{e}^{-\frac{M\epsilon^{2}}{8}}$.

Next we consider the second term in Eq. (S63). Since the eigenvalues of $H$
range in $[-1,1]$, we obtain

$\displaystyle\Big{|}\operatorname{Tr}\left(H\left(\bar{\rho}-\frac{I}{2^{n}}\right)\right)\Big{|}\leq\Big{|}\Big{|}\bar{\rho}-\frac{I}{2^{n}}\Big{|}\Big{|}_{\text{tr}}\leq
2\sqrt{1-F\left(\bar{\rho},\frac{I}{2^{n}}\right)},$ (S66)

where $\|\cdot\|_{\text{tr}}$ denotes the trace norm and the second inequality
is from the Fuchs–van de Graaf inequalities [63], i.e.,
$1-\sqrt{F(\rho,\sigma)}\leq\frac{1}{2}\|\rho-\sigma\|_{\text{tr}}\leq\sqrt{1-F(\rho,\sigma)}$.
By combining the upper bound in Theorem 2 with the fact that $-\log
F(\rho,\sigma)\leq D_{2}(\rho,\sigma)$ [36], we have

$\displaystyle
F\left(\bar{\rho},\frac{I}{2^{n}}\right)\geq\frac{1}{2^{D_{2}\left(\bar{\rho}\|\frac{I}{2^{n}}\right)}}$
$\displaystyle\geq\frac{1}{1+(2^{n}-1)\mathrm{e}^{-D\sigma^{2}}}$ (S67)
$\displaystyle\geq\frac{1}{1+\frac{(2^{n}-1)\epsilon^{2}}{2^{n+4}}}\geq\frac{1}{1+\frac{2^{n}\epsilon^{2}}{16\cdot
2^{n}}}$ (S68) $\displaystyle=\frac{16}{16+\epsilon^{2}},$ (S69)

where in Eq. (S68) we use the condition
$D\geq\frac{1}{\sigma^{2}}\left[(n+4)\ln{2}+2\ln\left(1/\epsilon\right)\right]$.
By inserting Eq. (S69) into Eq. (S66), we can get

$\displaystyle\Big{|}\operatorname{Tr}\left(H\left(\bar{\rho}-\frac{I}{2^{n}}\right)\right)\Big{|}\leq
2\sqrt{1-\frac{16}{16+\epsilon^{2}}}=\frac{2\epsilon}{\sqrt{16+\epsilon^{2}}}\leq\frac{\epsilon}{2}.$
(S70)

Bringing Eqs. (S65) and (S70) into Eq. (S63), we complete the proof of
Corollary 2.1. ∎

##  Appendix D Proof of Proposition 4

######  Proposition 4.

Consider a $K$-classification task with the data set $\mathcal{D}$ defined in
Def. 3. If the encoding depth
$D\geq\frac{1}{\sigma^{2}}\left[(n+4)\ln{2}+2\ln\left(1/\epsilon\right)\right]$
for some $\epsilon\in(0,1)$, then the partial gradient of the loss function
defined in Eq. (9) with respect to each parameter $\theta_{i}$ of the employed
QNN is bounded as

$\displaystyle\Big{|}\frac{\partial
L\left(\bm{\theta};\mathcal{D}\right)}{\partial\theta_{i}}\Big{|}\leq
K\epsilon$ (S71)

with a probability of at least $1-2\mathrm{e}^{-M\epsilon^{2}/8}$.

###### Proof.

From the chain rule, we know

$\displaystyle\frac{\partial
L\left(\bm{\theta};\mathcal{D}\right)}{\partial\theta_{i}}=\frac{1}{KM}\sum_{m=1}^{KM}\frac{\partial
L^{(m)}}{\partial\theta_{i}}=\frac{1}{KM}\sum_{m=1}^{KM}\sum_{l=1}^{K}\frac{\partial
L^{(m)}}{\partial h_{l}}\frac{\partial h_{l}}{\partial\theta_{i}}.$ (S72)

We first calculate $\frac{\partial L^{(m)}}{\partial h_{l}}$ as follows

$\displaystyle\frac{\partial L^{(m)}}{\partial
h_{l}}=\frac{\partial\sum_{k=1}^{K}y^{(m)}_{k}\left(\ln{\sum_{j=1}^{K}\mathrm{e}^{h_{j}}}-h_{k}\right)}{\partial
h_{l}}=\begin{cases}\sum_{k=1}^{K}y^{(m)}_{k}\frac{\mathrm{e}^{h_{l}}}{\sum_{j=1}^{K}\mathrm{e}^{h_{j}}},&l\neq
k\\\
\sum_{k=1}^{K}y^{(m)}_{k}\left(\frac{\mathrm{e}^{h_{l}}}{\sum_{j=1}^{K}\mathrm{e}^{h_{j}}}-1\right),&l=k\end{cases}$
(S73)

Since ${\mathrm{e}^{h_{l}}}/{\sum_{j=1}^{K}\mathrm{e}^{h_{j}}}\in(0,1)$ and
$\bm{y}^{(m)}$ is one-hot, we can get its upper bound as $|\frac{\partial
L^{(m)}}{\partial h_{l}}|\leq 1$. Next, from the parameter-shift rule [45], we
calculate $\frac{\partial h_{l}}{\partial\theta_{i}}$ as follows

$\displaystyle\frac{\partial
h_{l}}{\partial\theta_{i}}=\frac{1}{2}\left[\operatorname{Tr}\left(H_{l}U(\bm{\theta}_{+\frac{\pi}{2}})\rho(\bm{x}^{(m)})U^{\dagger}(\bm{\theta}_{+\frac{\pi}{2}})\right)-\operatorname{Tr}\left(H_{l}U(\bm{\theta}_{-\frac{\pi}{2}})\rho(\bm{x}^{(m)})U^{\dagger}(\bm{\theta}_{-\frac{\pi}{2}})\right)\right],$
(S74)

where $\bm{\theta}_{+\frac{\pi}{2}}$ means adding $\frac{\pi}{2}$ to
$\theta_{i}$ and keeping the others unchanged, and
$\bm{\theta}_{-\frac{\pi}{2}}$ is similarly defined. If we define

$\displaystyle\tilde{H_{l}}\equiv\frac{1}{2}\left[U^{\dagger}(\bm{\theta}_{+\frac{\pi}{2}})H_{l}U(\bm{\theta}_{+\frac{\pi}{2}})-U^{\dagger}(\bm{\theta}_{-\frac{\pi}{2}})H_{l}U(\bm{\theta}_{-\frac{\pi}{2}})\right],$
(S75)

then together with Eqs. (S72)-(S74), we could bound the gradient as

$\displaystyle\Big{|}\frac{\partial
L\left(\bm{\theta};\mathcal{D}\right)}{\partial\theta_{i}}\Big{|}\leq\Big{|}\frac{1}{KM}\sum_{m=1}^{KM}\sum_{l=1}^{K}\frac{\partial
h_{l}}{\partial\theta_{i}}\Big{|}$
$\displaystyle=\Big{|}\frac{1}{KM}\sum_{m=1}^{KM}\sum_{l=1}^{K}\operatorname{Tr}\left(\tilde{H_{l}}\rho(\bm{x}^{(m)})\right)\Big{|}$
(S76)
$\displaystyle\leq\sum_{l=1}^{K}\Big{|}\frac{1}{KM}\sum_{m=1}^{KM}\operatorname{Tr}\left(\tilde{H_{l}}\rho(\bm{x}^{(m)})\right)\Big{|}$
(S77)
$\displaystyle=\sum_{l=1}^{K}\Big{|}\frac{1}{KM}\sum_{m=1}^{KM}\sum_{k=1}^{K}y^{(m)}_{k}\operatorname{Tr}\left(\tilde{H_{l}}\rho(\bm{x}^{(m)})\right)\Big{|}$
(S78)
$\displaystyle\leq\sum_{l=1}^{K}\frac{1}{K}\sum_{k=1}^{K}\Big{|}\frac{1}{M}\sum_{m=1}^{KM}y^{(m)}_{k}\operatorname{Tr}\left(\tilde{H_{l}}\rho(\bm{x}^{(m)})\right)\Big{|}$
(S79) $\displaystyle\leq\sum_{l=1}^{K}\frac{1}{K}\sum_{k=1}^{K}\epsilon.$
(S80)

Here, it could be easily verified that the eigenvalues of $\tilde{H_{l}}$
(defined in Eq. (S75)) range in $[-1,1]$ and
$\operatorname{Tr}(\tilde{H_{l}})=0$. Then from Corollary 2.1, we could bound
Eq. (S79) as Eq. (S80), i.e., for any $\epsilon\in(0,1)$, provided that the
encoding depth
$D\geq\frac{1}{\sigma^{2}}\left[(n+4)\ln{2}+2\ln\left(1/\epsilon\right)\right]$,
we have $|\frac{\partial
L\left(\bm{\theta};\mathcal{D}\right)}{\partial\theta_{i}}|\leq K\epsilon$
with a probability of at least $1-2\mathrm{e}^{-M\epsilon^{2}/8}$. This
completes the proof of Proposition 4. ∎