17

# Deterministic and random features for large-scale quantum kernel machine

Kouhei Nakaji  Quantum Computing Center, Keio University, Hiyoshi 3-14-1,
Kohoku-ku, Yokohama 223-8522, Japan  Research Center for Emerging Computing
Technologies, National Institute of Advanced Industrial Science and Technology
(AIST), 1-1-1 Umezono, Tsukuba, Ibaraki 305-8568, Japan.  Current Address:
Department of Chemistry, University of Toronto, Toronto, Ontario M5G 1Z8,
Canada  Hiroyuki Tezuka  Sony Group Corporation, 1-7-1 Konan, Minato-ku,
Tokyo, 108-0075, Japan  Quantum Computing Center, Keio University, Hiyoshi
3-14-1, Kohoku-ku, Yokohama 223-8522, Japan  Graduate School of Science and
Technology, Keio University, Hiyoshi 3-14-1, Kohoku-ku, Yokohama, 223-8522,
Japan  Naoki Yamamoto  Quantum Computing Center, Keio University, Hiyoshi
3-14-1, Kohoku-ku, Yokohama 223-8522, Japan  Department of Applied Physics and
Physico-Informatics, Keio University, Hiyoshi 3-14-1, Kohoku-ku, Yokohama,
223-8522, Japan

(August 2022)

###### Abstract

Quantum machine learning (QML) is the spearhead of quantum computer
applications. In particular, quantum neural networks (QNN) are actively
studied as the method that works both in near-term quantum computers and
fault-tolerant quantum computers. Recent studies have shown that supervised
machine learning with QNN can be interpreted as the quantum kernel method
(QKM), suggesting that enhancing the practicality of the QKM is the key to
building near-term applications of QML. However, the QKM is also known to have
two severe issues. One is that the QKM with the (inner-product based) quantum
kernel defined in the original large Hilbert space does not generalize;
namely, the model fails to find patterns of unseen data. The other one is that
the classical computational cost of the QKM increases at least quadratically
with the number of data, and therefore, QKM is not scalable with data size.
This paper aims to provide algorithms free from both of these issues. That is,
for a class of quantum kernels with generalization capability, we show that
the QKM with those quantum kernels can be made scalable by using our proposed
deterministic and random features. Our numerical experiment, using datasets
including $O(1,000)\sim O(10,000)$ training data, supports the validity of our
method.

##  I Introduction

Machine learning (ML) algorithms have been rapidly evolving, accompanied by
the increase in the volume and complexity of data. Demands for more efficient
models to describe those data ignited the interest in ML utilizing quantum
computing, i.e., quantum machine learning (QML) [1, 2, 3, 4]. Among many
proposals in QML, we focus on the so-called quantum-classical hybrid
algorithms that work both in near-term quantum computers and fault-tolerant
quantum computers. There are two directions in the hybrid algorithms: the
quantum neural network (QNN) [5] and the quantum kernel method (QKM) [6, 7]. A
notable fact is that QKM can find a globally optimal solution better than QNN
in supervised machine learning because, even though a globally optimal
solution of QKM and infinite depth QNN are equivalent [8], the non-convex
optimization in QNN is much more problematic than the convex optimization in
QKM due to the problems such as the barren plateau phenomenon [9]. Also, Ref.
[10] gives a characterization of QKM that has a quantum advantage over
classical ML algorithms.

QKM, however, has two serious issues: the generalization capability issue and
the scalability issue, both of which are shared with the classical kernel
method. The generalization capability issue states as follows. Suppose that a
quantum kernel, which represents a similarity between data, is a function of
the distance between data-embedded quantum states in a Hilbert space with
exponentially large dimensions. The original quantum kernel [6], defined by
the inner product of pure quantum states, is one of such kernels. However, in
this case, the difference of kernel for different data decreases exponentially
fast as the size of Hilbert space grows [11], and the resulting Gram matrix
becomes close to the identity matrix [10, 12]. The QKM with such quantum
kernels does not generalize, meaning that it fits with the pattern of the
training data, but fails to find patterns of the unseen data.

The scalability issue states that, given the number of training data as $M$,
we need at least $O(M^{2})$ classical computation, which is problematic when
$M$ is large (See [8]). For example, in the kernel Ridge regression,
$O(M^{3})$ computation is required for diagonalizing the Gram matrix. This
scalability issue is not unique to the quantum case; the issue of poor
scalability with data volume exists in the general kernel method and severely
limits its applicability. Hence, in the classical case, various scalable
kernel methods have been proposed [13, 14, 15, 16, 17, 18]. Among them, the
most popular framework is the method using random Fourier features [13]; the
idea is to approximate the target kernel by the inner products of
probabilistically generated feature vectors, where these two quantities are
guaranteed to be close with each other. The solution to the linear machine
learning problem using those approximating features achieves a competitive
performance to the original kernel method, while the computational complexity
to have the approximating solution is much reduced compared to the original
one. For example, given a dimension of the features as $D$, the computational
complexity of training the linear regression model with the features is
reduced to be $O(MD^{2})$, while the corresponding kernel ridge regression
requires $O(M^{3})$ computation. Note that the random Fourier features require
the kernel to be shift-invariant, and thus we cannot directly apply this
technique to the quantum kernel, which is generally not shift-invariant.
Still, the idea of approximating the quantum kernel with an inner product of
low-dimensional features is an attractive approach to scalable QKM.

This paper proposes QKM free from the generalization capability issue and the
scalability issue. We first examine a class of quantum kernels with
generalization capability, which we call the quantum kernel with
generalization capability (QKGC). The quantum kernel with reduced density
matrix (RDM) is previously proposed [10, 12] as QKGC. As other possible QKGC,
we examine a quantum kernel with reduced observable (RO), which we define by a
distance between observables. However, our theoretical analysis shows that the
quantum kernel with RO is almost equivalent to the quantum kernel with RDM. We
also examine naively constructible QKGCs, but it is shown that they lack
quantum advantage. These observations led us to examine the scalability
property of QKGC with RDM.

Our main contribution is to show that the scalability issue can be solved for
QKGC with RDM. Specifically, we rigorously show that QKGC with RDM can be
always approximated by the inner products of low-dimensional features, with a
guaranteed error bound. Therefore, as with the random Fourier features, we can
obtain the approximating solution with those features to the original QKM
problem with reduced computational complexity. Our numerical experiment, using
datasets including $O(1,000)\sim O(10,000)$ training data, supports the
validity of our proposed method.

The rest of the paper is organized as follows. In Section II, we briefly
review the background of QKM. The generalization capability issue and the
scalability issue of QKM are also discussed in the section. In Section III, we
discuss QKGC with RDM as a solution for the generalization capability issue.
Section IV is dedicated to describing our method for approximating QKGC.
Finally, we demonstrate the performance of the proposed QKM method in some
benchmark ML problems in Section V.

##  II Conventional QKM

In this section, we first review the basics of the QKM; in particular, the
correspondence between QNN and QKM is discussed. Next, we show the issues of
the QKM; the issue of generalization capability and the issue of computational
complexity. Finally, we give some remarks on the recently proposed data
reuploading model [19, 20, 21] in light of the QKM.

###  II.1 Preliminary

####  II.1.1 Basics of QKM

Let $\mathcal{X}$ be an instance space and $\mathcal{Y}$ be a label space and
there is a hidden relationship between ${\boldsymbol{\bf x}}\in\mathcal{X}$
and $y\in\mathcal{Y}$ as $y=f^{\ast}({\boldsymbol{\bf x}})$. The goal of
supervised ML is to train a model function
$f_{{\boldsymbol{\bf\theta}}}:\mathcal{X}\rightarrow\mathcal{Y}$ so that
$f_{{\boldsymbol{\bf\theta}}}({\boldsymbol{\bf x}})\simeq
f^{\ast}({\boldsymbol{\bf x}})$ by using a training data $\mathcal{X}_{\rm
data}=\\{{\boldsymbol{\bf x}}_{j},y_{j}\\}_{j=1}^{M}$, where
${\boldsymbol{\bf\theta}}$ is model parameters, ${\boldsymbol{\bf
x}}_{j}\in\mathcal{X}$, and $y_{j}\in\mathcal{Y}$.

In the QKM, we construct the model function by

$f_{{\boldsymbol{\bf a}}}({\boldsymbol{\bf
x}})=\sum_{j=1}^{M}a_{j}Q({\boldsymbol{\bf x}}_{j},{\boldsymbol{\bf x}}),$ (1)

with $Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})$ as a quantum
kernel and ${\boldsymbol{\bf a}}=\\{a_{j}\\}_{j=1}^{M}$ as real parameters to
be determined (to clearly distinguish the parameters from those contained in
the quantum circuit, we write the parameters of the model function in kernel
method as ${\boldsymbol{\bf a}}$ instead of ${\boldsymbol{\bf\theta}}$). The
quantum kernel is computed from two quantum states in which data is embedded.
Namely, for a quantum state (density operator) $\rho({\boldsymbol{\bf x}})$
with ${\boldsymbol{\bf x}}$ a classical data, we compute the quantum kernel as
$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})=h(\rho({\boldsymbol{\bf
x}}),\rho({\boldsymbol{\bf x}}^{\prime}))$, where $h$ is a real-valued
function that takes two density operators. Note that $\rho({\boldsymbol{\bf
x}})$ can be a “quantum data” generated by some quantum process, in which case
${\boldsymbol{\bf x}}$ represents a label or parameter for identifying such
quantum data.

Once the quantum kernels are computed for all training dataset and the Gram
matrix is constructed, we follow the standard ML algorithm such as the kernel
Ridge regression and the support vector machine [22] to have the model
function. That is, we train the parameters ${\boldsymbol{\bf a}}$ so that a
cost function $L({\boldsymbol{\bf a}},\lambda,\mathcal{X}_{\rm data})$ defined
by

$L({\boldsymbol{\bf a}},\lambda,\mathcal{X}_{\rm
data})=\frac{1}{M}\sum_{k=1}^{M}\ell(y_{k},f_{{\boldsymbol{\bf
a}}}({\boldsymbol{\bf x}}_{k}))+\lambda{\boldsymbol{\bf
a}}^{T}{\boldsymbol{\bf Q}}{\boldsymbol{\bf a}},$ (2)

is minimized, where $\lambda$ is the regularization parameter and
${\boldsymbol{\bf Q}}$ is the Gram matrix with $(j,k)$ element
$Q_{jk}=Q({\boldsymbol{\bf x}}_{j},{\boldsymbol{\bf x}}_{k})$. The function
$\ell:\mathcal{Y}\times\mathcal{Y}\rightarrow\mathbf{R}$ depends on the
algorithm; for example, the mean squared loss $\ell(y,f({\boldsymbol{\bf
x}}))=(y-f({\boldsymbol{\bf x}}))^{2}/2$ corresponds to the kernel Ridge
regression. As far as $\ell$ is a convex function, minimization of $L$ with
respect to ${\boldsymbol{\bf a}}$ is the convex optimization problem.

The QKM is recognized as a promising variant of the kernel method, because the
quantum kernel utilizes exponentially high dimensional feature space of
$\rho({\boldsymbol{\bf x}})$, which is intractable by any classical means but
possible via quantum devices with many qubits.

####  II.1.2 Correspondence between QKM and QNN

The correspondence between QKM and QNN is discussed in [8]. In the QNN models,
the model function is constructed as

$f_{{\boldsymbol{\bf\theta}}}({\boldsymbol{\bf x}})={\rm
Tr}(OU({\boldsymbol{\bf\theta}})\rho({\boldsymbol{\bf
x}})U^{\dagger}({\boldsymbol{\bf\theta}}))),$ (3)

with a data-embedded quantum state $\rho({\boldsymbol{\bf x}})$, parameters
${\boldsymbol{\bf\theta}}$, and an observable $O$. This model function can be
evaluated on a quantum circuit; namely, the data encoding process generates
$\rho({\boldsymbol{\bf x}})$, which then goes through a parameterized circuit
$U({\boldsymbol{\bf\theta}})$, and finally the expectation value of $O$ is
computed.

Let $\mathcal{O}$ be a Hermitian observable defined by

$\mathcal{O}=U^{\dagger}({\boldsymbol{\bf\theta}})OU({\boldsymbol{\bf\theta}}).$
(4)

Then $f_{{\boldsymbol{\bf\theta}}}({\boldsymbol{\bf
x}})=f(\mathcal{O},{\boldsymbol{\bf x}})={\rm
Tr}(\mathcal{O}\rho({\boldsymbol{\bf x}}))$. Though the matrix elements of
$\mathcal{O}$ are constrained such that they have to satisfy Eq. (4), let us
relax the constraint and suppose that $\mathcal{O}$ can be an arbitrary
Hermitian operator. Now consider the cost function

$L(\mathcal{O},\lambda,\mathcal{X}_{\rm
data})=\frac{1}{M}\sum_{k=1}^{M}\ell(y_{k},f(\mathcal{O},{\boldsymbol{\bf
x}}_{k}))+\lambda{\rm Tr}(\mathcal{O}^{\dagger}\mathcal{O}),$ (5)

and suppose that the minimizer of the cost is $\mathcal{O}=\mathcal{O}^{opt}$.
The representer theorem states that the optimal function with
$\mathcal{O}^{opt}$ can be written as

$f(\mathcal{O}^{opt},{\boldsymbol{\bf
x}})=\sum_{j=1}^{M}a_{j}^{opt}Q({\boldsymbol{\bf x}}_{j},{\boldsymbol{\bf
x}}),$ (6)

where $Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})={\rm
Tr}(\rho({\boldsymbol{\bf x}})\rho({\boldsymbol{\bf x}}^{\prime}))$. The
coefficients ${\boldsymbol{\bf a}}^{opt}=\\{a_{j}^{opt}\\}_{j=1}^{M}$ are the
minimizer of (2) with the same $\ell$ and $\lambda$ as those appearing in (5).

The consequence of the above discussion is that the function obtainable by
using the QNN is at most as good as that obtained by using the QKM. Also, from
another viewpoint, we should use the QKM rather than the QNN; because
$\mathcal{O}$ may not be able to take $\mathcal{O}^{opt}$ due to the
constraint (4), and the optimization of the circuit
$U({\boldsymbol{\bf\theta}})$ in the QNN is, in general, much more difficult
than the convex optimization of ${\boldsymbol{\bf a}}$ in the QKM. However,
the QKM has two serious issues, which will be shown in the next subsection.

Before moving forward, note that the above discussion regarding the
correspondence between QNN and QKM does not hold for the recently proposed
data re-uploading model [19, 20, 21], which is a variant of QNN. We will give
some remarks on the correspondence between the data re-uploading QNN model and
QKM in Section II.3.

###  II.2 Issues of the conventional QKM

####  II.2.1 Issue regarding the generalization capability

For pure quantum states $\ket{\psi({\boldsymbol{\bf x}})}$ with
${\boldsymbol{\bf x}}\in\mathcal{X}$, the original quantum kernel [6] is
defined as the inner product of two pure quantum states:

$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})=|\langle\psi({\boldsymbol{\bf x}})|\psi({\boldsymbol{\bf
x}}^{\prime})\rangle|^{2}.$ (7)

The model function with this kernel, $f_{{\boldsymbol{\bf
a}}}({\boldsymbol{\bf x}})$ given in Eq. (1), can learn any function
$f^{*}({\boldsymbol{\bf x}})$ of the form $f^{*}({\boldsymbol{\bf
x}})=\langle\psi({\boldsymbol{\bf x}})|\mathcal{M}|\psi({\boldsymbol{\bf
x}})\rangle$ with any observable $\mathcal{M}$.

However, the subsequent works [10, 12] show that it is practically impossible
to train the model function $f_{{\boldsymbol{\bf a}}}({\boldsymbol{\bf x}})$
with the kernel (7), if the dimension of Hilbert space of
$|\psi({\boldsymbol{\bf x}})\rangle$ is large. More concretely,
$M\geq\Omega(2^{n})$ of training data is necessary for training
$f_{{\boldsymbol{\bf a}}}({\boldsymbol{\bf x}})$ so that it well approximates
$f^{\ast}({\boldsymbol{\bf x}})$. A brief explanation is as follows. Given a
probability distribution of data as $P_{\rm data}$, let us consider two
different samples ${\boldsymbol{\bf x}}$ and ${\boldsymbol{\bf x}}^{\prime}$
sampled from $P_{\rm data}$. Then, the probability that $Q({\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime})$ is larger than a certain value $\epsilon$,
is exponentially suppressed by the factor ${\rm poly}(1/\epsilon,M,1/2^{n})$,
where, again, $M$ is the number of data and we denote a polynomial function of
$(a,b,c)$ by ${\rm poly}(a,b,c)$. Thus, as far as $M\ll 2^{n}$,
$f_{{\boldsymbol{\bf a}}}({\bf x}_{k})\simeq a_{k}~{}(\forall k)$ and the
coefficients are trained to be $a_{k}\simeq y_{k}~{}(\forall k)$. This means
that, even though the resulting model function $f_{{\boldsymbol{\bf
a}}}({\boldsymbol{\bf x}})$ well reproduces the label of the training data as
$f_{{\boldsymbol{\bf a}}}({\boldsymbol{\bf x}}_{k})\simeq y_{k}$, it holds
$f_{{\boldsymbol{\bf a}}}({\boldsymbol{\bf x}})\simeq 0$ for almost all data
${\boldsymbol{\bf x}}$ sampled from $P_{\rm data}$. Namely, the function
trained with the kernel (7) does not have the generalization capability. The
same argument is true for the case when two quantum states are mixed states
$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})={\rm
Tr}(\rho({\boldsymbol{\bf x}})\rho({\boldsymbol{\bf x}}^{\prime}))$ as far as
the dimension of $\rho({\boldsymbol{\bf x}})$ is exponentially large.

####  II.2.2 Issue regarding the computational complexity

The kernel method, including QKM, generally has the scalability issue; namely,
the time complexity and the spatial complexity increase drastically when data
volume increases. Suppose that the kernel function $Q({\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime})$ is defined in the instance space
${\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime}\in\mathcal{X}$. The poor
scalability comes from the computation related to Gram matrix
${\boldsymbol{\bf Q}}$. For example, in the kernel Ridge regression, the time
complexity scales as $O(M^{3})$ (recall that $M$ is the number of training
data), since we need to compute the inverse of ${\boldsymbol{\bf Q}}$. Also,
the spatial complexity scales as $O(M^{2})$, since we need to store all
components of ${\boldsymbol{\bf Q}}$. These scalability issues hinder adopting
the QKM to problems with a large dataset.

In the context of the classical kernel method, several solutions have been
proposed [13, 14]. One of the most promising solutions is the random Fourier
features [13], which provides a way of mitigating the scalability issue by
approximating the kernel function. See Appendix A for a brief review of the
random Fourier features. A notable point is that we can use this technique
only when the kernel is of the following shift-invariant form:

$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})=Q({\boldsymbol{\bf
x}}-{\boldsymbol{\bf x}}^{\prime}).$ (8)

Because in general the quantum kernel does not satisfy this condition, we need
other solutions in the quantum case, which is the topic discussed in Section
IV.

###  II.3 Remark on the data reuploading model

The data reuploading model [19, 20, 21] is recently proposed as a variant of
the QNN. Unlike the QNN with single data layer, we repeatedly encode data into
the quantum state as follows;

$\begin{split}&\ket{\psi({\boldsymbol{\bf\theta}},{\boldsymbol{\bf x}})}\\\
&=U_{L}({\boldsymbol{\bf\theta}}_{L})U_{L}({\boldsymbol{\bf x}})\cdots
U_{2}({\boldsymbol{\bf\theta}}_{2})U_{2}({\boldsymbol{\bf
x}})U_{1}({\boldsymbol{\bf\theta}}_{1})U_{1}({\boldsymbol{\bf
x}})|0\rangle^{\otimes n},\end{split}$ (9)

and build the model function as $f_{{\boldsymbol{\bf\theta}}}({\boldsymbol{\bf
x}})=\bra{\psi({\boldsymbol{\bf\theta}},{\boldsymbol{\bf
x}})}O\ket{\psi({\boldsymbol{\bf\theta}},{\boldsymbol{\bf x}})}$ in the data
reuploading model. The repeated encoding increases the number of Fourier
components in the model function
$f_{{\boldsymbol{\bf\theta}}}({\boldsymbol{\bf x}})$ and accordingly the
expressibility of $f_{{\boldsymbol{\bf\theta}}}({\boldsymbol{\bf x}})$, as we
show in Appendix B.

The theoretical correspondence between the data reuploading model and the QKM
can be seen by embedding trainable parameters in the quantum kernel. More
concretely, given a quantum state

$\begin{split}&\ket{\psi(\tilde{{\boldsymbol{\bf\theta}}},{\boldsymbol{\bf
x}})}\\\ &=U_{L}({\boldsymbol{\bf
x}})U_{L-1}({\boldsymbol{\bf\theta}}_{L-1})\cdots
U_{2}({\boldsymbol{\bf\theta}}_{2})U_{2}({\boldsymbol{\bf
x}})U_{1}({\boldsymbol{\bf\theta}}_{1})U_{1}({\boldsymbol{\bf
x}})|0\rangle^{\otimes n},\end{split}$ (10)

with
$\tilde{{\boldsymbol{\bf\theta}}}=\\{{\boldsymbol{\bf\theta}}_{1},{\boldsymbol{\bf\theta}}_{2},\cdots,{\boldsymbol{\bf\theta}}_{L-1}\\}$,
let us define the parameter embedded kernel function by $Q({\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime},\tilde{{\boldsymbol{\bf\theta}}})={\rm
Tr(\rho({\boldsymbol{\bf
x}},\tilde{{\boldsymbol{\bf\theta}}})\rho({\boldsymbol{\bf
x}}^{\prime},\tilde{{\boldsymbol{\bf\theta}}}))}$, where
$\rho({\boldsymbol{\bf
x}},\tilde{{\boldsymbol{\bf\theta}}})=\ket{\psi(\tilde{{\boldsymbol{\bf\theta}}},{\boldsymbol{\bf
x}})}\bra{\psi(\tilde{{\boldsymbol{\bf\theta}}},{\boldsymbol{\bf x}})}$. Then,
the training of $f_{{\boldsymbol{\bf\theta}}}({\boldsymbol{\bf x}})$ with a
certain cost function corresponds to the QKM with the quantum kernel
$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime},\tilde{{\boldsymbol{\bf\theta}}})$, where parameters
$\tilde{{\boldsymbol{\bf\theta}}}$ are fixed. Of course, the training of the
data reuploading model also includes the training of the parameters
$\tilde{{\boldsymbol{\bf\theta}}}$, and therefore, to fully relate the QKM
with the data reuploading model, we need to train
$\tilde{{\boldsymbol{\bf\theta}}}$ within the quantum kernel framework.

As far as we know, there are few pieces of research dedicated to the training
of the quantum kernel. For instance, see [23] that contains the training of
the quantum kernel in the context of quantum phase learning. This is mainly
due to the issue of scalability discussed above; that is, whenever we
iteratively update parameters $\tilde{{\boldsymbol{\bf\theta}}}$, we need to
recompute the Gram matrix, which requires $O(M^{2})$ computation in each
iteration. Conversely, if we resolve the scalability issue, we may be able to
train the quantum kernel. In Section IV, we will propose a scalable QKM and
thereby discuss a method of training quantum kernel.

##  III Quantum kernels with generalization capability (QKGC)

As shown in Section II.2, the QKM with the naive quantum kernel (7) lacks the
generalization capability. In this section, we examine quantum kernels that
have the generalization capability of QKM; we simply call such kernels as
quantum kernels with the generalization capability (QKGC). In Section III.1,
we give a generalized version of QKGC using reduced density matrices (RDMs),
which was originally introduced in [10]. We then examine QKGC with reduced
observables (ROs) in Section III.2. Finally, Section III.3 is devoted to
discussing the other possibility of QKGC without RDM.

###  III.1 QKGC with the reduced density matrix (RDM)

As shown in Section II.2, the low generalization capability of the QKM
attributes to the large dimension of the Hilbert space where
$\rho({\boldsymbol{\bf x}})$ is located. Therefore, using a reduced density
matrix (RDM) $\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf x}})={\rm
Tr}_{\neq{\boldsymbol{\bf q}}}(\Phi(\rho({\boldsymbol{\bf x}})))$ instead of
$\rho({\boldsymbol{\bf x}})$, is a natural solution for the issue, where ${\rm
Tr}_{\neq{\boldsymbol{\bf q}}}$ means tracing out the qubits not included in
an integer vector ${\boldsymbol{\bf q}}$ and $\Phi$ is a completely positive
and trace-preserving (CPTP) map. For restoring the generalization capability,
the dimension of Hilbert space where $\rho^{({\boldsymbol{\bf
q}})}({\boldsymbol{\bf x}})$ exists must be smaller than the number of data
$M$ [12]. In the following, we introduce the inner product kernel and the
distance kernel defined with $\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}})$, which are the generalized version of QKGC proposed in [10].

####  III.1.1 Inner product kernel with RDM

######  Definition 1.

Let $\rho^{({\boldsymbol{\bf q}}_{k})}({\boldsymbol{\bf x}})$ be the $k$-th
data encoded RDM. The index $k$ runs from $1$ to $K$ with some positive
integer $K$. The inner product kernel $Q$ is a function
$Q:\mathcal{M}\times\mathcal{M}\rightarrow\mathbf{R}$ written as

$\displaystyle Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})$
$\displaystyle=\sum_{k=1}^{K}\alpha_{k}{\rm Tr}(\rho^{({\boldsymbol{\bf
q}}_{k})}({\boldsymbol{\bf x}})\rho^{({\boldsymbol{\bf
q}}_{k})}({\boldsymbol{\bf x}}^{\prime})),$ (11)

with $\\{\alpha_{k}\\}_{k=1}^{K}$ as positive coefficients.

For the generalization capability, the dimension of $\rho^{({\boldsymbol{\bf
q}}_{k})}({\boldsymbol{\bf x}})$ is smaller than the number of data. The inner
product kernel with RDM is a natural extension of the original quantum kernel
(7).

####  III.1.2 Distance kernel with RDM

######  Definition 2.

Let $\rho^{({\boldsymbol{\bf q}}_{k})}({\boldsymbol{\bf x}})$ be the $k$-th
data encoded density matrix. The distance kernel $Q$ is a function
$Q:\mathcal{M}\times\mathcal{M}\rightarrow\mathbf{R}$ written as

$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})=f\left(\sum_{k=1}^{K}\alpha_{k}d^{\rm
HS}(\rho^{({\boldsymbol{\bf q}}_{k})}({\boldsymbol{\bf
x}}),\rho^{({\boldsymbol{\bf q}}_{k})}({\boldsymbol{\bf
x}}^{\prime}))\right),$ (12)

where $f:{\bf R}\rightarrow{\bf R}$ is a function that satisfies $f(0)=1$, and
$d^{\rm HS}$ is the distance $(0\leq d^{\rm HS}\leq 1)$ defined by

$d^{\rm HS}(\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}),\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}^{\prime}))=\left\|\frac{\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}})-\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}^{\prime})}{2}\right\|_{HS},$ (13)

with $\|\cdot\|_{HS}$ the Hilbert Schmidt distance.

In [10], the Gaussian kernel, where $K=1$, $a_{1}=-\gamma$, and
$f(c)=\exp(-c)$, is proposed. The quantum kernel defined in (12) is a natural
extension of it.

###  III.2 QKGC with reduced observables (RO)

The above two definitions of quantum kernels are based on the similarity of
two data-embedded quantum states. Another way of building a quantum kernel
would be one using two data-embedded observables:

$\begin{split}&Q^{\rm obs}({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})\\\ &\equiv\left|\langle\psi|A({\boldsymbol{\bf
x}})A({\boldsymbol{\bf{\boldsymbol{\bf
x}}^{\prime}}})|\psi\rangle\right|^{2}\\\ &={\rm
Tr}\left[\left(A({\boldsymbol{\bf x}})\rho A({\boldsymbol{\bf
x}})\right)\left(A({\boldsymbol{\bf x}}^{\prime})\rho A({\boldsymbol{\bf
x}}^{\prime})\right)\right],\end{split}$ (14)

where $\rho=|\psi\rangle\langle\psi|$ is a quantum state. Here we define
$A({\boldsymbol{\bf x}})$ by

$A({\boldsymbol{\bf x}})=\sum_{j}\gamma_{j}U({\boldsymbol{\bf
x}})P_{j}U({\boldsymbol{\bf x}})^{\dagger},$ (15)

where $\\{P_{j}\\}$ are non-identity generalized Pauli observables and
$\\{\gamma_{j}\\}$ are real coefficients. As in the case of the original
quantum kernel [6], if the dimension of Hilbert space where
$A({\boldsymbol{\bf x}})$ is located is exponentially large, all the off-
diagonal terms of the Gram matrix generated from the kernel $Q^{\rm
obs}({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})$ takes an
exponentially small value, and hence QKM with the kernel $Q^{\rm
obs}({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})$ does not have the
generalization capability.

We can restore the generalization capability by defining the quantum kernel
using the reduced observable (RO) as follows;

$Q^{\rm RO}({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})\equiv\sum_{k=1}^{K}\alpha_{k}{\rm
Tr}\left(\tilde{A}_{\rho}^{{\boldsymbol{\bf q}}_{k}}({\boldsymbol{\bf
x}})\tilde{A}_{\rho}^{{\boldsymbol{\bf q}}_{k}}({\boldsymbol{\bf
x}}^{\prime})\right),$ (16)

where RO is defined as

$\displaystyle\tilde{A}_{\rho}^{{\boldsymbol{\bf q}}}({\boldsymbol{\bf x}})$
$\displaystyle={\rm Tr}_{\neq{\boldsymbol{\bf q}}}\left(A({\boldsymbol{\bf
x}})\rho A({\boldsymbol{\bf x}})\right).$ (17)

Note that this can be represented as

$\begin{split}&\tilde{A}_{\rho}^{{\boldsymbol{\bf q}}}({\boldsymbol{\bf
x}})\\\ &=\sum_{j,\ell}\gamma_{j}\gamma_{\ell}{\rm Tr}_{\neq{\boldsymbol{\bf
q}}}\left(U({\boldsymbol{\bf x}})P_{j}U({\boldsymbol{\bf x}})^{\dagger}\rho
U({\boldsymbol{\bf x}})P_{\ell}U({\boldsymbol{\bf
x}})^{\dagger})\right).\end{split}$ (18)

As in the case of QKGC with RDM, we assume that the dimension of Hilbert space
after tracing out is smaller than the number of data.

The above-defined QKGC with RO (16) seems to be an alternative to QKGC with
RDM. However, QKGC with RO is equivalent to QKGC with RDM other than
exponentially suppressed terms. Actually, in Appendix C, we show that the
terms with $j\neq\ell$ in (18) are exponentially suppressed for almost all of
$U({\boldsymbol{\bf x}})$. Therefore, the following quantum kernel

$\tilde{Q}^{\rm RO}({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})\equiv\sum_{k=1}^{K}\alpha_{k}{\rm
Tr}\left({A}_{\rho}^{{\boldsymbol{\bf q}}_{k}}({\boldsymbol{\bf
x}}){A}_{\rho}^{{\boldsymbol{\bf q}}_{k}}({\boldsymbol{\bf
x}}^{\prime})\right),$ (19)

where

$A^{{\boldsymbol{\bf q}}}_{\rho}({\boldsymbol{\bf
x}})=\sum_{j}\gamma_{j}^{2}{\rm Tr}_{\neq{\boldsymbol{\bf
q}}}\left(U({\boldsymbol{\bf x}})P_{j}U({\boldsymbol{\bf x}})^{\dagger}\rho
U({\boldsymbol{\bf x}})P_{j}U({\boldsymbol{\bf x}})^{\dagger}\right),$ (20)

is equal to (16) other than the exponentially suppressed terms for almost all
of $U({\boldsymbol{\bf x}})$. Since $P_{j}$ is a unitary operator,

$\rho_{j}({\boldsymbol{\bf x}})=U({\boldsymbol{\bf x}})P_{j}U({\boldsymbol{\bf
x}})^{\dagger}\rho U({\boldsymbol{\bf x}})P_{j}U({\boldsymbol{\bf
x}})^{\dagger}$ (21)

is a density operator and ${\rm Tr}_{\neq{\boldsymbol{\bf
q}}}(\rho_{j}({\boldsymbol{\bf x}}))$ is a RDM. Thus, (19) can be written in
the form of the inner product kernel with RDM discussed in Section III.1.

###  III.3 Other candidates for QKGC

Recall that the root cause of the low generalization capability is that the
kernel $Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})$ becomes almost
zero if ${\boldsymbol{\bf x}}$ and ${\boldsymbol{\bf x}}^{\prime}$ are
different, and the Gram matrix ${\boldsymbol{\bf Q}}$ is almost diagonal.
Thus, all we need to restore the generalization capability is to modify
$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})$ so that it can take a
large value even if ${\boldsymbol{\bf x}}$ and ${\boldsymbol{\bf x}}^{\prime}$
are different. Actually, the quantum kernels with RDM discussed in Section
III.1 satisfy this condition.

Therefore it is interesting to ask if we could construct a good quantum kernel
without using RDM or RO. In Appendix D, we examine two types of QKGC without
using RDM; the quantum kernel with tiny coefficients and the quantum kernel
with a few Fourier components. The result is that, even though both of these
quantum kernels may have generalization capability, they have no quantum
advantages.

Let us summarize Section III. QKGC with RDM successfully restores the
generalization capability. QKGC with RO we proposed, is another possible QKGC,
but it is almost equivalent to QKGC with RDM. Moreover, we examined some other
types of QKGC, but they lack quantum advantage. Based on this fact, in the
rest of this paper, we will focus on QKGC with RDM as the quantum kernel that
enjoys both the generalization capability and, further, may have the quantum
advantage.

##  IV Feature representation of QKGC

The goal of this section is to show that QKGC with RDM has scalability
properties, in addition to the generalization capability. More concretely, we
show that for any QKGC with RDM, $Q({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})$, there always exists a feature vector ${\boldsymbol{\bf
z}}({\boldsymbol{\bf x}})$ that satisfies

$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})\simeq{\boldsymbol{\bf
z}}({\boldsymbol{\bf x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}}^{\prime}),$ (22)

where $T$ denotes the transpose of the vector.

It is well known that the scalability issue is much-alleviated by using the
feature representation ${\boldsymbol{\bf z}}({\boldsymbol{\bf x}})$ instead of
the quantum kernel, as long as we take the dimension of the vector
${\boldsymbol{\bf z}}({\boldsymbol{\bf x}})$ smaller than the number of data
$M$. For example, in the kernel Ridge regression problem, if the kernel can be
approximated as the inner product of feature vectors, then the problem boils
down to that of a simple linear regression problem, and as a result, the
computational complexity improves from $O(M^{3})$ to $O(MD^{2})$ and the
spatial complexity improves from $O(M^{2})$ to $O(MD)$.

In Section IV.1, we identify the feature vector for the inner product kernel
with RDM. Then the feature representation of the distance kernel with RDM is
given in Section IV.2. In Section IV.3, we summarize those features and
discuss their advantages.

###  IV.1 Feature representation of the inner product kernel with RDM

Here, we show that the summand of the right-hand side of the inner product
kernel (11) can be represented as

${\rm Tr}(\rho^{({\boldsymbol{\bf q}}_{k})}({\boldsymbol{\bf
x}})\rho^{({\boldsymbol{\bf q}}_{k})}({\boldsymbol{\bf
x}}^{\prime}))={\boldsymbol{\bf z}}(k,{\boldsymbol{\bf
x}})^{T}{\boldsymbol{\bf z}}(k,{\boldsymbol{\bf x}}),$ (23)

with a feature vector ${\boldsymbol{\bf z}}(k,{\boldsymbol{\bf x}})$. Then, it
directly holds that

$\displaystyle Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})$
$\displaystyle=\sum_{k=1}^{K}\alpha_{k}{\rm Tr}(\rho^{({\boldsymbol{\bf
q}}_{k})}({\boldsymbol{\bf x}})\rho^{({\boldsymbol{\bf
q}}_{k})}({\boldsymbol{\bf x}}^{\prime}))$ (24)
$\displaystyle={\boldsymbol{\bf z}}({\boldsymbol{\bf x}})^{T}{\boldsymbol{\bf
z}}({\boldsymbol{\bf x}}^{\prime}),$ (25)

with

${\boldsymbol{\bf z}}({\boldsymbol{\bf
x}})=\left(\begin{array}[]{c}\sqrt{\alpha_{1}}{\boldsymbol{\bf
z}}(1,{\boldsymbol{\bf x}})\\\ \sqrt{\alpha_{2}}{\boldsymbol{\bf
z}}(2,{\boldsymbol{\bf x}})\\\ \vdots\\\ \sqrt{\alpha_{k}}{\boldsymbol{\bf
z}}(K,{\boldsymbol{\bf x}})\end{array}\right).$ (26)

If $K$ is large, instead of concatenating all
$\\{\sqrt{\alpha_{k}}{\boldsymbol{\bf z}}(k,{\boldsymbol{\bf
x}})\\}_{k=1}^{K}$, we may sample the set of indices
$\\{k_{1},k_{2},\cdots,k_{m}\\}$ $(m\ll K)$ according to the probability
distribution $p(k)=\sqrt{\alpha_{k}}/\sum_{k=1}^{K}\sqrt{\alpha_{k}}$ and
build ${\boldsymbol{\bf z}}({\boldsymbol{\bf x}})$ as

${\boldsymbol{\bf z}}({\boldsymbol{\bf
x}})=\left(\begin{array}[]{c}{\boldsymbol{\bf z}}(k_{1},{\boldsymbol{\bf
x}})\\\ {\boldsymbol{\bf z}}(k_{2},{\boldsymbol{\bf x}})\\\ \vdots\\\
{\boldsymbol{\bf z}}(k_{m},{\boldsymbol{\bf x}})\end{array}\right).$ (27)

For simplifying the notation, in what follows, we consider the quantum kernel
of the form $Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})={\rm
Tr}(\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf x}})\rho^{({\boldsymbol{\bf
q}})}({\boldsymbol{\bf x}}^{\prime}))$ and will show that $Q({\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime})$ can be represented by an inner product of
two feature vectors. The following theorem is the key to constructing the
feature vector.

######  Theorem 1.

Let $n_{{\boldsymbol{\bf q}}}$ be the number of qubits in
$\rho_{{\boldsymbol{\bf q}}}({\boldsymbol{\bf x}})$ and $N_{{\boldsymbol{\bf
q}}}=2^{n_{\boldsymbol{\bf q}}}$. Then the following equality holds:

$\begin{split}&{\rm Tr}(\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}})\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf x}}^{\prime}))\\\
&=\frac{1}{N_{{\boldsymbol{\bf q}}}}\sum_{j=1}^{N_{{\boldsymbol{\bf
q}}}^{2}}{\rm Tr}\left((P_{j}^{({\boldsymbol{\bf q}})}\otimes
I^{(\neq{\boldsymbol{\bf q}})})\Phi\left(\rho({\bf x})\right)\right)\\\
&~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{\rm
Tr}\left((P_{j}^{({\boldsymbol{\bf q}})}\otimes I^{(\neq{\boldsymbol{\bf
q}})})\Phi\left(\rho({\bf x}^{\prime})\right)\right),\end{split}$ (28)

where $P_{j}^{({\boldsymbol{\bf q}})}\in\\{I,X,Y,Z\\}^{\otimes
n_{{\boldsymbol{\bf q}}}}$ are operators acting on the qubits specified by
${\boldsymbol{\bf q}}$ and $I^{(\neq{\boldsymbol{\bf q}})}$ is the identity
operator acting on all the other qubits.

The proof is given in Appendix E. From Theorem 1, we can represent the kernel
$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})={\rm
Tr}(\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf x}})\rho^{({\boldsymbol{\bf
q}})}({\boldsymbol{\bf x}}^{\prime}))$ using two vectors as

$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})={\boldsymbol{\bf
z}}({\boldsymbol{\bf x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}}^{\prime}),$ (29)

where ${\boldsymbol{\bf z}}({\boldsymbol{\bf x}})=\\{z_{j}({\boldsymbol{\bf
x}})\\}_{j=1}^{N_{{\boldsymbol{\bf q}}}^{2}}$ with

$z_{j}({\boldsymbol{\bf x}})=\frac{{\rm Tr}\left((P_{j}^{({\boldsymbol{\bf
q}})}\otimes I^{(\neq{\boldsymbol{\bf q}})})\Phi\left(\rho({\bf
x}^{\prime})\right)\right)}{\sqrt{N_{{\boldsymbol{\bf q}}}}}.$ (30)

Note that the vector ${\boldsymbol{\bf z}}({\boldsymbol{\bf x}})$ can be
efficiently computed using a quantum device. We call ${\boldsymbol{\bf
z}}({\boldsymbol{\bf x}})$ the deterministic quantum feature (DQF).

We can also estimate the effect of the shot noise. Let $N_{\rm shot}$ be the
number of measurements to estimate ${\rm Tr}((P_{j}^{({\boldsymbol{\bf
q}})}\otimes I^{(\neq{\boldsymbol{\bf q}})})\Phi(\rho({\boldsymbol{\bf x}})))$
for each $j$. Then, the probability that the kernel (29) is distorted with
magnitude $\epsilon>0$ by shot noise is bounded as

${\rm Prob}\left[{\rm sup}_{{\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime}\in\mathcal{X}_{\rm data}}\left|{\boldsymbol{\bf
z}}({\boldsymbol{\bf x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}}^{\prime})-Q({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})\right|\geq\epsilon\right]\leq\delta,$

if the number of measurements $N_{\rm shot}$ is bounded as

$N_{\rm shot}\geq\frac{18N_{{\boldsymbol{\bf
q}}}^{2}}{\epsilon^{2}}\log\left(\frac{2M}{\delta}\right).$

The proof of this fact is given in Appendix E.2.

###  IV.2 Feature representation of the distance kernel with RDM

As in the case of the inner product kernel, we focus on the simplified version
of the kernel (12) and show that

$f\left(d^{\rm HS}(\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}),\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}^{\prime}))\right)\simeq{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf x}}),$ (31)

with a feature vector ${\boldsymbol{\bf z}}({\boldsymbol{\bf x}})$. Recall
that $d^{\rm HS}$ is defined using the Hilbert Schmidt distance in Eq. (13).
The following theorem is the key to constructing the features.

######  Theorem 2.

It holds

$\begin{split}&f\left(d^{\rm HS}(\rho^{({\boldsymbol{\bf
q}})}({\boldsymbol{\bf x}}),\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}^{\prime}))\right)\\\ &={\bf E}_{{\boldsymbol{\bf\omega}}\sim
P({\boldsymbol{\bf\omega}})}\left[\cos\left({\rm
Tr}({\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf c}}({\boldsymbol{\bf
x}}))\right)\cos\left({\rm Tr}({\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf
c}}({\boldsymbol{\bf x}}^{\prime}))\right)\right.\\\
&~{}~{}\left.\sin\left({\rm Tr}({\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf
c}}({\boldsymbol{\bf x}}))\right)\sin\left({\rm
Tr}({\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf c}}({\boldsymbol{\bf
x}}^{\prime}))\right)\right],\end{split}$ (32)

where $P({\boldsymbol{\bf\omega}})$ is a probability distribution dependent on
$f$, ${\boldsymbol{\bf\omega}}\sim P({\boldsymbol{\bf\omega}})$ states that
${\boldsymbol{\bf\omega}}\in{\bf R}^{N_{{\boldsymbol{\bf q}}}^{2}}$ is sampled
from $P({\boldsymbol{\bf\omega}})$, and ${\boldsymbol{\bf c}}({\boldsymbol{\bf
x}})\in{\bf R}^{N_{{\boldsymbol{\bf q}}}^{2}}$ is a vector with $j$-th element
defined by $c({\boldsymbol{\bf x}})_{j}={\rm
Tr}\left((P_{j}^{({\boldsymbol{\bf q}})}\otimes I^{(\neq{\boldsymbol{\bf
q}})})\Phi\left(\rho({\bf x})\right)\right)/N_{{\boldsymbol{\bf q}}}$.

We give the proof in Appendix F. As the corollary of Theorem 2, we can
construct a feature vector corresponding to the distance kernel. Let
$z_{{\boldsymbol{\bf\omega}}}^{s}({\boldsymbol{\bf x}})=\sin({\rm
Tr}({\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf c}}({\boldsymbol{\bf x}})))$
and $z_{{\boldsymbol{\bf\omega}}}^{c}({\boldsymbol{\bf x}})=\cos({\rm
Tr}({\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf c}}({\boldsymbol{\bf x}})))$.
Sampling ${\boldsymbol{\bf\omega}}$ from $P({\boldsymbol{\bf\omega}})$, we can
generate an array of ${\boldsymbol{\bf\omega}}$ as
$\\{{\boldsymbol{\bf\omega}}^{(1)},{\boldsymbol{\bf\omega}}^{(2)},\cdots,{\boldsymbol{\bf\omega}}^{(D/2)}\\}$.
Then, defining a feature vector ${\boldsymbol{\bf z}}({\boldsymbol{\bf x}})$
by

${\boldsymbol{\bf z}}({\boldsymbol{\bf
x}})=\left(\begin{array}[]{c}{\boldsymbol{\bf z}}^{s}({\boldsymbol{\bf x}})\\\
{\boldsymbol{\bf z}}^{c}({\boldsymbol{\bf x}})\end{array}\right),$ (33)

where

$\displaystyle{\boldsymbol{\bf z}}^{s}({\boldsymbol{\bf x}})$
$\displaystyle=\sqrt{\frac{2}{D}}\left(\begin{array}[]{c}z_{{\boldsymbol{\bf\omega}}_{1}}^{s}({\boldsymbol{\bf
x}})\\\ z_{{\boldsymbol{\bf\omega}}_{2}}^{s}({\boldsymbol{\bf x}})\\\
\vdots\\\ z_{{\boldsymbol{\bf\omega}}_{D/2}}^{s}({\boldsymbol{\bf x}})\\\
\end{array}\right),$ (38) $\displaystyle{\boldsymbol{\bf
z}}^{c}({\boldsymbol{\bf x}})$
$\displaystyle=\sqrt{\frac{2}{D}}\left(\begin{array}[]{c}z_{{\boldsymbol{\bf\omega}}_{1}}^{c}({\boldsymbol{\bf
x}})\\\ z_{{\boldsymbol{\bf\omega}}_{2}}^{c}({\boldsymbol{\bf x}})\\\
\vdots\\\ z_{{\boldsymbol{\bf\omega}}_{D/2}}^{c}({\boldsymbol{\bf x}})\\\
\end{array}\right),$ (43)

we obtain $f\left(d^{\rm HS}(\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}),\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}^{\prime}))\right)\simeq{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf x}}^{\prime})$. We call this
${\boldsymbol{\bf z}}({\boldsymbol{\bf x}})$ as the random quantum feature
(RQF).

There are two sources of kernel approximation error: the error due to the shot
noise and the error from sampling due to the limited number of samples $D$.
Combining the effects of those errors, we obtain the following theorem.

######  Theorem 3.

Let $L_{f}$ be the Lipschitz constant of f with respect to the $L_{1}$ norm.
Given $Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})=f\left(d^{\rm
HS}(\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}),\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf x}}^{\prime}))\right)$,
the following bound holds for kernel approximation error:

$\begin{split}{\rm Prob}\left[{\rm sup}_{{\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime}\in\mathcal{X}_{\rm data}}\left|{\boldsymbol{\bf
z}}({\boldsymbol{\bf x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}}^{\prime})-Q({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})\right|\geq\epsilon\right]\leq\delta,\end{split}$ (44)

if

$N_{\rm shot}\geq\frac{8N_{{\boldsymbol{\bf
q}}}^{2}L_{f}^{2}}{\epsilon^{2}}\log\left(\frac{4M}{\delta}\right),$ (45)

and

$D\geq\frac{32(N_{{\boldsymbol{\bf
q}}}^{2}+2)}{\epsilon^{2}}\log\left(\frac{2112\sigma_{p}^{2}}{\epsilon^{2}\delta}\right),$
(46)

where $\sigma_{p}=\mathbf{E}_{{\boldsymbol{\bf\omega}}\sim
P({\boldsymbol{\bf\omega}})}\left[{\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf\omega}}\right]$.

We give the proof in Appendix F.2. Therefore, there are strict lower bounds on
the number of shots, $N_{\rm shot}$, and the dimension of the feature vector,
$D$, to guarantee a given approximation error.

###  IV.3 Summary and discussion on the use of DQF and RQF

In Sections IV.1 and IV.2, we obtained DQF and RQF for two types of QKGC. In
particular, the dimension of the feature vector, $D$, needs to be
$N_{{\boldsymbol{\bf q}}}^{2}$ in the case of DQF and $O(N_{{\boldsymbol{\bf
q}}}^{2}/\epsilon^{2})$ in the case of RQF, where $\epsilon$ is a given kernel
approximation error.

In Fig. 1, we plot the two-dimensional map with respect to the number of data
$M$ and the dimension of the reduced Hilbert space $N_{{\boldsymbol{\bf q}}}$,
and specify the region such that solving the linear regression problems with
DQF has an advantage over the quantum kernel method with the conventional
quantum kernel (7). For simplicity, we assume that the training cost for the
kernel method is $O(M^{3})$ and that for the corresponding linear model with
DQF is $O(MD^{2})$ with $D=N_{{\boldsymbol{\bf q}}}^{2}$ again, which are the
cases in the kernel ridge regression. However, a similar figure can be drawn
in the case of another kernel method, such as the support vector machine. In
the region where $N_{{\boldsymbol{\bf q}}}\gtrsim M$, the QKM with DQF does
not have the generalization capability because the discussion in Section II B
1 is applied to this case as well; the corresponding region is colored gray.
When $M$ is small enough ($M\leq M_{0}$ with $M_{0}$ as the maximum data size
where $O(M_{0}^{3})$ classical computation is executable), and
$N_{{\boldsymbol{\bf q}}}$ is between $\sqrt{M}$ and $M$, we should use the
quantum kernel method with the exact quantum kernel because $O(MD^{2})\gtrsim
O(M^{3})$ in the region; the region is colored with green. When
$N_{{\boldsymbol{\bf q}}}$ is small enough to satisfy $N_{{\boldsymbol{\bf
q}}}<\sqrt{M}$ and $O(MD^{2})$ classical computation is executable, i.e.
$O(MD^{2})<O(M_{0}^{3})$, we should use the linear model with DQF in the
quantum kernel method. The region is colored orange. Otherwise, we can use
neither the quantum kernel method nor the linear model with DQF, and we may
need to use a QNN; the region is colored yellow. A similar contour can be
drawn in the case of RQF.

Figure 1: Regions where DQF has an advantage over the conventional quantum
kernel. The horizontal axis denotes the number of data $M$, and the vertical
axis denotes the dimension of the Hilbert space.

Note that in the region where $N_{{\boldsymbol{\bf q}}}<\sqrt{M}$ and
$M<M_{0}$, both the quantum kernel method with the exact quantum kernel and
the linear model with DQF are usable. However, our view is that it is better
to use the linear model with DQF in this region because of the flexibility of
DQF. In particular, we can extend the QKM to the one including the training of
the quantum kernel when using DQF. More specifically, by embedding the
parameters ${\boldsymbol{\bf\theta}}$ in RDM, we obtain each element of DQF as

$z_{j}({\boldsymbol{\bf x}},{\boldsymbol{\bf\theta}})=\frac{{\rm
Tr}\left((P_{j}^{({\boldsymbol{\bf q}})}\otimes I^{(\neq{\boldsymbol{\bf
q}})})\Phi\left(\rho({\bf
x},{\boldsymbol{\bf\theta}})\right)\right)}{\sqrt{N_{{\boldsymbol{\bf q}}}}}.$
(47)

Then, given the linear model using the features as

$f({\boldsymbol{\bf x}},{\boldsymbol{\bf\theta}})={\boldsymbol{\bf
w}}^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf x}},{\boldsymbol{\bf\theta}})$
(48)

and the cost function as

$\mathcal{L}=\sum_{m=1}^{M}C(f({\boldsymbol{\bf
x}}_{m},{\boldsymbol{\bf\theta}}),y_{m}),$ (49)

we can minimize $\mathcal{L}$ not only for ${\boldsymbol{\bf w}}$ but for
${\boldsymbol{\bf\theta}}$. The same arguments hold for the case of RQF.
Actually, we can efficiently compute the gradient of the cost with respect to
${\boldsymbol{\bf\theta}}$ using the parameter-shift rule [24], and therefore,
we can update ${\boldsymbol{\bf\theta}}$ by the gradient descent. Note that
training the parameters ${\boldsymbol{\bf\theta}}$ corresponds to learning the
quantum kernel. As noted in Section II.3, QKM involving such kernel learning
process corresponds to the data reuploading model. Certainly, the optimization
of ${\boldsymbol{\bf\theta}}$ is a non-convex problem, and the difficulty of
training QNNs may appear in this problem as well. Nevertheless, in our view,
the quantum kernel method may still work with even roughly chosen
${\boldsymbol{\bf\theta}}$, as such a difficult optimization problem needs not
to be perfectly solved. We will study the learning problem of the quantum
kernel in a separate work.

##  V Numerical studies

In this section, we demonstrate the performance of DQF and RQF introduced in
the previous section. We perform the regression and the classification tasks
using the datasets: ‘wine quality’ and ‘magic04’ shown in TABLE 1. We encode
data so that the number of qubits in $\rho({\boldsymbol{\bf x}})$ is the same
as the dimension of the dataset; for example, in the case of the wine quality
dataset, we use 11-qubits. We set the CPTP map $\Phi$ as the identity map.
Each kernel is generated by reducing some qubits in $\rho({\boldsymbol{\bf
x}})$. The detail of the data encoding method to build $\rho({\boldsymbol{\bf
x}})$ is shown in Appendix G. Since the number of training data is large, it
is costly to run a kernel method without using DQF or RQF. For example, in the
case of the wine quality dataset, the number of training data is 4,000, and
therefore, to solve the kernel ridge regression, we need $4000^{3}\sim
10^{11}$ computation to diagonalize the Gram matrix. Thus, we need a kernel
approximation method to mitigate the computational complexity. As the
approximation method, we compare DQF/RQF with the Nystrom method [14]. We
review the Nystrom method in Appendix G.

For the regression task, we solve the linear regression with the
regularization parameter $\lambda=0.001$, where the cost function is set to be
the mean squared error. For the classification task, we solve the soft-margin
support vector machine with the regularization parameter $C=1$, where the cost
function is set to be the Hinge loss. To perform the support vector machine,
we use the package scikit-learn [25].

In addition to checking the performance in the machine learning tasks, we will
see how well a quantum kernel is approximated. As the metric to measure the
discrepancy between the exact quantum kernel $Q$ and the kernel $\tilde{Q}$
that is computed as the inner products of DQF or RQF, we use the following
distance

$d_{Q}(\tilde{Q},Q)\equiv\frac{1}{M^{2}}\sum_{j,k=1}^{M}\left|\tilde{Q}({\boldsymbol{\bf
x}}_{j},{\boldsymbol{\bf x}}_{k})-Q({\boldsymbol{\bf x}}_{j},{\boldsymbol{\bf
x}}_{k})\right|.$ (50)

Note that the source of the discrepancy between $\tilde{Q}$ and $Q$ is the
shot noise in DQF, while, in the case of RQF, the discrepancy arises from the
sampling of the features in addition to the shot noise. Note that, to exactly
compute $Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})$, we use the
state vector representation. Throughout our numerical experiment, we use
Qulacs [26] for simulating the quantum processes.

Table 1: Details of the dataset used in our numerical experiment. The wine quality dataset is available from https://archive.ics.uci.edu/ml/datasets/wine+quality and the magic04 dataset is available from https://networkrepository.com/magic04.php. Type |  Dataset |  Dimension |  #Training |  #Test
---|---|---|---|---
regression |  wine quality |  11 |  4,000 |  898
classification |  magic04 |  10 |  18,500 |  520
Table 2: MSE/Accuracy and the Kernel approximation error $d_{Q}$ in the regression problem with wine quality dataset in the inner product kernel. Dataset |  Algorithm |  #Features |  $d_{Q}$ |  MSE/Accuracy
---|---|---|---|---
wine quality |  DQF |  16 |  ${0.007\pm 0.000}$ |  ${0.536\pm 0.001}$
Nystrom |  16 |  $0.980\pm 0.547$ |  $1.393\pm 0.055$
Nystrom |  100 |  $0.484\pm 0.139$ |  $0.678\pm 0.008$
magic04 |  DQF |  64 |  ${0.013\pm 0.000}$ |  ${82.3\pm 0.0\%}$
Nystrom |  64 |  $11.190\pm 5.823$ |  $79.6\pm 0.0\%$
Nystrom |  100 |  $0.637\pm 0.084$ |  $79.8\pm 0.2\%$

### Experiment using DQF

In this experiment, we use the following inner product kernel,

$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})={\rm
Tr}(\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf x}})\rho^{({\boldsymbol{\bf
q}})}({\boldsymbol{\bf x}}^{\prime})),$ (51)

where ${\boldsymbol{\bf q}}$ is set to be ${\boldsymbol{\bf q}}=\\{9,10\\}$ in
the experiment with the wine quality dataset and ${\boldsymbol{\bf
q}}=\\{8,9,10\\}$ in the experiment with the magic04 experiment. The
corresponding feature vector for the quantum kernel (51) is DQF introduced in
Section IV.1. The number of measurements for building each element of the
feature vector is set to be $N_{\rm shot}=500$.

For comparison, we also perform an experiment with another kernel
approximation technique called the Nystrom method [14]. As shown in Appendix
G, the Nystrom method also builds features to approximate the kernel. Note
that Nystrom method requires the evaluation of the kernel $Q({\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime})$ for several data points. For the
evaluation, we use the classical shadow [27] as proposed in [10].

The resulting performance of the machine learning tasks is shown in TABLE 2.
We show the value of mean squared error (MSE) in the case of the regression,
and the classification accuracy in the case of the classification, computing
from the regression/classification results of the test data. In the same
table, we also show the kernel approximation quality $d_{Q}$. We perform three
trials of experiments and compute the mean and the standard deviation of the
mean. Note that the number of features in DQF is fixed to the dimension of the
Hilbert space where $\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf x}})$
exists, i.e., 16 in the experiment with the wine quality dataset and 64 in the
experiment with the magic04 dataset. In the case of Nystrom, however, we can
freely choose the number of features; we choose 16 or 100 in the case of the
wine quality dataset and 64 or 100 in the case of the magic04 dataset.

We see that DQF successfully approximates the quantum kernel in both tasks;
$d_{Q}$ is almost $0.01$ in both experiments. Such a good kernel approximation
quality results in the performance of the regression/classification tasks. DQF
outperforms the Nystrom method in MSE/Accuracy. Even if we change the number
of features, the performance of the Nystrom method is worse than that of DQF,
though the kernel approximation quality improves compared to the one with
fewer features. The above results show the validity of using DQF as an
alternative to the exact inner product kernel.

### Experiment using RQF

Table 3: MSE/Accuracy and the Kernel approximation error $d_{Q}$ in the regression problem with wine quality dataset in case of the inner product kernel. Dataset |  Algorithm |  #Features |  $d_{Q}$ |  MSE/Accuracy
---|---|---|---|---
wine quality |  RQF |  $100$ |  $0.021\pm 0.002$ |  $0.497\pm 0.002$
RQF |  200 |  $0.014\pm 0.002$ |  $0.511\pm 0.011$
Nystrom |  100 |  $0.007\pm 0.000$ |  $0.473\pm 0.006$
Nystrom |  200 |  $0.007\pm 0.000$ |  $0.502\pm 0.015$
magic04 |  RQF |  100 |  $0.020\pm 0.000$ |  $85.1\pm 0.0\%$
RQF |  200 |  $0.015\pm 0.000$ |  $85.5\pm 0.0\%$
Nystrom |  100 |  $0.007\pm 0.000$ |  $85.2\pm 0.0\%$
Nystrom |  200 |  $0.007\pm 0.000$ |  $85.5\pm 0.0\%$

In this experiment, we use the following distance kernel,

$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})=\sum_{{\boldsymbol{\bf
q}}\in\Lambda}\exp\left(-0.1||\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}})-\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}^{\prime})||_{HS}\right),$ (52)

where we set $\Lambda=\\{\\{j\\}\\}_{j=1}^{11}$ in the experiment with the
wine quality dataset and $\Lambda=\\{\\{2j-1,2j\\}\\}_{j=1}^{5}$ in the
experiment with the magic04 dataset. The corresponding feature vector for the
quantum kernel (52) is RQF introduced in Section IV.2. The number of
measurements for building each element of the feature vector is set to be
$N_{\rm shot}=500$.

Same as the experiment with DQF, we also perform an experiment with the
Nystrom method [14]. For the evaluation of $Q({\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime})$, which is required in the Nystrom method
as its subroutine, we estimate each element of $\rho^{({\boldsymbol{\bf
q}})}({\boldsymbol{\bf x}})$ with $N_{\rm shot}=500$ measurements and build
$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})$ according to (52).

The resulting performance of the machine learning tasks is shown in TABLE 3.
Same as the previous experiment, we perform three trials of experiments and
compute the mean and the standard deviation of the mean. Unlike the previous
experiment using DQF, we see that not only RQF but the Nystrom method
successfully approximates the quantum kernel, and RQF does not outperform the
Nystrom method.

Still, the results do not directly mean that we should use the Nystrom method
instead of RQF. As we discuss at the end of Section IV.3, we can flexibly tune
RQF. One of such tunings is embedding parameters in RDM and optimizing
parameters. Another possible tuning is changing the way of sampling elements
of RQF. In the context of the random Fourier feature, there are many proposals
to optimize the way of sampling elements [28, 29, 30, 31, 32, 33, 34, 35, 36,
37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55,
56]. Studying the effects of tuning RQF is a good direction for future work.

##  VI Discussion

The quantum kernel method is actively examined as an algorithm that may have a
quantum advantage, but the generalization capability issue and the scalability
issue severely limit its range of application. Previous literature [10, 12]
proposed the quantum kernel with generalization capability (QKGC) using the
reduced density matrix (RDM), but the ways of solving the scalability issue
remained to be solved.

In this paper, we first examined classes of QKGC other than the ones using
RDM. We examined a quantum kernel with reduced observable (RO), but our
theoretical analysis showed that the quantum kernel with RO is almost
equivalent to the quantum kernel with RDM. We also examined naively
constructible QKGCs, but they lack quantum advantage. From this observation,
we focused on solving the scalability issue of QKGC with RDM. We then showed
that the quantum kernel using QKGC with RDM is almost equivalent to the inner
product of two feature vectors, DQF and RQF; as a result, the machine learning
problem boils down to a linear problem that can be efficiently solved. We also
showed that in a wide range of problem settings, the linear model with those
features overcomes the scalability issue as in Fig. 1.

We consolidated the validity of using DQF by numerical experiments compared
with a kernel approximation technique called the Nystrom method. DQF
successfully outperforms the Nystrom method in regression and classification
tasks using a dataset with $O(1,000)\sim O(10,000)$. On the other hand, RQF
did not outperform the Nystrom method with the same dataset. Still, since
there is a large room for tuning RQF, we need further investigation regarding
how to utilize RQF.

In our work, we showed that currently conceivable QKGCs can be written using
feature vectors and are free from the scalability issue, which leads us to
have an opposite emphasis. Namely, we may say that, if we propose a new QKGC,
it is preferable to be written using a feature vector. This constraint will be
a good guideline for building a new QKGC.

We also believe that the feature representations can be utilized to recapture
the quantum kernel method beyond the tool for solving the scalability issue.
For example, as discussed at the end of Section IV.3, we can relate the data
reuploading model with the quantum kernel method by embedding the parameters
in DQF and RQF and optimizing them. As another example, we may derive the
condition for obtaining a quantum advantage as a constraint for the feature
vectors by reexamining the discussion in [10] in light of DQF and RQF. We
believe those understandings using the feature representations will pave the
way for realizing quantum machine learning algorithms with an advantage over
their classical counterpart.

###### Acknowledgements.

This work was supported by Grant-in-Aid for JSPS Research Fellow 22J01501 and
MEXT Quantum Leap Flagship Program Grants No. JPMXS0118067285 and No.
JPMXS0120319794.

## References

  * [1] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd.  Quantum machine learning.  Nature, 549(7671):195–202, 2017.
  * [2] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione.  An introduction to quantum machine learning.  Contemporary Physics, 56(2):172–185, 2015.
  * [3] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig.  Quantum machine learning: a classical perspective.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, 2018.
  * [4] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost.  Quantum algorithms for supervised and unsupervised machine learning.  arXiv preprint arXiv:1307.0411, 2013.
  * [5] Edward Farhi and Hartmut Neven.  Classification with quantum neural networks on near term processors.  arXiv preprint arXiv:1802.06002, 2018.
  * [6] 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.
  * [7] Maria Schuld and Nathan Killoran.  Quantum machine learning in feature hilbert spaces.  Physical review letters, 122(4):040504, 2019.
  * [8] Maria Schuld.  Supervised quantum machine learning models are kernel methods.  arXiv preprint arXiv:2101.11020, 2021.
  * [9] Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven.  Barren plateaus in quantum neural network training landscapes.  Nature communications, 9(1):1–6, 2018.
  * [10] 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 Communication, 12(1):2631, May 2021.
  * [11] Supanut Thanasilp, Samson Wang, M Cerezo, and Zoë Holmes.  Exponential concentration and untrainability in quantum kernel methods.  arXiv preprint arXiv:2208.11060, 2022.
  * [12] Jonas Kübler, Simon Buchholz, and Bernhard Schölkopf.  The inductive bias of quantum kernels.  Advances in Neural Information Processing Systems, 34:12661–12673, December 2021.
  * [13] Ali Rahimi and Benjamin Recht.  Random features for large-scale kernel machines.  Advances in Neural Information Processing Systems, 20, 2007.
  * [14] Christopher Williams and Matthias Seeger.  Using the nyström method to speed up kernel machines.  Advances in neural information processing systems, 13, 2000.
  * [15] Alex Smola and Bernhard Schölkopf.  Sparse greedy matrix approximation for machine learning.  In ICML, 2000.
  * [16] Cho-Jui Hsieh, Si Si, and Inderjit Dhillon.  A divide-and-conquer solver for kernel support vector machines.  In International conference on machine learning, pages 566–574. PMLR, 2014.
  * [17] Yuchen Zhang, John Duchi, and Martin Wainwright.  Divide and conquer kernel ridge regression.  In Conference on learning theory, pages 592–617. PMLR, 2013.
  * [18] Fanghui Liu, Xiaolin Huang, Chen Gong, Jie Yang, and Li Li.  Learning data-adaptive non-parametric kernels.  J. Mach. Learn. Res., 21(208):1–39, 2020.
  * [19] Francisco Javier Gil Vidal and Dirk Oliver Theis.  Input redundancy for parameterized quantum circuits.  Frontiers in Physics, 8:297, 2020.
  * [20] 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.
  * [21] 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.
  * [22] Kevin P Murphy.  Machine learning: a probabilistic perspective.  MIT press, 2012.
  * [23] Yusen Wu, Bujiao Wu, Jingbo Wang, and Xiao Yuan.  Provable advantage in quantum phase learning via quantum kernel alphatron.  arXiv preprint arXiv:2111.07553, 2021.
  * [24] Gavin E Crooks.  Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition.  arXiv preprint arXiv:1905.13311, 2019.
  * [25] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.
  * [26] Yasunari Suzuki, Yoshiaki Kawase, Yuya Masumura, Yuria Hiraga, Masahiro Nakadai, Jiabao Chen, Ken M Nakanishi, Kosuke Mitarai, Ryosuke Imai, Shiro Tamiya, et al.  Qulacs: a fast and versatile quantum circuit simulator for research purpose.  Quantum, 5:559, 2021.
  * [27] Hsin-Yuan Huang, Richard Kueng, and John Preskill.  Predicting many properties of a quantum system from very few measurements.  Nature Physics, 16(10):1050–1057, 2020.
  * [28] Ali Rahimi and Benjamin Recht.  Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning.  Advances in Neural Information Processing Systems, 21, 2008.
  * [29] Quoc Le, Tamás Sarlós, Alex Smola, and Others.  Fastfood-approximating kernel expansions in loglinear time.  In Proceedings of the international conference on machine learning, volume 85, page 8. proceedings.mlr.press, 2013.
  * [30] Andrew Wilson and Ryan Adams.  Gaussian process kernels for pattern discovery and extrapolation.  In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 1067–1075, Atlanta, Georgia, USA, 2013. PMLR.
  * [31] Bo Dai, Bo Xie, Niao He, Yingyu Liang, Anant Raj, Maria-Florina F Balcan, and Le Song.  Scalable kernel methods via doubly stochastic gradients.  Advances in Neural Information Processing Systems, 27, 2014.
  * [32] Jiyan Yang, Vikas Sindhwani, Haim Avron, and Michael Mahoney.  Quasi-Monte carlo feature maps for Shift-Invariant kernels.  In Eric P Xing and Tony Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 485–493, Bejing, China, 2014. PMLR.
  * [33] Chang Feng, Qinghua Hu, and Shizhong Liao.  Random feature mapping with signed circulant matrix projection.  In Twenty-Fourth International Joint Conference on Artificial Intelligence. aaai.org, June 2015.
  * [34] Zichao Yang, Andrew Wilson, Alex Smola, and Le Song.  A la carte–learning fast kernels.  In Artificial Intelligence and Statistics, pages 1098–1106. proceedings.mlr.press, 2015.
  * [35] Felix X Yu, Sanjiv Kumar, Henry Rowley, and Shih-Fu Chang.  Compact nonlinear maps and circulant extensions.  arXiv preprint arXiv:1503.03893, 2015.
  * [36] Krzysztof Choromanski and Vikas Sindhwani.  Recycling randomness with structure for sublinear time kernel expansions.  In Maria Florina Balcan and Kilian Q Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2502–2510, New York, New York, USA, 2016. PMLR.
  * [37] Aman Sinha and John C Duchi.  Learning kernels with random features.  Advances in Neural Information Processing Systems, 29, 2016.
  * [38] Junier B Oliva, Avinava Dubey, Andrew G Wilson, Barnabas Poczos, Jeff Schneider, and Eric P Xing.  Bayesian nonparametric Kernel-Learning.  In Arthur Gretton and Christian C Robert, editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 1078–1086, Cadiz, Spain, 2016. PMLR.
  * [39] Felix Xinnan X Yu, Ananda Theertha Suresh, Krzysztof M Choromanski, Daniel N Holtmann-Rice, and Sanjiv Kumar.  Orthogonal random features.  Advances in Neural Information Processing Systems, 29, 2016.
  * [40] Yueming Lyu.  Spherical structured feature maps for kernel approximation.  In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2256–2264. PMLR, 2017.
  * [41] Krzysztof M Choromanski, Mark Rowland, and Adrian Weller.  The unreasonable effectiveness of structured random orthogonal embeddings.  Advances in Neural Information Processing Systems, 30, 2017.
  * [42] Ping Li.  Linearized GMM kernels and normalized random fourier features.  In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’17, pages 315–324, New York, NY, USA, August 2017. Association for Computing Machinery.
  * [43] Weiwei Shen, Zhihui Yang, and Jun Wang.  Random features for Shift-Invariant kernels with moment matching.  AAAI, 31(1), February 2017.
  * [44] Tri Dao, Christopher De Sa, and Christopher Ré.  Gaussian quadrature for kernel features.  Advances in Neural Information Processing Systems, 30:6109–6119, December 2017.
  * [45] Wei-Cheng Chang, Chun-Liang Li, Yiming Yang, and Barnabás Póczos.  Data-driven random fourier features using stein effect.  arXiv preprint arXiv:1705.08525, 2017.
  * [46] Brian Bullins, Cyril Zhang, and Yi Zhang.  Not-so-random features.  arXiv preprint arXiv:1710.10230, 2017.
  * [47] Marina Munkhoeva, Yermek Kapushev, Evgeny Burnaev, and Ivan Oseledets.  Quadrature-based features for kernel approximation.  Advances in Neural Information Processing Systems, 31, 2018.
  * [48] Alessandro Rudi, Daniele Calandriello, Luigi Carratino, and Lorenzo Rosasco.  On fast leverage score sampling and optimal learning.  Advances in Neural Information Processing Systems, 31, 2018.
  * [49] Shahin Shahrampour, Ahmad Beirami, and Vahid Tarokh.  On Data-Dependent random features for improved generalization in supervised learning.  AAAI, 32(1), April 2018.
  * [50] Zhu Li, Jean-Francois Ton, Dino Oglic, and Dino Sejdinovic.  Towards a unified analysis of random fourier features.  In International conference on machine learning, pages 3905–3914, 2019.
  * [51] Raj Agrawal, Trevor Campbell, Jonathan Huggins, and Tamara Broderick.  Data-dependent compression of random features for large-scale kernel approximation.  In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 1822–1831. PMLR, 2019.
  * [52] Chun-Liang Li, Wei-Cheng Chang, Youssef Mroueh, Yiming Yang, and Barnabas Poczos.  Implicit kernel learning.  In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 2007–2016. PMLR, 2019.
  * [53] Zheyang Shen, Markus Heinonen, and Samuel Kaski.  Harmonizable mixture kernels with variational fourier features.  In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 3273–3282. PMLR, 2019.
  * [54] Jian Zhang, Avner May, Tri Dao, and Christopher Ré.  Low-Precision random fourier features for Memory-Constrained kernel approximation.  Proc Mach Learn Res, 89:1264–1274, April 2019.
  * [55] Fanghui Liu, Xiaolin Huang, Yudong Chen, Jie Yang, and Johan Suykens.  Random fourier features via fast surrogate leverage weighted sampling.  AAAI, 34(04):4844–4851, April 2020.
  * [56] Tamas Erdelyi, Cameron Musco, and Christopher Musco.  Fourier sparse leverage scores and approximate kernel learning.  Advances in Neural Information Processing Systems, 33:109–122, 2020\.
  * [57] Salomon Bochner.  Harmonic Analysis and the Theory of Probability.  University of California Press, September 2020.
  * [58] Danica J Sutherland and Jeff Schneider.  On the error of random fourier features.  arXiv preprint arXiv:1506.02785, 2015.
  * [59] Bharath Sriperumbudur and Zoltan Szabo.  Optimal rates for random fourier features.  Advances in Neural Information Processing Systems, 28, 2015.
  * [60] Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh.  Random fourier features for kernel ridge regression: Approximation bounds and statistical guarantees.  In International conference on machine learning, pages 253–262, 2017.
  * [61] Jean Honorio and Yu-Jun Li.  The error probability of random fourier features is dimensionality independent.  arXiv preprint arXiv:1710.09953, 2017.
  * [62] Krzysztof Choromanski, Mark Rowland, Tamas Sarlos, Vikas Sindhwani, Richard Turner, and Adrian Weller.  The geometry of random features.  In Amos Storkey and Fernando Perez-Cruz, editors, Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1–9. PMLR, 2018.
  * [63] Zbigniew Puchała and Jarosław Adam Miszczak.  Symbolic integration with respect to the haar measure on the unitary group.  arXiv preprint arXiv:1109.4244, 2011.
  * [64] Benoît Collins and Piotr Śniady.  Integration with respect to the haar measure on unitary, orthogonal and symplectic group.  Communications in Mathematical Physics, 264(3):773–795, 2006.
  * [65] Franz J Schreiber, Jens Eisert, and Johannes Jakob Meyer.  Classical surrogates for quantum learning models.  arXiv preprint arXiv:2206.11740, 2022.

##  Appendix A Review of the random Fourier feature

Machine learning with random Fourier features [13] is a widely used technique
to solve the scalability issue of the kernel method. Random Fourier features
technique is available when the kernel function $Q({\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime})$ with ${\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime}\in\mathcal{X}\subset\mathbf{R}^{d}$ is
written in the form of $Q({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})=Q({\boldsymbol{\bf x}}-{\boldsymbol{\bf x}}^{\prime})$. The
theoretical foundation of random Fourier features is given by Bochner’s
theorem [57], which states that a positive definite distance kernel on
$\mathbf{R}^{d}$ can be written in the form of the Fourier transform of a non-
negative measure. Particularly, if the kernel is properly scaled as
$Q({\boldsymbol{\bf 0}})=1$, the kernel is written as

$Q({\boldsymbol{\bf x}}-{\boldsymbol{\bf
x}}^{\prime})=\int_{\mathbf{R}^{d}}d{\boldsymbol{\bf\omega}}p({\boldsymbol{\bf\omega}})e^{i{\boldsymbol{\bf\omega}}^{T}({\boldsymbol{\bf
x}}-{\boldsymbol{\bf x}}^{\prime})},$ (53)

with $p({\boldsymbol{\bf\omega}})$ as a probability distribution on
$\mathbf{R}^{d}$ defined by the Fourier transform of
$Q({\boldsymbol{\bf\Delta}})$ as

$p({\boldsymbol{\bf\omega}})=\frac{1}{(2\pi)^{d}}\int_{\mathbf{R}^{d}}d{\boldsymbol{\bf\Delta}}Q({\boldsymbol{\bf\Delta}}).$
(54)

Note that the kernel is a real-valued function, and therefore, the imaginary
part of (53) disappears; namely, $Q({\boldsymbol{\bf x}}-{\boldsymbol{\bf
x}}^{\prime})=\int_{\mathbf{R}^{d}}p({\boldsymbol{\bf\omega}})\cos({\boldsymbol{\bf\omega}}^{T}({\boldsymbol{\bf
x}}-{\boldsymbol{\bf x}}^{\prime}))$. Thus by properly choosing a probability
distribution $p({\boldsymbol{\bf\omega}})$,

$\begin{split}Q({\boldsymbol{\bf x}}-{\boldsymbol{\bf
x}}^{\prime})&=\int_{\mathbf{R}^{d}}d{\boldsymbol{\bf\omega}}p({\boldsymbol{\bf\omega}})\cos({\boldsymbol{\bf\omega}}^{T}({\boldsymbol{\bf
x}}-{\boldsymbol{\bf x}}^{\prime}))\\\
&=\int_{\mathbf{R}^{d}}d{\boldsymbol{\bf\omega}}p({\boldsymbol{\bf\omega}})\left(\cos({\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf
x}})\cos({\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf
x}}^{\prime})+\sin({\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf
x}})\sin({\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf
x}}^{\prime})\right)\end{split}$ (55)

holds. Sampling
$\\{{\boldsymbol{\bf\omega}}_{1},{\boldsymbol{\bf\omega}}_{2},\cdots,{\boldsymbol{\bf\omega}}_{D/2}\\}$
from $p({\boldsymbol{\bf\omega}})$, we can build the random Fourier features
as follows:

${\boldsymbol{\bf z}}({\boldsymbol{\bf
x}})=\sqrt{\frac{2}{D}}\left(\begin{array}[]{c}{\boldsymbol{\bf
z}}_{{\boldsymbol{\bf\omega}}}^{c}({\boldsymbol{\bf x}})\\\ {\boldsymbol{\bf
z}}_{{\boldsymbol{\bf\omega}}}^{s}({\boldsymbol{\bf
x}})\end{array}\right),~{}{\rm where}~{}{\boldsymbol{\bf
z}}_{{\boldsymbol{\bf\omega}}}^{c}({\boldsymbol{\bf
x}})=\left(\begin{array}[]{c}\cos({\boldsymbol{\bf\omega}}_{1}^{T}{\boldsymbol{\bf
x}})\\\ \cos({\boldsymbol{\bf\omega}}_{2}^{T}{\boldsymbol{\bf x}})\\\
\vdots\\\ \cos({\boldsymbol{\bf\omega}}_{D/2}^{T}{\boldsymbol{\bf
x}})\end{array}\right),~{}{\rm and}~{}{\boldsymbol{\bf
z}}_{{\boldsymbol{\bf\omega}}}^{s}({\boldsymbol{\bf
x}})=\left(\begin{array}[]{c}\sin({\boldsymbol{\bf\omega}}_{1}^{T}{\boldsymbol{\bf
x}})\\\ \sin({\boldsymbol{\bf\omega}}_{2}^{T}{\boldsymbol{\bf x}})\\\
\vdots\\\ \sin({\boldsymbol{\bf\omega}}_{D/2}^{T}{\boldsymbol{\bf
x}})\end{array}\right).$ (56)

Then,

$Q({\boldsymbol{\bf x}}-{\boldsymbol{\bf x}}^{\prime})\simeq{\boldsymbol{\bf
z}}({\boldsymbol{\bf x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}}^{\prime}).$ (57)

In [58], it is shown that the probability of the error of the kernel
approximation is bounded as

$\begin{split}{\rm Prob}\left[{\rm sup}_{{\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime}\in\mathcal{X}}|{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf x}}^{\prime})-Q({\boldsymbol{\bf
x}}-{\boldsymbol{\bf x}}^{\prime})|>\epsilon\right]\leq
66\left(\frac{\sigma_{p}{\rm
diam}(\mathcal{X})}{\epsilon}\right)^{2}\exp\left(-\frac{D\epsilon^{2}}{8(d+2)}\right),\end{split}$
(58)

where $\sigma_{p}^{2}=\mathbf{E}_{{\boldsymbol{\bf\omega}}\sim
p({\boldsymbol{\bf\omega}})}\left[{\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf\omega}}\right]$
and ${\rm diam}(\mathcal{X})$ is the diameter of the space $\mathcal{X}$.
Namely, the error scales as $\epsilon\sim d/\sqrt{D}$. See also literature
[59, 60, 61, 62, 54] for the updated bounds.

##  Appendix B A merit of the data reuploading model

In this Section, we show the merit of using the data reuploading model
according to the literature [21]. For simplicity, let us consider the case
where the dimension of the data is one and

$\ket{\psi({\boldsymbol{\bf\theta}},x)}=U({\boldsymbol{\bf\theta}})\exp(iVx),$
(59)

with $V$ as a Hermitian operator with two eigenvalues $\pm\lambda$. Then the
model function constructed by
$f_{{\boldsymbol{\bf\theta}}}(x)=\bra{\psi({\boldsymbol{\bf\theta}},x)}O\ket{\psi({\boldsymbol{\bf\theta}},x)}$
with (59), is limited to the form of

$f_{{\boldsymbol{\bf\theta}}}(x)=c_{0}({\boldsymbol{\bf\theta}})+c_{1}({\boldsymbol{\bf\theta}})e^{i\lambda
x}+{\rm c.c.},$ (60)

where $c_{0}({\boldsymbol{\bf\theta}})$ and $c_{1}({\boldsymbol{\bf\theta}})$
are the function only dependent on ${\boldsymbol{\bf\theta}}$ [21].

To the contrary, if we use the data reuploading model function constructed by
setting $U_{\ell}({\boldsymbol{\bf x}})=\exp(iVx)\ (\forall\ell)$ in (9), we
obtain

$f_{{\boldsymbol{\bf\theta}}}(x)=\sum_{\omega\in\Omega}c_{\omega}e^{i\omega
x},$ (61)

where the set $\Omega$ is defined by

$\Omega=\\{\omega|(p-q)\lambda~{}{\rm with}~{}p,q\in{\bf N}~{}{\rm
and}~{}1\leq p,q\leq L\\}.$ (62)

Namely, the expressibility of the QNN model is limited because the number of
Fourier components is small; the data reuploading model gives the solution to
the problem [21].

##  Appendix C Analysis regarding QKGC with RO

Let us define

$O_{j\ell}^{ab}(U({\boldsymbol{\bf x}}))\equiv\bra{a}{\rm
Tr}_{\neq{\boldsymbol{\bf q}}}\left(U({\boldsymbol{\bf
x}})P_{j}U({\boldsymbol{\bf x}})^{\dagger}\rho U({\boldsymbol{\bf
x}})P_{\ell}U({\boldsymbol{\bf x}})^{\dagger}\right)\ket{b}.$ (63)

We show that $O_{j\ell}^{ab}(U({\boldsymbol{\bf x}}))$ vanishes if $j\neq\ell$
for almost all of $U({\boldsymbol{\bf x}})$. For the purpose, we investigate
the behavior of $O_{j\ell}^{ab}(U({\boldsymbol{\bf x}}))$ when
$U({\boldsymbol{\bf x}})$ is distributed according to the Haar measure. More
specifically, we compute the first two moments of $O_{j\ell}^{ab}(U)$:

$\displaystyle\langle O_{j\ell}^{ab}\rangle_{\rm Haar}$
$\displaystyle\equiv\int_{\rm Haar}dUO_{j\ell}^{ab}(U),$ (64)
$\displaystyle\langle O_{j\ell}^{ab}O_{j\ell}^{ab\ast}\rangle_{\rm Haar}$
$\displaystyle\equiv\int_{\rm Haar}dUO_{j\ell}^{ab}(U)O_{j\ell}(U)^{ab\ast}.$
(65)

For the first moment (64), we can use the element-wise integration formula
[63]

$\int_{\rm
Haar}U_{ab}U^{\ast}_{cd}U_{ef}U^{\ast}_{gh}=\frac{1}{2^{2n}-1}\left(\delta_{ac}\delta_{bd}\delta_{eg}\delta_{fh}+\delta_{ag}\delta_{bh}\delta_{ce}\delta_{df}\right)-\frac{1}{2^{n}(2^{2n}-1)}(\delta_{ac}\delta_{bh}\delta_{eg}\delta_{fd}+\delta_{ah}\delta_{bd}\delta_{ec}\delta_{fg}),$
(66)

where $n$ is the number of qubits in $U$. A direct calculation shows

$\langle O_{j\ell}^{ab}\rangle_{\rm
Haar}=\frac{2^{2n-m}}{2^{2n}-1}\delta_{j\ell}\delta_{ab}+O\left(\frac{1}{2^{n}}\right),$
(67)

where $m$ is the number of qubits in ${\boldsymbol{\bf q}}$.

For the second moment (65), we use the Weingarten calculus [64],

$U_{i_{1}j_{1}}U_{i_{2}j_{2}}U_{i_{3}j_{3}}U_{i_{4}j_{4}}U_{i_{1}^{\prime}j_{1}^{\prime}}^{\ast}U_{i_{2}^{\prime}j_{2}^{\prime}}^{\ast}U_{i_{3}^{\prime}j_{3}^{\prime}}^{\ast}U_{i_{4}^{\prime}j_{4}^{\prime}}^{\ast}=\sum_{\sigma,\tau\in
S_{4}}\delta_{i_{1}i_{\sigma(1)}^{\prime}}\delta_{i_{2}i_{\sigma(2)}^{\prime}}\delta_{i_{3}i_{\sigma(3)}^{\prime}}\delta_{i_{4}i_{\sigma(4)}^{\prime}}\delta_{j_{1}j_{\tau(1)}^{\prime}}\delta_{j_{2}j_{\tau(2)}^{\prime}}\delta_{j_{3}j_{\tau(3)}^{\prime}}\delta_{j_{4}j_{\tau(4)}^{\prime}}{\rm
Wg}(\sigma\tau^{-1}),$ (68)

where $S_{4}$ is the set of the symmetric group with degree four and ${\rm
Wg}(\cdot)$ is the Weingarten function [64] that takes an element of the
symmetric group as its input. A direct but complicated calculation shows

$\langle O_{j\ell}^{ab}O_{j\ell}^{ab\ast}\rangle_{\rm Haar}=2^{4n-2m}{\rm
Wg}([1,1,1,1])\delta_{j\ell}\delta_{ab}+O\left(\frac{1}{2^{n}}\right),$ (69)

where

${\rm Wg}([1,1,1,1])=\frac{2^{4n}-2^{2n}+6}{2^{8n}-14\times 2^{6n}+49\times
2^{4n}-36\times 2^{2n}}$ (70)

in our notation.

The above computation of the first moment (67) and the second moment (69)
shows that if $j\neq\ell$, the first and the second moment of
$O_{j\ell}^{ab}(U)$ is exponentially suppressed by the factor $O(1/2^{n})$,
meaning that for almost all $U$, $O_{j\ell}^{ab}=O(1/2^{n})$. Note that as far
as $m$ is taken to be small, the first and the second moment of
$O_{j\ell}^{ab}(U)$ with $j=\ell$ is not exponentially suppressed, which is
the effect of reducing the dimension of the observable.

##  Appendix D Other possible QKGC

One naive approach to realizing QKGC without using RDM is embedding each data
with a tiny coefficient. More concretely, given the dimension of data as $d$,
and $x_{k}$ as a $k$-th component of ${\boldsymbol{\bf x}}$, let us define

$\ket{\psi({\boldsymbol{\bf x}})}=\prod_{k=1}^{d}V_{k}\exp\left(i\epsilon
A_{k}x_{k}\right)\ket{0}^{\otimes n},$ (71)

where $\\{V_{k}\\}_{k=1}^{d}$ are unitary operators, $\\{A_{k}\\}_{k=1}^{D}$
are Hermitian operators, and $\epsilon$ is a tiny coefficient. If we define
$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})=|\langle\psi({\boldsymbol{\bf x}})|\psi({\boldsymbol{\bf
x}}^{\prime})\rangle|^{2}$, we can readily show that

$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})=1-\epsilon\sum_{k=1}^{d}\beta_{k}(x_{k}+x_{k}^{\prime})+O(\epsilon^{2}).$
(72)

with $\\{\beta_{k}\\}_{k=1}^{d}$ as real $O(1)$ coefficients. As long as
$\epsilon$ is tiny, the quantum kernel defined by (72) has a value large value
even if ${\boldsymbol{\bf x}}$ and ${\boldsymbol{\bf x}}^{\prime}$ are
different, and therefore, the QKM with (72) may have the generalization
capability.

Another approach to realizing QKGC is embedding each data so that the number
of Fourier components of the quantum kernel is small. In general,
$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})$ can be written as

$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})=\sum_{{\boldsymbol{\bf\lambda}},{\boldsymbol{\bf\lambda}}^{\prime}\in\Lambda}c_{{\boldsymbol{\bf\lambda}},{\boldsymbol{\bf\lambda}}^{\prime}}e^{i{\boldsymbol{\bf\lambda}}^{T}{\boldsymbol{\bf
x}}+i{\boldsymbol{\bf\lambda}}^{\prime T}{\boldsymbol{\bf x}}}+const,$ (73)

where
$c_{{\boldsymbol{\bf\lambda}},{\boldsymbol{\bf\lambda}}^{\prime}}=c_{{\boldsymbol{\bf\lambda}},{\boldsymbol{\bf\lambda}}^{\prime}}^{\ast}$
$\Lambda$ as a set of vectors with the dimension of the data and
$c_{{\boldsymbol{\bf\lambda}},{\boldsymbol{\bf\lambda}}^{\prime}}$ are complex
coefficients. If the dimension of data and the number of vectors in $\Lambda$
are small, $Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})$ tends to be
large and may have the generalization capability even if the dimension of the
Hilbert space is exponentially large. For example, if the dimension of data is
one and $\Lambda$ = $\\{1,-1\\}$, the kernel is given by

$Q(x,x^{\prime})=2c_{1,1}\sin(x+x^{\prime}+\phi_{1,1})+2c_{1,-1}\sin(x-x^{\prime}+\phi_{1,-1})+const.,$
(74)

where $\phi_{1,1}$ and $\phi_{1,-1}$ are real numbers. Obviously,
$Q(x,x^{\prime})$ can take a value close to one even if $x$ and $x^{\prime}$
is different. We can naturally construct quantum kernels with a small number
of Fourier components as long as the dimension of data is small and we do not
encode data repeatedly.

However, in utilizing the above-introduced QKGCs, the role of the quantum
device is quite limited. In the case of the kernel with tiny coefficients,
once we determine the values of $\\{\beta_{k}\\}_{k=1}^{d}$ by a quantum
device, we can execute all the other processes by a classical computer. In the
case of the kernel where the number of Fourier components is small, we can
classically pre-determine the set of frequencies $\Lambda$, and determine the
values of
$\\{c_{{\boldsymbol{\bf\lambda}},{\boldsymbol{\bf\lambda}}^{\prime}}\\}_{{\boldsymbol{\bf\lambda}},{\boldsymbol{\bf\lambda}}^{\prime}\in\Lambda}$
according to the procedure proposed in [65]. Then, once they are determined,
no quantum computation is necessary. From these observations, we contend that
the above QKGCs do not have a quantum advantage, and we do not discuss them
further in the main text.

##  Appendix E Proof of theorems for the feature representation of the
projected quantum kernel

###  E.1 Proof of Theorem 1

###### Proof.

Let us expand each density matrix as

$\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}})=\sum_{j=1}^{N_{{\boldsymbol{\bf q}}}^{2}}c_{j}({\boldsymbol{\bf
x}})P_{j}^{({\boldsymbol{\bf q}})},$ (75)

with $\\{c_{j}({\boldsymbol{\bf x}})\\}_{j=1}^{N_{{\boldsymbol{\bf q}}}^{2}}$
as coefficients dependent on ${\boldsymbol{\bf x}}$. Then, the left-hand side
of (LABEL:eq:quantum-theorem) becomes,

$\displaystyle Q({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})=\sum_{j=1}^{N_{{\boldsymbol{\bf q}}}^{2}}c_{j}({\boldsymbol{\bf
x}})c_{j^{\prime}}({\boldsymbol{\bf x}}^{\prime}){\rm
Tr}(P_{j}^{({\boldsymbol{\bf q}})}P_{j^{\prime}}^{({\boldsymbol{\bf
q}})})=N_{{\boldsymbol{\bf q}}}\sum_{j=1}^{N_{{\boldsymbol{\bf
q}}}^{2}}c_{j}({\boldsymbol{\bf x}})c_{j}({\boldsymbol{\bf x}}^{\prime}).$
(76)

The right-hand side becomes

$\displaystyle\frac{1}{N_{{\boldsymbol{\bf
q}}}}\sum_{j=1}^{N_{{\boldsymbol{\bf q}}}^{2}}{\rm
Tr}\left((P_{j}^{({\boldsymbol{\bf q}})}\otimes I^{(\neq{\boldsymbol{\bf
q}})})\rho({\bf x})\right){\rm Tr}\left((P_{j}^{({\boldsymbol{\bf q}})}\otimes
I^{(\neq{\boldsymbol{\bf q}})})\rho({\bf x}^{\prime})\right)$ (77)
$\displaystyle=\frac{1}{N_{{\boldsymbol{\bf
q}}}}\sum_{j=1}^{N_{{\boldsymbol{\bf q}}}^{2}}{\rm
Tr}\left(P_{j}^{({\boldsymbol{\bf q}})}\rho^{({\boldsymbol{\bf
q}})}({\boldsymbol{\bf x}})\right){\rm Tr}\left(P_{j}^{({\boldsymbol{\bf
q}})}\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf x}}^{\prime})\right)$ (78)
$\displaystyle=\frac{1}{N_{{\boldsymbol{\bf
q}}}}\sum_{j,k,\ell=1}^{N_{{\boldsymbol{\bf q}}}^{2}}c_{k}({\boldsymbol{\bf
x}})c_{\ell}({\boldsymbol{\bf x}}^{\prime}){\rm
Tr}\left(P_{j}^{({\boldsymbol{\bf q}})}P_{k}^{({\boldsymbol{\bf
q}})}\right){\rm Tr}\left(P_{j}^{({\boldsymbol{\bf
q}})}P_{\ell}^{({\boldsymbol{\bf q}})}\right)$ (79)
$\displaystyle=N_{{\boldsymbol{\bf q}}}\sum_{j=1}^{N_{{\boldsymbol{\bf
q}}}^{2}}c_{j}({\boldsymbol{\bf x}})c_{j}({\boldsymbol{\bf x}}^{\prime}),$
(80)

which is equal to the left hand side (76). ∎

###  E.2 Proof of the bound for $N_{\rm shot}$

Let $\tilde{P}_{j}^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf x}})$ be an
unbiased estimator of ${\rm Tr}\left((P_{j}^{({\boldsymbol{\bf q}})}\otimes
I^{(\neq{\boldsymbol{\bf q}})})\Phi\left(\rho({\boldsymbol{\bf
x}})\right)\right)$, whose value is determined by $N_{\rm shot}$ measurements
(each element of feature $z_{j}({\boldsymbol{\bf x}})$ is directly constructed
as $z_{j}({\boldsymbol{\bf x}})=\tilde{P}_{j}^{({\boldsymbol{\bf
q}})}({\boldsymbol{\bf x}})/\sqrt{N_{{\boldsymbol{\bf q}}}}$). Then we can
readily show that if at least

$|\tilde{P}_{j}^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf x}})-{\rm
Tr}((P_{j}^{({\boldsymbol{\bf q}})}\otimes I^{(\neq{\boldsymbol{\bf
q}})})\Phi\left(\rho({\boldsymbol{\bf
x}}))\right)|\leq\frac{\epsilon}{3N_{{\boldsymbol{\bf q}}}},$ (81)

for all $j$ with $\epsilon<1$,

$\left|\sum_{j=1}^{N_{{\boldsymbol{\bf q}}}^{2}}{\boldsymbol{\bf
z}}({\boldsymbol{\bf x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}}^{\prime})-{\rm Tr}\left(\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}})\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}^{\prime})\right)\right|<\epsilon,$ (82)

is satisfied. From Hoeffding’s inequality, the probability that (81) is not
satisfied is bounded as

${\rm Prob}\left(\left|\tilde{P}_{j}^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}})-{\rm Tr}\left((P_{j}^{({\boldsymbol{\bf q}})}\otimes
I^{(\neq{\boldsymbol{\bf q}})})\Phi\left(\rho({\boldsymbol{\bf
x}})\right)\right)\right|\geq\frac{\epsilon}{3N_{{\boldsymbol{\bf
q}}}}\right)\leq 2\exp\left(-\frac{N_{\rm
shot}\epsilon^{2}}{18N_{{\boldsymbol{\bf q}}}^{2}}\right).$ (83)

Thus, the probability $\delta$ that at least one of the inequality (81) is not
satisfied in the training data is bounded as

$\delta\leq 2M\exp\left(-\frac{N_{\rm shot}\epsilon^{2}}{18N_{{\boldsymbol{\bf
q}}}^{2}}\right).$ (84)

Conversely, if

$N_{\rm shot}\geq\frac{18N_{{\boldsymbol{\bf
q}}}^{2}}{\epsilon^{2}}\log\left(\frac{2M}{\delta}\right),$ (85)

is satisfied,

${\rm Prob}\left[{\rm sup}_{{\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime}\in\mathcal{X}_{\rm data}}\left|{\boldsymbol{\bf
z}}({\boldsymbol{\bf x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}}^{\prime})-{\rm Tr}(\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}})\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}^{\prime}))\right|\geq\epsilon\right]\leq\delta$ (86)

holds for all data.

##  Appendix F Proof of theorems for the feature representation of the
distance kernel with RDM

###  F.1 Proof of theorem 2

With the expansion (75),

$\begin{split}d^{\rm HS}(\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}),\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}^{\prime}))&=\frac{1}{4}{\rm Tr}\left((\rho^{({\boldsymbol{\bf
q}})}({\boldsymbol{\bf x}})-\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}^{\prime}))^{2}\right)\\\ &=\frac{N_{{\boldsymbol{\bf
q}}}}{4}\left|\left|{\boldsymbol{\bf c}}({\boldsymbol{\bf
x}})-{\boldsymbol{\bf c}}({\boldsymbol{\bf
x}}^{\prime})\right|\right|_{2}^{2},\end{split}$ (87)

where ${\boldsymbol{\bf c}}({\boldsymbol{\bf x}})=\left\\{{\rm
Tr}\left((P_{j}^{({\boldsymbol{\bf q}}_{k})}\otimes I^{(\neq{\boldsymbol{\bf
q}}_{k})})\Phi\left(\rho({\boldsymbol{\bf
x}})\right)\right)/N_{{\boldsymbol{\bf
q}}}\right\\}_{j=1}^{N_{{\boldsymbol{\bf q}}}^{2}}$. Therefore, $f(d^{\rm
HS}(\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}),\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf x}}^{\prime})))$ is a
shift-invariant function in the sense that

$f\left(d^{\rm HS}(\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}),\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}^{\prime}))\right)=F\left({\boldsymbol{\bf c}}({\boldsymbol{\bf
x}})-{\boldsymbol{\bf c}}({\boldsymbol{\bf x}}^{\prime})\right),$ (88)

where $F\in{\mathbf{R}^{N_{{\boldsymbol{\bf q}}}^{2}}\rightarrow\mathbf{R}}$
is defined by $F({\bf b})=f(N_{{\boldsymbol{\bf q}}}||{\bf b}||_{2}^{2}/4)$.

Then, from (55),

$\begin{split}F({\boldsymbol{\bf c}}\left({\boldsymbol{\bf
x}})-{\boldsymbol{\bf c}}({\boldsymbol{\bf
x}}^{\prime})\right)&=\int_{\mathbf{R}^{N_{{\boldsymbol{\bf
q}}}^{2}}}d{\boldsymbol{\bf\omega}}p({\boldsymbol{\bf\omega}})e^{i{\boldsymbol{\bf\omega}}^{T}\left({\boldsymbol{\bf
c}}({\boldsymbol{\bf x}})-{\boldsymbol{\bf c}}({\boldsymbol{\bf
x}}^{\prime})\right)}\\\ &=\int_{\mathbf{R}^{N_{{\boldsymbol{\bf
q}}}^{2}}}d{\boldsymbol{\bf\omega}}p({\boldsymbol{\bf\omega}})\left(\cos({\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf
c}}({\boldsymbol{\bf x}}))\cos({\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf
c}}({\boldsymbol{\bf
x}}^{\prime}))+\sin({\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf
c}}({\boldsymbol{\bf x}}))\sin({\boldsymbol{\bf\omega}}^{T}{\boldsymbol{\bf
c}}({\boldsymbol{\bf x}}^{\prime}))\right),\end{split}$ (89)

where

$p({\boldsymbol{\bf\omega}})=\frac{1}{(2\pi)^{N_{{\boldsymbol{\bf
q}}}^{2}}}\int_{\mathbf{R}^{N_{{\boldsymbol{\bf
q}}}^{2}}}F({\boldsymbol{\bf\Delta}}),$ (90)

Eq. (89) is equivalent to (32) in Theorem 2.

###  F.2 Proof of Theorem 3

We write

$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})=f\left(d^{\rm
HS}(\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf
x}}),\rho^{({\boldsymbol{\bf q}})}({\boldsymbol{\bf x}}^{\prime}))\right).$
(91)

From the triangle inequality, it holds

${\rm sup}_{{\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime}\in\mathcal{X}_{\rm data}}|{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf x}}^{\prime})-Q({\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime})|\leq{\rm sup}_{{\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime}\in\mathcal{X}_{\rm
data}}|\tilde{Q}({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})-{Q}({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})|+{\rm
sup}_{{\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime}\in\mathcal{X}_{\rm
data}}|{\boldsymbol{\bf z}}({\boldsymbol{\bf x}})^{T}{\boldsymbol{\bf
z}}({\boldsymbol{\bf x}}^{\prime})-\tilde{Q}({\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime})|,$ (92)

where

$\tilde{Q}({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})=F(\tilde{{\boldsymbol{\bf c}}}({\boldsymbol{\bf
x}})-\tilde{{\boldsymbol{\bf c}}}({\boldsymbol{\bf x}}^{\prime})),$ (93)

with $\tilde{{\boldsymbol{\bf c}}}({\boldsymbol{\bf x}})$ as an unbiased
estimator of ${\boldsymbol{\bf c}}({\boldsymbol{\bf x}})$, where each element
is determined by $N_{\rm shot}$ measurements. We see that the first term on
the right-hand side of (92) corresponds to the sampling error due to the
limited number of samples $D$, and the second term corresponds to the error
due to the shot noise.

For the first term,

$\begin{split}|\tilde{Q}({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})-Q({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})|&=\left|f\left(\frac{N_{{\boldsymbol{\bf
q}}}||\tilde{{\boldsymbol{\bf c}}}({\boldsymbol{\bf
x}})-\tilde{{\boldsymbol{\bf c}}}({\boldsymbol{\bf
x}}^{\prime})||_{2}^{2}}{4}\right)-f\left(\frac{N_{{\boldsymbol{\bf
q}}}||{{\boldsymbol{\bf c}}}({\boldsymbol{\bf x}})-{{\boldsymbol{\bf
c}}}({\boldsymbol{\bf x}}^{\prime})||_{2}^{2}}{4}\right)\right|\\\
&\leq\frac{N_{{\boldsymbol{\bf q}}}L_{f}}{4}\left|||\tilde{{\boldsymbol{\bf
c}}}({\boldsymbol{\bf x}})-\tilde{{\boldsymbol{\bf c}}}({\boldsymbol{\bf
x}}^{\prime})||_{2}^{2}-||{{\boldsymbol{\bf c}}}({\boldsymbol{\bf
x}})-{{\boldsymbol{\bf c}}}({\boldsymbol{\bf x}}^{\prime})||_{2}^{2}\right|\\\
&\leq\frac{N_{{\boldsymbol{\bf q}}}L_{f}}{4}\left|||\tilde{{\boldsymbol{\bf
c}}}({\boldsymbol{\bf x}})-{\boldsymbol{\bf c}}({\boldsymbol{\bf
x}})-\left(\tilde{{\boldsymbol{\bf c}}}({\boldsymbol{\bf
x}}^{\prime})-{\boldsymbol{\bf c}}({\boldsymbol{\bf
x}}^{\prime})\right)+\left({\boldsymbol{\bf c}}({\boldsymbol{\bf
x}})-{\boldsymbol{\bf c}}({\boldsymbol{\bf
x}}^{\prime})\right)||^{2}_{2}-||{{\boldsymbol{\bf c}}}({\boldsymbol{\bf
x}})-{{\boldsymbol{\bf c}}}({\boldsymbol{\bf x}}^{\prime})||_{2}^{2}\right|\\\
&\leq\frac{N_{{\boldsymbol{\bf q}}}L_{f}}{4}\left(||\tilde{{\boldsymbol{\bf
c}}}({\boldsymbol{\bf x}})-{{\boldsymbol{\bf c}}}({\boldsymbol{\bf
x}})||_{2}^{2}+||\tilde{{\boldsymbol{\bf c}}}({\boldsymbol{\bf
x}}^{\prime})-{{\boldsymbol{\bf c}}}({\boldsymbol{\bf
x}}^{\prime})||_{2}^{2}\right),\end{split}$ (94)

where in the second line, we use that the Lifshitz constant of $f$ with
respect to the $L_{1}$ norm is $L_{f}$. Thus, if

$||\tilde{{\boldsymbol{\bf c}}}({\boldsymbol{\bf x}})-{{\boldsymbol{\bf
c}}}({\boldsymbol{\bf x}})||_{2}^{2}<\frac{\epsilon}{N_{{\boldsymbol{\bf
q}}}L_{f}},$ (95)

for all ${\boldsymbol{\bf x}}\in\mathcal{X}$,

${\rm sup}_{{\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime}\in\mathcal{X}_{\rm data}}|\tilde{Q}({\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime})-Q({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})|<\frac{\epsilon}{2}.$ (96)

The probability that (95) does not hold is bounded from Hoeffding’s inequality
as

${\rm Prob}\left[||\tilde{{\boldsymbol{\bf c}}}({\boldsymbol{\bf
x}})-{{\boldsymbol{\bf c}}}({\boldsymbol{\bf
x}})||_{2}^{2}\geq\frac{\epsilon}{N_{{\boldsymbol{\bf q}}}L_{f}}\right]\leq
2\exp\left(-\frac{N_{\rm shot}\epsilon^{2}}{8N_{{\boldsymbol{\bf
q}}}^{2}L_{f}^{2}}\right),$ (97)

where we use

$0\leq||\tilde{{\boldsymbol{\bf c}}}({\boldsymbol{\bf x}})-{{\boldsymbol{\bf
c}}}({\boldsymbol{\bf x}})||_{2}^{2}\leq 4.$ (98)

Thus,

${\rm Prob}\left[{\rm sup}_{{\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime}\in\mathcal{X}_{\rm data}}||\tilde{Q}({\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime})-{Q}({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})||_{2}^{2}\geq\frac{\epsilon}{2}\right]\leq
2M\exp\left(-\frac{N_{\rm shot}\epsilon^{2}}{8N_{{\boldsymbol{\bf
q}}}^{2}L_{f}^{2}}\right).$ (99)

Next, we bound the second term in (92). Given the space where
${\boldsymbol{\bf c}}({\boldsymbol{\bf x}})$ is located as
$\mathcal{X}_{{\boldsymbol{\bf c}}}$, using (58) with $d=N_{{\boldsymbol{\bf
q}}}^{2}$, $\mathcal{X}=\mathcal{X}_{{\boldsymbol{\bf c}}}$, and
$\epsilon\rightarrow\epsilon/2$, we obtain

${\rm Prob}\left[{\rm sup}_{{\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime}\in\mathcal{X}_{\rm data}}|{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}}^{\prime})-\tilde{Q}({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})|\geq\frac{\epsilon}{2}\right]\leq 264\left(\frac{\sigma_{p}{\rm
diam}(\mathcal{X}_{{\boldsymbol{\bf
c}}})}{\epsilon}\right)^{2}\exp\left(-\frac{D\epsilon^{2}}{32(N_{{\boldsymbol{\bf
q}}}^{2}+2)}\right).$ (100)

Since $|{\boldsymbol{\bf c}}({\boldsymbol{\bf x}})|\leq 1$, it holds ${\rm
diam}(\mathcal{X}_{{\boldsymbol{\bf c}}})\leq 2$. Therefore,

${\rm Prob}\left[{\rm sup}_{{\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime}\in\mathcal{X}_{\rm data}}|{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}}^{\prime})-\tilde{Q}({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})|\geq\frac{\epsilon}{2}\right]\leq
1056\left(\frac{\sigma_{p}}{\epsilon}\right)^{2}\exp\left(-\frac{D\epsilon^{2}}{32(N_{{\boldsymbol{\bf
q}}}^{2}+2)}\right).$ (101)

From the above, we observe the followings:

  * •

(a) From (99), with probability less than or equal to $\delta/2$,

${\rm sup}_{{\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime}\in\mathcal{X}_{\rm data}}|\tilde{Q}({\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime})-Q({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})|\geq\frac{\epsilon}{2},$ (102)

if $N_{\rm shot}$ is bounded as

$N_{\rm shot}\geq\frac{8N_{{\boldsymbol{\bf
q}}}^{2}L_{f}^{2}}{\epsilon^{2}}\log\left(\frac{4M}{\delta}\right).$ (103)

  * •

(b) From (100), with probability less than or equal to $\delta/2$,

${\rm sup}_{{\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime}\in\mathcal{X}_{\rm data}}|{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}}^{\prime})-\tilde{Q}({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})|\geq\frac{\epsilon}{2},$ (104)

if $D$ is bounded as

$D\geq\frac{32(N_{{\boldsymbol{\bf
q}}}^{2}+2)}{\epsilon^{2}}\log\left(\frac{2112\sigma_{p}^{2}}{\epsilon^{2}\delta}\right).$
(105)

Combining (a) and (b) with Eq. (92), we conclude that

${\rm Prob}\left[\left|{\rm sup}_{{\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime}\in\mathcal{X}_{\rm data}}|{\boldsymbol{\bf z}}({\boldsymbol{\bf
x}})^{T}{\boldsymbol{\bf z}}({\boldsymbol{\bf x}}^{\prime})-Q({\boldsymbol{\bf
x}},{\boldsymbol{\bf x}}^{\prime})\right|\geq\epsilon\right]\leq\delta$ (106)

if (103) and (105) are both satisfied.

##  Appendix G Detail of the numerical experiment

###  G.1 Data encoding circuit

Here let us show the data encoding circuit in the numerical experiment in
Section V. Suppose that the dimension of the data is $n$. The number of qubits
is also $n$ (recall that the dimension of the data is equal to the number of
qubits in our numerical experiment). Then, as the data encoding circuit, we
use the following unitary operator

$U({\boldsymbol{\bf x}})=U_{\rm ent}U_{Y}(\\{x_{j}\\}_{j=1}^{n})H^{\otimes
n},$ (107)

and build the density operator before the reduction of qubits as
$\rho({\boldsymbol{\bf x}})=U({\boldsymbol{\bf x}})|0\rangle^{\otimes
n}\langle 0|^{\otimes n}U^{\dagger}({\boldsymbol{\bf x}})$. Here, we define

$U_{Y}(\\{x_{j}\\}_{j=1}^{n})=R_{Y}(x_{1})\otimes
R_{Y}(x_{2})\otimes\cdots\otimes R_{Y}(x_{n}).$ (108)

Also, we define

$U_{\rm ent}=U_{\rm ent}^{(n)}\cdots U_{\rm ent}^{(2)}U_{\rm ent}^{(1)},$
(109)

with

$U_{\rm ent}^{(j)}={\rm CNOT}(j,n)\cdots{\rm CNOT}(j,j+2){\rm CNOT}(j,j+1),$
(110)

where ${\rm CNOT}(j,k)$ is the CNOT operator with $j$ as the control qubits
and $k$ as the target qubits. We show the data encoding circuit when $n=4$ as
an example in Fig. 2.

@C=1.0em @R=0.2em @!R
q_1 : & q_1 : H R_Y (x_1) 1 2 3 [0em]3 [0em]3 [0em]3
q_2 : q_2 : H R_Y (x_2) 1 2
q_3 : q_3 : H R_Y (x_3) 1
q_4 : q_4 : H R_Y (x_4)

Figure 2: The data encoding circuit when $n=4$.

###  G.2 Nystrom method

The Nystrom method, which we demonstrate in Section V is another algorithm to
construct features that approximates the kernel. The procedure for
approximating a kernel $Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})$
is as follows. We first sample $D$ data, where we write them as
$\\{\hat{{\boldsymbol{\bf x}}}_{1},\hat{{\boldsymbol{\bf
x}}}_{2},\cdots\hat{{\boldsymbol{\bf x}}}_{D}\\}$. By using the sampled data,
we construct the following matrix
$\hat{Q}\in\mathbf{R}^{D}\times\mathbf{R}^{D}$ defined by
$\hat{Q}=\\{Q(\hat{{\boldsymbol{\bf x}}}_{k},\hat{{\boldsymbol{\bf
x}}}_{\ell})\\}$, where the indices $k,\ell$ run from $1$ to $D$.

Suppose that the non-zero eigenvalues of $\hat{Q}$ as $\\{d_{s}\\}_{s=1}^{S}$
and the corresponding eigenvectors as $\\{{\boldsymbol{\bf
v}}_{s}\\}_{s=1}^{S}$, where $S\leq D$. Given matrices

$A=diag\left(\frac{1}{\sqrt{\lambda_{1}}},\frac{1}{\sqrt{\lambda_{2}}},\cdots,\frac{1}{\sqrt{\lambda_{S}}}\right)~{}{\rm
and}~{}B=({\boldsymbol{\bf v}}_{1},{\boldsymbol{\bf
v}}_{2},\cdots{\boldsymbol{\bf v}}_{S}),$ (111)

we build the features as

${\boldsymbol{\bf z}}({\boldsymbol{\bf
x}})=AB^{T}\left(\begin{array}[]{c}Q({\boldsymbol{\bf
x}},\hat{{\boldsymbol{\bf x}}}_{1})\\\ Q({\boldsymbol{\bf
x}},\hat{{\boldsymbol{\bf x}}}_{2})\\\ \vdots\\\ Q({\boldsymbol{\bf
x}},\hat{{\boldsymbol{\bf x}}}_{S})\\\ \end{array}\right).$ (112)

Note that the kernel $\tilde{Q}({\boldsymbol{\bf x}},{\boldsymbol{\bf
x}}^{\prime})={\boldsymbol{\bf z}}({\boldsymbol{\bf x}})^{T}{\boldsymbol{\bf
z}}({\boldsymbol{\bf x}}^{\prime})$ is the approximate of the original kernel
$Q({\boldsymbol{\bf x}},{\boldsymbol{\bf x}}^{\prime})$.