Problem-Dependent Power of Quantum Neural Networks on Multi-Class
  Classification
Quantum neural networks (QNNs) have become an important tool for
understanding the physical world, but their advantages and limitations are not
fully understood. Some QNNs with specific encoding methods can be efficiently
simulated by classical surrogates, while others with quantum memory may perform
better than classical classifiers. Here we systematically investigate the
problem-dependent power of quantum neural classifiers (QCs) on multi-class
classification tasks. Through the analysis of expected risk, a measure that
weighs the training loss and the generalization error of a classifier jointly,
we identify two key findings: first, the training loss dominates the power
rather than the generalization ability; second, QCs undergo a U-shaped risk
curve, in contrast to the double-descent risk curve of deep neural classifiers.
We also reveal the intrinsic connection between optimal QCs and the Helstrom
bound and the equiangular tight frame. Using these findings, we propose a
method that uses loss dynamics to probe whether a QC may be more effective than
a classical classifier on a particular learning task. Numerical results
demonstrate the effectiveness of our approach to explain the superiority of QCs
over multilayer Perceptron on parity datasets and their limitations over
convolutional neural networks on image datasets. Our work sheds light on the
problem-dependent power of QNNs and offers a practical tool for evaluating
their potential merit.
Yuxuan Du, Yibo Yang, Dacheng Tao, Min-Hsiu Hsieh
# Demystify Problem-Dependent Power of Quantum Neural Networks on Multi-Class Classification

###### Abstract

Quantum neural networks (QNNs) have become an important tool for understanding the physical world, but their advantages and limitations are not fully understood. Some QNNs with specific encoding methods can be efficiently simulated by classical surrogates, while others with quantum memory may perform better than classical classifiers. Here we systematically investigate the problem-dependent power of quantum neural classifiers (QCs) on multi-class classification tasks. Through the analysis of expected risk, a measure that weighs the training loss and the generalization error of a classifier jointly, we identify two key findings: first, the training loss dominates the power rather than the generalization ability; second, QCs undergo a U-shaped risk curve, in contrast to the double-descent risk curve of deep neural classifiers. We also reveal the intrinsic connection between optimal QCs and the Helstrom bound and the equiangular tight frame. Using these findings, we propose a method that uses loss dynamics to probe whether a QC may be more effective than a classical classifier on a particular learning task. Numerical results demonstrate the effectiveness of our approach to explain the superiority of QCs over multilayer Perceptron on parity datasets and their limitations over convolutional neural networks on image datasets. Our work sheds light on the problem-dependent power of QNNs and offers a practical tool for evaluating their potential merit.

## I Introduction

The advent of hardware fabrication pushes the boundary of quantum computing from verifying its superiority on artificial tasks [1, 2, 3] to conquering realistic problems with merits [4, 5, 6]. This has led to the emergence of a popular paradigm known as quantum neural networks (QNNs), which combine variational quantum Ansatze with classical optimizers [7, 8]. So far, various QNN-based methods have been proposed to address difficult problems in areas such as quantum physics [9, 10, 11, 12], quantum information theory [13, 14, 15, 16], combinatorial optimization [17, 18, 19, 20, 21], and machine learning [22, 23, 24, 25, 26]. Among these applications, QNNs are often deployed as _quantum classifiers_ (QCs) to predict correct labels of the input data [27, 28, 29, 30, 31, 32], e.g., categorize image objects [33, 34, 35], classify phases of quantum matters [36, 37, 38, 39], and distinguish entangled states from separable states [40, 41].

To comprehend the full potential of existing quantum classifiers (QCs) and to spur the development of novel QCs, huge efforts have been made to unveil the learnability of QCs [42, 43, 44]. Prior literature establishes the foundations of QCs from three primary aspects, i.e., model capacity [45, 46, 47, 48], trainability [49, 50, 51], and generalization [52, 53, 54, 55, 56, 57]. Nevertheless, the advantages and constraints of QCs have rarely been proven [57, 58, 59, 60, 61, 62]. Meanwhile, previous results cannot rigorously explain the empirical observations such that QCs generally outperform classical classifiers (CCs) on handcraft or quantum data [44, 63] but are inferior to them on realistic problems [64]. As a result, the need for QCs to address classical issues remains highly questionable.

A principal criteria in characterizing the power of a classifier is the expected risk [65], which weighs the empirical risk (i.e., training loss) and the generalization error (i.e., test loss) jointly. An _optimal_ classifier is one which achieves zero expected risk. As shown in Fig. 1(a), the success of deep neural classifiers is attributed to their double-descent risk curves [66, 67]. This means that as the hypothesis space is continually expanded, the expected risk of a trained deep neural classifier initially decreases, increases, and when it overfits the train set, undergoes a second descent. As such, to show the superiority of QCs over CCs, it demands to distill ubiquitous rules that capture the risk curve of diverse QCs in addition to conditions where the expected risk of QCs can be lower than CCs.

In this study, we unify a broad class of QCs in the same framework and understand their problem-dependent ability under the expected risk (see Fig. 1(b)). Our analysis reveals two substantial outcomes: (i) trainability dominates QCs' ability more than generalization ability; (ii) QCs undergo a U-shape risk curve instead of the double-descent curve for CCs. These outcomes consolidate and refine previous observations. Concretely, the first outcome suggests that the deficiency of QCs on classical data stems from their limited ability to fit the train set, resulting in a larger training loss compared to CCs. The second outcome highlights the distinct learning behavior of QCs and CCs. Despite the fact that overparameterization is fundamental to enhance the performance of CCs, it adversely affects the power of QCs. In line with the diverse dynamics of the risk curves for QCs and CCs, we devise an efficient problem-dependent method to recognize potential merits of QCs, as shown in Fig. 1(a). Conceptually, for a given learning task, our method fits the loss (risk) dynamics of QC and CC under the prior (i.e., U-shape versus double descent) and then
identify the 'advant' regime where the risk of QC is lower than CC. Numerical simulations are conducted to support our theoretical results.

On the technical level, we approach the two outcomes by separately quantifying the empirical risk and generalization error of QCs. Specifically, we first prove conditions of QCs that lead to near-zero empirical risk, the geometric interpretation of which is depicted in Fig. 1(c). As a byproduct, we elucidate how such conditions are inherently linked to quantum state discrimination and quantum measurement theory. In addition, we prove that deep QCs can never reach the vanished empirical risk by utilizing the concentration property of quantum observables [68, 69]. We next analyze the generalization error of QCs by exploiting algorithmic robustness [70]. The derived bound surpasses prior results because it is the first non-vacuous bound in the over-parameterized regime. By combining the unreachable zero empirical risk with the manipulatable generalization error, we obtain the first outcome. The second outcome is gained by integrating the fact that deep QCs are unable to reach the vanished empirical risk with the first outcome.

## II Main results

_Expected risk._-- Let us first introduce a \(K\)-class (\(K\geq 2\)) classification task. Denote the input space as \(\mathcal{X}\), the label (class) space as \(\mathcal{Y}=\{1,\cdots,K\}\), and the train set as \(\mathcal{D}=\bigcup_{k=1}^{K}\{(\mathbf{x}^{(i,k)},y^{(i,k)})\}_{i=1}^{n_{k}}\) with \(|\mathcal{D}|\) samples drawn i.i.d. from an unknown probability distribution \(\mathbb{D}\) on \(\mathcal{Z}=\mathcal{X}\times\mathcal{Y}\). In standard scenarios, the number of train samples in each class is the same, i.e., \(n_{1}=...=n_{k}\equiv n_{c}\) and \(|\mathcal{D}|:=n=Kn_{c}\). The purpose of a classification algorithm \(\mathcal{A}\) is using \(\mathcal{D}\) to infer a hypothesis (a.k.a., a classifier) \(h_{\mathcal{A}_{\mathcal{D}}}:\mathcal{X}\rightarrow\mathbb{R}^{K}\) from the hypothesis space \(\mathcal{H}\) to separate train examples from different classes. This is equivalent to identifying an optimal hypothesis in \(\mathcal{H}\) minimizing the _expected risk_\(\mathsf{R}(h)=\mathbb{E}_{(\mathbf{x},\mathbf{y})\sim\mathbb{D}}[\ell(h(\mathbf{x}),y)]\), where \(\ell(\cdot,\cdot)\) is the per-sample loss and for clarity we specify it as the square error with \(\ell(\mathbf{a},\mathbf{b})=\frac{1}{2}\|\mathbf{a}-\mathbf{b}\|_{2}^{2}\)[71]. Unfortunately, the inaccessible distribution \(\mathbb{D}\) forbids us to assess the expected risk directly. In practice, \(\mathcal{A}\) alternatively learns an _empirical classifier_\(\hat{h}\in\mathcal{H}\), as the global minimizer of the (regularized) loss function

\[\mathcal{L}(h,\mathcal{D})=\frac{1}{n}\sum_{i=1}^{n_{c}}\sum_{k=1}^{K}\ell(h( \mathbf{x}^{(i,k)}),y^{(i,k)})+\mathfrak{E}(h), \tag{1}\]

where \(\mathfrak{E}(h)\) is an optional regularizer.

The foremost role of the risk means that quantum advantages can be ascertained if \(\mathsf{R}(\hat{h}_{Q})<\mathsf{R}(\hat{h}_{C})\), where \(\hat{h}_{Q}\) and \(\hat{h}_{C}\) are the empirical QC and CC on \(\mathcal{D}\). Unlike conventions merely focusing on a QC on one specific task, the above criteria orients to unearth _ubiquitous rules_ of QCs with computational advantages. To reconcile the intractable issue of \(\mathsf{R}(\hat{h})\) and proceed the following analysis, we decomposed it into two measurable terms, i.e.,

\[\mathsf{R}(\hat{h})=\mathsf{R}_{\text{ERM}}(\hat{h})+\mathsf{R}_{\text{Gene}}( \hat{h}), \tag{2}\]

where \(\mathsf{R}_{\text{ERM}}(\hat{h})=\frac{1}{n}\sum_{i=1}^{n}\sum_{k=1}^{K}\ell( \hat{h}(\mathbf{x}^{(i,k)}),y^{(i,k)})\) is the _empirical risk_ and \(\mathsf{R}_{\text{Gene}}(\hat{h})=\mathsf{R}(\hat{h})-\mathsf{R}_{\text{ERM}}( \hat{h})\) is the _generalization error_. Based on Eq. (2), detecting advances of QCs is translated to deriving under what conditions do QCs commit both lower \(\mathsf{R}_{\text{ERM}}\) and \(\mathsf{R}_{\text{Gene}}\) than CCs.

To better elucidate our results, let us recall that the general form of QC is \(\hat{h}_{Q}=\arg\min_{h_{Q}\in\mathcal{H}_{Q}}\mathcal{L}(h_{Q},\mathcal{D})\)

Figure 1: **Risk curve and geometry of the unified QCs.** (a) The risk curve of QCs and CCs are highlighted by the solid red and blue lines (labeled by ‘Q-\(\mathcal{R}\)’ and ‘C-\(\mathcal{R}\)’), respectively. The former yields a ‘U’ shape while the latter yields a double-descent tendency. Potential advantages of QCs are dominated by the empirical risk, highlighted by the dashed curve. The shaded region refers to the potential merits of QCs. (b) The unified QC consists of two parts, the feature state \(\rho\) and the measure operator \(\mathbf{o}\). This model covers diverse QCs. (c) Geometric relationship between \(\{\rho^{(i,k)}\}\) and \(\mathbf{o}\) of QCs with (near) zero training loss: (i) the feature states associated with train samples belonging to the same class concentrate around their class-feature mean, i.e., \(\bar{\rho}^{*(k)}:=\rho^{*(1,k)}=...=\rho^{*(n_{c},k)}\) for \(\forall k\in[K]\); (ii) the class-feature means are maximally distant with each other, i.e., \(\operatorname{Tr}(\bar{\rho}^{*(k)}\bar{\rho}^{*(k^{\prime})})\sim\delta_{k,k^{ \prime}}\); (iii) the measure operator should align with class-feature means, i.e., \(\operatorname{Tr}(\bar{\rho}^{*(k)}o^{*(k^{\prime})})\sim\delta_{k,k^{\prime}}\).
where \(\mathcal{L}\) is defined in Eq. (1) and \(\mathcal{H}_{Q}\) is the hypothesis space. For an \(N\)-qubit QC, its hypothesis space is

\[\mathcal{H}_{Q}=\left\{\left[h_{Q}(\cdot,U(\mathbf{\theta}),O^{(k)})\right]_{k=1:K} \left|\mathbf{\theta}\in\mathbf{\Theta}\right.\right\}, \tag{3}\]

where \([\cdot]_{k=1:K}\) is a \(K\)-dimensional vector, its \(k\)-th entry \(h_{Q}(\mathbf{x},U(\mathbf{\theta}),O^{(k)})=\mathrm{Tr}(O^{(k)}U(\mathbf{\theta})\sigma( \mathbf{x})U(\mathbf{\theta})^{\dagger})\) for \(\forall k\in[K]\) refers to the output (prediction) of quantum circuits, \(\sigma(\mathbf{x})=U_{E}(\mathbf{x})(\ket{0}\bra{0}^{\otimes N}U_{E}(\mathbf{x})^{\dagger}\) is the input state of \(\mathbf{x}\) with the encoding circuit \(U_{E}(\cdot)\), \(\mathbf{O}=\{O^{(k)}\}_{k=1}^{K}\) is a set of measure operators, and \(U(\mathbf{\theta})\) is the adopted Ansatz with trainable parameters \(\mathbf{\theta}\) living in the parameter space \(\mathbf{\Theta}\). Without loss of generality, we define \(U(\mathbf{\theta})=\prod_{l=1}^{N_{l}}(u_{l}(\mathbf{\theta})u_{e})\in\mathcal{U}(2^{ N})\), where \(u_{l}(\mathbf{\theta})\in\mathcal{U}(2^{m})\) is the \(l\)-th parameterized quantum gate operated with at most \(m\) qubits (\(m\leq N\)) and \(u_{e}\) refers to fixed quantum gates. Similarly, we define \(U_{E}(\mathbf{x})=\prod_{g=1}^{N_{g}}u_{g}(\mathbf{x})\in\mathcal{U}(2^{N})\), where \(u_{g}(\mathbf{x})\in\mathcal{U}(2^{m})\) refers to the \(g\)-th quantum gate operated with at most \(m\) qubits, and \(N_{g}\) gates contain \(N_{ge}\) tunable gates and \(N_{g}-N_{ge}\) fixed gates.

Due to the diverse constructions of \(U(\mathbf{\theta})\) and \(U_{E}(\cdot)\), it is necessary to unify various QCs into the same framework to obtain the generic results. Notably, the unified QC should be _agnostic to_ particular forms of these two terms. A feasible way is rewritten \(h_{Q}(\cdot,U(\mathbf{\theta}),O^{(k)})\) as

\[h_{Q}(\rho^{(i,k)},o^{(k)}):=\mathrm{Tr}(\rho^{(i,k)}o^{(k)})\ \forall k\in[K], \tag{4}\]

where \(O^{(k)}=\mathbb{I}_{2^{N-D}}\otimes o^{(k)}\) with the nontrivial local operator \(o^{(k)}\in\mathbb{C}^{2^{D}\times 2^{D}}\), \(D\) describes the locality, and \(\rho^{(i,k)}=\mathrm{Tr}_{D}(U(\mathbf{\theta})\sigma(\mathbf{x}^{(i,k)})U(\mathbf{\theta} )^{\dagger})\) corresponds to the state before measurements, named as _feature state_. An intuition of the unified QC is shown in Fig. 1(b).

We are now ready to exploit the unified framework to analyze the expected risk of QCs. Let \(\mathbf{\rho}=\{\rho^{(i,k)}\}\) and \(\mathbf{o}=\{o^{(k)}\}\) be two sets collecting all feature states and measure operators. The following theorem exhibits conditions in which QCs allow a low expected risk, where the formal statement and the proof are deferred to SM A.

**Theorem 1** (informal).: _Following notations in Eqs. (1)-(4), when the train data size is \(nO(KN_{ge}\log\frac{KN_{g}}{\epsilon\delta})\) with \(\epsilon\) being the tolerable error, and the optimal sets of \(\mathbf{\rho}^{*}\) and \(\mathbf{o}^{*}\) satisfy three conditions: (i) the feature states have the vanished variability in the same class; (ii) all feature states are equal length and are orthogonal in the varied classes; (iii) any feature state is alignment with the measure operator in the same class, with probability \(1-\delta\), the expected risk of QC tends to be zero, i.e., \(\mathsf{R}(\hat{h}_{Q})\to 0\)._

Conditions (i)-(iii) visualized in Fig. 1(c) sculpt the geometric interpretations of \(\mathbf{\rho}^{*}\) and \(\mathbf{o}^{*}\). These properties come across the design philosophy of CCs, e.g., linear discriminant analysis and neural collapse phenomenon appeared in most deep neural classifiers [71, 72, 73]. Moreover, these conditions unveil the intrinsic connection between optimal QCs and the quantum state discrimination [74], since \(\mathbf{\rho}^{*}\) and \(\mathbf{o}^{*}\) should maximize the Helstrom bound [75], which explains the ultimate limit of QCs observed in [76]. However, as will be explained later (see Corollary 1 and Lemma 1), under certain scenarios, it is hard for QCs to meet these conditions. A typical instance is applying QC to learn the image dataset, where the difficulty stems from the limited nonlinearity of QC to fit the train set, thereby inducing a large empirical risk.

Conditions (i)-(iii) also imply how the quantum measurement theory can be used to guide the design of QCs. Namely, the mean feature states of each class \(\{\tilde{\rho}^{\star(k)}\}\) compose the equiangular tight frame (ETF) and Condition (iii) suggests that the optimal measure operators \(\{\mathbf{o}^{*}\}\) also satisfy this ETF [77]. Due to the relation between symmetric informationally complete (SIC) measurements and ETF [78, 79], the optimal measure operators could be estimated by various SIC construction strategies [80]. Besides, the locality \(D\) of \(\{\mathbf{o}^{*}\}\) should be carefully selected in QCs in which a small \(D\) precludes the acquisition of the optimal QCs (i.e., the complex ETF does not exist when \(2^{D}=K\)[81, 82]), while an extremely large \(D\) may incur the barren plateaus [83, 84]. Furthermore, when \(K\) is large, Pauli-based measurements are preferable than computational basis measurements in QCs, since the former allows classical shadow techniques to accelerate the training of QCs [85, 86].

The scaling behavior of \(n\) indicates that it is data-efficient for QCs to attain a low generalization error, where the size of train set only linearly depends on the class number \(K\) and the number of encoding gates \(N_{ge}\) (see Lemma 3 for the technical elaboration). In other words, the generalization error of QCs can be well controlled by the modest-size train data.

According to Theorem 1, the challenges in satisfying Conditions (i)-(iii) and the well controlled generalization error pinpoint that the risk of a QC is mostly dominated by its empirical loss rather than its generalization error. In this view, the core in devising advanced QCs is tailoring \(\mathcal{H}_{Q}\) in Eq. (3) so that \(\hat{h}_{Q}\) has a (near) zero empirical risk on \(\mathcal{D}\), or equivalently examining whether the employed QCs can fulfill Conditions (i)-(iii).

_U-shape risk curve._--The risk curve concerns how the expected risk of a classifier behaves with the varied hypothesis space. It is desired that as with deep neural classifiers, QCs undergo a double-descent risk curve in the sense that the over-parameterized QCs consent a low expected risk when the trainable parameters \(N_{t}\) is much greater than the train data \(n\). If so, 'over-parameterization' could serve as a golden law in designing QCs. However, the following corollary refutes the existence of the double-descent risk curve for QCs.

**Corollary 1**.: _Following notations in Theorem 1, when \(\{U_{E}(\mathbf{x})|\mathbf{x}\in\mathcal{X}\}\) follows the Haar distribution, with probability \(1-\delta\), the empirical QC follows \(|\,\mathrm{Tr}\left(\sigma(\mathbf{x}^{(i,k)})\sigma(\mathbf{x})\right)-\frac{1}{2^{N}}| \leq\sqrt{\frac{3}{2^{2N}\delta}}\). When \(\{U(\mathbf{\theta})|\mathbf{\theta}\in\Theta\}\) follows the Haar distribution, with probability \(1-\delta\), the empirical QC follows
\(\sqrt{\frac{\operatorname{Tr}(\rho^{(k^{\prime})})^{2}+2\operatorname{Tr}((\rho^{(k^ {\prime})})^{2})}{2^{2}\hbar\delta}}\).

The proof is deferred to SM B. The achieved results reveal the caveat of deep QCs. Specifically, when \(U_{E}(\mathbf{x})\) is deep, two encoded states \(\sigma(\mathbf{x}^{(i,k)})\) and \(\sigma(\mathbf{x}^{(i^{\prime},k)})\) from the same class tend to be orthogonal, which contradicts with Conditions (i) in Theorem 1. Besides, when \(U(\mathbf{\theta})\) is deep, the output of QC concentrates to zero, regardless how \(o^{(k^{\prime})}\) and \(\rho^{(i,k)}\) are selected. This violates Condition (iii) in Theorem 1. Overall, over-parameterized QCs encounter the high empirical risk and thus the high expected risk, which suggests that QCs experience a _U-shape risk curve_. This observation differs the dynamics of QCs from variational quantum Eigensolvers, since the latter can benefit from over-parameterization, e.g., better trainability and convergence rate [87, 88, 89, 90]. Moreover, the rule of thumb in QCs' construction is slimming \(\mathcal{H}_{Q}\) to find the valley region. Intriguingly, tailoring the feature states echoes with quantum metric learning and quantum self-supervised learning [91, 92, 93, 94, 95].

_Probe power of QCs via loss dynamics._--The distinct tendency of the risk curves between QCs and CCs provides a succinct way to recognize the potential quantum advantages. As shown in Fig. 1(a), given a specific data set, the U-shape risk curve of QCs indicates that its advantages mostly appear in the valley region. Precisely, if the risk values of QC around the basin are lower than those of CC, potential merits may exist; otherwise, QC is inferior to CC. The proved learning behavior of QCs, accompanied with the tight generalization bound, allows us to effectively fit its risk curve according to their loss dynamics. Specifically, our method contains three steps. First, \(W\) tuples of \(\{n,N_{t},T\}\) are initialized based on Theorem 1 so that the collected risk points of QC span the basin area with low generalization error. Second, we execute QC and CC under these \(W\) hyper-parameter settings and fit their loss dynamics to attain the risk curve. Last, we compare two risk curves and probe potential advantages. See SM F for the implementation details.

_Technical analysis._--Theorem 1 is achieved by analyzing when \(\mathsf{R}_{\mathrm{ERM}}(\hat{h}_{Q})\) and \(\mathsf{R}_{\mathrm{Gene}}(\hat{h}_{Q})\) are (near) zero. In the analysis of \(\mathsf{R}_{\mathrm{ERM}}(\hat{h}_{Q})\), we first consider the most general case in which both \(\mathbf{\rho}\) and \(\mathbf{o}\) are tunable, where \(\hat{h}_{Q}\equiv h_{Q}(\mathbf{\rho}^{*},\mathbf{o}^{*})\) with \((\mathbf{\rho}^{*},\mathbf{o}^{*})=\min_{\mathbf{\rho},\mathbf{o}}\mathcal{L}(\mathbf{\rho},\mathbf{ o})\).

**Lemma 1** (Informal).: _When the regularizer \(\mathfrak{E}\) is considered and \((\mathbf{\rho}^{*},\mathbf{o}^{*})\) meets the three conditions in Theorem 1, the global minimizer leads to \(\mathsf{R}_{\mathrm{ERM}}(\hat{h}_{Q})=C_{1}^{2}/2\) with \(C_{1}\) depending on the hyper-parameters in \(\mathfrak{E}\)._

The achieved properties of \(\mathbf{o}^{*}\) can be used as a priori to simplify QCs. To this end, the following lemma quantifies \(\mathsf{R}_{\mathrm{ERM}}(\hat{h}_{Q})\) when \(\mathbf{o}\) is predefined and \(\mathfrak{E}=0\), where \(\hat{h}_{Q}\equiv h_{Q}(\mathbf{\rho}^{*},\mathbf{o})\) with \(\mathbf{\rho}^{*}=\min_{\mathbf{\rho}}\mathcal{L}(\mathbf{\rho},\mathbf{o})\).

**Lemma 2** (Informal).: _When the predefined \(\{o^{(k)}\}\) are mutually orthogonal with each other and the conditions in Theorem 1 are satisfied, we have \(\mathsf{R}_{\mathrm{ERM}}(\hat{h}_{Q})=0\)._

The proofs of Lemmas 1 and 2 are given in SM C&D.

We next analyze \(\mathsf{R}_{\mathrm{Gene}}(\hat{h}_{Q})\). Prior results cannot be used to prove Theorem 1, since such bounds polynomially scale with the trainable parameters and become vacuous in the over-parameterized regime. To remedy this issue, we utilize the concept of algorithmic robustness [70].

**Definition 1** (Robustness).: _A learning algorithm \(\mathcal{A}\) is \((R,\nu(\cdot))\)-robust with \(R\in\mathbb{N}\) and \(\nu(\cdot):\mathcal{Z}^{n}\to\mathbb{R}\), if \(\mathcal{Z}\) can be partitioned into \(R\) disjoint sets, denoted by \(\{C_{r}\}_{r=1}^{R}\), such that the following holds for all \(\mathcal{D}\subset\mathcal{Z}^{n}:\forall\mathbf{s}=(\mathbf{x}^{(i)},y^{(i)})\in \mathcal{D}\), \(\forall z=(\mathbf{x},y)\in\mathcal{Z}\), \(\forall r\in[R]\),_

\[\mathbf{s},\mathbf{z}\in\mathcal{C}_{r}\Rightarrow|l(h_{\mathcal{A}_{D}}(\mathbf{x}^{(i)}), y^{(i)})-l(h_{\mathcal{A}_{D}}(\mathbf{x}),y)|\leq\nu(\mathcal{D}).\]

Concisely, robustness measures how much the loss value can be varied with respect to the input space \(\mathcal{Z}\). A higher robustness of a classifier admits lower \(R\), \(\nu(\cdot)\), and \(\mathsf{R}_{\mathrm{Gene}}\)[70]. The following lemma quantifies the upper bound of \(\mathsf{R}_{\mathrm{Gene}}(\hat{h}_{Q})\) whose proof is given in SM E.

**Lemma 3**.: _Suppose the measure operator is bounded by \(C_{2}\) with \(\max_{k\in[K]}\|o^{(k)}\|\leq C_{2}\). Define \(\epsilon\) as the tolerable error. Following notations in Definition 1, the empirical QC is \((K(28N_{ge}/\epsilon)^{4nN_{ge}},4L_{1}KC_{2}\epsilon)\)-robust, and with probability \(1-\delta\) we have_

\[\mathsf{R}_{\mathrm{Gene}}(\hat{h}_{Q})\leq 4L_{1}KC_{2}\epsilon+5\xi(\hat{h}_{Q}) \sqrt{\frac{|\mathcal{T}_{\mathcal{D}}|4^{m}N_{ge}\ln\frac{56KN_{ge}}{\epsilon \delta}}{n}},\]

_where \(L_{1}\) is the Lipschitz constant of \(\ell\) with respect to \(h_{Q}\), \(\mathcal{T}_{\mathcal{D}}^{\mathcal{D}}=\{i\in[n]:\mathbf{z}^{(i)}\in\mathcal{C}_{r}\}\), \(\xi(\hat{h}):=\max_{\mathbf{z}\in\mathcal{Z}}(\xi(\hat{h},\mathbf{z}))\), and \(\mathcal{T}_{\mathcal{D}}:=\{r\in[R]:|\mathcal{T}_{r}^{\mathcal{D}}|\geq 1\}\)._

The achieved results convey threefold insights. First, our bound does not explicitly depend on the number of trainable parameters [96]. This unlocks a new way to understand the generalization ability of QCs, especially for the over-parameterized ones. Next, our bound hints that a carefully designed \(U_{E}\) can enhance performance of QCs [97, 53]. Last, \(\mathsf{R}_{\mathrm{Gene}}(\hat{h}_{Q})\to 0\) requires \(n\gg|\mathcal{T}_{\mathcal{D}}|4^{m}N_{ge}\). Fortunately, a reasonable value of \(n\) is sufficient to warrant this condition, because in general \(m\leq 2\), \(N_{ge}\propto|\mathbf{x}|\), and \(|\mathcal{T}_{\mathcal{D}}|\) is continuously decreased from \(n\) to \(K\) with respect to the reduced empirical loss.

## III Numerical simulations

We conduct numerical simulations to exhibit that the advantages and limitations of QCs on different classification tasks can be interpreted by the derived risk curve and feature states. The omitted construction details and results are deferred to SM G.

We first apply QC to accomplish the binary classification on the parity dataset [98, 99, 100]. The number of qubits is \(N=6\) and the hardware-efficient Ansatz is adopted to realize \(U(\mathbf{\theta})\). The gradient descent method is used as the classical optimizer. Two measure operators are
\(o^{(1)}=\left|0\right\rangle\left\langle 0\right|\) and \(o^{(2)}=\left|1\right\rangle\left\langle 1\right|\). The simulation results of QC with \(N_{t}=54\) are displayed in Fig. 2(a). Particularly, the averaged train (test) accuracy steadily grows from \(44.1\%\) to \(100\%\) within \(22\) epochs, and the corresponding loss decreases from \(0.26\) to \(4\times 10^{-5}\). The dynamics of the feature states \(\{\rho^{(i,t,\dagger)}\}\) with \(t\in\{0,10,20,30,40\}\) visualized by Bloch spheres echo with Lemma 2. Besides, QC becomes more robust when we continue the training. Although the train (test) accuracy reaches the optimum, the loss can be further reduced and suggests a lower risk warranted by Theorem 1. We further compare the risk curve between QC and multilayer Perceptron (MLP) on this dataset. We fit their risk curves following the proposed method to probe potential quantum merits. As shown in Fig. 2(b), QC clearly outperforms MLP when the trainable parameters ranges from \(20\) to \(140\) and the valley of the risk curve is around \(N_{t}=70\)[101].

We then apply QC to learn the Fashion-MNIST image dataset with \(K=9\)[102]. The employed number of qubits is \(N=10\) and the Pauli-based measure operators are employed. Convolutional neural networks (CNNs) are exploited as the reference. For all classifiers, the number of epochs is fixed to be \(T=50\) and the number of trainable parameters \(N_{t}\) ranges from \(60\) to \(9000\). Each setting is repeated with \(3\) times. As shown in Fig. 3, when the layer number is \(50\) with \(N_{t}=1500\), both the train and test accuracies of QC are about \(50\%\). This performance is inferior to CNN under the similar setting. To explore whether QC has the potential to outperform CNN on this dataset, we compare their risk curves. As shown in Fig. 3(b), unlike the parity dataset, QC is evidently inferior to CNN on Fashion-MNIST dataset.

## IV Discussions and Outlook

We understand the potential of diverse QCs in terms of the expected risk. Our theoretical findings demonstrate that the efficacy of QCs is dependent on the problem at hand, which explains the empirical evidence of their superiority on synthetic and quantum datasets, yet inferiority on realistic tasks. With the clear difference between the risk curve of QCs and deep neural classifiers, we present a concise technique to investigate potential quantum benefits by fitting their loss dynamics. Numerical results validate our theoretical results and the effectiveness of our method.

There are several interesting future research directions. The U-shape curve of QCs poses two open questions. First, can contemporary QCs attain quantum benefits on certain classical data when only limited data and restricted computing resources are available? Secondly, is it necessary to redesign QCs such as nonlinear QCs [103, 104] that can also exhibit a double-descent risk curve? Besides, the unearthed connection between the conditions towards optimal empirical risk and quantum state discrimination opens a new research avenue that amplifies the potential of QCs on quantum data aided by quantum information theory. Finally, it is intriguing to extend the developed non-vacuous generalization error bound of QCs to other scenarios, such as out-of-distribution data, in order to identify potential quantum advantages.

###### Acknowledgements.

 The authors thank Xinbiao Wang for valuable input and inspiring discussions.

Figure 3: **Multi-class classification on the image dataset with \(K=9\).** (a) The learning performance of QC when the layer number is \(50\). (b) The fitted risk curve of QC and CNN. All labels have the same meaning with those used in Fig. 2.

Figure 2: **Binary classification on the parity dataset.** (a) The learning performance of QC when the layer number is \(3\). The \(x\)-axis denotes the epoch numbers. Shaded region represents variance. The Bloch spheres display the quantum feature states at different epochs. (b) The fitted risk curve of QC and MLP. The \(x\)-axis denotes the number of trainable parameters. The label ‘_QC-risk_’ (‘_MLP-risk_’) refers to the fitted risk curve of QC and MLP. The label ‘_QC-res_’ (‘_MLP-res_’) refers to the collected results used for fitting the curves.