# Coreset selection can accelerate quantum machine learning models with
provable generalization

Yiming Huang  Center on Frontiers of Computing Studies, Peking University,
Beijing 100871, China  School of Computer Science, Peking University, Beijing
100871, China  Huiyuan Wang  Peterhouse, Univeristy of Cambridge, CB2 1RD
Cambridge, Cambridgeshire, U.K.  Yuxuan Du  JD Explore Academy, Beijing
101111, China  Xiao Yuan  Center on Frontiers of Computing Studies, Peking
University, Beijing 100871, China  School of Computer Science, Peking
University, Beijing 100871, China

###### Abstract

Quantum neural networks (QNNs) and quantum kernels stand as prominent figures
in the realm of quantum machine learning, poised to leverage the nascent
capabilities of near-term quantum computers to surmount classical machine
learning challenges. Nonetheless, the training efficiency challenge poses a
limitation on both QNNs and quantum kernels, curbing their efficacy when
applied to extensive datasets. To confront this concern, we present a unified
approach: coreset selection, aimed at expediting the training of QNNs and
quantum kernels by distilling a judicious subset from the original training
dataset. Furthermore, we analyze the generalization error bounds of QNNs and
quantum kernels when trained on such coresets, unveiling the comparable
performance with those training on the complete original dataset. Through
systematic numerical simulations, we illuminate the potential of coreset
selection in expediting tasks encompassing synthetic data classification,
identification of quantum correlations, and quantum compiling. Our work offers
a useful way to improve diverse quantum machine learning models with a
theoretical guarantee while reducing the training cost.

##  1 Introduction

Quantum neural networks (QNNs) [1, 2, 3, 4] and quantum kernels [5, 6] have
emerged as pivotal models in the burgeoning field of quantum machine learning
(QML) [7, 8, 9], poised to unlock the power of near-term quantum computers to
address challenges that elude classical machine learning paradigms [10, 11].
The allure of these models is rooted in a fusion of theoretical advances and
practical adaptability. That is, theoretical evidence showcases their
superiority over classical counterparts in diverse scenarios, spanning
synthetic datasets, discrete logarithmic problems, and quantum information
processing tasks [6, 12, 13, 14, 15, 16], as measured by sample complexity and
runtime considerations. Complementing their theoretical strength, their
implementation displays flexibility, adeptly accommodating constraints posed
by contemporary quantum hardware, including qubit connectivity and limited
circuit depth. This convergence of theoretical promise and practical
flexibility has spurred a wave of empirical investigations, substantiating the
viability and potential benefits of QNNs and quantum kernels across real-world
applications such as computer vision [17, 18, 19] and quantum physics [20,
21].

Despite their promising potential, QNNs and quantum kernels confront a
pertinent challenge concerning the training efficiency, resulting in a
constrained practical applicability towards large-scale datasets [22]. This
limitation is particularly evident due to the absence of fundamental training
mechanisms like back-propagation and batch gradient descent in the majority of
QNNs, imperative for the swift training of deep neural networks [23].
Similarly, the training process of quantum kernels necessitates the collection
of a kernel matrix of size $O(N^{2})$, with $N$ being the number of training
examples and each entry demanding independent evaluation via a specific
quantum circuit. Consequently, the capacities of both QNNs and quantum kernels
to effectively navigate vast training datasets, characterized by millions of
data points, are compromised.

In response to the above challenge, several research lines have emerged to
enhance the training efficiency of QNNs. The first line embarks on improving
the optimizer or the initialization methods, seeking to expedite convergence
towards the minimal empirical risk through a reduction in measurements and
iterations [24, 25, 26, 27, 28]. Nonetheless, the non-convex nature of the
loss landscape cautions against potential entrapment within saddle points
during the optimization process [29, 30, 31]. The second avenue delves into
feature dimension reduction techniques, enabling more streamlined utilization
of quantum resources for each data point [32, 33]. However, this approach may
not necessarily alleviate overall runtime complexity, potentially even
exacerbating it. The third research pathway navigates the realm of QNN
expressivity, imposing judicious constraints to facilitate the integration of
back-propagation through meticulously engineered ansatzes [34, 35].
Nevertheless, the extent to which these constrained ansatzes might impact QNN
performance on unseen data remains a dynamic yet unresolved facet.

The endeavor to enhance the training efficiency of quantum kernels has
received less attention in contrast to QNNs. This divergence in attention
stems from the shared observation that both classical and quantum kernels
demand $O(N^{2})$ runtime for the collection of the kernel matrix. Existing
literature focused on enhancing the training efficiency of quantum kernels has
predominantly centered on the development of advanced encoding methods [36,
37]. These methods aim to mitigate the usage of quantum resources and
attenuate the manifestation of barren plateaus [38]. However, despite the
cultivation of various research trajectories directed at enhancing QML models,
it is noteworthy that these approaches often retain model-specific attributes,
potentially harboring unforeseen side effects. This realization begets a
pivotal inquiry: Can a unified approach be devised that systematically
enhances the training efficiency of both QNNs and quantum kernels while
safeguarding a steadfast theoretical guarantee?

In this study, we provide an affirmation of the above question by introducing
the coreset selection techniques into QML. Conceptually, coreset is an
effective preprocessing approach to distill a weighted subset from the large
training dataset, which guarantees that models fitting the coreset also
provide a good fit for the original data. Considering that the training
efficiency of both QNNs and quantum kernels hinges on the number of training
examples, coreset provides a unified way to enhance their training efficiency.
Moreover, the theoretical foundation of coreset is established on the recent
generalization error analysis of QNNs and quantum kernels, indicating that few
training examples are sufficient to attain a good test performance. In this
regard, we provide a rigorous analysis of the generalization ability of QNNs
and quantum kernels training on the coreset. The achieved bounds exhibit the
comparable generalization performance of QNN and quantum kernel learning when
they are optimized under the original dataset and the coreset. Numerical
simulations on synthetic data, identification of non-classical correlations in
quantum states, and quantum circuit compilation confirm the effectiveness of
our proposal.

##  2 Related works

The prior literature related to our work can be divided into two classes: the
algorithms for accelerating the optimization of QML models and the
generalization error analysis of QML models. In the following, we separately
explain how our work relates to and differs from the previous studies.

Acceleration algorithms for QML models. As aforementioned, various algorithms
have been introduced to expedite the optimization of QNNs rather than quantum
kernels. These algorithms can be classified into three distinct categories,
each addressing different facets of optimization improvement: data feature
engineering, QNN architecture design, and optimizer enhancement.

In the realm of data feature engineering, the core concept revolves around
implementing dimensionality reduction techniques such as principal component
analysis and feature selection during the pre-processing stage [39]. This
strategy effectively reduces the quantum resources required for processing
data points compared to their unprocessed counterparts. Within the domain of
architecture design, there exists a dual focus on encoding strategy design
[40, 41] and ansatz design [42, 43, 44, 45, 46]. The underlying principle
emphasizes the utilization of a minimal number of qubits, trainable
parameters, and shallower circuit depths, all geared towards achieving
competent performance in learning tasks. In parallel, efforts to enhance
optimizers have also garnered attention. The deployment of higher-order
gradient descent or machine-learning assisted optimizers [24, 25, 26, 27, 28]
and distributed learning schemes [47] has been advocated as a means to
accelerate convergence rates and wall-clock time, thereby further augmenting
the efficiency of QNN optimization.

Our work is complementary to the above approaches since the reduced size of
data is independent of data feature engineering, QNN architecture design, and
optimizer enhancement. In other words, QNNs trained on coreset can be further
accelerated by the above approaches. Moreover, different from prior literature
that concentrates on the acceleration of QNNs, coreset selection can be
directly employed to accelerate the collection of quantum kernels.

Generalization of QML models. Several studies have undertaken the task of
quantifying the generalization error of QNNs through the lens of the
foundational learning-theoretic technique known as uniform convergence [48,
49, 50, 51, 52]. In general, the resulting bound for generalization adheres to
the format of $O(\sqrt{p/N})$, where $p$ denotes the count of trainable
parameters and $N$ signifies the number of training instances. For quantum
kernels, the generalization error upper bound scales with $O(\sqrt{C_{1}/N})$,
where $C_{1}$ depends on the labels of data and the value of quantum kernel
[6]. When system noise is considered, the generalization error upper bound
degrades to $O(\sqrt{C_{1}/N}+N/(C_{2}\sqrt{m}))$, where $m$ is the shot
number and $C_{2}$ depends on the kernel value, shot number, and the noise
level [53].

Our work leverages the above analysis to quantify how the coreset selection
effects the learning performance of QNNs and quantum kernels, respectively.

We note that although Ref. [54] also discusses quantum coreset. Their primary
emphasis lies in employing fault-tolerant quantum computers to speed up the
construction of coresets, a subject that falls beyond the scope of our work.
In addition, Ref. [55] and Ref. [56] illustrated the potential of coreset in
specific applications, i.e., clustering and image classification, without a
unified view and generalization error analysis.

##  3 Preliminaries

In this section, we first introduce the concept of machine learning and
corerset. Then, we formally introduce the mechanism of quantum neural networks
(QNNs) and quantum kernels under the supervised learning paradigm.

###  3.1 Foundations of machine learning

Let ${\cal{S}}_{t}=\\{{{\bm{x}}}_{i},y_{i}\\}_{i=1}^{N_{t}}$ be the dataset in
which each paired training example $({{\bm{x}}}_{i},y_{i})$ is independent and
identically sampled over $\cal{Z}=\cal{X}\times\cal{Y}$ with probability
distribution $p_{\cal{Z}}$, where $\cal{X}$ is feature space and $\cal{Y}$ the
label space. The goal of supervised learning algorithms is to find a
hypothesis $f:\cal{X}\rightarrow\cal{Y}$ with trainable parameters ${\bm{w}}$
such that the true risk $R$ on the distribution $p_{\cal{Z}}$ is minimized
with

$R=\mathbb{E}_{{({{\bm{x}}},y)}\sim p_{\cal{Z}}}[l(f_{\bm{w}}(\bm{x}),y)],$
(1)

where $l(\cdot,\cdot)$ is the loss function used to measure the degree of fit
between the output of the hypothesis and its corresponding ground truth. As
the distribution $p_{\cal{Z}}$ is unknown and, even given, accessing all the
data over $\cal{Z}$ would be impractical, in practice, the optimal hypothesis
is estimated by optimizing $\bm{w}$ to minimize the empirical risk $R_{e}$
over the training dataset, i.e.,

$R_{e}=\frac{1}{N_{t}}\sum_{({{\bm{x}}}_{i},y_{i})\in\cal{S}}l(f_{\bm{w}}({{\bm{x}}}_{i}),y_{i}).$
(2)

###  3.2 Coreset in machine learning

As the learning algorithm evolves, not only are models becoming increasingly
complex, but training datasets are also growing larger. With growing volumes
of data, the challenges on how to organize and analyze the massive data force
us to devise effective approaches to condense the enormous data set. The
concept of coreset selection, as a paradigm for extracting a data subset that
is comprised of informative samples such that the generalization performance
of the model trained over this reduced set is closed to those trained on the
entire data set [57], is a promising solution to address the issue.

######  Definition 1.

(Coreset) Let $P$ be a set of points in space $\mathcal{V}$, and $f$ be a
monotone measure function, we call a subset $Q\subseteq P$ as an
$\epsilon$-coreset of $P$, if

$|f(Q)-f(P)|\leq\epsilon\cdot f(P).$ (3)

Various coreset selection approaches are exploited to assist in dealing with
computationally intractable problems in different learning tasks and data
types [58, 59]. Throughout the whole work, we consider a geometry-based method
to construct coreset [60]. As shown in Fig. 1, the goal of coreset
construction is to find $k$ data points as the centers $\mathcal{C}$ such that
the maximum distance between any point $s\in\mathcal{S}$ to its nearest center
is minimized, i.e., selecting $\mathcal{C}$ such that the radius $\delta_{c}$
of which is minimized. The optimization of finding the coreset can be
formulated as

$\mathcal{S}_{c}=\arg\min_{\mathcal{C}\subseteq\mathcal{S},|\mathcal{C}|=k}\max_{{{\bm{x}}}_{j}\in\mathcal{S}}D({{\bm{x}}}_{j},{{\bm{x}}}_{c}),$
(4)

where
$D({{\bm{x}}}_{i},{{\bm{x}}}_{c})=\min_{{{\bm{x}}}_{c}\in\mathcal{C}}d({{\bm{x}}}_{i},{{\bm{x}}}_{c})$
denotes the distance between the point $i$ to its closest center. Although it
is an NP-Hard problem to find $\mathcal{S}_{c}$, there is a provable greedy
algorithm can efficiently get a 2-approximate solution, i.e., if
$\mathcal{C}^{*}$ is the optimal solution of Eq. (4), we can efficiently find
a solution $\mathcal{C}$ such that
$\delta_{\mathcal{C}^{*}}\leq\delta_{\mathcal{C}}\leq
2\cdot\delta_{\mathcal{C}^{*}}$.

Figure 1: Coreset construction as a $k$-center problem. The red stars are $k$
picked points with $\delta_{c}$ radius covering the entire set. In the case
shown in the figure, there are 5 center data points $P_{k}\in\mathcal{S}$ with
$k\in\\{1,2,...,5\\}$ such that the maximum distance from any point in
$\mathcal{D}$ to its closest center is minimized.

###  3.3 Quantum neural networks

Quantum neural network (QNN) refers to a class of neural networks that
leverages the power of variational quantum circuits and classical optimizers
to tackle learning problems. A QNN is mainly composed of three components:
feature encoding, variational parametrized circuit, and measurement, as
depicted in Fig. 2. Generally, feature encoding utilizes an encoding circuit
$U_{\bm{x}}$ to map the classical input $\bm{x}$ into an $n$-qubit state
$|\bm{x}\rangle$. The concrete approaches of feature encoding are diverse, as
outlined in [41, 61]. A variational parametrized circuit $U_{\theta}$ evolves
the feature state $|\bm{x}\rangle$ to a parametrized state
$|\bm{x},\theta\rangle$, where the parameters $\theta$ are to be tuned for
minimizing the training loss. Measurement extracts the processed information
stored in parametrized state $|\bm{x},\theta\rangle$ into the classical
register and may combine with a post-processing operation to form the output
of QNN.

Figure 2: A general feed-forward process of quantum neural networks. The input
state $|\phi_{0}\rangle$ is firstly fed to feature encoding block to map the
classical data $\bm{x}$ to $|\bm{x}\rangle$, and then use variational circuit
$U_{\theta}$ to form a parametrized state $|\bm{x},\theta\rangle$ which is
used for minimizing the loss function. In the end, the measurement output will
be used to estimate the prediction residuals.

In this work, we consider a QNN implemented by the data-reuploading strategy
[61, 40, 62], alternating the feature encoding circuit $U_{\bm{x}}$ and the
variational circuit $U_{\theta}$ to generate parametrized state
$|\bm{x},\theta\rangle$, i.e.,

$|\bm{x},\theta\rangle=U_{\theta}U_{\bm{x}}...U_{\bm{x}}U_{\theta}U_{\bm{x}}\lvert\varphi\rangle.$
(5)

Without loss of generality, the feature encoding circuit and the variational
circuit take the form as

$U_{\bm{x}}=\bigotimes_{j=1}^{n}\exp{(-i\bm{x}_{j}H)}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\
U_{\theta}=\bigotimes_{j=1}^{n}\exp(-i\theta_{j}H)V,$ (6)

where $H\in\\{\sigma_{x},\sigma_{y},\sigma_{z}\\}$ is the Hermitian operator
and $V$ refers to the fixed gates such as a sequence of CNOT gates. Once the
variational state $|\bm{x},\theta\rangle$ is evolved, the measurement operator
$M$ is applied to obtain the estimated expectation value. Given the training
data set $\mathcal{S}=\\{\bm{x}_{i},y_{i}\\}_{i=1}^{N_{t}}$, the empirical
risk of QNN over $\mathcal{S}$ is

$R_{e}^{\text{QNN}}(\theta)=\frac{1}{|\mathcal{S}|}\sum_{\bm{x}_{i},y_{i}\in\mathcal{S}}l(tr[M|\bm{x}_{i},\theta\rangle\langle\bm{x}_{i},\theta|],y_{i}).$
(7)

A possible choice of $l$ is the mean square error, i.e., $l(a,b)=(a-b)^{2}$.
The optimization of QNN, i.e., the minimization of $R_{e}^{\text{QNN}}$, can
be completed by the gradient-descent optimizer based on the parameter shift
rule [22].

###  3.4 Quantum kernels

The kernel methods have been extensively studied in classical machine learning
and applied to various scenarios such as face recognition and the
interpretation of the dynamics of deep neural networks [63, 64]. Their quantum
counterparts have also been extensively investigated from both experimental
and theoretical perspectives [3, 53]. Formally, quantum kernels leverage
quantum feature maps that encode the classical vector $\bm{x}$ into a higher
Hilbert space to perform the kernel trick. One well known quantum kernel
function $\kappa(\bm{x},\bm{x}^{\prime})$ is defined as the overlap between
the quantum states $|\bm{x}\rangle$ and $|\bm{x}^{\prime}\rangle$ that encodes
$\bm{x}$ and $\bm{x}^{\prime}$ via an $n$-qubit feature encoding circuit
$U_{e}$, i.e.
$\kappa(\bm{x},\bm{x}^{\prime})=|\langle\bm{x}^{\prime}|\bm{x}\rangle|^{2}$
with $|\bm{x}\rangle=U_{e}(\bm{x})|+\rangle^{\otimes N}$ and
$|+\rangle=H\lvert 0\rangle$, as shown in Fig. 3. In this work, we consider a
generic quantum feature map proposed in [3], i.e.,

$U_{e}(\bm{x})=\exp{(\sum_{i}\bm{x}_{i}\sigma_{j}^{Z}+\sum_{i,j}(\pi-\bm{x}_{i})(\pi-\bm{x}_{j})\sigma_{i}^{Z}\sigma_{j}^{Z})}.$
(8)

We note that other symmetric positive-definite functions are also valid
candidates for implementing quantum kernels. Different forms of the quantum
kernel correspond to different feature maps in Hilbert space, which could
provide quantum merits for classification tasks if designed properly [65].

Figure 3: The quantum circuit implementation of quantum kernel
$\kappa{(\bm{x},\bm{x}^{\prime})}$ considered in this work. The circuit
separately encodes $\bm{x}$ and $\bm{x}^{\prime}$ as the parameter of $h$
layers variational circuit $U$ and $U^{\dagger}$ into the states
$|\bm{x}\rangle$ and $|\bm{x}^{\prime}\rangle$ .

##  4 Coreset selection for QML models

This section first introduces the algorithmic implementation of coreset
selection. Then, we elucidate how to use the constructed coreset to train QNNs
and quantum kernels.

The Pseudo code of coreset selection for QML models is summarized in Algorithm
1. The main idea is regarding the coreset selection as a data preprocessing
strategy, which aims to find $k$ balls, centered at points
$\\{\bm{x}_{s}\\}_{s=1}^{k}$ in data space $\mathcal{P}$, to cover the whole
data set with the radius $\delta_{c}$. Let
$\mathcal{S}=\\{(\bm{x}_{1},y_{1}),\dots,(\bm{x}_{N_{t}},y_{N_{t}})\\}$ be an
$n_{c}$-class data set and a hyper-parameter $k$ satisfy $k\gg n_{c}$. We
apply the following procedure to each class to construct the coreset.

1

input : Data set
$\mathcal{S}=\\{(\bm{x}_{1},y_{1}),\dots,(\bm{x}_{N_{t}},y_{N_{t}})\\}$,
covering number $k$.

output : The subset $\mathcal{S}_{c}\subseteq\mathcal{S}$ with
$|\mathcal{S}_{c}|=k$ and corresponding weight $\\{\gamma_{s}\\}_{s=1}^{k}$.

2 for  _$i\leftarrow 1$ to $n_{c}$_ do

3 $\mathcal{S}_{c}^{(i)}\leftarrow\emptyset$; /* initialize the coreset for
each class */

4

5 end for

6for  _$i\leftarrow 1$ to $n_{c}$_ do

7 $\mathcal{S}_{c}^{(i)}\leftarrow\bm{x}\in\mathcal{S}^{(i)}$;

8 /* randomly select point $\bm{x}$ from set $\mathcal{S}^{(i)}$ associated
with class $i$, and add it to set $\mathcal{S}_{c}^{(i)}$. */

9 while  _$|\mathcal{S}_{c}^{(i)}|
<\left\lceil\frac{|\mathcal{S}^{(i)}|}{|\mathcal{S}|}\cdot k\right\rceil$_ do

10
$\bm{x}=\operatorname*{arg\,max}_{\bm{x}\in\mathcal{S}^{(i)}\textbackslash{\mathcal{S}_{c}^{(i)}}}\min_{\bm{x}^{\prime}}d(\bm{x},\bm{x}^{\prime})$;

11 $\mathcal{S}_{c}^{(i)}\leftarrow\mathcal{S}_{c}^{(i)}\bigcup\\{\bm{x}\\}$;

12

13 end while

14

15 end for

16$s=1$;

17 for  _$j\leftarrow 1$ to $n_{c}$_ do

18 for  _ $\bm{x}\in\mathcal{S}_{c}^{(j)}$_ do

19
$\gamma_{s}\leftarrow\sum_{\bm{x}^{\prime}\in\mathcal{S}^{(j)}}\bm{I}_{|\bm{x}-\bm{x}^{\prime}|\leq\delta_{c}^{(j)}}$;

20 /* use the indicator function to count the number of same-class training
samples in radius $\delta_{c}$. */

21 $s\leftarrow s+1$;

22

23 end for

24

25 end for

26

27$\mathcal{S}_{c}\leftarrow\emptyset$;

28 for  _$i\leftarrow 1$ to $n_{c}$_ do

29 $\mathcal{S}_{c}\leftarrow\mathcal{S}_{c}\bigcup\mathcal{S}_{c}^{(i)}$

30 end for

return $\mathcal{S}_{c}$ and $\\{\gamma_{s}\\}_{s=1}^{k}$.

Algorithm 1 The greedy algorithm for $k$-center coreset selection.

For each class $i\in[n_{c}]$, at the first step, we randomly pick a data point
$\bm{x}$ from the set $\mathcal{S}^{(i)}\subseteq\mathcal{S}$ and put it into
the initialized empty set $\mathcal{S}_{c}^{(i)}$, where $\mathcal{S}^{(i)}$
refers to the set of all training data points associated with the label $i$.
In the second step, we iteratively choose the data point from
$\mathcal{S}^{(i)}$ to be as far away as possible from the other centers in
$\mathcal{S}_{c}^{(i)}$. That is, for each class $i$, repeatedly finding a
data point $\bm{x}$ for which the distance $d(\bm{x},\bm{x}^{\prime})$ is
maximized where
$\bm{x}\in\mathcal{S}^{(i)},\bm{x}^{\prime}\in\mathcal{S}_{c}^{(i)}$. The
searched data point is then appended to $\mathcal{S}_{c}^{(i)}$. This
iteration procedure is terminated when
$|\mathcal{S}_{c}^{(i)}|\geq\left\lceil\frac{|\mathcal{S}^{(i)}|}{|\mathcal{S}|}\cdot
k\right\rceil$. In other words, the coreset size of each class $i$ is
restricted to be proportional to the ratio of the size of that class
$|\mathcal{S}^{(i)}|$ to the overall amount of data $|\mathcal{S}|$. When the
coreset for each class is collected, we merge these sets together to create a
coreset with $\mathcal{S}_{c}=\cup_{i=1}^{n_{c}}\\{\mathcal{S}_{c}^{(i)}\\}$
and set the weight $\gamma_{s}$ as the number of samples covered by the
coreset example $\bm{x}_{s}$ in radius $\delta_{c}$. Once the coreset
$\mathcal{S}_{c}$ is built, we can integrate it into QML models. In the
following, we introduce how it works on QNNs and quantum kernels.

The Pseudo code of QNN trained over the coreset is summarized in Algorithm 2.
Conceptually, we only need to replace the full training data $\mathcal{S}$
with the coreset $\mathcal{S}_{c}$, and rewrite the cost function by
introducing the weight $\\{\gamma_{s}\\}$ for each corresponding data point
$\bm{x}$ in coreset $\mathcal{S}_{c}$, i.e.,

$R_{c}^{\text{QNN}}=\frac{1}{|\mathcal{S}_{c}|}\sum_{\bm{x}_{s},y_{s}\in\mathcal{S}_{c}}\gamma_{s}\cdot
l(tr[M\cdot|\bm{x}_{s},\theta\rangle\langle\bm{x}_{s},\theta|,y_{s}),$ (9)

where $|\bm{x}_{s},\theta\rangle$ and $M$ are identical to those in Eq. (7).

1

input : Coreset $\mathcal{S}_{c}$, weights $\\{\gamma_{s}\\}_{s=1}^{k}$,
maximum epoch number $K_{max}$, learning rate $\eta$

output : trained QNN.

2 Initialize the parametrized quantum circuit $U(\theta)$;

3 $l=1$;

4 while  _$l <K_{max}$_ do

5 for  _$\bm{x}_{j},y_{j}\in\mathcal{S}_{c}$_ do

6 Estimate the gradient of $R_{c}$ with respect to $\theta$,
$\nabla_{\theta}f(\bm{x}_{j},y_{j})$ ;

7
$\theta_{l+1}\leftarrow\theta_{l}+\eta\cdot\gamma_{j}\cdot\nabla_{\theta}f(\bm{x}_{j},y_{j})$;

8 end for

9

10 end while

return the QNN $tr[M\cdot
U(\theta)U(\bm{x}_{i})\rho_{0}U^{\dagger}(\theta)U^{\dagger}(\bm{x}_{i})]$.

Algorithm 2 QNN with coreset selection

We next explain the implementation of a quantum-kernel-based support vector
machine (SVM) classifier over coreset. As we employ the coreset
$\mathcal{S}_{c}$ and introduce the weights $\\{\gamma\\}$, there is a slight
difference between original SVM and coreset enhanced SVM, where the Lagrange
multipliers $\alpha_{i}$ in dual problem is upper bounded by
$C\cdot\gamma_{i}$ instead of $C$. Mathematically, we have

$\displaystyle\max_{\alpha}\quad$
$\displaystyle\sum_{i}\alpha_{i}-\frac{1}{2}\sum_{i,j}\alpha_{i}\alpha_{j}y_{i}y_{j}K(\bm{x}_{i},\bm{x}_{j}),$
(10) s.t. $\displaystyle\sum_{i}y_{i}\alpha_{i}=0,$ $\displaystyle
0\leq\alpha_{i}\leq C\cdot\gamma_{i},i=1,\cdots,k.$

where $K(\bm{x},\bm{x}^{\prime})=|\langle\bm{x}|\bm{x}^{\prime}\rangle|^{2}$
is the quantum kernel function. The training process is similar to the
original SVM and depicted in Algorithm 3.

1

input : Coreset $\mathcal{S}_{c}$, weights $\\{\gamma_{s}\\}_{s=1}^{k}$,
encoding circuit $U$, regularization parameter $C$

output : SVM with quantum kernel.

2 for  _$\bm{x}\in\mathcal{S}_{c}$_ do

3 for  _$\bm{x}^{\prime}\in\mathcal{S}_{c}$_ do

4 $K_{\bm{x},\bm{x}^{\prime}}=|\langle
0|U^{\dagger}(\bm{x}^{\prime})|U(\bm{x})|0\rangle|^{2}$;

5 /* construct kernel matrix $K$ */

6

7 end for

8

9 end for

10Solve the dual problem in Eq.(10), get the optimal parameters $\alpha^{*}$;

Calculate the parameter $W^{*},b^{*}$;
$W^{*}=\sum_{i}\alpha_{i}y_{i}\bm{x}_{i},$ (11)
$b^{*}=y_{i}-\sum_{i}\alpha_{i}y_{i}K(\bm{x}_{i},\bm{x}_{j}),$ (12) return the
quantum kernel based SVM,
$f(\bm{x})=\sum_{i}\alpha_{i}y_{i}K(\bm{x},\bm{x}_{i})+b^{*}$.

Algorithm 3 Quantum kernel with coreset selection.

##  5 Generalization ability of QML models under coreset selection

In machine learning, generalization analysis is a crucial theoretical tool to
measure how accurately a learning model predicts previously unseen data [66].
It helps us as a guiding metric to choose the best-performing model when
comparing different model variations. As explained in Section 3.1, the purpose
of learning algorithms is to find a hypothesis $f$ such that the true risk $R$
on the data distribution $\mathcal{Z}$ is as small as possible. However, it is
unlikely to directly estimate the true risk $R$ since the distribution
$\mathcal{Z}$ is unknown and an alternative solution is minimizing the
empirical risk $R_{e}$ over the given samples. The generalization error
quantifies the gap between the true risk $R$ and empirical risk $R_{e}$, i.e.,

$|R-R_{e}|=\left|\mathbb{E}_{{({{\bm{x}}},y)}\sim
p_{\cal{Z}}}[l(f_{\bm{w}}(\bm{x}),y)]-\frac{1}{|\mathcal{S}|}\sum_{({{\bm{x}}}_{i},y_{i})\in{\cal{S}}_{t}}l(f_{\bm{w}}({{\bm{x}}}_{i}),y_{i})\right|.$
(13)

Thus, the true risk $R$ can be upper bounded by its empirical error and the
generalization error, i.e.,

$R\leq\underbrace{\left|R-R_{e}\right|}_{\text{generalization
error}}+\underbrace{\left|R_{e}\right|}_{\text{empirical error}}.$ (14)

Since the empirical error, namely the training loss, is close to zero in
general, we can only consider the upper bound of the generalization error.
Thus, a natural question is whether the coreset selection could provide a
tighter generalization bound compared to random sampling under the same pruned
training size. To answer this question, we need first define the empirical
error $R_{r}$ on a sub-training set $\mathcal{S}_{r}$ that is generated by
random sampling from full data set $\mathcal{S}$ as,

$R_{r}=\frac{1}{|\mathcal{S}_{r}|}\sum_{\bm{x}_{i},y_{i}\in\mathcal{S}_{r}}l(f_{\bm{w}}(\bm{x}_{i}),y_{i}),$
(15)

where $|\mathcal{S}_{r}|=N_{r}$ is the size of $\mathcal{S}_{r}$. Hence, the
generalization error $G_{r}$ over $\mathcal{S}_{r}$ is represented as,

$G_{r}=\left|R-R_{r}\right|=\left|\mathbb{E}_{{({{\bm{x}}},y)}\sim
p_{\cal{Z}}}[l(f_{\bm{w}}(\bm{x}),y)]-\frac{1}{|\mathcal{S}_{r}|}\sum_{\bm{x}_{i},y_{i}\in\mathcal{S}_{r}}l(f_{\bm{w}}(\bm{x}_{i}),y_{i})\right|.$
(16)

According to previous studies on the generalization analysis of QNNs and
quantum kernels [52, 6], with probability at least $\geq 1-\delta$ over
$\mathcal{S}_{r}$, we have the generalization error of QNNs,

$G_{r}^{\text{QNN}}\leq\mathcal{O}\left(\sqrt{\frac{m\log{(m)}}{N_{r}}}+\sqrt{\frac{\log{(1/\delta)}}{N_{r}}}\right),$
(17)

where $m$ is the trainable parameters of QNNs, and the generalization error of
quantum kernel,

$G_{r}^{\text{qkernel}}\leq\mathcal{O}\left(\sqrt{\frac{\lceil\|\bm{w}\|\rceil^{2}}{N_{r}}}+\sqrt{\frac{\log{(4/\delta)}}{N_{r}}}\right).$
(18)

To bound the generalization error $G_{c}$ on coreset $\mathcal{S}_{c}$, we
similarly define the empirical error $R_{c}$ on the coreset $\mathcal{S}_{c}$
as,

$R_{c}=\frac{1}{|\mathcal{S}_{c}|}\sum_{\bm{x}_{s},y_{s}\in\mathcal{S}_{r}}\gamma_{s}\cdot
l(f_{\bm{w}}(\bm{x}_{s}),y_{s}),$ (19)

where $|\mathcal{S}_{c}|=N_{c}$ is the size of $\mathcal{S}_{c}$ and
$\gamma_{s}$ is the weight for each coreset example $\bm{x}_{s}$ that is used
to make $R_{c}$ approximate to $R_{e}$ over full data set $\mathcal{S}$. Then,
we can present $G_{c}$ as,

$G_{c}=|R-R_{c}|=\left|\mathbb{E}_{{({{\bm{x}}},y)}\sim
p_{\cal{Z}}}[l(f_{\bm{w}}(\bm{x}),y)]-\frac{1}{|\mathcal{S}_{c}|}\sum_{\bm{x}_{s},y_{s}\in\mathcal{S}_{c}}l(f_{\bm{w}}(\bm{x}_{s}),y_{s})\right|.$
(20)

Based on the triangle inequality, $G_{c}$ can be bounded by,

$G_{c}=\left|R-R_{c}\right|\leq\underbrace{|R-R_{e}|}_{\text{generalization
error}}+\underbrace{|R_{e}-R_{c}|}_{\text{coreset error}}.$ (21)

Here, we name the second term, i.e. $|R_{e}-R_{c}|$, as the coreset error that
describes the gap between the empirical loss on the full data set and the
coreset. As the bound of the generalization error term, i.e. $|R-R_{e}|$, is
given by previous works [52, 6], we can only focus on the bound of coreset
error.

By analyzing the coreset error, we first provide the generalization error
bound of QNNs.

######  Theorem 1.

(Generalization error bound of QNN on coreset) Given sample set
$\mathcal{S}=\\{{{\bm{x}}}_{i},y_{i}\\}_{i=1}^{N_{t}}$ are $i.i.d$ randomly
drawn from distribution $\mathcal{Z}$, $\mathcal{S}_{c}$ is $\delta_{c}$ cover
of $\mathcal{S}$. Assume there is $\lambda_{\eta}$-Lipshcitz continuous class-
specific regression function $\eta(\bm{x})=p(y=c|\bm{x})$, and the loss
$l(f_{\bm{w}}(\bm{x}_{s},y_{s}))$ over coreset $\mathcal{S}_{c}$ is zero and
bounded by $L$. We have the following upper bound for the generalization error
of QNNs trained on coreset with probability $1-\delta$,

$G_{c}^{\text{QNN}}\leq\mathcal{O}\left(\sqrt{\frac{m\log(m)}{N_{t}}}+\sqrt{\frac{\log(1/\delta)}{N_{t}}}+\delta_{c}(\lambda_{\eta}Ln_{c}+d\sqrt{d_{\bm{x}}}\max_{j}|\bm{w}_{j}|\left|M\right|(\left|M\right|+\max|y|)\right),$
(22)

where $m$ is the number of the parameters in QNN, $d$ is the number of QNN
layers, $n_{c}$ is the number of classes, $M$ is the measurement operator,
$d_{\bm{x}}$ is the feature dimension.

For the coreset error $|R_{e}-R_{c}|$, we assume the training error on coreset
is equal to zero, thus it becomes the average error over the entire data set
which can be bound with the radius $\delta_{c}$ determined by the $k$-center
covering problem shown in Fig. LABEL:fig:kcp, which is related to the data
prune rate $\zeta=|\mathcal{S}_{c}|/|\mathcal{S}|$. Combining the
generalization bound on the full data set and the bound of risk gap between
the full data set and coreset together, we have the generalization error of
QNN on coreset is mainly bounded by two terms, i.e.
$\mathcal{O}((\sqrt{m\log(m)/N_{t}}+\delta_{c})$. Thus, the
$G_{c}^{\text{QNN}}$ will give a tighter bound than $G_{r}^{\text{QNN}}$ when
we carefully choose the data prune rate $\zeta$. It is clear that
$G_{c}^{\text{QNN}}$ gives the tighter bound on the first term since
$N_{r}<N_{t}$. For the second term, as $\delta_{c}$ is related to $\zeta$, a
low $\zeta$ will cause $\delta_{c}$ to become large leading to a high
approximation error. Conversely, a high $\zeta$ will decrease the
approximation error but the acceleration of training will disappear because
$N_{c}$ is approximate to $N_{t}$.

We next provide the generalization error bound of quantum kernels under the
coreset.

######  Theorem 2.

(Generalization error bound of quantum kernels on coreset.) Given sample set
$\mathcal{S}=\\{\bm{x}_{i},y_{i}\\}_{i=1}^{N_{t}}$ are $i.i.d$ randomly drawn
from distribution $\mathcal{Z}$, $\mathcal{S}_{c}$ is $\delta_{c}$ cover of
$\mathcal{S}$. Assume there is $\lambda_{\eta}$-Lipshcitz continuous class-
specific regression function $\eta(\bm{x})=p(y=c|\bm{x})$, and the loss
$l(f_{\bm{w}}(\bm{x}_{s},y_{s}))$ over coreset $\mathcal{S}_{c}$ is zero and
bounded by $L$. We have the following upper bound for the generalization error
of SVM with quantum kernel trained on coreset with probability $1-\delta$,

$G_{c}^{\text{qkernel}}\leq\mathcal{O}\left(\sqrt{\frac{\lceil\|\bm{w}\|\rceil^{2}}{N_{t}}}+\sqrt{\frac{\log{(4/\delta)}}{N_{t}}}+\delta_{c}(\lambda_{\eta}Ln_{c}+N_{c}\sqrt{d_{\bm{x}}}\max_{j}|\bm{w}_{j}|\cdot(1+(N_{q}-1)r))\right),$
(23)

where $n_{c}$ is the number of classes, $d_{\bm{x}}$ is the feature dimension
of $\bm{x}$, $N_{q}$ is the size of mapped quantum state $|\bm{x}\rangle$, r
is the maximum value of feature $\bm{x}$.

Similar to the analysis of the generalization error of QNNs on coreset, the
generalization error of SVM with a quantum kernel is also mainly bounded by
two terms, i.e.
$\mathcal{O}(\sqrt{\frac{\lceil\|\bm{w}\|\rceil^{2}}{N_{t}}}+\delta_{c})$ that
indicates we have the similar results like $G_{c}^{\text{QNN}}$. Here, when we
employ coreset selection to reduce the size of training examples, we will
reduce the complexity of getting kernel matrix, that provides
$\mathcal{O}(k^{2})$ speedup where $k=N_{t}/N_{c}$, meanwhile also having
provable generalization guarantee.
It should be pointed out that it is not easy to propose a universal trick for
selecting an appropriate data prune rate $\zeta$ that determines the
$\delta_{c}$ to achieve a good generalization performance. Because it is
related to the distribution of the given training set $\mathcal{S}$ and
unknown true data distribution $\mathcal{Z}$. Nevertheless, we give some
numerical experiments on various data and models, the results not only support
the analytical findings but also might provide some practical advice for the
selection of $\zeta$. Consequently, if we carefully choose the data prune rate
and the size of the training set to be scaled at least quasi-linearly with the
number of gates employed, we are able to accelerate the quantum machine
learning model with a performance guarantee. These results provide effective
and practical guidance on achieving accurate and reliable performance with a
reasonable model complexity and sample complexity.

##  6 Numerical results

In this section, we conduct extensive numerical simulations to explore the
performance of the proposed coreset selection method. Specifically, we employ
our proposal to accomplish three learning tasks, which are synthetic data
classification, quantum correlation identification, and quantum compiling.

###  6.1 Synthetic data classification by quantum kernels

We first utilize the quantum kernel to classify a synthetic dataset with
coreset. The construction rule of the synthetic dataset mainly follows Ref.
[6]. Specifically, given the data set $\\{{\bm{x}}_{i},y_{i}\\}_{i=1}^{N}$
that independently sampled from the distribution $\mathcal{X}$, the
corresponding labels are modified according to the maximized geometric
difference given by

$\max_{y\in\mathbb{R}^{N}}\frac{\sum_{i=1}^{N}\sum_{j=1}^{N}(K^{Q})^{-1}_{ij}y_{i}y_{j}}{\sum_{i=1}^{N}\sum_{j=1}^{N}(K^{C})^{-1}_{ij}y_{i}y_{j}},$
(24)

where $K^{Q}$ and $K^{C}$ denote the quantum and classical kernel
respectively. The optimal solution of Eq. (24) yields the modified labels
${\bf{y}}^{*}$ such that maximize the geometric difference.

${\bf{y}}^{*}=\text{sign}(\sqrt{K^{Q}}v),$ (25)

where $v$ is the eigenvector of $\sqrt{K^{Q}}(K^{C})^{-1}\sqrt{K^{Q}}$ with
the maximum eigenvalue, and $\text{sign}(\bf{z})$ is the element-wise function
such that set the $i$-th element as $+1$ if $z_{i}>median({\bf{z}})$ otherwise
set as $-1$. As proved in Ref. [6], quantum kernels can achieve quantum
advantages when learning this dataset.

Figure 4: Illustration of the employed synthetic dataset adapted from the
fashion-MINIST [67]. We use principal component analysis to get the low-
dimensional representation, then embed the reduced data into quantum Hilbert
space. In the end, we relabel the data according to maximizing the geometric
difference between classical and quantum kernels in Eq. (24).

An illustration of the synthetic dataset construction is shown in Fig. 4.
Concretely, in our numerical simulations, the synthetic dataset is based on
fashion-MNIST [67]. As the dimension of vectorized data of the fashion-MNIST
is too high for NISQ device, we preprocess it as the low-dimension
representation by principle component analysis and then relabel the class of
each data point according to Eq. (24). Besides, the element of classical
kernel $K^{C}_{ij}$ is given by the radial basis function kernel
$K^{C}_{ij}=\exp(-\frac{||{\bm{x}}_{i}-{\bm{x}}_{j}||^{2}}{2\sigma^{2}})$. The
quantum kernel $K^{Q}_{ij}$ is generated through encoding the data points into
$N_{q}$-qubit Hilbert space by a quantum circuit $U_{e}$,

$K^{Q}_{ij}=tr(\rho({\bm{x}}_{i})\rho({\bm{x}}_{j})),$ (26)

where $\rho({\bm{x}})=U_{e}({\bm{x}})|0\rangle\langle
0|U^{\dagger}_{e}({\bm{x}})$. We can further assume the following form of
$U_{{\bm{x}}}$ implemented through quantum gates in an $N_{q}$-qubit circuit:
$U_{{\bm{x}}}=(U({{\bm{x}}})H^{\otimes N_{q}})^{2}|0\rangle^{\otimes N_{q}}$,
where
$U({{\bm{x}}})=\exp(\sum_{j=1}^{N_{q}}{{\bm{x}}}_{j}\sigma^{Z}_{j}+\sum_{j,j^{\prime}=1}^{N_{q}}{{\bm{x}}}_{j}{{\bm{x}}}_{j^{\prime}}\sigma^{Z}_{j}\sigma^{Z}_{j^{\prime}})$.

Figure 5: The comparison between the proposed model with random sampling and
coreset selection. It shows the average performance of classification of
synthetic data where the solid line is the test accuracy of the models that
trained over coreset and random sampling. The shaded area refers to the range
of the test accuracy. The red dashed line denotes the maximum accuracy
achieved by random sampling.

Once the synthetic data set was prepared, we conducted experiments on training
sets with various sizes and subsequently tested on 200 unseen examples to get
the test accuracy. Instead of independently and randomly choosing training
data from entire set $\mathcal{S}$, we first solve the $k$-center problem over
set $\mathcal{S}$ with $1000$ examples that are equivalent to form the coreset
$\mathcal{S}_{c}$. In Fig. 5, we show the comparison of the classification
performance under these settings. They respectively depict the correlation
between the size of the training set, obtained using random sampling and
coreset selection, and the corresponding test accuracy. For experiments
involving the same number of training examples, we carried out five
independent trials, each employing randomized initialization, resulting in the
shaded area as shown in Fig. 5. The average test performance of these trials
is plotted as a solid line. We also highlight the best test accuracy of random
sampling as the red dash line. From the results shown in Fig. 5, when the
models are trained on a set with 250 examples (i.e., $\zeta=0.25$), the test
accuracy of those trained on the data points obtained by coreset selection is
higher than that of the model via random sampling. Besides, when achieving the
same test accuracy, the model only needs 250 coreset examples while requiring
400 randomly sampled examples. They support our analytical results, the QNNs
trained on coreset have better generalization performance than those with
randomly picked training data under appropriate data prune rate. The coreset-
enhanced classifier significantly improves the training efficiency, achieving
competitive performance while only utilizing approximately $50\%$ of the
training examples compared to random sampling.

###  6.2 Correlation identification by QNNs

Non-classical correlation plays a core role in quantum information and quantum
computation [68]. Nevertheless, identifying the non-classical correlation of a
given quantum state is a challenging task. Ref. [69] explored classifying non-
classical correlation experimentally with machine learning techniques.
Consider the family of quantum states characterized by $p$ and $\theta$ with
the following form,

$\rho_{AB}(p,\theta)=p|\psi_{\theta}\rangle\langle\psi_{\theta}|+(1-p)\frac{\mathbb{I}}{2}\otimes
tr_{A}(|\psi_{\theta}\rangle\langle\psi_{\theta}|),$ (27)

where the $p\in(0,1)$, $\theta\in(0,2\pi)$ and state
$|\psi_{\theta}\rangle=\cos(\theta)|00\rangle+\sin(\theta)|11\rangle$. There
are following rules to determine the non-classical correlation of quantum
states $\rho_{AB}$ including separable, entangled, one-way steerable, and non-
local.

  1. 1.

According to PPT criterion, the states are separable when $p<\frac{1}{3}$
otherwise they are entangled.

  2. 2.

When $\frac{1}{\sqrt{2}}<p<\frac{1}{\sqrt{1+\sin^{2}(2\theta)}}$, the quantum
state is one-way steerable.

  3. 3.

When $p>\frac{1}{\sqrt{1+\sin^{2}(2\theta)}}$, the state is non-local.

Therefore, to identify the non-local correlation of a given state under the
learning framework, we can label the quantum states with different non-
classical correlations according to the above criteria and create the data set
$\\{\rho^{AB}_{j},y_{j}\\}_{j=1}^{N}$ where $y_{i}$ represents the type of
correlation, i.e. separable, entangled, one-way steerable, non-local.

(a) quantum states

(b) test accuracy of random sampling and coreset

Figure 6:  Results related to correlation identification. (a) The states are
represented as dots in polar plots. The radius of the polar plot represents
the parameter $p$ that varies from $0$ to $1$. The phase stands for the
parameter $\theta$ that varies from $0$ to $2\pi$. The blue and orange dots
indicate the separable and entangled states separately. (b) The comparison of
test accuracy between the classifier with random sampling and coreset under
different sizes of training set.

To further enhance the methods, the fewer training samples the less run time,
we apply the coreset selection to this learning task. For classifying the
quantum correlation, we uniformly pick the parameters $p\in(0,1)$ and
$\theta\in(0,2\pi)$ to generate the 1000 quantum states as the full training
set as shown in the subfigure (a) of Fig. 6b. Then label the class of
correlation in terms of the criterion listed above. Here, we continue with the
same experimental setup as the previous section. where we examine the test
accuracy of the model, trained over various sample sizes, on 200 unseen random
samples.

The red dash lines in subfigure (i) and (ii) denote the maximum test accuracy
attained by the classifier through random sampling, with a maximum of 900
training samples. When utilizing the coreset method to prune the dataset, for
sample sizes exceeding 180, the averaged test accuracy obtained by coreset is
almost higher than the best accuracy achieved by random sampling. It indicates
that when $\zeta\geq 0.18$, the coreset selection could provide better
performance compared to training on random sampling data, which matches our
theoretical findings.

###  6.3 Quantum compiling by QNN

Compiling a unitary into a sequence of gates is a challenging and high-profile
task for NISQ quantum devices. With the limitation of current NISQ hardware,
compiling a unitary not only should take account of the function but also
consider the connectivity and depth of the output circuit. Recently, various
methods for quantum compiling have been proposed under the framework of
variational quantum algorithms [70, 52, 42]. In general, these algorithms
consider the compiling task as an optimization problem on a given compact
quantum gates set which consists of fixed and parametrized quantum gates. The
goal is to optimize the structure and gate parameters such that the proposed
quantum circuit approximates to the given unitary.

Here, we consider the method that tackles the compiling task by a quantum
machine learning protocol. Given an $n$-qubit target unitary $U$, the training
data consists of random input states and their corresponding output when $U$
applied on, i.e. $\\{|\psi_{j}\rangle,U|\psi_{j}\rangle\\}_{j=1}^{N}$. To
approximate the target unitary $U$, one can simply minimize the empirical loss
of the squared trace distance between target states $U|\psi_{j}\rangle$ and
parametrized output states $V(\bm{\theta})|\psi_{j}\rangle$ and over randomly
sampled states in Hilbert space. Concretely, we randomly pick the quantum
gates from the gate pool consisting of single parametrized gates
$\\{R_{x},R_{y},R_{z}\\}$ and CNOT gate to build the target quantum circuits
$U$. Then set the input as the random state $|\psi_{i}\rangle$ in Hilbert
space and get training pairs
$\\{|\psi_{j}\rangle,U|\psi_{j}\rangle\\}_{j=1}^{1000}$. In subfigure (b) of
Fig. 7, we present the comparison between the models trained on random
sampling and coreset with various data sizes and pruning ratios. We separately
estimate the performance of the model with $\zeta=\\{0.8,0.4,0.6,0.2\\}$. Each
data point with a different color on the plot corresponds to different
$\zeta$. For the compiling task on a specific unitary, we found that 1000
training examples are redundant, and the effective size of training data
scales linearly with the system size which is similar to what previous work
found [52]. When given around 20 examples, it is sufficient for training the
variational compiler to achieve a reasonable performance for a 6-qubit system.
Since the randomly sampled training points are likely to be uniformly located
in Hilbert space and the proposed coreset selecting approach also uses
$k$-centers to uniformly cover the entire set, the compilers trained on
coreset with the different $\zeta$ have similar performance compared to those
trained on the random-sampled set.

(a) target ansatz

(b) performance of random sampling and coreset

Figure 7: Results of unitary compiling. (a) The target unitary is exploited in
numerical simulations. (b) The performance comparison between the different
prune ratios $\zeta$ of coreset on compiling task. The solid dark and light
lines represent the models trained on the coreset and random samples. The
vertical axis represents the percentage of states in the test set for which
the trace distance to their corresponding targets is below $10^{-5}$.

##  7 Discussion

In this work, we investigate enhancing QML model from the data engineering
perspective and attempt to alleviate a practical problem when handling a large
volume of data samples. In particular, we consider the coreset construction as
a $k$-set cover problem and then analyze the generalization performance of QML
models on coreset. Our investigation of various learning scenarios, including
on classification of synthetic data, identification of non-classical
correlations in quantum states, and quantum circuit compilation, confirm the
extreme improvements in the effectiveness of our proposal.

Our research findings highlight the considerable enhancement in model training
achieved through the utilization of the coreset method. Data pruning
contributes to improved training efficiency. Besides, it also helps filter out
noise data, thereby enhancing model performance. It’s evident that selecting a
sparser coreset enforces a more rigorous upper bound on the count of trainable
gates and appropriate data prune rate. The size of the training set should be
scaled at least quasi-linearly with the number of gates. These findings
provide effective and practical guidelines to achieve accurate and reliable
results with a reasonable configuration of gates and training data. Although
we have improved model training efficiency through data pruning methods, there
is still significant room for enhancement. For instance, the introduction of
influence functions could better characterize the impact of data variations on
the model, thus achieving more precise data filtering.

We aspire for the work presented in this article to offer valuable insights
and guidance for future practical research in quantum machine learning, from
theoretical or practical aspects, on NISQ devices.

## References

  * [1] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione.  The quest for a quantum neural network.  Quantum Information Processing, 13(11):2567–2586, 2014.
  * [2] Edward Farhi and Hartmut Neven.  Classification with quantum neural networks on near term processors.  arXiv preprint arXiv:1802.06002, 2018.
  * [3] 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, 2019.
  * [4] Iris Cong, Soonwon Choi, and Mikhail D Lukin.  Quantum convolutional neural networks.  Nature Physics, 15(12):1273–1278, 2019.
  * [5] Maria Schuld and Nathan Killoran.  Quantum machine learning in feature hilbert spaces.  Physical review letters, 122(4):040504, 2019.
  * [6] 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, 2021.
  * [7] Jacob D. Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd.  Quantum machine learning.  Nature, 549:195–202, 2017.
  * [8] Marcello Benedetti, Erika Lloyd, and Stefan H. Sack.  Parameterized quantum circuits as machine learning models.  ArXiv, abs/1906.07682, 2019.
  * [9] 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.
  * [10] John Preskill.  Quantum computing in the nisq era and beyond.  Quantum, 2:79, 2018.
  * [11] 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.
  * [12] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme.  A rigorous and robust quantum speed-up in supervised machine learning.  ArXiv, abs/2010.02174, 2021.
  * [13] Amira Abbas, David Sutter, Christa Zoufal, Aurélien Lucchi, Alessio Figalli, and Stefan Woerner.  The power of quantum neural networks.  Nature Computational Science, 1(6):403–409, 2021.
  * [14] Jonas Jäger and Roman V Krems.  Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines.  Nature Communications, 14(1):576, 2023.
  * [15] Yuxuan Du, Yibo Yang, Dacheng Tao, and Min-Hsiu Hsieh.  Demystify problem-dependent power of quantum neural networks on multi-class classification.  arXiv preprint arXiv:2301.01597, 2022.
  * [16] Yusen Wu, Bujiao Wu, Jingbo Wang, and Xiao Yuan.  Quantum phase recognition via quantum kernel methods.  Quantum, 7:981, 2023.
  * [17] 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.  npj Quantum Information, 7(1):161, 2021.
  * [18] He-Liang Huang, Yuxuan Du, Ming Gong, Youwei Zhao, Yulin Wu, Chaoyue Wang, Shaowei Li, Futian Liang, Jin Lin, Yu Xu, et al.  Experimental quantum generative adversarial networks for image generation.  Physical Review Applied, 16(2):024051, 2021.
  * [19] Xiaoxuan Pan, Xi Cao, Weiting Wang, Ziyue Hua, Weizhou Cai, Xuegang Li, Haiyan Wang, Jiaqi Hu, Yipu Song, Dong-Ling Deng, et al.  Experimental quantum end-to-end learning on a superconducting processor.  npj Quantum Information, 9(1):18, 2023.
  * [20] Wenhui Ren, Weikang Li, Shibo Xu, Ke Wang, Wenjie Jiang, Feitong Jin, Xuhao Zhu, Jiachen Chen, Zixuan Song, Pengfei Zhang, et al.  Experimental quantum adversarial learning with programmable superconducting qubits.  Nature Computational Science, 2(11):711–717, 2022.
  * [21] Johannes Herrmann, Sergi Masot Llima, Ants Remm, Petr Zapletal, Nathan A McMahon, Colin Scarato, François Swiadek, Christian Kraglund Andersen, Christoph Hellings, Sebastian Krinner, et al.  Realizing quantum convolutional neural networks on a superconducting quantum processor to recognize quantum phases.  Nature Communications, 13(1):4144, 2022.
  * [22] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran.  Evaluating analytic gradients on quantum hardware.  Physical Review A, 99(3):032331, 2019.
  * [23] Ian J. Goodfellow, Yoshua Bengio, and Aaron C. Courville.  Deep learning.  Nature, 521:436–444, 2015.
  * [24] Guillaume Verdon, Michael Broughton, Jarrod R McClean, Kevin J Sung, Ryan Babbush, Zhang Jiang, Hartmut Neven, and Masoud Mohseni.  Learning to learn with quantum neural networks via classical neural networks.  arXiv preprint arXiv:1907.05415, 2019.
  * [25] James Stokes, Josh Izaac, Nathan Killoran, and Giuseppe Carleo.  Quantum natural gradient.  Quantum, 4:269, 2020.
  * [26] Julien Gacon, Christa Zoufal, Giuseppe Carleo, and Stefan Woerner.  Simultaneous perturbation stochastic approximation of the quantum fisher information.  Quantum, 5:567, 2021.
  * [27] Barnaby van Straaten and Bálint Koczor.  Measurement cost of metric-aware variational quantum algorithms.  PRX Quantum, 2(3):030324, 2021.
  * [28] Tyler Volkoff and Patrick J Coles.  Large gradients via correlation in random parameterized quantum circuits.  Quantum Science and Technology, 6(2):025008, 2021.
  * [29] Ryan Sweke, Frederik Wilde, Johannes Meyer, Maria Schuld, Paul K Fährmann, Barthélémy Meynard-Piganeau, and Jens Eisert.  Stochastic gradient descent for hybrid quantum-classical optimization.  Quantum, 4:314, 2020.
  * [30] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, and Dacheng Tao.  Learnability of quantum neural networks.  PRX Quantum, 2(4):040337, 2021.
  * [31] Lennart Bittel and Martin Kliesch.  Training variational quantum algorithms is np-hard.  Physical review letters, 127(12):120502, 2021.
  * [32] CM Wilson, JS Otterbach, Nikolas Tezak, RS Smith, AM Polloreno, Peter J Karalekas, S Heidel, M Sohaib Alam, GE Crooks, and MP da Silva.  Quantum kitchen sinks: An algorithm for machine learning on near-term quantum computers.  arXiv preprint arXiv:1806.08321, 2018.
  * [33] Tak Hur, Leeseok Kim, and Daniel K Park.  Quantum convolutional neural network for classical data classification.  Quantum Machine Intelligence, 4(1):3, 2022.
  * [34] Joseph Bowles, David Wierichs, and Chae-Yeun Park.  Backpropagation scaling in parameterised quantum circuits.  arXiv preprint arXiv:2306.14962, 2023.
  * [35] Amira Abbas, Robbie King, Hsin-Yuan Huang, William J Huggins, Ramis Movassagh, Dar Gilboa, and Jarrod R McClean.  On quantum backpropagation, information reuse, and cheating measurement collapse.  arXiv preprint arXiv:2305.13362, 2023.
  * [36] Jennifer R Glick, Tanvi P Gujarati, Antonio D Corcoles, Youngseok Kim, Abhinav Kandala, Jay M Gambetta, and Kristan Temme.  Covariant quantum kernels for data with group structure.  arXiv preprint arXiv:2105.03406, 2021.
  * [37] Thomas Hubregtsen, David Wierichs, Elies Gil-Fuster, Peter-Jan HS Derks, Paul K Faehrmann, and Johannes Jakob Meyer.  Training quantum embedding kernels on near-term quantum computers.  Physical Review A, 106(4):042431, 2022.
  * [38] Supanut Thanasilp, Samson Wang, Marco Cerezo, and Zoë Holmes.  Exponential concentration and untrainability in quantum kernel methods.  arXiv preprint arXiv:2208.11060, 2022.
  * [39] Christopher M. Bishop.  Pattern Recognition and Machine Learning (Information Science and Statistics).  Springer, 1 edition, 2007.
  * [40] 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.
  * [41] Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Izaac, and Nathan Killoran.  Quantum embeddings for machine learning.  arXiv preprint arXiv:2001.03622, 2020.
  * [42] M Bilkis, María Cerezo, Guillaume Verdon, Patrick J Coles, and Lukasz Cincio.  A semi-agnostic ansatz with variable structure for quantum machine learning.  arXiv preprint arXiv:2103.06712, 2021.
  * [43] Shi-Xin Zhang, Chang-Yu Hsieh, Shengyu Zhang, and Hong Yao.  Differentiable quantum architecture search.  Quantum Science and Technology, 7(4):045023, 2022.
  * [44] Yuxuan Du, Tao Huang, Shan You, Min-Hsiu Hsieh, and Dacheng Tao.  Quantum circuit architecture search for variational quantum algorithms.  npj Quantum Information, 8(1):62, 2022.
  * [45] Frederic Sauvage, Martin Larocca, Patrick J Coles, and M Cerezo.  Building spatial symmetries into parameterized quantum circuits for faster training.  arXiv preprint arXiv:2207.14413, 2022.
  * [46] Martin Larocca, Frédéric Sauvage, Faris M Sbahi, Guillaume Verdon, and Patrick J Coles.  Group-invariant quantum machine learning.  PRX Quantum, 3(3):030341, 2022.
  * [47] Yuxuan Du, Yang Qian, Xingyao Wu, and Dacheng Tao.  A distributed learning scheme for variational quantum algorithms.  IEEE Transactions on Quantum Engineering, 3:1–16, 2022.
  * [48] Leonardo Banchi, Jason Pereira, and Stefano Pirandola.  Generalization in quantum machine learning: A quantum information standpoint.  PRX Quantum, 2(4):040321, 2021.
  * [49] 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.
  * [50] Casper Gyurik, Vedran Dunjko, et al.  Structural risk minimization for quantum linear classifiers.  Quantum, 7:893, 2023.
  * [51] Yuxuan Du, Zhuozhuo Tu, Xiao Yuan, and Dacheng Tao.  Efficient measure for the expressivity of variational quantum algorithms.  Physical Review Letters, 128(8):080506, 2022.
  * [52] Matthias C Caro, Hsin-Yuan Huang, Marco Cerezo, Kunal Sharma, Andrew Sornborger, Lukasz Cincio, and Patrick J Coles.  Generalization in quantum machine learning from few training data.  Nature communications, 13(1):4919, 2022.
  * [53] Xinbiao Wang, Yuxuan Du, Yong Luo, and Dacheng Tao.  Towards understanding the power of quantum kernels in the nisq era.  Quantum, 5:531, 2021.
  * [54] Yecheng Xue, Xiaoyu Chen, Tongyang Li, and Shaofeng H-C Jiang.  Near-optimal quantum coreset construction algorithms for clustering.  arXiv preprint arXiv:2306.02826, 2023.
  * [55] Fanzhe Qu, Sarah M Erfani, and Muhammad Usman.  Performance analysis of coreset selection for quantum implementation of k-means clustering algorithm.  arXiv preprint arXiv:2206.07852, 2022.
  * [56] Soronzonbold Otgonbaatar and Mihai Datcu.  Assembly of a coreset of earth observation images on a small quantum computer.  Electronics, 10(20):2482, 2021.
  * [57] Pankaj K Agarwal, Sariel Har-Peled, Kasturi R Varadarajan, et al.  Geometric approximation via coresets.  Combinatorial and computational geometry, 52(1), 2005.
  * [58] Olivier Bachem, Mario Lucic, and Andreas Krause.  Practical coreset constructions for machine learning.  arXiv preprint arXiv:1703.06476, 2017.
  * [59] Dan Feldman.  Introduction to core-sets: an updated survey.  arXiv preprint arXiv:2011.09384, 2020.
  * [60] Reza Zanjirani Farahani and Masoud Hekmatfar.  Facility location: concepts, models, algorithms and case studies.  Springer Science & Business Media, 2009.
  * [61] Sofiene Jerbi, Lukas J Fiderer, Hendrik Poulsen Nautrup, Jonas M Kübler, Hans J Briegel, and Vedran Dunjko.  Quantum machine learning beyond kernel methods.  Nature Communications, 14(1):517, 2023.
  * [62] 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.
  * [63] Ming-Hsuan Yang.  Face recognition using kernel methods.  Advances in neural information processing systems, 14, 2001.
  * [64] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  Advances in neural information processing systems, 31, 2018.
  * [65] Jonas Jäger and Roman V. Krems.  Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines.  Nature Communications, 14(1), feb 2023.
  * [66] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  Foundations of machine learning.  MIT press, 2018.
  * [67] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  arXiv preprint arXiv:1708.07747, 2017.
  * [68] David Gross, Steve T Flammia, and Jens Eisert.  Most quantum states are too entangled to be useful as computational resources.  Physical review letters, 102(19):190501, 2009.
  * [69] Mu Yang, Chang-liang Ren, Yue-chi Ma, Ya Xiao, Xiang-Jun Ye, Lu-Lu Song, Jin-Shi Xu, Man-Hong Yung, Chuan-Feng Li, and Guang-Can Guo.  Experimental simultaneous learning of multiple nonclassical correlations.  Physical review letters, 123(19):190401, 2019.
  * [70] Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cincio, Andrew T Sornborger, and Patrick J Coles.  Quantum-assisted quantum compiling.  Quantum, 3:140, 2019.

##  Appendix A Appendix

######  Theorem 3.

(Generalization bound for QNN [52]) Let the QNN to be trained consists of $m$
trainable parameterized 2-qubit or 1-qubit gates, and an arbitrary number of
non-trainable fixed gates. Suppose that, given training data
${\cal{S}}=\\{{{\bm{x}}}_{i},y_{i}\\}_{i=1}^{N_{t}}$ and a loss function
$l(f_{\bm{\theta}};{{\bm{x}}}_{i},y_{i})$ bounded by $L$, our optimization
yields optimized parameters $\bm{\theta^{*}}$. Then, according to Theorem C.6
in [52], the generalization error of the optimized QNN is bounded by the
following form with probability at least $(1-\delta)$ over the choice of
$i.i.d$ training data ${\cal{S}}_{t}$ from $\mathcal{Z}$:

$\left|R-R_{e}\right|<\mathcal{O}\left(\sqrt{\frac{m\log(m)}{N_{t}}}+\sqrt{\frac{\log(1/\delta)}{N_{t}}}\right).$
(28)

######  Lemma 1.

The loss function $l(f_{\bm{\theta}}(\bm{x}),y)$ of $d$-layer QNN introduced
in section 3.3 is the $\lambda$-Lipschitz in feature space with

$\lambda=2d\sqrt{d_{\bm{x}}}\max_{j}|\bm{w}_{j}|\left|M\right|(\left|M\right|+\max|y|).$
(29)

###### Proof.

Assume given data $\bm{x}=(x_{1},\cdots,x_{d_{\bm{x}}})$, data encoding scheme
used by the QNN is the $d$-layer re-uploading scheme, the mapped quantum state
is written as,

$\lvert\bm{x},\bm{\theta}\rangle=U({\bm{x}},\bm{\theta}^{(d)},\bm{w}^{(d)})...U({\bm{x}},\bm{\theta}^{(1)},\bm{w}^{(1)})\lvert
0\rangle,$ (30)

where $\bm{w}$ is encoding parameters in data-reuploading, the $i$-th layer
$U({\bm{x}},\bm{\theta}^{(i)},\bm{w}^{(i)})$ can be presented as,

$U({\bm{x}},\bm{\theta}^{(i)},\bm{w}^{(i)})=U(\bm{\theta}^{(i)})\prod_{k}\exp{(iw_{k}^{(i)}x_{k}P_{k})},$
(31)

where $P$ is a Pauli gate and $\bm{\theta},\bm{w}$ both trainable parameters.

Assume the Jacobian vector $J$ of the loss function
$l=(\langle\bm{x},\bm{\theta}|M|\bm{x},\bm{\theta}\rangle-y)^{2}$ is bounded
in the feature space, now we investigate the Lipschitz constant of $l$.

$\left|l({\bm{x}})-l(\bm{x}^{\prime})\right|\leq\max\|J\|_{2}\|{\bm{x}}-\bm{x}^{\prime}\|_{2},\forall{\bm{x}},\bm{x}^{\prime}\in\mathbb{R}^{d_{\bm{x}}},$
(32)

where the Jacobian matrix is,

$J=\left[\frac{\partial l}{\partial x_{1}},\cdots,\frac{\partial l}{\partial
x_{d_{\bm{x}}}}\right].$ (33)

Thus the maximum norm of the Jacobian matrix $J$ can be bounded by the maximum
norm of derivative of $l$ with respect to $\bm{x}$,

$\max\|J\|_{2}\leq\sqrt{d_{\bm{x}}}\max_{j}\left|\frac{\partial l}{\partial
x_{j}}\right|,$ (34)

where the $\left|\frac{\partial l}{\partial x_{j}}\right|$ can be bounded by

$\displaystyle\left|\frac{\partial l}{\partial x_{j}}\right|$
$\displaystyle=\left|\left(\langle\psi\rvert M\lvert\psi\rangle-y\right)\cdot
2\mathcal{R}\left(\langle\psi\rvert M\frac{\partial\lvert\psi\rangle}{\partial
x_{j}}\right)\right|$ (35) $\displaystyle\leq(\left|M\right|+\max|y|)\cdot
2|M|\cdot\left|\frac{\partial\lvert\psi\rangle}{\partial x_{j}}\right|_{2}.$
(36)

Here, $\left|M\right|$ denotes the spectral norm of the measurement operator.
To bound $\|\frac{\partial\lvert\psi\rangle}{\partial x_{j}}\|_{2}$, let
$U^{(k)}=U({\bm{x}},\bm{\theta}^{(k)},\bm{w}^{(k)})$, we first apply product
rule to $\frac{\partial\lvert\psi\rangle}{\partial x_{j}}$,

$\frac{\partial\lvert\psi\rangle}{\partial
x_{j}}=\sum_{k=1}^{d}U^{(d)}...iw_{j}^{(k)}P_{j}U^{(k)}...U^{(1)}\lvert
0\rangle.$ (37)

As the norm of operators $U^{(k)}$ and $P_{j}$ is equal to 1, we can bound
$\left|\frac{\partial\lvert\psi\rangle}{\partial x_{j}}\right|_{2}$ by

$\displaystyle\left|\frac{\partial\lvert\psi\rangle}{\partial
x_{j}}\right|_{2}$
$\displaystyle\leq\sum_{k=1}^{d}\left|U^{(d)}...w_{j}^{(k)}P_{j}U^{(k)}...U^{(1)}\lvert
0\rangle\right|_{2}$ (38)
$\displaystyle=\sum_{k=1}^{d}\left|w_{j}^{(k)}\right|$ (39) $\displaystyle\leq
d\max_{j}\left|\bm{w}_{j}\right|.$ (40)

Hence, we can bound $\left|\frac{\partial l}{\partial x_{j}}\right|$ by

$\displaystyle\left|\frac{\partial l}{\partial x_{j}}\right|$
$\displaystyle\leq
2d\max_{j}|\bm{w}_{j}|\cdot\left|M\right|\cdot(\left|M\right||+\max|y|).$ (41)

Provided the feature space and the label space are bounded, the loss function
is $\lambda$-Lipschitz continuous with

$\lambda=2d\sqrt{d_{\bm{x}}}\max_{j}\left|\bm{w}_{j}\right|\cdot\left|M\right|(\left|M\right|+\max|y|).$
(42)

∎

###  A.1 Proof of Theorem 1

We neglect the residual training error in coreset from now on. For the
$n_{c}$-class classification problem, we assume that there are class-specific
regression functions that represent the probability of a class label in the
neighborhood of a feature vector $\eta_{c}({\bm{x}})=p(y=c|{{\bm{x}}})$ and
that they satisfy the property of being $\lambda_{\eta}$-Lipschitz continuous
with respect to the feature space of $\bm{x}$. Then we present Lipschitz
constants for the loss functions of QNN and derive the upper bound for the
generalization error.

###### Proof.

By triangular inequality,

$G_{c}^{\text{QNN}}=\left|R-R_{c}^{\text{QNN}}\right|\leq\left|R-R_{e}^{\text{QNN}}\right|+\left|R_{e}^{\text{QNN}}-R_{c}^{\text{QNN}}\right|.$
(43)

Since $\left|R-R_{e}^{\text{QNN}}\right|$ is bounded by Theorem 3,

$|R-R_{e}^{\text{QNN}}|<\mathcal{O}\left(\sqrt{\frac{m\log(m)}{N_{t}}}+\sqrt{\frac{\log(1/\delta)}{N_{t}}}\right).$
(44)

Let us attempt to relate $R_{e}$ with coreset. Since we assume the training
loss over coreset $R_{c}^{\text{QNN}}$ is equal to zero, only
$R_{e}^{\text{QNN}}$ should be considered. Here we allow differently labelled
samples to appear mixed in a local region of the feature space. Instead of
regarding the probability of each label jumping between 0 and 1, we use the
local class-specific regression function $\eta$ to describe the probability of
each label close to a point.

$\displaystyle R_{e}^{\text{QNN}}$
$\displaystyle=\frac{1}{|{\cal{X}}|}\sum_{{{\bm{x}}}_{j}\in{\cal{X}}}\sum_{c_{i}}(\eta_{c_{i}}({\bm{x}_{j}})\cdot
l(f_{\bm{\theta}}({{\bm{x}}}_{j}),c_{i}))$ (45)
$\displaystyle=\mathbb{E}_{{{\bm{x}}}_{j}\in{\cal{X}}}\sum_{c_{i}}(\eta_{c_{i}}({\bm{x}_{j}})\cdot
l(f_{\bm{\theta}}({{\bm{x}}}_{j}),c_{i})).$ (46)

For each $({\bm{x}_{j}},y_{j})$ drawn from the training set, we are guaranteed
with the nearest center $({\bm{x}_{c}},y_{j})$ of the same class in the
coreset with distance less than $\delta_{c}$. If locally the class-specific
regression function $\eta_{c_{j}}\neq 0$ for another label $c_{i}$ with
$c_{i}\neq y_{j}$, then we would have at least one differently labeled sample
within $\delta_{c}$ from ${\bm{x}_{c}}$ and $2\delta_{c}$ from ${\bm{x}_{j}}$.
This other-class sample in the same circle, in turn, guarantees an other-class
center ${\bm{x}_{c}}(c_{i})$ within $3\delta_{c}$ from ${\bm{x}_{j}}$. For
each $\bm{x}_{j}$, we have

$\displaystyle\sum_{c_{i}}\eta_{c_{i}}({\bm{x}_{j}})\cdot
l(f_{\bm{\theta}}({\bm{x}_{j}}),c_{i})$ (47) $\displaystyle=$
$\displaystyle\sum_{c_{i}}\eta_{c_{i}}({\bm{x}_{j}})\cdot\left[l(f_{\bm{\theta}}(\bm{x}_{j}),c_{i})-l(f_{\bm{\theta}}(\bm{x}_{j}(c_{i})),c_{i})\right]+\sum_{c_{i}}\eta_{c_{i}}(\bm{x}_{j})\cdot
l(f_{\bm{\theta}}(\bm{x}_{c}(c_{i})),c_{i})$ (48) $\displaystyle=$
$\displaystyle\sum_{c_{i}}\eta_{c_{i}}({\bm{x}_{j}})\cdot\left[l(f_{\bm{\theta}}(\bm{x}_{j}),c_{i})-l(f_{\bm{\theta}}(\bm{x}_{j}(c_{i})),c_{i})\right]+\sum_{c_{i}}\left[\eta_{c_{i}}(\bm{x}_{j})-\eta_{c_{i}}(\bm{x}_{c}(c_{i}))\right]\cdot
l(f_{\bm{\theta}}(\bm{x}_{c}(c_{i})),c_{i})$ (49)
$\displaystyle+\sum_{c_{i}}\eta_{c_{i}}(\bm{x}_{c}(c_{i}))\cdot
l(f_{\bm{\theta}}(\bm{x}_{c}(c_{i})),c_{i}).$ (50)

The last term is the loss of the center weighted by the local probability of
being same-class as that center. For a specific center, it will be called by
both same-class samples and other-class samples that find it closest in the
coreset, the number of calls is approximately proportional to the number of
samples covered by the center. With the factor
$\eta_{c_{i}}(\bm{x}_{c}(c_{i}))$ in each call, the corresponding weight for a
center in the coreset should be the number of samples covered $\times$ local
probability of being center-class, i.e., the number of same-class samples
covered by the center. This justifies our choice of the weight in Eq. (19).
Assuming the weighted loss is trained to zero, the form of the previous
expression is then simplified to

$\displaystyle\sum_{c_{i}}\eta_{c_{i}}(\bm{x}_{j})\cdot
l(f_{\bm{\theta}}(\bm{x}_{j}),c_{i})$
$\displaystyle=\sum_{c_{i}}\eta_{c_{i}}(\bm{x}_{j})\cdot\left[l(f_{\bm{\theta}}(\bm{x}_{j}),c_{i})-l(f_{\bm{\theta}}(\bm{x}_{c}(c_{i})),c_{i})\right]$
(51)
$\displaystyle+\sum_{c_{i}}\left[\eta_{c_{i}}(\bm{x}_{j})-\eta_{c_{i}}(\bm{x}_{c}(c_{i})\right]\cdot
l(f_{\bm{\theta}}(\bm{x}_{c}(c_{i})),c_{i}).$ (52)

The two parts in the last equation can be separately bounded by the Lipschitz
continuity $\lambda_{\zeta}$ and $\lambda_{l}$ of $\eta_{c_{i}}$ and $l$, and
assume the $l$ is bounded by $L$. Substituting into the corresponding
constants, we have

$\displaystyle\mathbb{E}_{{{\bm{x}}}_{j}\in{\cal{X}}}\sum_{c_{i}}(\eta_{c_{i}}({\bm{x}_{j}})\cdot
l(f_{\bm{\theta}}({{\bm{x}}}_{j}),c_{i}))\leq$ $\displaystyle(\sum_{c_{i}\neq
y_{j}}\eta_{c_{i}}(\bm{x}_{j})\cdot
3\delta_{c}+\eta_{y_{j}}(\bm{x}_{j})\cdot\delta_{c})\lambda_{l}+((n_{c}-1)\cdot
3\delta_{c}+\delta_{c})L\lambda_{\eta}$ (53) $\displaystyle\leq$
$\displaystyle(\sum_{c_{i}}\eta_{c_{i}}(\bm{x}_{j}))3\delta_{c}\lambda_{l}+(3n_{c}-2)\delta_{c}\lambda_{\eta}L$
(54) $\displaystyle=$ $\displaystyle
3\delta_{c}\lambda_{l}+(3n_{c}-2)\delta_{c}\lambda_{\eta}L.$ (55)

According to Hoeffding’s bound and assumption of zero coreset training loss,
we have the coreset error of QNN with probability $1-\delta$,

$\left|R_{e}^{\text{QNN}}-R_{c}^{\text{QNN}}\right|\leq
3\delta_{c}\lambda_{l}+(3n_{c}-2)\delta_{c}\lambda_{\eta}L+\sqrt{\frac{L^{2}\log(1/\delta)}{2n}}.$
(57)

Combing the bound of the $\left|R-R_{e}^{\text{QNN}}\right|$, we have the
generalization bound of QNN on coreset with probability $1-\delta$

$G_{c}^{\text{QNN}}\leq\mathcal{O}\left(\sqrt{\frac{m\log(m)}{N_{t}}}+\sqrt{\frac{\log(1/\delta)}{N_{t}}}+\delta_{c}(\lambda_{\eta}Ln_{c}+d\sqrt{d_{\bm{x}}}\max_{j}|\bm{w}_{j}|\left|M\right|(\left|M\right|+\max|y|)\right).$
(58)

∎

######  Theorem 4.

(Generalization bound for learning with quantum kernel [13]) Suppose the
parameters $\bm{w}$ of the hypothesis $f_{\bm{w}}$ is optimized to be
$\bm{w^{*}}$ by minimizing the loss
$l(f_{\bm{w}}(\bm{x})),y)=|\min(1,\max(-1,\sum_{j}w_{j}\kappa(\bm{x}_{j},\bm{x})))-y|$
on a training set $\\{{{\bm{x}}}_{i},y_{i}\\}_{i=1}^{N_{t}}$. Then, according
to Theorem 2 in [6], the generalization error of the optimized hypothesis is
bounded by the following form with probability at least $(1-\delta)$ over the
choice of $i.i.d$ training data ${\cal{S}}$ from $\mathcal{Z}$:

$|R-R_{e}^{\text{qkernel}}|<\mathcal{O}\left(\sqrt{\frac{\lceil\|\bm{w}\|^{2}\rceil}{N_{t}}}+\sqrt{\frac{\log(4/\delta)}{N_{t}}}\right).$
(59)

######  Lemma 2.

The function
$l(f_{\bm{w}}(\bm{x})),y)=|\min(1,\max(-1,\sum_{j}w_{j}\kappa(\bm{x}_{j},\bm{x})))-y|$,
where $\kappa(\bm{x},\bm{x}^{\prime})$ is the quantum kernel function, is
$\lambda$-Lipschitz continuous in feature space with

$\lambda=2k_{c}\sqrt{d_{\bm{x}}}\max_{i}|w_{i}|\cdot(1+(N_{q}-1)r).$ (60)

###### Proof.

This follows immediately from evaluating the norm of the weight vector in the
mapped Hilbert space. The function $l$ can be viewed as $l=g\circ f$, where

$g(f)=|\min(1,\max(-1,f))-y|,$ (61)

and

$f({\bm{w}},\bm{x})=\sum_{j=1}^{k_{c}}w_{j}\kappa({\bm{x}_{j}},\bm{x}),$ (62)

where $\kappa:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}$ is the quantum
kernel function and $k_{c}$ being the size of the coreset. The function $g$
has a Lipschitz constant of $1$ with respect to $f$. Concretely, it is defined
as follows

$\kappa(\bm{x}_{j},\bm{x}_{k})=\langle\phi(\bm{x}_{j}),\phi(\bm{x}_{k})\rangle=|\langle
0|U_{\bm{x}_{j}}^{\dagger}U_{\bm{x}_{k}}|0\rangle|^{2},$ (63)

where $U_{\bm{x}}=(U(\bm{x})H^{\otimes N_{q}})^{2}|0\rangle^{\otimes N_{q}}$,
$U(\bm{x})=\exp(\sum_{j=1}^{N_{q}}\bm{x}_{j}\sigma^{Z}_{j}+\sum_{j,j^{\prime}=1}^{N_{q}}\bm{x}_{j}\bm{x}_{j^{\prime}}\sigma^{Z}_{j}\sigma^{Z}_{j^{\prime}})$,
and $N_{q}$ is system size of mapped state
For any fixed ${\bm{w}}$, we have

$\displaystyle\left|f({\bm{w}},\bm{x})-f(\bm{w},\bm{x}^{\prime})\right|$
$\displaystyle\leq\max_{\bm{x}}\sqrt{\sum_{j=1}^{d_{\bm{x}}}\left|\frac{\partial{f}}{\partial{x_{j}}}\right|^{2}}\cdot\left|\bm{x}-\bm{x}^{\prime}\right|$
(64)
$\displaystyle\leq\sqrt{d_{\bm{x}}}\max_{j}\left|\frac{\partial{f}}{\partial{x_{j}}}\right|\cdot\left|\bm{x}-\bm{x}^{\prime}\right|.$
(65)

Assume we train the SVM with quantum kernel on a coreset
$\\{\bm{x}_{i}\\}_{i=1}^{k_{c}}$, and let
$\rho(\bm{x})=U_{\bm{x}}|0\rangle\langle 0|U^{\dagger}_{\bm{x}}$, we have

$\displaystyle\left|\frac{\partial{f}}{\partial{x_{j}}}\right|$
$\displaystyle=2\left|\sum_{k=1}^{k_{c}}w_{k}\mathcal{R}(\langle
0|\frac{\partial{U^{\dagger}(\bm{x})}}{\partial{x_{j}}}\rho(\bm{x}_{k})U(\bm{x})|0\rangle)\right|$
(66) $\displaystyle\leq 2k_{c}\cdot\max_{k}|\bm{w}_{k}|\cdot\left|\langle
0|\frac{\partial{U^{\dagger}(\bm{x})}}{\partial{x_{j}}}\rho(\bm{x}_{k})U(\bm{x})|0\rangle\right|$
(67)
$\displaystyle=2k_{c}\cdot\max_{k}|\bm{w}_{k}|\cdot\left|\frac{\partial{U(\bm{x})}}{\partial{x_{j}}}\right|_{2}.$
(68)

Since
$U(\bm{x})=\exp(\sum_{j=1}^{N_{q}}\bm{x}_{j}\sigma^{Z}_{j}+\sum_{j,j^{\prime}=1}^{N_{q}}\bm{x}_{j}\bm{x}_{j^{\prime}}\sigma^{Z}_{j}\sigma^{Z}_{j^{\prime}})$,
we denote $U_{s}=\prod_{k=1}^{N_{q}}\exp(ix_{k}\sigma^{Z}_{k})$ and
$U_{e}=\prod_{k<l}^{N_{q}}U_{k,l}$, where
$U_{k,l}=\exp(ix_{k}x_{l}\sigma^{Z}_{k}\sigma^{Z}_{l})$, then the norm of the
derivative of $U(\bm{x})$ with respect to $x_{j}$ can be bounded,

$\displaystyle\left|\frac{\partial{U(\bm{x})}}{\partial{x_{j}}}\right|_{2}$
$\displaystyle=\left|\frac{\partial{U_{s}}}{\partial{x_{j}}}U_{e}+U_{s}\frac{\partial{U_{e}}}{\partial{x_{j}}}\right|$
(69)
$\displaystyle\leq\left|\frac{\partial{U_{s}}}{\partial{x_{j}}}\right|_{2}\cdot\left|U_{e}\right|_{2}+\left|U_{s}\right|_{2}\cdot\left|\frac{\partial{U_{e}}}{\partial{x_{j}}}\right|_{2}$
(70)
$\displaystyle\leq\left|i\sigma^{Z}_{j}\right|\cdot\left|\exp(ix_{j}\sigma^{Z}_{j})\right|\cdot\left|\prod^{N_{q}}_{k\neq
j}\exp(ix_{k}\sigma^{Z}_{k})\right|$ (71) $\displaystyle+\left|\sum_{k\neq
j}^{{N_{q}}}ix_{k}\sigma_{k}^{Z}\sigma_{j}^{Z}U_{k,j}\cdot\prod_{m<n,(m,n)\neq(k,j)\text{or}(j,k)}^{N_{q}}U_{m,n}\right|$
(72) $\displaystyle\leq 1+(N_{q}-1)\max_{j}|x_{j}|.$ (73)

Substitute Eq.(73) to Eq.(68), we have

$\left|\frac{\partial{f}}{\partial{x_{j}}}\right|\leq
2k_{c}\max_{i}|\bm{w}_{i}|\cdot(1+(N_{q}-1)r).$ (74)

Assuming $r$, the maximum feature value of $\bm{x}$, is bounded and
substituting Eq.(74) to Eq.(64), we can conclude the function
$l(f_{\bm{w}}(\bm{x})),y)$ is
$2k_{c}\sqrt{d_{\bm{x}}}\max_{i}|\bm{w}_{i}|\cdot(1+(N_{q}-1)r)$-Lipschitz
continuous. ∎

###  A.2 Proof of Theorem 2

###### Proof.

The proof of Theorem 2 is similar to the proof of Theorem 1, replacing the
relevant Lipschitz constant and generalization bound from Lemma 2 and Theorem
1 respectively. ∎