The Inductive Bias of Quantum Kernels
Authors: Jonas M. Kübler
Simon Buchholz
Bernhard Schölkopf
Venue: NeurIPS 2021 Poster (2021)
Keywords: Quantum Machine Learning
Kernel Methods
Quantum Kernels
Inductive Bias
Regression
Learning Theory

Abstract: It has been hypothesized that quantum computers may lend themselves well to applications in machine learning. In the present work, we analyze function classes defined via quantum kernels. Quantum computers offer the possibility to efficiently compute inner products of exponentially large density operators that are classically hard to compute. However, having an exponentially large feature space renders the problem of generalization hard. Furthermore, being able to evaluate inner products in high dimensional spaces efficiently by itself does not guarantee a quantum advantage, as already classically tractable kernels can correspond to high- or infinite-dimensional reproducing kernel Hilbert spaces (RKHS).
   We analyze the spectral properties of quantum kernels and find that we can expect an advantage if their RKHS is low dimensional and contains functions that are hard to compute classically. If the target function is known to lie in this class, this implies a quantum advantage, as the quantum computer can encode this inductive bias, whereas there is no classically efficient way to constrain the function class in the same way. However, we show that finding suitable quantum kernels is not easy because the kernel evaluation might require exponentially many measurements.
   In conclusion, our message is a somewhat sobering one: we conjecture that quantum machine learning models can offer speed-ups only if we manage to encode knowledge about the problem at hand into quantum circuits, while encoding the same bias into a classical model would be hard. These situations may plausibly occur when learning on data generated by a quantum process, however, they appear to be harder to come by for classical datasets.


The Inductive Bias of Quantum Kernels
Jonas M. Kübler*
Simon Buchholz"
Bernhard Schölkopf"
Max Planck Institute for Intelligent Systems
Tübingen, Germany (jnkuebler, sbuchholz, bs} peruue.pp mpg.
Abstract
It has been hypothesized that quantum computers may lend themselves well applications in machine learning. In the present work, we analyze function classes defined via quantum kernels. Quantum computers offer the possibility efficiently compute inner products of exponentially large density operators that are classically hard to compute. However, having an exponentially large feature space renders the problem of generalization hard. Furthermore, being able to evaluate inner products in high dimensional spaces efficiently by itself does not guarantee a quantum advantage, as already classically tractable kernels can correspond to high- or infnite-diimensionll reproducing kernel Hilbert spaces (RKHS).
We analyze the spectral properties of quantum kernels and find that we can expect advantage if their RKHS is low dimensional and contains functions that are hard to compute classically. If the target function is known to lie in this class, this implies quantum advantage, the quantum computer bias, whereas there no classically efficient way to constrain the function class the same way. However, show that finding suitable quantum kernels is easy because the kernel evaluation might require exponentially many measurements.
encode this inductive
In conclusion, our message is somewhat sobering one: we conjecture that quan- tum machine learning models can offer speed-ups only we manage encode knowledge about the problem at hand into quantum circuits, while encoding the same bias into classical model would be hard. These situations may plausibly occur when learning on data generated by quantum process, however, they appear be harder come by for classical datasets.
Introduction
In recent years, much attention has been dedicated to studies of how small and noisy quantum devices [1] could be used for near term applications to showcase the power of quantum computers. Besides fundamental demonstrations (2), potential applications that have been discussed are in quantum chemistry [3], discrete optimization [4] and machine learning (ML) [5-12].
Initiated by the seminal HHL algorithm [13], carly work in quantum machine learning (QML) was focused on speeding up linear algebra subroutines, commonly used in ML, offering the perspective of a runtime logarithmic in the problem size [14-17]. However, most of these works have an inverse polynomial scaling of the runtime in the error and it was shown rigorously by Ciliberto et al. [18] that due to the quantum mechanical measurement process runtime complexity O(yn) is necessary for convergence rate 1/vn.
Rather than speeding up linear algebra subroutines, we focus on more recent suggestions that use quantum device to define and implement the function class and do the optimization classical computer. There are two ways to that: the first are so-called Quantum Neural Networks (QNN) or
*JMK and SB contribuled equally and ordered randomly.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

10)
(1)
M
(0)
(x1
[0)
Rx (x1)
py (x)
10)
Rx(
id
10)
Rx(x22)
10) -
Rx (22)
id
V
(x)
(0)
Rx (xa)
id
10]
Rx (xa)
10)
Rx (ra)
id
(a)
(b)
Figure 1: Quantum advantage via inductive bias: (a) Data generating quantum circuit f(x)
Tr le" (M @ id)] = =Tr TT (x) (b) The full quantum kernel k( x") Tr po (x)p (x')) too general and cannot learn f efficiently.
(c) The biased quantum kernel q(2, x²)
Tr [p" (x)p" (x") meaningfully constrains the function space and allows learn f with little data.
parametrized quantum circuits [5-7] which can be trained via gradient based optimization [5, 19-23). The second approach to use a predefined way of encoding the data in the quantum system and defining quantum kernel as the inner product of two quantum states [7-11]. These two approaches essentially provide a parametric and a non-parametric path to quantum machine learning, which are closely related to each other [11]. Since the optimization of QNNs is non-convex and suffers from so-called Barren Plateaus [24], we here focus on quantum kernels, which allow for convex problems and thus lend themselves more readily to theoretical analysis.
The central idea of using a QML model is that it enables to do computations that are exponentially hard classically. However, also in classical ML, kernel methods allow us to implicitly work with high- or infinite dimensional function spaces [25, 26]. Thus, purely studying the expressivity of QML models [27] is not sufficient to understand when we can expect speed-ups. Only recently first steps where taken into this direction [10, 12, 28]. Assuming classical hardness of computing discrete logarithms, Liu et al. [10] proposed task based the computation of the discrete logarithm where the quantum computer, equipped with the right feature mapping, can learn the target function with exponentially less data than any classical (efficient) algorithm. Similarly, Huang et al. [12] analyzed generalization bounds and realized that the expressivity of quantum models can hinder generalization. They proposed heuristic to optimize the labels of a dataset such that it can be learned well by quantum computer but not a classical machine.
In this work, we relate the discussion of quantum advantages to the classical concept of inductive bias. The no free lunch theorem informally states that no learning algorithm can outperform other algorithmss on all problems. This implies that algorithm that performs well one type of problem necessarily performs poorly on other problems. A standard inductive bias in ML is to prefer functions that are continuous. An algorithm with that bias, however, will then struggle to learn functions that are discontinuous. For a QML model to have an edge over classical ML models, we could thus ensure that it is equipped with inductive bias that cannot be encoded (efficiently) with classical machine. a given dataset fits this inductive bias, the QML model will outperform any classical algorithm. For kernel methods, the qualitative concept of inductive bias can be formalized by analyzing the spectrum of the kernel and relating it to the target function [25, 29-33].
Our main contribution is the analysis of the inductive bias of quantum machine learning models based on the spectral properties of quantum kernels. First, we show that quantum kernel methods will fail to generalize soon as the data embedding into the quantum Hilbert space is too expressive (Theorem 1). Then we note that projecting the quantum kernel appropriately allows to construct inductive biases that are hard to create classically (Figure 1). However, our Theorem 2 also implies that estimating the biased kernel requires exponential measurements, a phenomenon reminiscent of the Barren plateaus observed in quantum neural networks. Finally show experiments supporting our main claims.
While our work gives guidance to find a quantum advantage in ML, this yields no recipe for obtaining a quantum advantage on classical dataset. We conjecture that unless we have clear idea how the data generating process can be described with a quantum computer, we cannot expect an advantage by using a quantum model in place of classical machine learning model.

---

2 Supervised learning
We briefly introduce the setting and notation for supervised learning as a preparation for our analysis of quantum mechanical methods in this context. The goal of supervised learning is the estimation of a functional mechanism based on data generated from this mechanism. For concreteness we focus on the regression setting where we assume data is generated according to Y = (X) + where denotes zero-mean noise. We focus X X C Rd, Y TR. We denote the joint probability distribution of (X, Y) by 2 and we are given n. i..d. observations D, from D. We will refer to the marginal distribution of X as yr, define the 7 inner product (f. g) = f f(x (g())) u(dx) and denote the corresponding norm by || ||. The least square risk and the empirical risk of some hypothesis h X + R. is defined by R(h) = ED [(h(X) - y)²] and R,, (h) ED.. (h(X)-Y)
-
In supervised machine learning, one typically considers a hypothesis space H of functions h X IR and tries to infer argmin; и R(h) (assuming for simplicity that the minimizer exists). Typically this done by (regularized) empirical risk minimization argmin R., (h) + X2((h), where À > 0 and Ω determine the regularization. The risk of h can then be decomposed in generalization and training error R(h)= = (R(h) - R,,hh) + (h).
Kernel ridge regression. We will focus on solving the regression problem over a reproducing kernel Hilbert space (RKHS) [25, 26]. An RKHS F associated with a positive definite kernel k: X' x X' + R is the space of functions such that for all x E X' and h E F the reproducing property h(x))= = (h, k(x,) :) holds. Kernel ridge regression regularizes the RKHS norm, i.e., 52(h) = 1|.13-
With observations ((x((), y ) we can compute the kernel matrix {(X,X);;
k(x(()) x))
and the Representer Theorem [34] ensures that the empirical risk minimizer of kernel ridge regression is of the form (.) Σi= ack(x(1), .). with a XX) + A Aid)-'y. y. The goal of our work is to study when a (quantum) kernel is suitable for learning a particular problem. The central object to study this is the integral operator.
Spectral properties and inductive bias. For kernel & and marginal distribution μa, the integral Mercer's Theorem ensures that there
operator K, is defined as (z) = k(æ, exist spectral decomposition of K with (possibly infinitely many) eigenvalues 7/8 (ordered non- increasingly) and corresponding eigenfunctions 6;, which are orthonormal in L2, i.e., (Øs, Q3) 85.j- We will assume that Tr [r] E. = 1 which we can ensure by rescaling the kernel. We can then write (<z,, x²) = E. (z))). While the functions o form a basis of F they might not completely span -. In this case we simply complete the basis and implicitly take ? 0 for the added functions. Then we can decompose functions in L as
f(x)= = E, a.de((x).
(1)
We have ||f = E, and |1 E, of f F). Kernel ridge regression penalizes the RKHS norm of functions. The components corresponding to zero eigenvalues are infinitely penalized and cannot be learned since they are not in the RKHS. For large regularization À the solution f is heavily biased towards learning only the coefficients of the principal components (corresponding to the largest eigenvalues) and keeps the other coefficients small (at the risk of underfitring). Decreasing the regularization allows ridge regression to also fit the other components, however, at the potential risk of overfitting the noise in the empirical data. Finding good choices of thus balances this caa-vvariecce tradeoff.
We less concerned with the choice of X, but rather with the spectral properties of a kernel that allow for a quantum advantage. Similar to the above considerations, a target function f can easily be learned if it is well aligned with the principal components of kernel. In the easiest case, the kernel only has a single non-zero eigenvalue and is just k(æ, x') fxx) Such construction is arguably the simplest path a quantum advantage in ML.
Example (Trivial Quantum Advantage). Let f be a scalar function that easily computable on a quantum device but requires exponential resources to approximate classically. Generate data as Y y= [(X) + e. The kernel k(r,, x')= = f(==((a')) then has an exponential advantage for learning f from data.
3

---

To go beyond this trivial case, we introduce two qualitative measures to judge the quality of a kernel for learning the function f. The kernel target alignment of Cristiamini et al. [30] is
f f)
Σ, mag (E, E.
A(k, f) (k. f f) f)1/
and measures how well the kernel fits f. If A = 1, learning reduces to estimating a single real parameter, whereas for A = 0, learning is infeasible. We note that the kernel target alignment also weighs the contributions of f depending on the corresponding eigenvalue, i.e., the alignment is better if large |a,] correspond to large %/- The kernel target alignment
used extensively to optimize kernel functions [31] and recently also used to optimize quantum kernels [35].
In similar spirit, the task-model alignment of Canatar et al. [32] measures how much of the signal of f is captured in the first i principal components: C()) Ejs; e3(E; a - The slower C(i) approaches 1, the harder it is learn as the target function is more spread over the eigenfunctions.
3 Quantum computation in machine learning
In this section we introduce hypothesis spaces containing functions whose output is given by the result of quantum computation. For general introduction to concepts of quantum computation we refer to the book of Nielsen and Chuang [36].
We will consider quantum systems comprising d E N qubits. Discussing such systems and their algebraic properties does not require in-depth knowledge of quantum mechanics. A pure state of a single qubit is described by vector (a, 3) E C2 s.t. |ce +
and we write | = a [0) + 3 [1).
where {10). } forms the computational basis. A d qubit pure state lives in the tensor product of the
single qubit state spaces, i.e., it is described by normalized vector in C²". A mixed state of dl-ubit
system can be described by a density operator p E C² x2" i.e., a positive definite matrix (p 2 0) with unit trace (Tr [p] 1). For pure state (()) the corresponding density operator is p = (t) (vb)
(here, (1b is the complex conjugate transpose of (e)).. A general density operator can be thought of as classical probabilistic mixture of pure states. We can extract information from p by estimating (through repeated measurements) the expectation of a suitable observable, i.c., a Hermitian operator M = M (where the adjoint (-) is the complex conjugate of the transpose), as
Tr [pM]
(3)
Put simply, the potential advantage of a quantum computer arises from its state space being expo- nentially large in the number of qubits d, thus computing general expressions like (3) on a classical computer is exponentially hard. However, besides the huge obstacles in building quantum devices with high fidelity, the fact that the outcome of the quantum computation (3) has to be estimated from measurements often prohibits to easily harness this power, see also Wang et al. [37], Peters et al. [38]. We will discuss this in the context of quantum kernels in Section
We consider parameter dependent quantum states p(x) (z)) (x) that are generated by evolving the initial state po with the data dependent unitary transformation Ü (xx) [7, 11]. Most often will without loss of generality assume that the initial state is Pe (10) (o))add, We then define quantum machine learning models via observables M of the data dependent state
far = Tr (o)))) = Tr [p(x)
(4)
In the following we introduce the two most common function classes suggested for quantum machine learning. We note that there also exist proposals that do not fit into the form of Eq. (4) [27, 39].
Quantum neural networks. A "quantum neural network" (QNN) is defined via a variational quantum circuit (VQC) [6, 40, 41]. Here the observable Me is parametrized by E N classical parameters 0 E θ C RP This defines a parametric function class Fe = {fM, 10 E θ). The most where (+) II, ((.)) is the composition of
common ansatz is to consider Ma- U(O) unitary evolutions each acting on few qubits. For this and other common models of the parametric circuit it is possible to analytically compute gradients and specific optimizers for quantum circuits based on gradient descent have been developed [5, 19-23]. Nevertheless, the optimization is usually non-convex problem and suffers from additional difficulties due to oftentimes exponentially (in d)

---

Table 1: Concepts in the quantum Hilbert space H. and the reproducing kernel Hilbert space F.
Quantum Space of d qubits
RKHS
> p(a) E H (explicit feature map)
x + k(,,z) E F (canonical feature map)
7 {o C2" x2" p= p. -
k(x, 1') = Tr Tr(p(z)p(=')) ((()))
k(x, x') 1,,,,,,,))))))) F = Span (()(-,)) 1 x3)
F = =fM((f(() = Tr (r = Mr
vanishing gradients [24]. This hinders a theoretical analysis. Note that the non-convexity does not arise from the fact that the QNN can learn non- linear functions, but rather because the observable Ma depends non-linearly on the parameters. In fact, the QNN functions are linear in the fixed feature mapping p(a:). Therefore the analogy to classical neural networks is somewhat incomplete.
Quantum kernels. The class of functions we consider are RKHS functions where the kernel is expressed by a quantum computation. The key observation is that (4) linear in p(r). Instead of optimizing over the parametrie function class Fe.
define the nonparametric class of functions F= { {fM](f()) = Tr [p())M] M = .M }.2 To endow this function class with the structure of an RKHS, observe that the expression Tr [01P2] defines scalar product on density matrices. We then define kernels via the inner product of data-dependent density matrices:
Definition (Quantum Kernel [7, 8, 11)). Let p: p + p(æ) be a fixed feature mapping from X' to density matrices. Then the corresponding quantum kernel k(x, = Tr Tr(o())p(z')).
The Representer Theorem [34] reduces the empirical risk minimization over the exponentially large function class F to an optimization problem with a set of parameters whose dimensionality corresponds to the training set size. Since the ridge regression objective is convex (and many other common objective functions in ML), this can be solved efficiently with a classical computer.
In the described setting, the quantum computer is only used to estimate the kernel. For pure state encodings, this done by inverting the data encoding transformation (taking its conjugate transpose) and measuring the probability that the resulting state equals the initial state po. To see this we use the cyclic property the trace k(I, x²) = Tr (p(x))((x') = Tr (U()) (x) (x) ((o')) (x')] = po]. If po (10) (0)8d, then k( x') corresponds to the proba- bility of observing every qubit in the '0' state after the initial state was evolved with Ut (ar (x)). To evaluate the kernel, we thus need to estimate this probability from finite number of measurements. For our theoretical analysis we work with the exact value of the kernel and in our experiments we also simulate the full quantum state. We discuss the difficulties related to measurements Sec. 4.
Tr [(U (z))(())
4 The inductive bias of simple quantum kernels
We now study the inductive bias for simple quantum kernels and their learning performance. We first give a high level discussion of a general hurdle for quantum machine learning models to surpass classical methods and then analyze two specific kernel approaches in more detail.
Continuity in classical machine learning. Arguably the most important bias in nonparametric regression are continuity assumptions on the regression function. This becomes particularly apparent in, e.g., nearest neighbour regression or random regression forests [42] where the regression function is a weighted average of close points. Here we want to emphasize that there is long list of results concerning the minimax optimality of kernel methods for regression problems [43-45]. In particular these results show that asymptotically the convergence of kernel ridge regression of, e.g., Sobolev functions reaches the statistical limits which also apply any quantum method.
2F is defined for a fixed feature mapping x + p(x). Although M is finite dimensional and thus J can be seen as a parametric function class, we will be interested in the case where M is exponentially large in d and we only access functions from F implicitly. Therefore refer it nonparametric class of functions.
5

---

A simple quantum kernel. We now restrict our attention to rather simple kernels to facilitate a theoretical analysis. As indicated above we consider data in &' C IR and we assume that the distribution jl of the data factorizes over the coordinates (i.e. μ can be written as Jr X p4). This data is embedded in d-qubit quantum circuit. Let us emphasize here that the RKHS based on a quantum state of d-qubits is at most 4d dimensional, i.e., finite dimensional and in the infinite data limit n + oo standard convergence guarantees from parametric statistics apply. Here we consider growing dimension d + oo, and sample size polynomial in the dimension n(d) E Poly(d). In particular the sample size n << 4" will be much smaller than the dimension of the feature space and bounds from the parametric literature do not apply.
Here we consider embeddings where each coordinate is embedded into a single qubit using a map P; followed by arbitrary unitary transformation V, so that can express the embedding in the quantum Hilbert space as 1& (x)) = V 8 [xp((x;) with corresponding density matrix (feature map)'
(z) = 1 (x)) (x))-
(5)
Note that the corresponding kernel k(x, x²) Tr (((()))(())) is independent of V and factorizes where p,(2,g) = (x;))) (xx)). The
Tr
<'x,,')= Tr I (1.) 2 (x()) = Ir (f.)))
product structure of the kernel allows us to characterize the RKHS generated by k based on the one dimensional case. The embedding of single variable can be parametrized by complex valued
functions a(z), 6(x) as
[x,())) = a(x))0) + b(x)
(6)
One important object characterizing this embedding turns out to be the mean density matrix of this embedding given by Py, = J p; p:(dy) = (p: (.(dy). This can be identified with the kernel mean embedding of the distribution [46]. Note that for factorizing base measure the factorization Pμ = X Pp: holds. Let us give a concrete example to clarify the setting, see Fig. 1(b).
Example 2. [11, Example III.1.] We consider the cosine kernel where a(x) = cos (00(1/2))) (2). b(x) =
i sin(x/2). This embedding can be realized using a single quantum Rx(x) exp (-i (- ax) gate
such that (x)) = Rx (z) = (2/s/2/2///) + (sin(xr/2)]1 In this case the kernel is given by
k(x, = (0) R (z) Rx (z) cos( 5 cos( {
sin( ( sin( 1 )12 cos (
As a reference measure μr we consider the uniform measure on [- T]. Then the mean density matrix is the completely mixed state Pr: 1 id. For IRd valued data whose coordinates are encoded independently the kernel is given by k( x²) = πI cos² ((z; /2) and P. 2 2ddi x22. We emphasize that due to the kernel trick this kernel can be evaluated classically in runtime (dd).
Quantum RKHS. We now characterize the RKHS and the eigenvalues of the integral operator for quantum kernels. The RKHS consists of all functions E F that can be written as f(x Tr M) where M e C²"x2" is a Hermitian operator. Using this characterization of the finite dimensional RKHS can rewrite the infinite dimensional eigenvalue problem of the integral operator as a finite dimensional problem. The action of the corresponding integral operator on f can be written
(xf(()) / (w)
p(dy) / Tr [(M ((=)) @ p(v)) m(dy) Tr [M @ p(x)) / plv) @ plv) p(v))(a))
[M
(8)
We denote the operator O,- = f p(y) 2 plu) p(dy) for which Tr [0n = holds. Then we can write (Kf)(z) = Tr (0, (M @ ((x))
Tr [M, @ id) @ p(x)) Tr Tr, (M (M @ id) p(r))
3 When we can ignore V, we simply assume V id and write p(œ) instead of p" (x)) For the kernel, since vtv id = vtV and due the cyclic property of the trace we have KY (a, x') = Tr [p" (z)p"(z))
Tr p = Tr (vtvp(x)V vt p(x') Tr [r(x))((x²)] k(x,z').

---

where Tr [-] refers to the partial trace over the first factor. For the definition and a proof of the last equality we refer to Appendix A. The eigenvalues of K can now be identified with the eigenvalues of the linear map Tp mapping M - Tr, (M @o id)]. As shown in the appendix there is an eigendeconposition such that (M) = Σ X A,A,T Tr [A,M] where A, are orthonormal Hermitian matrices (for details, proof and an example we refer to Appendix C). The eigenfunctions of K are given by fi(x) = Tr A.])
We now state a bound that controls the largest eigenvalue of the integral operator K in terms of the eigenvalues of the mean density matrix Pp (Proof in Appendix C.2).
Lemma 1. The largest eigenvalue "/max of K satisfies the bound Ymaa S V Tr [pA
The lemma above shows that the squared eigenvalues of K are bounded by Tr [e an expression known as the purity [36] of the density matrix Pμ+ which measures the diversity of the data embedding. On the other hand the eigenvalues of K are closely related to the learning guarantees of kernel ridge regression. In particular, standard generalization bounds for kernel ridge regression [47] become vacuous when Ymaz is exponentially smaller than the training sample size (if Tr [K] for pure state embeddings). The next result shows that this is not just a matter of bounds.
which holds
Theorem 1. Suppose the purity of the embeddings Pu, satisfies Tr [pp..] S 5 < 1 as the dimension and number of qubits d grows. Furthermore, suppose the training sample size only grows polynomially in d, i.e,, n S d' for some fixed E N. Then there exists do = do(6,1,E) such that for all d Z do no function can be learned using kernel ridge regression with the d-qubit kernel k(x, x')
Tr (p(x))(')) in the sense that for any f E L2,, with probability at least 1 - E for all X 2 0
R( 2 (1 =)
(10)
The proof of the theorem can be found in Appendix D. It relies on general result (Theorem 3 in Appendix D) which shows that for any (not necessarily quantum) kernel the solution of kernel ridge regression cannot generalize when the largest eigenvalue in the Mercer decomposition is sufficiently small (depending on the sample size). Then the proof of Theorem I essentially boils down to proving bound on the largest eigenvalue using Lemma 1.
Theorem implies that generalization is only possible when the mean embedding of most coordinates is close to a pure state, i.e. the embedding x - (x)) is almost constant. To make learning from data feasible we cannot use the full expressive power of the quantum Hilbert space but instead only
very restricted embeddings allow to learn from data. This generalizes an observation already made in [12]. Since also classical methods allow to handle high-dimensional and infinite dimensional RKHS the same problem occurs for classical kernels where one solution is to adapt the bandwidth of the kernel to control the expressivity of the RKHS. In principle this is also possible in the quantum context, e.g., for the cosine embedding.
Biased kernels. We have discussed that without any inductive bias, the introduced quantum kernel cannot learn any function for large d. One suggestion to reduce the expressive power of the kernel is the use of projected kernels [12]. They are defined using reduced density matrices given by (%,()) (x) = Trm+ (p'(x) (x) where Trm+1...a [-] denotes the partial trace over qubits m + 1 to d (definition in Appendix A) Then they consider the usual quantum kernel for this embedding
an (zz, 2²) = Tr | (z)p) (x")]. Physically, this corresponds to just measuring the first m qubits and the functions f in the RKHS can be written in terms of a hermitian operator M acting on m qubits so that fx) Tr p (M @ id)l = Tr ( If V is sufficiently complex is assumed that f is hard to compute classically [48].
Indeed above procedure reduces the generalization gap. But this comes at the price of an increased approximation error if the remaining RKHS cannot fully express the target function I* anymore, i.e,, the learned function underfits. Without any reason to believe that the target function is well represented via the projected kernel, we cannot hope for performance improvement by simply reducing the size of the RKHS in an arbitrary way. However, if we know something about the data generating process than this can lead to a meaningful inductive bias. For the projected kernel this could be that we know that the target function can be expressed as f*) Tr (,.()) see Fig. In this case using S improves the generalization error without increasing the approximation error. To emphasize this, we will henceforth refer to qh, as biased kernel.
7

---

100
10-1
Moan Squared Error
a train
Size of elgenvalue
test
train
10a2
Kar train
Kar test
2-4
1011
trein
Ow test
10a
Number Qubits
Number Qubits
Figure Left: Spectral behavior of biased kernel q. see Theorem 2b) and Equation (11) Right: The biased kernel y. equipped with prior knowledge, easily learns the function for arbitrary number of qubits and achieves optimal mean squared error (MSE). Models that are ignorant to the structure of f fail to learn the function. The classical kernel k and the full quantum kernel overfit (they have low training error, but large test error). The biased kernel on the wrong qubit qw has litle capacity with the wrong bias and thus underfits (training and test error essentially overlap).
We now investigate the RKHS for reduced density matrices where V is a Haar-distributed random unitary matrix (proof in Appendix E).
Theorem 2. Suppose V is distributed according to the Haar measure on the group of unitary matrices. Fix m. Then the following two statements hold:
a) The reduced density operator satisfies with high probability PY: = 2- + 0(2-4/2) and the projected kernel satisfies with high probability an (x,x²) 2-m + O(2 d/2) as + co.
b) Let p.m. denote the linear integral operator for the kernel 4% as defined above. Then the averaged operator Ey [Ty.mm] has one eigenvalue 2 mm + 0 2d) whose eigenfunction is constant (up to higher order terms of order O22-2d) and 2 eigenvalues 2 mn + ((2
The averaged integral operator in the second part of the result is not directly meaningful, however gives some indication the behavior the operators TyM.. In particular, we expect a similar result to hold for most V if the mean embedding Pp is sufficiently mixed. A proof of this result would require to bound the variance of the matrix elements of f..m which is possible using standard formula for expectations of polynomials over the unitary group but lengthy.
Note that the dimension of the RKHS for the biased kernel 4% with m-qubits is bounded by 4t This implies that learning possible when projecting to sufficiently low dimensional biased kernels such that the training sample size satisfies Z 4th 2 dim(F).
Let us now focus on the case m that is the biased kernel is solely defined via the first qubit. Assuming that Theorem 2b) also holds for fixed V we can assume that the biased kernel has the form
q(x,x') = b (z, x') 7000(2))0(z)) + E (z)
(11)
where 7u = 1122 and (z) is the constant function up to terms of order O(2-20) 2d). For i = 1, 3 have 7i 0(2 d-1) = 0 (Fig. 2) and Φ; is function that conjectured to be exponentially hard in d to compute classically [48]. It is thus impossible to include a bias towards those three eigenfunctions classically. On the other hand we can include strong bias towards the constant eigenfunction also classically. The straightforward way to do this is to center the data in the RKHS (see Appendix for details).
Barren plateaus. Another conclusion from Theorem 2a) is that the fluctuations of the reduced density matrix around its mean are exponentially vanishing in the number of qubits. In practice value of the kernel would be determined by measurements and exponentially many measurements are necessary to obtain exponential accuracy of the kernel function. Therefore the theorem suggests that it is not possible in practice to learn anything beyond the constant function from generic biased

---

kernels for (modestly) large values of d. This observation is closely related to the fact that for many quantum neural networks architectures, the gradient of the parameters with respect to the loss is exponentially vanishing with the system size d, a phenomenon known as Barren plateaus [24, 49].
5
Experiments
Since for small d we can simulate the biased kernel efficiently, we illustrate our theoretical findings in the following experiments. Our implementation. building on standard open source packages [50, 51]. is available online." We consider the case described above where we know that the data was generated by measuring an observable on the first qubit, i.e., (x) Tr p M. but we do not know M", see Fig. 1. We use the full kernel i and the biased kernel q for the case m = 1. To show the effect of selecting the wrong bias, we also include the behavior of a biased kernel defined only on the second qubit, denoted as que As classical reference we also include the performance of radial basis function kernel kinr(z,, = exp(-Ilx x' /2)) For the experiments we fix a single qubit observable M = σ= and perform the experiment for varying number d of qubits. First we draw random unitary V. The dataset is then generated by drawing N = 200 realizations (zx(*)
[i=] from the d dimensional uniform distribution on [0, 2T]² - We then define the labels as y ef (x(") + c(t), where (x) = Tr T (z)o=]. e() is Gaussian noise with Var = 10-4, and is chosen such that Var[f(X)] = 1. Keeping the variances fixed ensures that we can interpret the behavior for varying d.
We first verify our findings from Theorem 2b) and Equation (11) by estimating the spectrum of g. Fig. (left) shows that Theorem 2b) also holds for individual V with high probability. We then use 2/3 of the data for training kernel ridge regression (we fit the mean seperately) with preset regularization, and use 1/3 to estimate the test error. We average the results over ten random seeds (random V. (1) e and results are reported in the right panel of Fig. 2. This showcases that as the number of qubits increases, it is impossible to learn f without the appropriate spectral bias. k and her have too little bias and overfit, whereas the has the wrong bias and severly underfits. The performance of que underlines that randomly biasing the kernel does not significantly improve the performance over the full kernel k. In the appendix we show that this is not due to a bad choice of regularization, by reporting cherry-picker results over range of regularizations.
To further illustrate the spectral properties, we empirically estimate the kernel target alignment [30] and the task-model alignment [32] that we introduced in Sec. 2. By using the centered kernel matrix (see App. B) and centering the data we can ignore the first eigenvalue in (11) corresponding the constant function. In Figure 3 (left) we show the empirical (centered) kernel target alignment for 50 random seeds. The biased kernel is the only one well aligned with the task. The right panel of Fig. shows the task model alignment. This shows that f* can be completely expressed with the first four components of the biased kernel, while the other kernels essentially need the entire spectrum (we use sample size of 200, hence the empirical kernel matrix is only 200 dimensional) and thus are unable to learn. Note that the kernel Iu is four dimensional, and so higher contributions correspond to functions outside its RKHS that it actually cannot even learn at all.
Discussion
We provided an analysis of the reproducing kernel Hilbert space (RKHS) and the inductive bias of quantum kernel methods. Rather than the dimensionality of the RKHS, its spectral properties determine whether learning is feasible. Working with exponentially large RKHS comes with the risk of having a correspondingly small inductive bias. This situation indeed occurs for naive quantum encodings, and hinders learning unless datasets are of exponential size. To enable learning, we neces- sarily need to consider models with a stronger inductive bias. Encoding a bias towards continuous functions is likely not a promising path for a quantum advantage, this is where classical machine learning models excel.
Our results suggest that data generating process and cannot efficiently encode this classically, yet are able use this information to bias the quantum model. We indeed observe exponential advantage in the case where we know that the data comes from a single qubit observable and constrain the RKHS accordingly. However,
only achieve quantum advantage if we know something about the

---

50-
1.0
Aligmment C()) C())
0.8
TaskeModel Task-ModdeAllgnmentt
30-
0.6
0.4
20
0.2
10
Knp/
0.0
0.0
0.2
0.4
0.6
0.8
1.0
10a
10'
10'
Kernel Alignment
Figure 3: Histogram of the kernel target alignment over 50 runs (left) and task model alignment (right) for 7.
find that evaluating the kernel requires exponentially many measurements, an issue related to Barren Plateaus encountered in quantum neural networks.
With fully error-corrected quantum computers it becomes feasible to define kernels with a strong bias that do not require exponentially many measurements. An example this kind was recently presented by Liu et al. [10]: here one knows that the target function is extremely simple after computing the discrete logarithm. A quantum computer is able to encode this inductive bias by using an efficient algorithm for computing the discrete logarithm.
However, for fully coherent quantum computers it is unclear how can reasonably encode strong inductive bias about a classical dataset (e.g., images of cancer cells, climate-date, etc.). The situation might be better when working with quantum data, i.c., data that is collected via observations of systems at a quantum mechanical scale. To summarize, we conclude that there is no indication that quantum machine learning will substantially improve supervised learning on classical datasets.
Acknowledgments and Disclosure of Funding
The authors thank the anonymous reviewers for their helpful comments that made the theorems and their proofs more accessible. This work was in part supported by the German Federal Ministry of Education and Research (BMBF) through the Tübingen AI Center (FKZ: O1IS 18039B) and the Machine Learning Cluster Excellence, EXC number 2064/1 Project number 390727645.
References
[1] John Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2:79, 2018.
[2] Frank Arute, Kunal Arya, Ryan Babbush, et al. Quantum supremacy using programmable superconducting processor. Nature, 574(7779::055-500, 2019.
[3] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter Love, Alán Spuru-Guzik, and Jeremy I. O'brien. A variational eigenvalue solver on photonic quantum processor. Nature Communications, 5:4213, 2014.
[4] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv:1411.4003 2014.
[5] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii. Quantum circuit learning. Phys. Rev. A, 98:032309, 2018.
[6] Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term processors. arXiv:1802 06002, 2018.
10

---

[7] 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 -enaannede feature spaces. Nature, 567(7777) 2019.
[8] Maria Schuld and Nathan Killoran. Quantum machine learning in feature Hilbert spaces. Phys. Rev. Lett., 122:040504, 2019.
[9] Jonas M. Kübler, Krikamol Muandet, and Bernhard Schölkopf. Quantum mean embedding of probability distributions. Phys. Rev. Research, 1:033159, 2019.
[10] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics, 1709)1013-1017, 2021.
[11] Maria Schuld. Quantum machine learning models are kernel methods. arXiv:2101.11022 2021.
[12] Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hart- mut Neven, and Jarrod R. McClean. Power of data in quantum machine learning. Nature Communications, 12(1):2631, 2021.
[13] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., (3S(15):50000 2009.
[14] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Phys. Rev. Letr., 1 113(1)) 2014.
[15] Nathan Wiebe, Daniel Braun, and Seth Lloyd. Quantum algorithm for data fitting. Phys. Rev. Lett., 109:050505, 2012.
[16] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum algorithms for supervised and unsupervised machine learning. arXiv:1307.041 2013.
[17] lordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares. Phys. Rev. A, 101:022316, 2020.
[18] Carlo Ciliberto, Andrea Rocchetto, Alessandro Rudi, and Leonard Wossnig. Statistical limits of supervised quantum learning. Physical Review A, 102(4), 2020.
[19] Gian Giacomo Guerreschi and Mikhail Smelyanskiy, Practical optimization for hybrid quantum- classical algorithms. vrXiv:1701.01450) 2017.
[20] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran. Evaluating analytic gradients on quantum hardware. Physical Review A, 99(3):03233,, 2019.
[21] James Stokes. Josh Izaac, Nathan Killoran, and Giuseppe Carleo. Quantum natural gradient. Quantum, 4:269, 2020.
[22] Ryan Sweke, Frederik Wilde, Johannes Jakob Meyer, Maria Schuld, Paul K Fährmann, Barthélémy Meynard-Piganeau, and Jens Eisert. Stochastic gradient descent for hybrid quantum- classical optimization. Quantum, 4:314, 2020.
[23] Jonas M. Kübler, Andrew Arrasmith, Lukasz Cincio, and Patrick J. Coles. An Adaptive Optimizer for Measurement-Frugal Variational Algorithms. Quantum, 4:263, 2020.
[24] Jarred R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9: 4812, 2018.
[25] Bernhard Schölkopf and Alexander J. Smola. Learning with Kernels. MIT Press, Cambridge, MA, USA, 2002.
[26] John Shawe-Taylor and Nello Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press, 2004.
[27] Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer. Effect of data encoding on the expressive power of variational guantu--machine-leanng models. Phys. Rev. A, 103:032430. 2021.

---

[28] Hsin- Yuan Huang, Richard Kueng, and John Preskill. Information-Hee -thoorettiitt bounds on quantum advantage in machine learning. Phys. Rev. Lett., 126:190505, 2021.
[29] Robert C. Williamson, Alexander Smola, and Bernhard Schölkopf. Generalization perfor- mance of regularization networks and support vector machines via entropy numbers of compact operators. IEEE Transactions on Information Theury, 47(6):2516-23322 2001.
[30] Nello Cristianini, Jaz Kandola, Andre Elisseeff, and John Shawe-Taylor. On kernel target alignment. In Dawn E. Holmes and Lakhmi C. Jain, editors, Innovations in Machine Learning: Theory and Applications, pages 205-256. Springer Berlin Heidelberg, 2006.
[31] Corinna Cortes, Mchryar Mohri, and Afshin Rostamizadch. Algorithms for learning kernels based on centered alignment. Journal of Machine Learning Research, 13(28):795-822 2012.
[32] Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature Communications, 12(1):2914, 2021.
[33] Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clement Hongler, and Franck Gabriel. Kernel alignment risk estimator: Risk prediction from training data. In NeurIPS, 2020.
[34] Bernhard Schölkopf, Ralf Herbrich, and Alexander J. Smola. A generalized representer theorem. In COLT, 2001.
[35] Thomas Hubregtsen, David Wierichs, Elies Gil-Fuster, Peter-Jan H. S. Derks, Paul K. Fachrmann, and Johannes Jakob Meyer. Training quantum embedding kernels on near-term quantum computers. arXiv:2105. 105.:2200500226. 2021.
[36] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010.
[37] Xinbiao Wang, Yuxuan Du, Yong Luo, and Dacheng Tao. Towards understanding the power of quantum kernels in the NISQ era. Quantum, 5:531, 2021.
[38] Evan Peters, João Caldeira, Alan Ho, Stefan Leichenauer, Masoud Mohseni, Hartmut Neven, Panagiotis Spentzouris, Doug Strain, and Gabriel N. Perdue. Machine learning of high dimen- sional data on a noisy quantum processor. arXiv:2101.09581 2021.
[39] Adrián Pélez-Sa Alba Cervera-Lierta, Elies Gil-Fuster, and José I. Latorre. Data re- uploading for universal quantum classifier. Quantum, 4:226, 2020.
[40] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick Coles. Variational quantum algorithms. Nature Reviews Physics, 3()):625-644, 2021.
[41] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, al. Noisy intermediate-scaae quantum 2021.
(nisq) algorithms.
[42] Leo Breiman. Random forests. Mach. Learn., 45(1):5-32, 2001.
[43] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
[44] Ingo Steinwart, Don R. Hush, and Clint Scovel. Optimal rates for regularized least squares regression. In COLT, 2009.
[45] Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least- algorithms. Journal of Machine Learning Research, 21 2020.
[46] Krikamol Muandet, Kenji Fukumizu, Bharath K. Sriperumbudur, and Bernhard Schölkopf. Kernel mean embedding of distributions: A review and beyond. Found, Trends Mach. Learn., 10(1-2):1-141, 2017.
[47] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, 2012.
12

---

[48] Aram W. Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549 (7671):203-20) 2017.
[49] M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature Communications, 12(1))1771, 2021.
[50] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, et al. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830 2011.
[51] Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, and Nathan Killoran. Pennylane: Automatic differentiation of hybrid quantum-classical computations. arXiv:1811.04900 2018.
[52] Vern I. Paulsen and Mrinal Raghupathi. An Introduction to the Theory of Reproducing Kernel Hilbert Spaces. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2016.
[53] Zbigniew Puchata and Jarostaw A. Miszezak. Symbolic integration with respect to the haar measure on the unitary groups Bulletin of the Polish Academy of Sciences: Technical Sciences, 65(No 1):21-27, 2017.
[54] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Phys. Rev. A, 80:012304, 2009.
13


Reviews:
[{"review_id": "zaWK3GfVQpD", "reviewer": "Reviewer_fXtY", "summary": "The paper investigates quantum kernels and learning with them, and whether it can be advantageous over using classical computations. A lemma is proposed which bounds the eigenvalues of the integral operator of a quantum kernel, and a theorem which shows how the empirical risk of the KRR solution with certain kinds of quantum kernels is bounded from below. Further, a biased quantum kernel is introduced for which the integral operators are also investigated. From these results (and experimentally verifying the last of them) the authors conclude that the advantage of learning with quantum kernels is restricted to very particular functions.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper introduces relevant analysis for the quantum machine learning community, showcasing that the very popular idea of quantum advantage in reality is not easy to achieve. This is very significant, and in this sense I would like to see this paper accepted.\n\nWhile for the most part the authors have made admirable effort to as simply as possible communicate the complicated contributions (e.g. introduced theorems and concepts are thoroughly discussed), this is not fully successful. Some details in the paper remain unclear to me (at the level of mainly focusing on the main paper but also taking quick looks to appendix trying to see if it would clear things up), but I would assume mostly due to undefined notation. However not being able to understand the theorem statements etc fully hinders the full understanding the paper, and as it is difficult to fully understand I'm slightly reserved in my acceptance recommendation.\n\n\nWhile I'm somewhat familiar with the concepts of quantum computation in machine learning, I am not very familiar with most of the literature there. Thus I cannot too accurately judge the novelty of the work and its relation to other quantum machine learning papers.\n\n\nComments and questions:\n\n- You at the beginning of your paper introduce the two measures to assess the quality of a kernel to learn a function. I was expecting to see them in your theoretical analysis, but it seems that instead they are only used in the experimental validation? \n- A comment about the measures to judge the quality of a kernel:  while having a high value on kernel target alignment to ideal kernel certainly indicates the good quality to learn f, it is very much possible that other kinds of kernels could be also reasonably good at the task even if they don't have a high alignment. On some easy learning problem RBF kernel can produce great results even if doesn't look like the ideal kernel. Could you comment if this has any impact on your analysis and conclusions? \n\n- Line 228, what is \\varphi? It has not been formally defined previously as far as I can see.\n\n- Line between 251&252 Tr_1 has not yet been defined - is this partial or block trace? Does the last equality follow from some property detailed e.g. in [1]? \n\n- Biased kernels: V just starts to appear (line 280) in superscript of \\rho without any further introduction; only later it is said that it is a Haar-distributed random unitary matrix but it doesn't really explain why they are used with \\rho. Nor does section 3 introduce such notation. Paragraph starting from line 227 introduces unitary tranformation V for the embeddings, but the notation in superscript is not used there either. Note: also Figure 1 uses this notation. \n\n- Theorem 1: \n  * line 266: what is k here? k has been the kernel function throughout the paper, now it's in the exponent. \n  * for all d >= d0 no function can be learned with KRR and d-qubit kernel. What if d is smaller than d0, what happens then? \n    -> it seems that you do not illustrate this theorem experimentally. While I realise that theorem 2 is more relevant to be illustrated mainly due to it not having a fixed V, it could be very illuminating to the reader to illustrate also this theorem. \n  * what is the formula for d_0? I did not see this laid out in appendix (and the proof is overall difficult to grasp quickly as the parts introduced in theorem statement were not explicitly used there; to me it seems that the reader has to fill many gaps.)\n  * Reading the theorem I can't help but think of deep neural networks, and other models with high number of parameters. Can we interpret that if d>=d0 then there are too many parameters for the restricted number of samples n for the function to be learned effectively? Or is my comparison completely faulty? \n\n- Figure 2: gamma0 is stated on line 311 to be 0.5+O(2^-d); why is this constant in the figure when the x-axis displays d? Is it derived from your choice of keeping variances fixed?\n\n- Abstract: \"we show that finding suitable quantum kernels is not easy because the kernel evaluation might require exponentially many measurements\" where is this shown? Something like this is discussed in paragraph \"barren plateaus\", but there it seems like kernel evaluation being costly is general knowledge. Or have I missed the assumption of requiring the measurements in some of the theorems?\n\n- Might I suggest that for a reader not too familiar with quantum kernels but very familiar with kernel methods otherwise a table in which all the relevant things about quantum kernels (i.e. RKHS, kernel function, feature mapping...) are thoroughly detailed. (I realise space constraints probably won't allow this to be added to the main part of the paper.)\n\n\n\n\nMinor comments (clear typos etc):\n- Is \"joint probability law\" and \"marignal law\" (i.e. with the term law) standard language in this setting? Line 81 & 82. To me at least it would be more natural to use \"distribution\" rather than \"law\". \n- First in line 95 K is used for kernel matrix; then in 101 and after that it is integral operator.\n- typo on line 235: bet->be\n- typo line 247 \"consists of all functionS\"\n- \"id\" as identity matrix should be introduced as notation. Why not use I?\n- Figures 2 & 3: left plot missing label for y-axis, Figure 2 left: it is not clear if the legend lists \"gamma\" or \"y\" (even if it can be deduced). Figure 2 right: are qw train and test on top of each other?\n- Line 341, here \"with high probability\" is probably not an exact mathematical statement (but these words can be used as such in some settings).\n- Line 346 \"have to little bias\" -> too little?\n- Line 377 \"Here\" no need for capital H\n\n\n[1] Filipiak et al, \"THE PROPERTIES OF PARTIAL TRACE AND BLOCK TRACE OPERATORS OF PARTITIONED MATRICES\", Electronic Journal of Linear Algebra, Volume 33, pp. 3-15", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of this work: according to authors end of section 4 and section 6. However to me especially section 6 sounds more like limitations of quantum machine learning based on the results obtained. In any case I find it very good that authors mention and highlight that in practice the kernel would need to be determined via measurements, which is not something they consider in their analysis or experiments. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "mEPfaKJtpWo", "reviewer": "Reviewer_J6gU", "summary": "The paper gives a general investigation of quantum kernel learning, where quantum computers are used to compute the kernel functions used in standard kernel learning problems. Several results are given characterizing the general behavior of quantum kernels, which together give useful guidance towards the design of effective kernels for specific problems.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Given the recent interest in quantum machine learning, with quantum kernel learning being an important special case of this, the (mostly negative) results given here are useful for researchers in the field to identify promising areas for further investigation. The results themselves are a bit scattered, but they are applicable to general quantum kernel learning problems. These results mostly come from a spectral analysis of the quantum kernel, which is usefully related to properties of the underlying embedding of data into quantum density operators, and are clearly and thoroughly explained in the paper. All theoretical results are proved in full detail in the supplemental material.\n\nA small collection of experiments are given which emphasize the utility of quantum kernels which are strongly biased towards specific problems, a fact which is justified by the theoretical results. The authors finally give a careful discussion about the impact of their results for further research in this area, which should be of interest to quantum ML researchers.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "ZVCnzZHqbF", "reviewer": "Reviewer_iZmY", "summary": "This article studies the learnability of functions using quantum kernels. More precisely, it investigates the potential advantages in learning that quantum kernels may offer compared to classical ones. The focus was put on ridge kernel regression as a running example of a learning task. In this case, the analysis boils down to two ingredients: 1) the spectral properties of the corresponding integration operator 2) the alignment of the function to learn with the first eigenfunctions of the integration operator. The contribution of this work is to highlight the fact that, under some assumptions, the class of functions for which quantum kernels would have an advantage over classical ones is very restricted: the functions that belong to RKHSs associated with the so-called biased kernels.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nOverall the article is well-written and tackles a crucial question in quantum learning theory. However, I believe that the conclusion is probably hasty since the analysis given in this work assumes that the kernel is separable:\n$k(x,y) = \\prod_{i \\in [d]} k_i(x_i,y_i)$. For this class of kernels, the eigenvalues are the product of the eigenvalues of the respective uni-dimensional kernels: the eigenvalues of the corresponding integration operator are arranged by “plateaus”. It seems that this arrangement of the eigenvalues is crucial in the argument of this work (Section C.2. from line 629 to line 635 in the appendix). It would be interesting to study the case of a non-separable quantum kernel (Matérn kernels constitute a family of classic kernels that are non-separable without being pathological).\n\n\n\nMinor observations: \n- In line 266, the letter k is already used for the kernel k. \n- In lines 717 and 718, I am not sure of the order in the inequalities since we assume that $n \\leq d^{k}$.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "EdWr9HWT3Fb", "reviewer": "Reviewer_X6Lb", "summary": "The paper presents the inductive bias of quantum kernels by analyzing their spectral properties. Specifically, their main theoretical results are that quantum kernels with too expressive RKHS will fail to generalize, and projected quantum kernels are a promising way to construct inductive biases that are hard to create classically.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThis paper is well written. It provides a clear perspective to present some problems faced by quantum kernel methods through the lens of the inductive bias by analyzing the spectral of the corresponding integral operator. \n\nWeakness:\nMy concerns lie in the following aspects about the two core theorems (Theorem 1 and 2):\n-I am very confused about condition   $n \\leq d^k$  in Theorem 1. First, I cannot find any clear definition of the notation \"$k$\". Is this a constant or a \"kernel\"? Second, in your proof, the usage of this condition seems to be unreasonable and even wrong. In particular, to ensure that the inequality in the bracket in the last row of the proof, the inequality \"$\\delta^{d/2} < \\epsilon n^{-4}/2$\" seems sufficient. Besides, the condition used in your proof is actually \"$n>d^k$\" instead of \"`$n<d^k$\" employed in Theorem 1.\n\n-In the proof of Theorem 3 (the first line of page 23), it is unclear why $\\lambda$ can be omitted in the derivation of inequality $\\|\\alpha\\|^2 \\le 2\\|y\\|^2$, as $K^{-1} \\le 2I_{n}$ cannot deduce $(K+\\lambda I_n)^{-1} \\le K^{-1}$ when $\\lambda$ can take any value. In the same place, the claim `for any $\\epsilon > 0 $ with probability $1-\\epsilon$ we have $\\|y\\|^2 \\le \\frac{n}{\\epsilon}\\|f\\|_2^2$’ is not obvious.\n \n-The conclusions and implications of Theorem 2 are arguable. Note that when $d$ grows, although the eigenfunctions are exponentially hard to compute classically, the eigenvalues and the projected kernel also exponentially tend to be a constant. Such a result can offset the quantum advantage brought by the eigenfunctions. \n\n-In addition, there should be some specific explanations or appropriate references in the analysis of Theorem 2. For example, there should be an appropriate reference for the statement “However, …, but a proof would require the evaluation of 8-th order polynomials over the unitary group”.    \n\nMinor issues:\n\n-the notation of kernel matrix and integral operator is the same.\n\n-there is no necessary label of the y-axis in Figure 2 and Figure 3.\n\n-the definition of $\\| \\cdot \\|_{HS}$ is not clearly given.\n\n-the subscript of $V_{\\alpha, \\alpha, j_1}$ in Eqn. (56) is confusing.\n\n-the subscript of $T_{\\alpha \\beta, \\gamma \\delta}$ in Eqn. (62) is confusing.\n\n-It should be $q_m^V(x, x’)=Tr[\\widetilde{\\rho}_m^V(x)  \\widetilde{\\rho}_m^V(x’)]$ in the introduction of `Biased kernels' in Page 8.\n\n-It should be $\\alpha=(K(X,X)+\\lambda id_{n \\times n})^{-1} y $ in the first line of page 23.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The results discussed in the submission can not be directly employed to solve practical learning tasks with provable quantum advantages. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is a consensus among the reviewers that this is a very strong theoretical analysis for the learnability of functions using quantum kernels. The results discovered poor learnability of quantum kernels which is similar to the “barren plateau” phenomenon in quantum neural networks and provided useful guidance towards the design of effective kernels for specific problems. In summary, the paper is helpful for understanding the power of quantum kernels, and I would like to recommend to accept this submission.
Decision: Accept (Poster)