Bandwidth Enables Generalization in Quantum Kernel Models
Authors: Abdulkadir Canatar
Evan Peters
Cengiz Pehlevan
Stefan M. Wild
Ruslan Shaydulin
Venue: Accepted by TMLR ()

Abstract: Quantum computers are known to provide speedups over classical state-of-the-art machine learning methods in some specialized settings. For example, quantum kernel methods have been shown to provide an exponential speedup on a learning version of the discrete logarithm problem. Understanding the generalization of quantum models is essential to realizing similar speedups on problems of practical interest. Recent results demonstrate that generalization is hindered by the exponential size of the quantum feature space. Although these results suggest that quantum models cannot generalize when the number of qubits is large, in this paper we show that these results rely on overly restrictive assumptions. We consider a wider class of models by varying a hyperparameter that we call quantum kernel bandwidth. We analyze the large-qubit limit and provide explicit formulas for the generalization of a quantum model that can be solved in closed form. Specifically, we show that changing the value of the bandwidth can take a model from provably not being able to generalize to any target function to good generalization for well-aligned targets. Our analysis shows how the bandwidth controls the spectrum of the kernel integral operator and thereby the inductive bias of the model. We demonstrate empirically that our theory correctly predicts how varying the bandwidth affects generalization of quantum models on challenging datasets, including those far outside our theoretical assumptions. We discuss the implications of our results for quantum advantage in machine learning.

Published in Transactions on Machine Learning Research (06/2023)
Bandwidth Enables Generalization in Quantum Kernel Models
Abdulkadir Canatar
comntarrffaiionnnsttttt.oo
Center for Computational Neuroscience Flatiron Institute
New York, NY 10010, USA
Evan Peters
cópeters@@uwnteello..c
Deportment of Physics
University of Waterloo
Walerloo, Onlario, N2L 3G1, Canada
Cengiz Pehlevan
cpehlevan www.wss..aaarr....oo edu
School of Engineering and Applied Sciences
Horvard University
Combridge, MA 0213, USA
Stefan M. Wild
wild@lbl.gov
Applied Mathematica & Computational Research Division Laurennce Berkeley National Laboratory
Berkeley, CA 94 720, USA
Ruslan Shaydulin
ruslun, ruslan shaydulin www.chsse.pppccccccccoco
Global Technology Applied Research JPMorgan Chase
New York, NY 10017, USA
Reviewed on OpenReview: https: // openreview. net/ formm? id- A1N2qp444
Abstract
Quantum computers are known to provide speedups over classical state-of-the-art machine learning methods in some specialized settings. For example, quantum kernel methods have been shown to provide an exponential speedup on a learning version of the discrete logarithm problem. Understanding the generalization of quantum models essential to realizing similar speedups on problems of practical interest. Recent results demonstrate that generalization hindered by the exponential size of the quantum feature space. Although these results suggest that quantum models cannot generalize when the number of qubits is large, in this paper show that these results rely overly restrictive assumptions. We consider wider class of models by varying hyperparameter that we call quantum kernel bandwidth. We analyze the large-qubit limit and provide explicit formulas for the generalization of quantum model that can be solved in closed form. Specifically, we show that changing the value of the bandwidth can take model from provably not. being able generalize to any target function to good generalization for well-aligned targets. Our analysis shows how the bandwidth controls the spectrum of the kernel integral operator and thereby the inductive bias of the model. We demonstrate empirically that theory correctly predicts how varying the bandwidth affects generalization of quantum models challenging datasets, including those far outside our theoretical assumptions. We discuss the implications of our results for quantum advantage machine learning.

---

Published in Transactions on Machine Learning Research (06/2023)
1 Introduction
Quantum computers have the potential to provide computational advantage over their classical counter- parts (Nielsen & Chuang 2011,, with machine learning commonly considered one of the most promising application domains. Many approaches to leveraging quanlum computers for machine learning problems have been proposed. In this work, we focus on quantum machine learning methods that only assume classical access to the data. Lack of strong assumptions on the data input makes such methods a promising candidate for realizing quantum computational advantage. Specifically, we consider an approach that has gained prominence in recent years wherein a classical data point is embedded into some subspace of the quantum Hilbert space and learning is performed using this embedding. This class of methods includes so-called quantum neural networks (Mitarai et al. 2018 Farhi & Neven 2018) and quantum kernel methods (Havličck et al.) 2019 Schuld& & Killoran 2019 Quantum neural networks are parameterized quantum circuits that are trained by optimizing the parameters to minimize some loss function. In quantum kernel methods, only the inner products of the embeddings of the data points are evaluated on the quantum computer. The values of these inner products (kernel values) are then used in a model optimized on a classical computer (e.g., support vector machine or kernel ridge regression). The two approaches are deeply connected and can be shown to be equivalent reformulations of each other in many cases (Schuld) 2021). : Since the kernel perspective is more amenable to theoretical analysis, in this work we focus only the subset of models that can be reformulated as kernel methods. A support vector machine (SVM) with a quantum kernel based on Shor's algorithm has been shown to provide exponential (in the problem size) speedup over any classical algorithm for a version of the discrele logarithum problem (Liu et al., 2021), suggesting that a judicious embedding of classical data inlo the quantum Hilbert space can enable a quantum kernel method to learn functions that would be hard to learn otherwisc. Quantum computers are also known to provide quadratic specdup for training a broad class of kernel models Li et al. (2019).
While the quantum kernels provide much larger class of learnable functions compared to their classical counterpart, the ability of quantum kernels to generalize when the number of qubits is large has been called into question. Informally, Kübler et al. (2021) show that generalization is impossible if the largest eigenvalue of the kernel integral operator is small, and Huang et al. (2021) h show that generalization is unlikely if the rank of the kernel matrix is large. The two conditions are connected since for a positive-definite kernel with fixed trace, a small value of the largest eigenvalue implics that the spectrum of the kernel is "flat" with many nonzero eigenvalues. Under the assumptions used by Kübler et al. (2021); 0: Huang et al. (2021). as the number of qubits grows, the largest eigenvalue of the integral operator gets smaller and the spectrum becomes "flat". Therefore, Kübler et al. (2021) Huang et al. (2021) conclude that learning is impossible for models with a large number of qubits unless the amount of training data provided grows exponentially with qubit count. This causes the curse of "exponential" dimensionality (Schölkopf et al. [002)] inherent in quantum kernels. However, Shaydulin & Wild (202)) show that if the class of quantum embeddings is extended by allowing a hyperparameter (denoted "kernel bandwidth") to vary, learning is possible even for high qubit counts. While extensive numerical evidence for the importance of bandwidth is provided, no analytical results are known that explain the mechanism by which bandwidth enables generalization.
In this work, we show analytically that quantum kernel models can generalize even in the limit of large numbers of qubits (and exponentially large feature space). The generalization is enabled by the bandwidth hyperparameter (Schölkopf et al., 2002 Silverman 2018) which controls the inductive bias of the quantum model. We study the impact of the bandwidth on the spectrum of the kernel using the framework of task-model alignment developed in Canatar et al. (2021), which is based on the replica method of statistical physics (Seung al. 1992; Dietrich et al., 1999 Mezard & Montanari 2009; Advani et al. 2013). While nonrigorous, this framework was shown to capture various generalization phenomenaa accurately compared with the vacuous bounds from statistical learning theory. Together with the spectral biases of the model, modkl alignment quantifics the required amount of samples to Icarn a task correctly. A "flat" kernel with poor spectral bias implies large sample complexities to learn each mode in a task, while poor lask-model alignment implies a large number of modes to learn. On an analytically tractable quantum kernel, we use this framework to show generalization of bandwidth-oquippel models in the limit of an infinite number of qubits. Generalization in this hnfnite-dimensionall limit contrasts sharply with previous results suggesting that high dimensionality of quantum Hilbert spaces precludes learning.
2

---

Published in Transactions on Machine Learning Research (06/2023)
Our main contribution is an analysis showing explicitly the impact of quantum kernel bandwidth the spectrum of the corresponding integral operator and on the generalization of the overall model. On toy quantum model, we first demonstrate this analytically by deriving closed-form formulas for the spectrum of the integral operator, and show that larger bandwidth leads to larger values of the top cigenvalue and to a less "flat" spectrum. We show that for an aligned larget function the kernel can generalize if bandwidth is optimized, whereas if bandwidth chosen poorly, generalization requires an exponential number of samples on any target. Furthermore, we provide numerical evidence that the same mechanism allows for successful learning for much broader class of quantum kernels, where analytical derivation of the integral operator spectrum is impossible. While our results do not necessarily imply quantum advantage, the evidence we provide suggests that, even with a compatible, well-aligned task, the quantum machine learning methods require a form of spectral bias to escape the curse of dimensionality and enable generalization.
2
Background
We begin by reviewing relevant classical and quantum machine learning concepts and establishing the notation used throughout the paper. We study the problem of regression, where the goal is to learn a target function from data. Specifically, the input is the training set D = "x" Ju= containing P observations, with x drawn from some marginal probability density function p : X - IR defined on X' C IR" and y produced by a target function f X as y = f(x).
Learning with kernels Given data in X' distributed according to probability density function p X'' - IR we consider a fmite-dimension
complex reproducing kernel Hilbert space (RKHS) H. and a corresponding feature map &b : X' + H. This feature map gives rise to a kernel function k(x, x') = (v²(x), (x))) The RKHS H associated with & is endowed with an inner product (s, satisfying the reproducing property and comprises functions/ f X' - R such that (f, < oc (Schölkopf al.) (002). Given a set of P data points x X, the positive semidefinite Gram matrix is defined elementwise by K,, = k(x", x*). The continuous analogue to the Gram matrix K is the integral kernel operator Ta: [x(x) (xt) defined according to its action:
(T&f)(x) = / k(x, ((xxx)(((()((xxd)
(1)
By Mercer's theorem (Schölkopf et al.) 2002), the eigenfunctions of T. satisfying Trox Th are or- thonormal (i.e., (or, Φ1) ŌKs), span (²)x), and give rise to eigendecomposition of h: given by x(x,')) Σx (x)) (x'), where {n&} are real-valued, nonnegative eigenvalues of the integral oper- alor due to its Hermilicity. The inner product (, in the RKHS of k may be computed with respect to the integral kernel operator of Eq. [ as (f.g)H = (f.Tx" 9)12(2), with the mull space of Ta ignored in computing T. From the kernel eigendecomposition, any target f E L2(X) that lies in the RKHS may therefore be decomposed as f(x)= = Σn (x), where ã = (J, dK)) are the target weights. We comment on the case where the target lies outside of the RKHS in Appendix C
Kernel ridge regression (KRR) is a convex optimization problem over functions that belong to a Hilbert space H and is stated as follows:
Σ (f*t) - 22) + A 1 JEHZ 2
f = arg min
(2)
where 1l denotes the norm with respect to the inner product (s defined on the Hilbert space and À 2 0 is the ridge parameter introduced for regularizing the solution.
Using these definitions, one can show that the solution to the regression problem takes the form f*(x = k(x) T (K + AI) y, where k(x) is a vector with elements k(x),, = k(x, x²) and y,, = y The kernel trick (Schölkopf et al. 2002) allows one perform regression without explicitly computing the features if one has access the analytical kernel function. While providing a rich class of kernels, quantum kernels are typically not expressible analytically and hence require explicit representations of the feature maps.
3

---

Published in Transactions on Machine Learning Research (06/2023)
Machine learning with quantum computers The central motivation for applying quantum computers to problems in machine learning is to leverage the ability of quantum systems to efficiently perform computation in a high-dimensional quantum Hilbert space. We consider quantum systems defined on n qubits whose dynamics may be described using complex-valued linear operators. A general quantum state on n qubits may be described by a positive definite 2n x 2n densily matric with unit trace and contained in the quantum Hilbert space H = {p p> 0, Tr(p) 1, E L(C²"), }}, where L(C4) denotes bounded linear operators of the form Cd + Cd or, equivalently, d x d complex matrices. H is endowed with the inner product (p, d') x given by the Hillert-Schmice inner product (A,
Br for A, E L(CC).
The dynamics of quantum states are described by applying linear operators to p. and we here will specifically consider unitary operations (represented by a 2" x 2" unitary matrix U). Then, the quantum states that we are interested in may be prepared by applying a unitary operator to the vacuum state [0), where the "ket" notation I.)) represents the jth standard basis vector ê in IR²".. When n 1, quantum states may be represented by the Bloch sphere: the constraints Tr(p) = and p= pt mean that the components of density matrix are parameterized by three real parameters be written in terms of Pauli matrices ē as p= _ (1+ n Ø). Since |||| S 1 is required for p Z 0 subject to Tr(p} 1, we can identify any single-qubit state P with a vector n in the unit sphere S c IR3. Similarly, any unitary operation acting on a single qubit may be represented as a sequence of rotations on the Bloch sphere (Nielsen& & Chuang 2011), thus making this representation convenient for visualizing feature maps associated with quantum kernels.
(Mz: Ry, 'z)) and the density matrix can
By associating the quantum Hilbert space with a feature space H. we can define a feature map that gives rise to quantum kernel (Havlfček et al. 2019 Schuld & Killoran| 2019 We consider a data-dependent unitary operator Ux) and prepare density matrix p(x) = U(x) (x (o (x)), where [0) (0) represents the
2" x 2d matrix with "1" in the top left corner and zeros elsewhere; later we discuss examples of how to construct data-dependent unitary operators. A natural choice for a feature map is then (xx) = p(x) with the corresponding inner product (p, p'yH = Tr(pp'] Under this feature map, the quantum kernel is defined as x') (vxx),, (xx)) = (r(p(x))(x') ). which inherits symmetry in its arguments from (s-) With this association between the feature map (xx and the quantum state p(x), we can freely apply existing theory for kernel methods in terms of complex vector spaces to study the spectra and generalization behavior of quantum kernels. In Appendix [ we provide further details on the theory of quantum states and kernels, such as construction of the RKHS from Hermitian linear operators (or observables) and the geometry and grobabilistic nature of quantum operations. In practice, quantum kernel method computes the kernel matrix entries on a quantum computer by evaluating the value of the observable (0) (0) on the state Uxx)U(x') 10) (0) (x')'
3 Motivating example: no generalization without bandwidth
Despite existing techniques for empirically evaluating the potential performance of quantum kernels on classical datasets (Huang et al.] 2021) and examples of successful implementation on currently available quantum computers (Glick et al. 2021 Peters et al., 2021 Wu et al.) 2021 Hubregtsen et al. 2021). it is often still unclear how to construct quantum kernel that will be suitable for learning real-world classical dataset. This uncertainty in the potential performance of quantum machine learning methods is compounded by regimes in which generalization is apparently impossible with a subexponential amount of training data. These regimes arise from the same feature of quantum computing that originally motivated quantum kernel methods: the availability of exponentially large feature spaces. In this section we discuss a simple example where the high dimensionality of the fcature space precludes learning with fixed quantum embeddings, and we show that the introduction of bandwidth enables generalization.
One example of how high dimensionality of the feature space precludes learning is provided by random feature maps. Given a feature map vb consisting entirely of independent and identically distributed Gaussian features, the operator Σ- = Ex(()]]] is proportional to the identity operator. Since Σ shares eigenvalues with Te of Eq. [ (Appendix AA), the eigenvalues of K concentrate around unity at a rate O(P-1/2) (Rosasco et al, 2010p. Analogously, we consider a quantum fcature map where states p(x) are prepared by 2" di-dimensional random unitaries Uxx), with the uniform distribution over unitaries being described by the Haar measure (e.g.. Collins & Nechita (0166)). Then, identifying a correspondence Σ - Bewe [p(x) s pT (x)) in the
4

---

Published in Transactions on Machine Learning Research (06/2023)
quantum case and applying standard results from measure theory, can directly compute the spectrum of Σ (Appendix Ap. This computation yields 22" + 1) nonzero eigenvalues with magnitude 21-x(2" + 1)-1, and thus the nonzero eigenvalues of K again become uniform as n + 30. Since the largest eigenvalue is exponentially small in n, generalization requires the number of data points to be exponentially large in n. The connection between the magnitude the largest eigenvalue and the required number of training samples can be seen directly from Kübler et al. (2021 Theorem 3), although it a straightforward consequence of many older results, for example, (Dietrich et al. 1999 [engiio et al., 2005 Liang et al., 2019 Bordelon et al,, 2020 Canatar et al., 2021). In other words, efficient generalization becomes impossible when the quantum feature map uses the full extent of the quantum state space uniformly. Our results demonstrate that the converse is true: restricting embeddings to smaller region of quantum state space recovers the possibility of efficient. learning.
3.1 Limitations of fixed quantum embeddings
To make the example concrete, consider the following learning problem. This learning problem and the failure of fixed quantum embeddings on it were considered in Huang et al. (2021 Supplementary Information 9). For an input x E {0, (0,x)" the goal is to learn a target function f(() = cos (((n)) where x:()) is the last element of the vector x. Since learning this function equivalent to learning the value of the last element of x, it is trivial classically, and simple linear regression succeeds. We now show how KRR with badly designed quantum kernel fails this trivial task, and we show how the introduction of bandwidth allows the KRR with quantum kernel to learn the target.
Consider a quantum kernel equipped with feature map
U(x())) = Rr (x(1)) cos (x0112)
isin x(01/2
(xx) = X j=1
(3)
isin (1( (2)0/22)
cos (200/2)
where X -- is the tensor product of single-qubit operations and (0) represents rotation of 0 about the z-axis of the single-qubit Bloch sphere (see Fig. [A). For this feature map, the embedding factorizes over qubits as p(x) = (0)) = - p(x(1), and
cos2(z11) /2)
ci (200)) /2) sin (2(01/2) (ini(x())) /2)
p(x(0))
(4)
icos( (z/11) /2) sin (z(ا)//
with the kernel given by
II cos² ((x5)- x000) 12)
x(x,x))= = Tr(p(x)p(x'))
(5)
While this kernel is obtained via quantum operations, the fact that it has a closed form expression makes it classically casy to simulate. Novertheless, it is a useful toy model (Kübler et al. 2021 Huang et al. 2021] for the analytical analysis of exponentially large quantum feat spaces. Since the input data x E {0, π }",, the kernel becomes a delta function: k(x,x')= = 8x,x. Therefore, any two points in the feature space p(x) and p(x') for x x' are orthogonal and the kernel cannot capture the correlations in data. KRR with this kernel simply memorizes the training set and cannot generalize to any target function with subexponential (in n)) training set size.
3.2 Bandwidth enables learning
The precoding example highlights how quantum kernel methods utilizing high-dimensional spaces can fail generalize. Our central technique for mitigating this limitation will be introduce bandwidth to quantum kernels (Shaydulin & Wild 2021). We reconsider the kernel with the feature map of Fq. 3 and introduce
5

---

Published in Transactions on Machine Learning Research (06/2023)
2
B
I:(x. x')
(x()
7(x)
y
64
44
(0) (cr)
Ry Re(crr))
2
('()
04
70x
y
C<1
x
A A quantum kernel method involves embedding data using a quantum circuit, often involving rotation by some angle about an axis. When angles are not rescaled properly, data can be embedded far apart in a space with dimensionality O(2") (Sec. 3) Similarly, Amax is suppressed as the mean embedding [x(] approaches the center of the Bloch sphere (Kübler et al. 2021). B High-dimensional feature space results in k(x, x') with narrow width (Eq. [ with n 50 and (top)
Figure 1:
(bottom) c 0.25) Tuning bandwidth escapes the "curse of dimensionality" associated with high-dimensional feature space. For 50 and f(x) = cos (50) quantum features that are nearly orthogonal result in a narrow kernel (c = 1, top)
and failure to generalize, while tuning bandwidth (c < 1, bottom) recovers KRR generalization performance.
scaling parameter [0, that controls the bandwidth of the kernel. The feature map and the kernel become
U(x(0) = Rs (czli).. 4(x, x') = II cos? ((x0)))2(0)) /2)
n
2=1
Geometrically, the factor e restricts features p(x) to smaller region of the Bloch sphere (Fig. [A]. Conse- quently, the kernel matrix is no longer diagonal, and we can straightforwardly chock that simply tuning c allows KRR with kernel Eq. e to generalize (see Fig. [3).
4 Effect of bandwidth on scaling and spectra
In the preceding section we provided a qualitative mechanism for how bandwidth improves the generalization of quantum kernels. We now analyze the expected generalization error quantum kernels equipped with bandwidth. We derive explicitly the spectrum of the bandwidth-oquinped quantum kernel with the feature map Eq. G and show how the bandwidth makes the spectrum less "flat," " thereby enabling learning. Our main tool the theory developed in Bordelon al. (2020); Canatar et al. (2021) where the generalization error, a function of the training set size, is analytically obtained from the eigenvalues of the kernel and the projection of the target function on the RKHS defined by the kernel.
4.1 Explicit formulas for generalization of bandwidth-equipped kernels
We consider the quantum kernel with the feature map given by Eq. 6 and the input distribution x Unif([- F| ), as previously studied by Kübler et al. (2021). For single qubit, the kernel becomes k(x, x') cos (a(x 22) with bandwidth parameter and the cigenvalues can be computed as follows
(see Appendix B
3
1 sinc sinc(2TTC)
1
Ag 1 1
\
+
+
V sinc(2 + (Gsinc(TT)2
sinc sinc(2Tc),
8
8
4
3
1
Ag
+
sinc (2TCC)
V(1 sinc(2rc)) + 16sino(Te))
A 0.
(7)
8

---

Published in Transactions on Machine Learning Research (06/2023)
For n-qubit system, the largest cigenvalue Mmax of the kernel in Eq. 6 falls exponentially with for a (1) and makes generalization impossible with P ~ poly(n) amount data (Kübler et al. 2021 (see Appendix. B To prevent Tmma decreasing with n, we choose a bandwidth that scales with (i.e., c c= an with a ~ (11) and a > 0). In Appendix B we show that a 2 2 is required for generalization. We consider
a = 1/2 henceforth. Then, all nonzero eigenvalues of the n-qubit kernel Eq. 6 can be expressed as X X Ag with 1 + l2 + h3 n, where the single-qubit cigenvalues asymptotically (with n) look like
a²m²
a an
1 22
A
6n
180n2
Starting from hn = n and 222 kg = 0, the hierarchy of eigenvalues obtained in this way are given in Table I We denote each of these eigenvalues as Ta,s and their corresponding eigenfunctions as (x,) where k indexes
Table 1: Hicrarchy of eigenvalues based on their scaling. N(n, k) denotes the degeneracy of eigenvalues with scaling n-k, and n, k) denotes the form of the corresponding eigenstates. Eigenstate |nt, k)
Degeneracy
N(n,k)
n 1
11/)) 8n 1 (1) ((11))())))))))) 1) (1/2)
(T)
n
n
(
+
1w)) 11)) (((=2) (1/2) 80 /10b)) 00(--)) ( 10,
m + (9)
1/ ((n33) (1/22)
603 (8b)) 00(m-2) 2) (wbbe (w/s)
n
the overall scaling of the eigenvalue and z indexes each of the individual eigenvalues with scaling n The degeneracy N(n, k) ~ (nn)) denotes the number of eigenvalues Te, ~ O(n ((n=*) for cach k. Notice that the quantity Thk= = N (n, k)),.== (1) with respect to the input dimension and its value depends on and k. For each k we will further make the approximation 17k. 7, for all pairs 2, 2' since the spectrum is almost flat at each scaling & (sce Figure A
We obtain the projections of larget function [(x) on the kernel eigenfunctions as ãx, f ((x))x,, ( (x)p(x))
We also define the total target power at each scaling az = Σ kn, az..- With the eigenvalues and the target weights 2R, the generalization error is given by CCanatar et al. 2021 (Appendix Ch:
=
K == x
Σ k
The
a T
(9)
(k+ )
K
(N a
where is the KRR regularization parameter, should be solved self-consistently, and we have defined ag Nm, Taking the large qubit and large data limit (n - and P + oo) while keeping aj (1)()) for some mode I (meaning P ~ On)))), the generalization error decouples across different scaling limits and becomes
P
x2
2 a
(an) =
2 a
(10)
1 1-7 7 (R amm)
k>!
k>!
The target modes with k > I remain unlearned since asot 0 and the modes k < I have already been learned using the provided data since agec = cc. This scaling defines learning stages where at each stage a single mode 7 is being learned, and the remaining modes contribute as constant error. The term in the perentheses goes to zero as aj + oo (see Appendix(C) Cp. Hence, when the mode is completely learned, the ratio of the generalization error to its initial value becomes Ex(ou=x)) = -Es,, (E, af). Therefore, given data
E,(0)
budget P ~ (n²), the quantum kernel is guaranteed to generalize to target functions whose weights beyond mode 1 are vanishing. The quantity C(I) 1 E, (a==so) called the cumulative power (Canatar al. 2021
(0)
describes the amount of power placed in the first modes and quantifies the task-model alignment.
It was shown in Canatar et al. (021)) that kernels generalize better for target functions with sharply rising C(I). In our case, for generalizability at P ~ O(n') samples, it is necessary but not sufficient. condition for
7

---

Published in Transactions on Machine Learning Research (06/2023)
target functions to have good task-model alignment for which C(I) 1. Note that the trace of this kernel is [xx, x x))((x)xx 1, and therefore the eigenvalues satisfy ΣR,= 0,, = 1. Flatness of the spectrum, then, implies 1/k,a ~ ()3 since there are 3 nonzero modes of the kernel in Eq. 6 (see Appendix B Equation 9 suggests that even if the target is aligned well with the kernel, it requires P (33)) samples to learn each mode, and so generalization becomes impossible with polynomial sample complexity P ~ O(n').
On the other hand, bandwidth enables sufficient decay in the spectrum of the kernel, and Eq. showws that P O(n') samples yield an excess generalization error Eg ~ 11-100 C(). In Figure 2 we show the results of simulating the kernel of Eq. 6 with 40 qubits for a target function given by f(x) E --Ixll//v' For 1, the kernel has a flat spectrum (Figure 2 with poor alignment with the task (Figure 2B). On the other hand, bandwidth introduces sufficient decay in the eigenspectrum so that polynomial time learning becomes possible. Surprisingly, bandwidth also improves the task-model alignment which, together with spectral bias, implies generalizability with better sample efficiency. In Figure 22, we perform kernel regression with our toy kernel and confirm that generalization improves with bandwidth up an optimal value after which it degrades again. This is due to the fact that larger bandwidths cause underfitting of the data. (Silverman 2018) since only a very few eigenmodes become learnable while the largel cannot be fully explained by those modes. In Figure 2 we find that the optimal bandwidth parameter is e² R
2 (see Appendix F
A 10"1
B
30"
C 10f
10-3.
10"
10-2
10
10-1.
c- 1.00
e- 1:00
C.-1000
10%
== 0.10
e- 0.10
10
<=
0.10
10-1.
0.05
poly(1=)
10-3
é 0.00
10-9.
0.05
0.03
10.2.
10-1
10-10
10
10ft
10
167
k
P
Figure 2: A Eigenvalues of the kernel Eq. with respect to data x Unif([->, m)))). Learnability is explained by the preservation of large-eigenvalue eigenspaces; without bandwidth, the model provably cannot. learn in poly(n) complexity due the flat spectrum. B The projections of the target f(x) = e eigenvectors of the kernel for each bandwidth. Apart from the flatness of the c kernel, its cigenfunctions align poorly with the target. C Generalization error function of the number of training samples compuled by using theory (solid lines) (Eq. 9 and performing kernel ridge regression empirically (dots). Bandwidth c= 1 yields a constant learning curve. While all c < kernels provide improvement, an optimal bandwidth parameter ex = 2/n gives the best mask- alignment.
on the
4.2 Evidence of performance gains in real datasets
To evaluate our theory in practical setting, consider two previously proposed quantum kernels that have been conjectured to be hard to simulate classically: a kernel with feature map inspired by instantaneous
quantum polynomial-time (TQP) circuit (Shepherd & Bremner 2009 Havliček et al. 2019 Huang et al. 2021
and a kernel with Hamiltonian evolution (EVO) feature map (Huang et al. 2021 Shaydulin & Wild 2021
(see Appendix E for details). Unlike the kernel considered in the preceding section, the spectrum cannot be derived analytically for these kernels.
We evaluate these kernels on binary classification versions of FMNIST (Xiao al. 2017), KMNIST Clanuwat/ et al. 2018), and PLAsTiCC (The PLASTICC team et al.) 2018) datasets with the input data downsized
to 22 dimensions, which were previously used to evaluate quantum kernel performance in Shaydulin & ; Peters et al. ). We use the kernel values reported in Shaydulin & Wild (202 which were evaluated with high precision using an idealized (noiseless) simulator. In practice,
Wild (2021) ; Huang et al. (2021);
an additive error is introduced when evaluating the kernel values on a fault-tolerant quantum computer. Bandwidth-oquippod kernels are robust against this error; see the discussion in /Shayuuinn Wild (2021). We perform SVM for binary classification using these kernels with varying bandwidths. In Table 2 we report the test. accuracies with bandwidth parameter c for the TQP and EVO kernels. We also report the test.
8

---

Published in Transactions on Machine Learning Research (06/2023)
performance with bandwidth parameters c' < optimized by hyperparameter tuning for each kernel using cross validation (see Appendix
F
For both kernels, bandwidth significantly improves the test performance.
IQP
EVO
Random Guess
e²
C
e*
1
FMNIST
0.926
0.542
0.916
0.643
0.5
KMNIST
0.915
0.629
0.914
0.600
0.5
PLASTICC 0.789
0.5
0.788
0.613
0.5
Table 2: Bandwidth tuning recovers significant performance gains out-of-the-box quantum models, opening up the possibility of better workflows for general quantum machine learning many qubits via hyperparameter tuning.
To test our intuition, we present Fig- BA the shape of the IQP kernel where the kernel clearly sharpens for larger values of bandwidth parameter implying flat spectrum. In Fig. 33, we further confirm that the spectrum decay improves with bandwidth when the IQP kernel is evaluated on the FMNIST dataset. We also find that the task-model alignment improves greatly with the bandwidth (Fig. 3C), thus implying, together with the previous point, possible generalization.
A 1C
C 1.0
10
0.01
0.6
0.1
10-1
0,5
0.4
0.5
10-7
1.0
0.2
10-12
0.6
-1.0
-0.5
11.0
0.5
1.0
10
10
10
10'
107
10'
13
Figure 3: A IQP kernel function example: Intuitive behavior of bandwidth persists when quantum kernel is not strictly shift-invariant. B TQP with the addition of bandwidth is capable of recovering significant target alignment with FMNIST dataset. C While the spectrum for IQP is flat, it also has poor alignment with the target (see Appendix
5 Related Work
Huang et al. 2021 introduce the idea that the exponential dimensionality of quantum feature spaces precludes gencralization of quantum kernel methods, and they provide an upper bound on genoralization error that includes the dimension of the space spanned by the training set. They connect their results to the spectrum of the kernel by introducing a measure of "approximate dimension" of the span of the training set given by E - Em= where (4 are the eigenvalues of the n kernel matrix. This number is effectively a measure of the flatness of the spectrum of the kernel and is used numerical experiments in Huang et al. (202T). An alternative analysis is given by Banchi et al. (2027), who derive bounds on generalization error using quantum information techniques and show that ncar-identity kernels resulting from large dimensionality of the feature space preclude generalization. We use the construction from Huang al. 2021 Appendix I) motivating example in Sec.
Kübler et al. (2021) introduce techniques for deriving the spectrum of quantum kernels and obtain the
spectrum of the kernel Eq. 5 They then use these techniques to show that the purily of the mean embedding provides an upper bound on the largest eigenvalue the quantum kernel integral operator and consequently that quantum kernel methods with feature maps that utilize the full quantum Hilbert space require an exponential number of qubits of data learn. However, Kübler et al. (2021) did not consider bandwidth as a method for controlling the inductive bias of quantum kernels. Our contribution is using the techniques of

---

Published in Transactions on Machine Learning Research (06/2023)
Kübler et al. (2021) to derive the spectrum of the bandwidth-equipped kernel Eq. 6 and explicit formulas for the expected generalization error.
Inspired by the bandwidth hyperparameter of classical radial basis function kernels, Shaydulin & Wild (2021 introduce the concept of quantum kernel bandwidth and provide mumerical evidence that bandwidth tuning (equivalent to rescaling of the input data) improves the generalization of SVM with quantum kernels. An analogous mechanism has been observed to improve trainability of quantum neural networks (Zhang et al,
2022]. However, previous results make no connection between the bandwidth and the spectrum of the kernel and provide analytical results for generalization. We reinterpret the data from Shaydulin & Wild (001 in Sec. 4.2 and show how the bandwidth controls the spectrum of the kernel and enables generalization.
6 Discussion
In this work, we studied the kernels induced by quantum feature embeddings of data and their generalization potential. Recent work suggests that machine learning models built in this way suffer from the curse of dimensionality, requiring exponentially large training sets to learn. Note that embedding n-dimensional data requires at least n qubits (where n ~ 100 for standard datasets) which span a 2" dimensional feature space. While quantum models may possess potentially powerful and classically inaccessible representations for certain tasks, utilization of those necessarily requires control over the large space they span in order to generalize.
Here we showed that the bandwidth hyperparameter enables generalization of quantum kernel methods when the numbers of qubits is large, and provided explicit formulas for the resulting expected generalization error on a toy model. Our results open up promise for quantum machine learning beyond intermediate numbers of qubits. A central lesson provided by our work that thoughtfully chosen hyperparameters can significantly improve the performance of quantum machine learning methods. Identifying such hyperparametors that control the inductive bias of quantum models is essential to realizing the full potential of quantum machine learning methods.
Unlike prior works, we focus not just on the spectrum of the quantum kernel but on the alignment between the kernel and the real-world datasets. Our empirical results imply that scaling the bandwidth not only makes the spectrum less flat, but also improves the alignment with real-world target functions. These observations make us optimistic about the potential of quantum kernel methods to solve classically challenging problems.
An important limitation of our results is that while bandwidth scaling guaranteed to improve the spectrum, it does not necessarily lead to good aligument. For example, in the limit of c -> the spectrum has only one nonzero eigenvalue, although learning is still not possible (see Appendix D). This suggests that optimizing bandwidth as hyperparameter during training can balance triviality of the feature map (c + 0) with greater utilization of the quantum state space. At the same time, if the feature map is chosen poorly, varying bandwidth would not lead to good generalization.
If the kernel values are evaluated on a noisy quantum computer, the quantum hardware noise would affect the spectrum of the kernel. Hardware noise reduces the purity of embedding, leading to a trivial lower bound generalization error from Kübler et al. (2021 Theorem 1). Heyraud et al. (2022) and Wang et al. (2021 give a more detailed analysis. While outside the scope of this work, the impact of noise on generalization is nonetheless an important consideration for near-term prospects of quantum kernel methods.
Acknowledgments
Funding in direct support of this work: U.S. Department of Energy (DOE), Office of Science, Office of Advanced Scientific Computing Research AIDE-QC and FAR-QC projects and by the Argonne LDRD program under contract numbers DE-AC02-05CH1123 and DE-AC02-06CH113577 computing resources provided on Bebop, a high-performance computing cluster operated by the Laboratory Computing Resource Center at Argonne National Laboratory. AC and CP were supported by an award from the Harvard Data Science Initiative Competitive Research Fund.
10

---

Published in Transactions on Machine Learning Research (06/2023)
References
Héctor Abraham, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, Thomas Alexander, G Alexandrowics, E Arbel, A Asfaw, C Azaaustre, P Barkoutsos, G Barron, et al. Qiskit: An open-source framework for quantum computing. URL httpss//doi. 1w/10.5521/zemoode 2562111, 2019. doi:
Madhu Advani, Subhaneil Lahiri, and Surya Ganguli. Stalistical mechanics of complex neural systems and high dimensional data. Journal of Statistical Mechanics: Theory and Experiment, 2033(03) 2013.
/2044/88/01////// 201////0013////// /003/3301//. doi: 10.1088/ 1742-5468/2200
Leonardo Banchi, Jason Pereira, and Stefano Pirandola. Generalization in quantun machine learning: A 2.0403...
quantum information standpoint. PRX Quamlum, 2(4), November 2021. doi: 10.
URL /ttpps:/ddi..rr// http:///ooooooogg1.11111aapppppp 11wppp/uua.///pmuuuuuum.mmmm 2. 040321
Yoshua Bengio, Olivier Delalleau, and Nicolas Te Roux. The curse of dimensionality for local kernel machines. Technical Report TR- 1258, Université de Montréal, March 2005. URL https://www.microsofff careeeucreeeeooe of en- ma-us/resse mee-us//esoaarcaapubbaaaioooooo http://eeeecceeeeeooeoooooooaaaa orgpapssooaaaattooooooooooa---a-
local -eree--mcchln-eees
Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel
regression and wide neural networks. In International Conference on Machine Learning, pp- 1024-1034.
1-12, 2021. doi: httpp///ppeeeiieiee..pp////////p
PMLR, 2020. URL https://proceedings. .ml.iiinnnmmmrr......m.m.. mlr wttpppess//111////reeolllaaaa.a
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):
Tarin Clanuwat, Mikel Bober-Irizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha.
Deep learning for classical Japanese literature. arXim:1812.017/1 2018. doi:
Benoît Collins and lon Nechita. Random matrix techniques in quantum information theory. Journal of Mathematical Physics, 57(1):115 January 2016. doi: 10.1063/1.4936688
Rainer Dietrich, Manfred Opper, and Haim Sompolinsky. Statistical mechanics of support vector networks. Physical Review Lellers, 82(14):2975, 1999. doi: 10. (0.100//hhysReeeLee......2
Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term processors. 1xXix:1802.000 06002, 2018. doi: 10.48550/ar 180.00002.
Jennifer R. Glick, Tanvi P. Gujarati, Antonio D. Corcoles, Youngseok Kim, Abhinav Kandala, Jay M. Gambetta, and Kristan Temme. Covariant quantum kernels for data with group structure. arXiu:105.03400, 2021. doi: 10.48550/ (0.48550/arXiv.211 aariiv2205.000
Vojtěch Havlič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(7777): 909-212, March 2019. doi: 00.1088/441586-019-000
Valentin Heyraud, Zejian Li, Zakari Denis, Alexandre Le Boité, and Cristiano Ciuti. Noisy quantum kernel machines. arXiv:2204.120 12192, 2022. doi:
Zoö Holmes, Kunal Sharma, M. Cerezo, and Patrick J. Coles. magnitudes and barren plateaus. PRX Quantum, 3(1), Jamuary 2022. doi: 10.1 1tt/3//rxuuunuu..000000 3.000333....
Connecting ansatz expressibility to gradient
Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R. McClean. Power of data in quantum machine learning. Nature Communications, 12(1), May 2021. doi: 00.1088/s11477-021222000
Thomas Hubregtsen, David Wicrichs, Elies Gil-Fuster, Peter-Jan S. Derks, Paul K. Fachrmann, and Johannes Jakob Meyer. Training quantum embedding kernels on near-term quantum computers. arXin:2105.02276, 2021. doi: 10.48550//rxiv.21055 2100000000....
11

---

Published in Transactions on Machine Learning Research (06/2023)
Jonas Kübler, Simon Buchholz, and Bernhard Schölkopf. The inductive bias of quantum kernels. Advonces in Newral Information Processing Systems, 34, 2021. URL htttp:://proceeddnngg www..nnnrrpp.... wwt.:/pp....pppprreeeeepppt pttppp..ccppppp//2221///
pdf
Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu. Sublinear quantum algorithms for training linear and
kernel-based classifiers. In International Conference on Machine Learning, pp. 3815-3824. PMLR, 2019.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels. arXic: 1002110881,022, 2019. doi: 10.48550/arXiv. 205
Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust quantum speed-up supervised machine learning. Nature Physics, 17(9):1013 1017, July 2021. doi: 10.1038/441167:021--013777
Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communiications, 9(1), November 2018. doi: 11-103//$11467-08--7709990
M. Mezard and A. Montanari. Information, Physics, and Computation. Oxford University Press, 2009. doi: N0.1008/cproo::ooo// 99775990777777999777777777777737 98570837.001.000 0007700000.0000...
K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii. Quantum circuit learning. Physical Review A, 98(3),
September 2018. doi: 10.1103/ 1..103/physreva.90 pwwsreva.98.0323000 08.3330..
Michael A Nielsen and Isaac L Chuang. Quantum Compulation and Quantum Informalion. Cambridge University Press, 2011. doi: 10.
Evan Peters, João Caldeira, Alan Ho, Stefan Leichenauer, Masoud Mohseni, Hartmut Neven, Panagiotis Spentzouris, Doug Strain, and Gabriel N. Perdue. Machine learning of high dimensional data on a noisy quantum processor. npj Quantum Information, 7(1), November 2021. doi: 111128//4113344-0-000044488
Zbigniew Puchala and Jaroslaw Adam Miszezak. Symbolic integration with respect to the Haar measure the unitary group. Bulletin of the Polish Academy of Sciences: Technical Sciences, 65(1):21 27, 2017. doi: 10.1515/bpasts- 2ttpl///bpaass2217-000...
2017-0003.
Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integrall Journal of Machine Learning Research, 11(30):905-95) 934, 2010. URL http://hhh...o.oo//../////////aa ott.a//g.///aaa...oo///paa/////a
Bernhard Schölkopf, Alexander Smola, Francis Bach, et al. Learning with Kernels: Support Vector Machines,
Regularization, Optimization, and Beyond. MIT Press, 2002. doi: 10.7551 /miitpress/4175.001.000
Maria Schuld. Supervised quantum machine learning models are kernel methods. arXiv:2101. 10tt21111.100000 2021. doi: 00.48550/a2Xiv.210..0
Maria Schuld and Nathan Killoran. Quantum machine learning in feature Hilbert spaces. Letters, 12)(4)) February 2019. doi: www.:///pysseelett..1. 120.0000
Physical Review
H. S. Seung, H. Sompolinsky, and N. Tishby. Statistical mechanics of learning from examples. Physical Review A, 45:6056-6099 6091, Apr 1992. doi:
J. Shawe- Taylor, C.K.I. Williams, N. Cristianini, and J. Kandola. On the eigenspectrum of the Gram matrix and the generalization error of kernel-pca. IEEE Transactions on Information Theory, 511))2250--252, 2005. doi: 10.1109/TIT.2005 Ttt.:/TT..2200021111 2005.85005..
Ruslan Shaydulin and Stefan M. Wild. Importance of kernel bandwidth in quantum machine learning.
arXiv:2111.05451 2021. doi: 10.48550/ /ataaarxii..1...0/
Dan J. Shepherd and Michael J. Bremner. Temporally unstructured quantum computation. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 465:1413-148 2009. doi: 10.1098/rspa.. /t.109//sppa.2208.04433
Bernard W Silverman. Densily estimation for statistics and data analysis. Routledge, 2018.
12

---

Published in Transactions on Machine Learning Research (06/2023)
Supanut Thanasilp, Samson Wang, M. Cerezo, and Zoë Holmes. Exponential concentration and untrainabilityy in quantum kernel methods. ar Xrv::22008. 1 11060, 2022.
The PLAsTiCC team, Tarek Allam, Anita Bahmanyar, Rahul Biswas, Mi Dai, Lluís Galbany, Renée Hložek, Fmiile F. O. Ishida, Saurabh W. Jha, David O. Jones, Richard Kessler, Michelle Lochner, Ashish A. Mahabal, Alex I. Malz, Kaisey S. Mandel, Juan Rafacl Martinez-Galares Jason D. McEwen, Daniel Muthukrishna, Gautham Narayan, Hiranya Peiris, Christina M. Peters, Kara Ponder, Christian N. Setzer, The LSST Dark Energy Science Collaboration, The LSST Transients, and Variable Stars Science Collaboration. The photometric LSST astronomical time-scries classification challonge (PLAsTICC): Data set. 1rXiv1180.00000 2018. doi: 10.48550/ /tt///avvvvv..i00..... 1810.00001.
Xinbiao Wang, Yuxuan Du, Yong Luo, and Dacheng Tao. Towards understanding the power of quantum kernels in the NISQ era. Quantum, 5:531, August 2021. doi:
URL https
//doi.org/10. 10. 22231/--221--8-300-3
John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. doi: 10.1017/
9781316848142.
Sau Lan Wu, Shaojun Sun, Wen Guan, Chen Zhou, Jay Chan, Chi Lung Cheng, Tuan Pham, Yan Qian, Alex Zeng Wang, Rui Zhang, Miron Livny, Jennifer Glick, Panagiotis Kl. Barkoutsos, Stefan Woerner, Ivano Tavernelli, Federico Carminati, Alberto Di Meglio, Andy C. Y. Li, Joseph Lykken, Panagiotis Spentzouris, Samuel Yen-Chi Chen, Shinjae Yoo, and Tzu-Chieh Wei. Application of quantum machine learning using the quantum kernel algorithm on high energy physics analysis at the LHC. Physical Review Research, 3(3), sep 2021. doi: 10.1103/ 10..:0//pp/yyssereeeerrr.h p 3.332211.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: novel image dataset for benchmarking machine learning algorithms. arXiv: 10.11008.0711 07747, 2017. doi: 10.48550/arXiv.I1i arXiv.1708.07747.
Kaining Zhang, Min-Hsiu Hsieh, Liu Liu, and Dacheng Tao. Gaussian initialization help deep variational quantum circuits escape from the barren plateau. 1:Xf::2203.09370 2022. doi: 10.48550/ar aavv (tt.X/i.22330977777
Disclaimer
This paper was prepared for information purposes with contributions from the Global Technology Applied Research center of JPMorgan Chase. This paper is not a product of the Research Department of JPMorgan Chase or its affiliates Neither JPMorgan Chase nor any of its affiliates make any explicit or implied representation warranty and none of them accept any liability in connection with this paper, including, but not limited to, the completeness, accuracy, reliability of information contained herein and the potential legal, compliance, tax accounting effects thereof. This document is not intended investment research or investment advice, or a recommendation, offer or solicitation for the purchase or sale of any security, financial instrument, financial product or service, or to be used in any way for evaluating the morits participating in any Iransaction.
13

---

Published in Transactions on Machine Learning Research (06/2023)
A Review of Classical and Quantum Data Operators
Here we discuss covariance operators and integral kernel operators for two types of data: classical real-valued vectors and fiiiteddimensional complex Hermitian operators. The goal is to relate the spectra of these operators order to better understand how feature maps and distributions of input data combine to allect. the learnability of a distribution.
Given symmetric positive semidefinite kernel function k. X X R, the integral kernel operator Te (x) + (22())) is defined according to its action on f'E (22)
(Txf)xx) S k(x, ((xxx (((
(A.1)
A quantum kernel is defined as the inner product of two quantum states,
xxx,x') = p(x')) Tr(p(x)p(x') = Vec (p(x)) Vec (p(x')),
where we have introducod the vectorization map (c.g., Watrous (2018) Vee L(C + Cd. which stacks rows of d x d matrix into d2 1 column vector and where L(C") denotes the space of linear operators of the form Cd Cd, Throughout this section we will consider d-dimensional quantum states and operations (where d = 2 in the case of n qubits). We will frequently use the identity
Vec (A)* Vec (B) = (A, = (T(AAB)
VA,
Observing that the RKHS of kernel defined (see, e.g., Schuld 2021)) by functions of the form f(x) (p(x), H),
we can rewrite Eq.
A.1
as
(Tef)(x)= = Vec (p(x)) / Vec (p(x') Vee (p(x')) Vec (H)) u(dx')
= (Vec (p(x)) E Vec (H)),
(A.2)
where we have defined the covariance operator,
== / Vec (p(x')) Vee (o(x')) p(dx') = / p(x') @ p(x'''
(A.3)
and the last equality in Eq. A.2 holds whenever the quantum embedding is a pure state (i.e., p(x) (1x(() for some (x))) We can intuitively understand this operator by analogy to lincar feature maps: If we consider v-dimensional real-valued input vectors x E X C R" and assume are centered such that Ex(x] 0, then the covariance operator is defined as Σ = Ex[xx]] such that (E)a E[m,,,,)- Equation A.3 therefore describes kind of quantum covariance operator, although this is an imperfect analogy since a centered quantum feature map [Ex[p(x)] = 0) would violate the requirement Tr(p(x)) = 1.
We are interested the eigenvalue equations
Vec (H) 1) Vec (H) (x))) = 170(x).
Given the operators defined in Eq. A.1 and Eq. A.3 one may verify (see, e.g., Shawe-Tayloo et al. (2005) that the following statements hold under the identification vb(x) Vee (p(x)) described above.
(S1) For every eigenfunction & satisfying (T))) = n)((x), there is a corresponding eigenvector Vec (H) of Σ given by
Vec (H) / o(x) Vec (p(x)) u(dx)
such that E Vee (H) 1) Vee (H). Furthermore, from the bijectivity of the Vee operation and the fact that Hermiticity is preserved under convex combination, it follows that H is Hermitian.
14

---

Published in Transactions on Machine Learning Research (06/2023)
(S2) For every eigenvector Vec (H) of E satisfying Σ Vec (H) 1j Vec (H), there is corresponding eigenfunction of T& given by
<(x) Tr(p(x)H} Vec (p(x)) Vec (H)
such that (Txo)(x) = 1)((x)).
(S3) Assuming that eigenfunctions @x of T3 indexed by eigenvalue nn are orthonormal,
(0x. ( = S (x(xx" (x)) òg1,
the eigenvectors Vec (H₂) of E indexed according to eigenvalue satisfy
Vec (H&)) Vee (Hi) (I((H(e)) 77 Ods
whenever Th > 0 (when ? 0, we may safely ignore Vec (H&) in the null space of Σ).
Letting spec (A) denote the sequence of eigenvalues of an operator A sorted in nonincreasing order, it then follows from (S1) and (S2) that
spec (Tk) spec (E).
The meon embedding is defined as the average state with respect to distribution over A::
Pμ 1 p(x))((dx)
As shown in Kübler et al. (2021, Lemma 1), the inequality 7max (E) S v Tr(px provides bound for the largest eigenvalue of E. Let be the Bloch vector for Pe defined on qubits, which can be parameterized as
n (sin f cos sin sin d, cos の)
(A.4)
Then Tr p/ = (1+ /// This provides geometric argument for the use of bandwidth in single-qubit system (or product thereof). For instance, consider each shaded region in Fig, DA representing the subspace spanned by quantum states associated with the feature map giving rise to k. Then we have that the maximum eigenvalue of Σ is suppressed like Tmaax < (1 + ||nl|3)1/2/
as the centroid n of each region (representing Pu) approaches the center of the Bloch sphere. By limiting bandwidth (and therefore restricting the shaded region Fig. B to polar cap of the Bloch sphere), the upper bound on Tmma (E) is lifted, and the possibility of learning on data is restored.
A.1 Spectrum of random quantum embedding
A foundational observation for this work is that using a kernel associated with a feature map that completely utilizes high-dimensional feature space leads to poor learning guarantees due to the flatness of the corresponding spectrum. Here, we present extreme (and somewhat contrived) example where quantum feature map associated with random state vectors lcads to a flat kernel spectrum. We assume the existence of a data distribution and feature map x + (0))))) (x) for which unitaries U(x) are sampled uniformly over the space of n-qubit unitaries U(2"). Such a distribution may be achieved by sampling uniformly with respect the Haar mcasure j(dU) (c.g., [ollins & Nochita (2016). As described Rosasco et al. (2010) Proposition 9), the spectrum of concentrates around the spectrum of E. We therefore explicitly compute the spectrum of E corresponding to random quantum features. Using standard results for integration with
15

---

Published in Transactions on Machine Learning Research (06/2023)
compute the average elements of E as respect to the Haar measure Puchala & Miszczak
2017
Lere (ilp(x) ([lx
(i)>))))
[ Ju(2n) JoOUROU
2n -1
222n -1) (dx.ze dzodgk)
(A.5)
The terms associated with ōzt correspond the identity operator Iąt, while the terms òzedze contribute to either manyany diagonal components En,ü for i 1,...,2" Eig whenever j ) i:
2 or 2n (2 1)-many off-diagonal components
E 41
Σ
ΣΣ ki)
(A.6)
j
Equation A.6 is therefore a direct sum of subspaces proportional to 21p and subspaces proportional to 12 + X2, the latter which may be easily diagonalized.. Combining with Eq. A.5 yields the spectrum
with multiplicity 2" (2"
spec (Σ)
2'12"+13
with multiplicity 2"
0
Coincidentally, the mean embedding associated with this feature map is proportional to the identity; that is, Py. Ex[e(x)]= =1/-" 1/2".
Spectrum of the Bandwidth-Equipped Kernel
Here we derive the spectrum the integral operator for kernel discussed in the main text. We follow the technique of diagonalizing Σ described in Appendix A and used in Kübler et al. (2021 Appendix C). We first derive the spectrum for the single-qubit (one-dimensional data) case. Then we leverage the observation that the kernel factorizes over the qubits to obtaín the full spectrum for the general n-dimensional case.
We begin by considering the input Uniform(-nn ग,, m.. Recall that the feature map p(x:) is generated by the unitary
cæ )r+ 2
CT 2
U(x) = cos
ssn
X.
Then, the vectorization of the image of data point in feature space p(x) U(x) (0) U(x)) is
cos
Vec (p(x:))
cos
sin
cos
sin 63
sin
and the corresponding kernel is
(x x²)
k(x,7') = Vec (p(x))* Vec (p(x') = cos?
c--
(A.7)
2
Our goal is to compute the eigenvalues of the integral operator Tk defined as (Tr)))()) =
Aeda( (z).
(A.8)
16

---

Published in Transactions on Machine Learning Research (06/2023)
Here we refer to single-qubit eigenvalues D and many-qubit cigenvalues 7/. As described in Appendix this is equivalent to computing the eigenvalues of the covariance operator E given by
Σ
/
Vec (p(v)) Vec (p(v)) p(dy)
cos' cos'("))
cos o sin 2
cccss ( sin (+)
cos" ( sin'
( (4)
-i c0os (
sin
cos ( 7 siu
cos 3))siu" siu" ( -i coc + (+) sin' San (#)
dy
2T
cos
sin
cos sin ( cos" (4) (4) siu (#) coe +x sin 3nn(( (4)
cos
sin
cos sin slnn(()) -dcos( ()) sin
alu
Q1
0
02
02
02
0
42
02
0
0
where
3 1
sinc(eT) + (sinc(2cT)
8
02 sinc(2c7)
03 sinc(cT) + sinc((cx).
We can easily obtain the eigenvalues of this matrix, which are
3
1
A
+
(inc(( + 8 g sinc(2re)) + (T))
8
8
A2 = sinc(2
4
4
3
1
1 / sinc(2 + 16sinc(Te))
À3 +
sinc
8
8
A4 0,
(A.9)
where d1 A2 2 A3 x for all CE 1]. With c= the cigenvalues become 1 0, respectively. Now 2 4' 4:
can examine the impact of bandwidth on the eigenvalues (see Eq. A.9 of the inlegral operator. We first observe that for с + 0, all eigenvalues except the top eigenvalue become zero; that is, A + 1 and As, A4 + O. This confirms our intuition about the impact of bandwidth on the spectrum of the integral operator. This also implies that for small the approximate dimension of the space spanned by the training data will be 1, which consistent with the observation that this limit the feature maps become constant.
For an n-qubit system and an input data distribution that factorizes over the dimensions, the kernel simply becomes the direct product of the copies of the single-qubit system. Since the n qubits are completely decoupled, the resulting kernel in Eq. has eigenvalues of the form
Maingnang X X 71 + + ng n44 = n, n1, 02, n3. 114 Zt (0),
where the nonzero eigenvalues are obtained by setting n4 = 0 since \a =0 Here, we note that the number of zero eigenvalues grows exponentially with number of qubits as 4" 3". However, its ratio to the total number of eigenvalues vanishes since
Uminngnnn = 0}
4th
3"
n 000
O;
(1hanggann)
4n
therefore the bulk of the spectrum remains nonzero.
For cm (1), the spectrum remains flat n + co. This can be casily seen with the case 1 where the eigenvalues are given by
7ek 2-"2-
17

---

Published in Transactions on Machine Learning Research (06/2023)
where & n2 + ny and takes values in {0, (0,...,P1) n). Each eigenvalue 7e is degenerate with (n,, k) 2 (x), and of course Ek=o (n,, k) 3 gives the number of nonzero eigenvalues. To obtain a nonflat spectrum, we need eigenvalues to scale with the number of qubits n. In the next section, we do so by imposing scaling conditions on the eigenvalues.
For completeness, we also provide the unnormalized eigenfunctions of the kernel using the eigenvectors of E. Inverting the Vec operation, we get the matrices
4sinc(#c) /(1 (1 (inc(2 (Te)?
11
0
H1
H2
0 H1
4sino(xe) v (inne(2 6sin
1
0
1 0
H3*
(2ree)
The corresponding eigenfunctions are given by (x) Tr(p(x))..) and become
(x) sin²
CF
cos²
cr
4sinc(me) + v(1 sinc((2rc) 16sinc xT))
2
1 - s2nc(
02(xx) isin(cr)
(s(x)) sin
G.F:
cos?
cx.
4sino(Te)
((1 sinc(2 2 + 16sino(xc)2 1 sinc(2Te)
(x) 0.
Setting c 1, we obtain the eigenfunctions given in Kübler et al. (202I): (1(x) 1, Φ2(x) isin(z), (x(x) = - cos(x), and 64 0. Note that unlike the case, the eigenfunction Φ1 (x) in general is not. constant.
B.1 Scaling restrictions to the bandwidth
The argument given by Kübler et al (2021 Theorem 1) is that when the largest eigenvalue of the kernel is sufficiently small compared with the sample size, the generalization error is lower bounded by the L2 norm of the target function with probability at least - c as
Fg 2 (1 ) =||=||=== = (1- Σ a
which matches our result from Soc. 4 The result in Kübler et al. (2021) depends on the exponentially small largest eigenvalue the kernel compared with the amount of training samples. In fact, from Eq. g it easily follows that for a polynomial number of training samples
n' and exponentially suppressed largest eigenvalue 7max 2- the learning is impossible as + oc. Kübler et al. [2021 Lemma 1) proves that the
largest eigenvalue of the kernel is upper bounded by the so-called purity:
Tmax S Myn
where purity given by M,, = J ((dx))((xx)) (x(x,)) x'). We also demonstrate their proof here for the reader's convenience. Consider a normalized kernel satisfying k(x,x) = 1 for all x. The normalized eigenfunction (x)x(x) corresponding to the largest eigenvalue Tmax is L2 bounded by the constant function -1/2 1(x) since
1 = k(x,x) > Mmmax Tmaxxtmmax (x)
Here 1(x) = 1 is the constant function.
This immediately implics that
= f ((dx)) (k(,, x' x')amxx (x)mmaxxxx)))) (x')
Tmax
S Tmax / (xxx)) -max Mr
18

---

Published in Transactions on Machine Learning Research (06/2023)
Given this bound, we demand that the bandwidth should scale such that the purity stays constant with respect to the number of qubits n. For our example kernel, this condition translates into
1 M₁ 2n (1 sincrr())))))
Inverting this equation is not possible. However, its numerical solution yields scaling for bandwidth as c(n)
(A.10)
where a (1) depends on the fixed purity Ma. Note that this is a lower bound for the bandwidth to keep could allow purity to increase with depending on the target function. For example, c(n) an an + 0 yields perfect purity since there is only single mode. Hence, we conclude that the bandwidth should at least scale as
purity from inversely scaling with n. In principle,
1
on
We remark, however, that the spectrum will collapse to a single mode for large exponents a and generalization will not be possible except for very specifie target functions.
B.2 Scaling of eigenvalues with bandwidth
Using the bandwidth scaling derived in Eq. A.10 we now study the scaling of eigenvalues at the large qubit limit - cc. Asymptotically, the kth power of these cigenvalues looks like
7²
1
+
6n
n
a
πT²
a²x²
1 n²
1/
+
O
6n
5n
a
2/
1
1
k
+
0
180n²
42n
n²
Notice that with this scaling of the bandwidth parameter, the largest eigenvalue remains constant asymptoti- cally. We also remark that cigenvalucs composed of large number (k = n) of X2 and λ scale as e logn and we consider them decoupled since none of these modes can be learned with a polynomial amount of data. Hence, we conclude that the spectral bias induced by the bandwidth restricts the space of learnable functions to lie in the space spanned by eigenfunctions of the form
(11) ((n--2-na) (22) 8mz labg) 8ms
such that n2 n2 < It can be shown that the hierarchy of eigenvalues obtained in this way scale polynomially with as discussed in Sec. 4 In Table B.2 we present the first few eigenvalue scalings where ((n,k) k) denotes the number of eigenvalues with scaling Vik ~ ((n and (V) denotes the corresponding states. We denote each eigenvalue Th, with two indices: & corresponds to the scaling of the eigenvalue as n n-k and = =1, 1,.... (N,, k) indexes the ((n, k) eigenvalues with the same scaling.
B.3 Bandwidth and projected (biased) kernels
An alternative way to control the inductive bias of the quantuum model is to define the kernel in terms of the reduced density matrix (e.g., single-qubit): x(z) = Trp...n-1] (p(z)), where Trp (-) denotes the partial trace over qubits 1,..., n
of n-qubit system. For a detailed discussion of such kernels, the interested reader is referred to Kübler et al.] (2021); 0: Huang al. (2021). Here, we briefly comment on the similarities and differences between the impacts of projection and bandwidth tuning on the spectrum of the kernel.
19

---

Published in Transactions on Machine Learning Research (06/2023)
Table 3: Degeneracies N(n, k) of quantum states for the first. few scalings.
Degenerate States and Spectrum Scaling
Scaling Degeneracy
States (V)
n
N (n,
n²
1
1/1) 8n
n=
(1)) 8(n 1) (122)
n 22 2
( + (R)
(7)
11)) 8(n 2)
(122)
82
| (a))((n))) 1&a)
n-3
(3) +
(w)) 8(n-3) 3)
122)
83
w/ (((-)) 11/2) leba)
n
+ (+)
(1b)) (222
8(n 4)
(1)) 8((-3) (1b22
@2 wa) (0)00(22) 22))
As shown in (Kübler al. 2021 Theorem 2), the spectrum of generic projected kernel has one constant (with n) eigenvalue, and the rest are exponentially small with n. Contrast that with the spectrum of the bandwidth-oquippee kernel given in Table B.2 Similarly to projected kernels, in bandwidth--quipped kernels the first cigenvalue stays constant as the number of qubits grows. However, the spectrum docay behavior is different, since the eigenvalues decay polynomially and not exponentially with n. This leads to a qualitatively different inductive bias, which may be beneficial in some settings.
B.4 Bandwidth and trainability of quantum neural networks
The phenomenon of flat spectrum of the quantum kernels is deeply connected to the barren plateaus phenomenon quantum neural networks (QNNs) (MeClean et al. 2018) since both stem from the exponential dimensionality of the space in which the classical data points are embedded (Kübber et al., 2021 Holmes et al. 2022). "Barren plateaus" in the context of QNNs refers to the gradients of the loss function becoming exponentially small with the number of qubits for sufficiently deep QNNs because of the loss function concentrating around its mean in high-dimensional quantum Hilbert space. Notably, a mechanism analogous to rescaling the bandwidth has been observed to enable training of quantum neural networks. [Zhang el. al. (2022) show that if the parameters are initialized from a Gaussian distribution with zero mcan and variance ( for circuits of depth L, the barren plateaus are provably avoided. Rescaling the initialization of trainable parameters avoids barren plateaus by limiting the effective dimensionality of the subspace of the quantum Hilbert space being used. This is analogous to how scaling down of the data controls the bandwidth and the spectrum of quantun kernels, with the connection coming from the equivalency between quantum kernel methods and infinitely deep QNNs (Schuld, 2021).. Recently, the connection between the trainability of QNNs and quantum kernel methods has been extended by TThaaaiip et al. (2022) to show that several mechanisms that make QNNs impossible to train efficiently also prevent efficient training of analogous quantum kernels
C Generalization Error in Kernel Ridge Regression
In this soction we review the thcoretical generalization error curves for kernel ridge regression developed by [Brdelon et al. (2020); Canatar et al. (2021) and extend our results to the cases with a nonzero ridge parameter and noise on the labels. For kernel machines, a reproducing kernel Hilbert space H defines set
of functions over which the empirical loss function is minimized. Consider training set D = {x*, y ) J==1 where the inputs are drawn i.i.d. from distribution p(x) on x E X and the labels are generated through a target function f(x) as y" = [x*) + ett, where e ~ o0, is an additive noise with variance o². Then the predictor is given by minimizing the empirical mean meea-squared-erroo over H:
P -((*)) - =²)² /
I (x) = arg min JEH 2
(A.11)
where À is the ridge parameter regularizing the Hilbert norm of the predictor. Associated with the RKHS H. is a positive semi-definite kernel k(x, x') satisfying the reproducing property:
(k(x,)), f())) f(x),
20

---

Published in Transactions on Machine Learning Research (06/2023)
where (x is the Hilbert inner product on H. A basis for H can be obtained by solving the integral eigenvalue problem with respect to the input distribution p(x):
J k(x, x')x (x' (p('))(('d))) ddx = me)x(x),
( = dRg.
where {x)( is basis for (x) with respect the distribution p(x). A normalized basis for the RKHS H is obtained by the features (x) (T)(((x)) that satisfy
= E11-
With these bases, the kernel can be decomposed
k(x,'' = Σ Tx = Σ (x)(x))((())
Furthermore, any target function in L2(X') can be decomposed as
f(x) = Σ (x)=xxx= = Σ as Th
11 Σ o
(x(xx),
7
Note that function belongs the RKHS only if Il co. In the case where K(x, x') has zero eigenvalues while the function f has components along the corresponding cigenfunctions, this function is said to be out-of- RKHS (since llfll = x0), and a kernel machine can learn only the components along the nonzero eigenvalues. We show that the formula for generalization error in Canatar et al. (2021 Eq. 4) also extends to out-of-RKHS targets by appropriately taking the 7/ + 0 limit.
Given the P P kernel Gram matrix Kn k(xx", x"), the solution the kernel regression problem Eq. A.11
is
(*() = k(x) (K AI) y:
where k(x) is a P-dimensional vector with components k(x),, k(x, x²) and y, - y P-dimensional vector of the labels. Then generalization error, function of number of training samples P and the dataset D, is defined as
E2(,,D)= - (
2 p(x)dx.
However, the dependency of this quantity to the particular choices of datasets of size P makes it analytically intractable. Instead, we are interested in the averaged generalization error (P, D)) over the datasets of size P, which has been calculated using replica theory in Canatar et al. 2021
As a function of number training samples P, ridge parameter X, and variance of label noise o² as well as the kernel eigenvalues {m7} and the target weights {āx}, the result for (P, D)), becomes (Canatar et al, 2021
R
Ey(P)
Σ
+ + ?
(A.12)
1 1-
(Pns + n)2
1 1-7"
where
Pij 2
K = ARR Σ
M Prp +
7 7=
Σ (Pr + k)
Here i to be solved self-consistently, and acts as an effective ridge parameter that depends on the kernel eigenvalues and number of training samples. Even the absence of an explicit ridge parameter (i.e. 0), implicit regularization prevents the predictor from having large variance.
21

---

Published in Transactions on Machine Learning Research (06/2023)
C.1 Derivation of Eq. 9 in main text
In Sec. of the main text and in Appendix we have shown that the top eigenvalues T,, of the kernel in Eq. scale polynomially with the number of input dimensions, that is, 0k,= O(n="), where the index 1, 2.... represents different scalings and index 1,...,,N ((,, represents the degenerate modes in scaling k. Note that the number of degenerate modes Nn,, k) grows O(n²) such that 7)s = [n,, k)ns O1). We also decomposed the target function onto the kernel basis as
0R = f (xx))x..
((n.k) and defined o = Σ s=1 "b.. as the lotal weight at scaling k. Plugging these quantities in Eq. A.12 we get.
N(n.))
x²
t² 7
Ey(P)
+
(Pii, + x)2
1 1-7'
((n.R)
N(n,k)
Pui (Pilk + x))
==
Qk.z
7= Σ
PTR.: +
Furthermore, we made the approximation that Thk s Mkke for all 2, x' since, large n limit, modes in the same scaling differ from cach other with some (1) quantity. Hence, we drop the index 2. Then, in terms of Tik Nn,, k) generalization error simplifies to
x²
(g(P) = 1-
[a + R2) + +
a 2 (ageTTk + x)2*
T
K k= ==
OA Th
where we define og = N().)) denoting the learning stage. Now, consider the number of samples P to scale with O(n') for some integer Since k(n,k) O(n'), as n + oo the quantity ag becomes
P
0 00,
a== ~ O(1),
0kel R/ 0.
Therefore, in the large limit, generalization error simplifies greatly and becomes
R²
af
am?
Eg(P) 7 (anT) + x)²
22
1-7
o
7
(arT) + x)²²
where 82 =0= 0² Eb>1 of is the effective noise and has explicit solution:
1 ( mar) -)))))
4h 1 v 1 (A+
2o S 1 \/
k =
1(A marx)
1 11
4rmaay
a ス 1+ \/1
(A+ 7
where -= x +xst Mi is the effective ridge parameter and describes the implicit regularization of the kernel model. Note that the total power beyond mode-l acts as label noise and also irreducible error.
22

---

Published in Transactions on Machine Learning Research (06/2023)
C.2 Out-of-RKHS target functions and label noise
We treat the case where largel function has out-of-RKHS components by setting eigenvalues with indices in an index set I in the generalization error formula to zero; that is, TREE = 0:
x²
of + to² ?
Eg(P)
1-7
(PiRk + k)²
1 1-7
x²
Pitle + x)) +
02
Σ
ax
?
1 ? K
1-7
KEI
KET
where K and y are again
TJk
PT
K -=
PTT + 7
(P + k)²
KgI
Notice that target power placed the modes corresponding to zero eigenvalues act both label noise and irreducible error (Canatar et al. 2021). This implies that the inaccessible modes in larget function due to small training set sizes simply le outside the effective RKHS defined by the accessible, large eigenvalues. This also implics that very large bandwidths can also impair generalization; for c 2 0 only a single non-zero eigenvahue survives and therefore generic targets which may have many modes corresponding to the remaining zero eigenvalues lie outside the effective RKHS. Therefore, the extreme case of very large bandwidth also creates problem. This just restatement of the well-known bias-variance trade-off.
D Bandwidth Makes Bounds on Generalization Vacuous
The following is a sketch of how the main theorem of Kübler et al. (2021) becomes vacuous ("fiils") in certain context where can guarantee that k(z, x²) is lower bounded by some bandwidth-ddeendden constant.
We first note that this cannot be a positive proof: nothing about lower bounding k(x, can provide a guarantee on classifier accuracy. Rather, this scenario just shows a context in which lower bound on the ridge regression classifier accuracy based on the largest eigenvalue Mmax is no longer effective at showing a failure of quantum kernel methods.
Now, we suppose that can use bandwidth to require that states are "not too far away" in Hilbert space. More specifically, we suppose that there is some function Ag such that
k(x",
N A..
(A.13)
Note that this does not interfere with the requirement that lo is L² intograble since we assume that k is defined restricted support x E [-T,,]] x|" (without this assumption, k is not integrable in a more general treatment). We will show that some choice of A. always ensures that the largest eigenvalue of K (and therefore the largest eigenvaluc of Tr with high probability) is bounded. Denote the cigenvalues of K as 7,k and in particular let 7max be the largest eigenvalue of K and Ku = 7max for some eigenvector R.. By definition, Imna = max =1 (v, Kv) for all v E TR... and particular
Ku) (u, ui)
(1. K1
P
7max
Σ #PK=1
K
where 1 is the vector of all ones and we have applied the inequality of Eq. al. 2010) states that
A.13
Proposition 10 of Rosasco
log(4 (og(4/22)
U]
Pr
sup b
7k
2
2 21-5,
P
P
23

---

Published in Transactions on Machine Learning Research (06/2023)
where contrast the empirical eigenvalues 7n with the eigenvalues "/ of the integral operator Tg. Note that the empirical eigenvalues "/k as P + 0o. Hence, with probability at least. 1 - it holds that
7max (-p-) P
P
log (4/62)
A
S
2
(A.14)
P
Theorem of Kübler et al. (2021) states that, with probability at least 1 Ymmax PA, the empirical risk for KRR with penalty À and training data is lower bounded by
mmax P2
Remp (f 2
lfll..
(A.15)
E
From Eq. A.14 however, we see that 7max approaches constant A. at a rate of O(L/VP); for sufficiently large P, Eq. A.15 holds with vanishing probability, and for all other choices of the bound becomes vacuous with high probability under the condition that v 22mmaxx P2fe & 2 1, which may be achieved within O(1/VP) precision by choosing
P
2P2
Importantly, this outcome does not guarantee that KRR using k satisfying the inequality in Eq. A.13 will achieve good generalization error. In particular, the choice A, = will result in Tç having a single nonzero eigenvalue associated with the constant function. Rather, this demonstration reemphasizes that there are two conditions to successful classification using quantum kernels: (i) the kernel should be chosen such that the eigenfunctions of T& align with the target function, and (ii) the corresponding eigenvalues should be large. By lower bounding k in this way, we can guarantee condition (ii); however, successful generalization will still depend on a choice of satisfying condition (i).
E Numerical Methods
E.1
Experiments with toy model
In Figs. and in the main lext, we consider the loy kernel k(x,x') x') II= cos
(o (x-xx)) (x
for varying
2
bandwidth parameter and n-dimensional input data [-T,, w|" and drawn uniformly (Kübler al. 2021]. We generate dataset of size P by uniformly sampling P input points and computing the corresponding
labels using target function f(x). We denote the vector of labels by RR and denote the kernel Gram
matrix by K whose elements are K, = k(x",x"" x²). We obtain the cigenvalues and cigenvectors of the kernel by solving the empirical eigenvalue problem:
P
no Pu.k
Mi D n.ks
P Σ p=1
4. n.l = Snt,
where & P the matrix of eigenvalues whose columns are the orthonormal eigenvectors and {nı J/ are the eigenvalues. Note that obtain at most P eigenmodes with P samples and hence k runs from I,..., Finally, obtain the target weights by projecting the targets the eigenvectors of K:
TTy. y.
Using the eigenvalues {m and larget weights we directly compute the gemeralization error by plugging them Eq. |A.1 To perform the experiments, we used the Kernel Generalization code by [Canatar et al. (2021) and utilized a single NVIDIA V100 GPU with GB of RAM. In Fig. E.1 we present the same experiment as Fig. g but for different input dimensions n. We find that the optimal bandwidth parameter is c² 2/n. Therefore, the optimal scaling of the bandwidth parameter is O(n-a) for in this special case.
24

---

Published in Transactions on Machine Learning Research (06/2023)
Note that bandwidth changes both the eigenvalues and the eigenfunctions of the kernel that affect spectral bias and task-model alignment, respectively. For certain tasks, faster decaying bandwidths might improve the task-model alignment and hence yield better generalization.
20
40
109
10-2
10-2
Eg(P)
Eg(P)
10
c 1e+00
1e+00
10
c 1e-01
10-8
C
1e-01
5e-02
5e-02
10-8.
c 3e-02
10-10
3e-02
c = 1e-02
== 1e-02
10a
10a
10a
102
P
P
200
10
10-1
10-3
10
10-5
(P)
(P(
10-7
10-7
c 1e+00
C 1e+00
1e-01
10
1e-01
1
5e-02
10-11
5e-02
10-11
c 3e-02
c
3e-02
1e-02
10-13.
1e-02
10a
103
10a
10a
P
Figure A.1: Generalization error as a function of the number of training samples computed by using both theory (solid lines) and performing kernel ridge regression empirically (dots). The target function is f(x) e - /n² and data is drawn uniformly from Unif(I- x)") for 20, 40, 80, 200. Bandwidth yields constant learning curve. While all e < kernels provide improvement, there is an optimal bandwidth parameter e* x 2/n that gives the best task-model alignment. Regularization with a small ridge parameter 10-10 is applied for numerical stability.
E.2
Bandwidth in quantum machine learning architectures
We use the experimental data provided by Shaydulin Wild [2021)] We use the kernel given by the instantancous quantum polynomial-time (IQP) circuit fcature map (Shepherd & Bremner 2009 Havlfčck
et. al. 2019: Huang el al. 2021) and Hamiltonian evolution circuit (EVO) feature mappHuane et al. 2021
Shaydulin & Wild 2021) and real datasets FMNIST (Xiao et al. 2017), KMNIST (Clanuwat et al.
2018
and PLASTiCC (The PLAsTiCC team et al. 2018
Since the dimensionallty of the datapoints in these datasets is too large (e.g., 784 for FMNIST and KMNIST) and leads quantum circuits that cannot be simulated by using available tools, the inputs were downsized
to 22-dimensions by using PCA (Shaydulin & Wild 2021 Following (Shaydulin Wild 2021 Huang et al.
'The code and the data publicly provided by Shaydulin & Wild 2021 Importance-on -oeeneee--eeeee-e----e Bandwidth- Quantum Machine-LLerringg
http:///ggttuub.co///eeeete
25

---

Published in Transactions on Machine Learning Research (06/2023)
we consider binary classification problem where for each dataset, only two classes were chosen (see Shaydulin & Wild (2021) for the details on data preprocessing)
2021
For n-dimensional inputs, the quantum circuit used to compute the n-qubit IQP kernel is given by
UiQP(x) =
Uz(x) - exp و2Z + c²
J.j'=1
where II is the Hadamard gate and z is the Pauli Z-gate (see Havlíček et al.
2019
This unitary acts
on the n-qubit ground state to embed an input x" to a quantum state
x²)
UIQP (x") [0] 00m Then the
resulting feature map is given by Piqr(x")= = (x*) (xx) with the corresponding quantum kernel Kiqr(x", x*)
Tr (fTQP(x*)) (TTOP(x))
For n-dimensional inputs, the quantum circuit used compute the EVO kernel (Huang et al. & Wild 2021 has n+1 qubits and is given by
2021 Shaydulin
(x)o(x)= II e iem (
Here, c parameterizes time evolution and corresponds to the bandwidth of the resulting kernel. The initial (n + qubit state is given by
(
where each |1i)) is randomly generated with respect to single-qubit Haar measure (Huang et al. 2021). Then the quantum embodding of a sample x" is xx") = UEvo (x"" (o) with the feature map PEvo (x") x²" (x"
and kernel Kxvo(x", x") = Tr (x")oo("))evooo
In both cases, the resulting kernel is conjectured to be intractable compute analytically, and both models utilize Hilbert spaces that are exponentially large in the number of qubits n. These quantum circuits were simulated in Shaydulin & Wild (2021) using Qiskit (Abraham el al. 2019) software to compute the kernel Gram matrices on the data. The kernel entries were computed exactly with high precision, i.e. with no hardware or statistical (shot) noise. Then the resulting kernels were used to perform SVM for the binary classification task.
The datasets were split into 800 training sets and 200 test sets. Each input was downsized to 22 dimensions using PCA, which leads to 2 and 2 Hilbert spaces for IQP and EVO circuits, respectively (Shaydulin & Wild 2 The code for accessing and processing the data obtained at httts://gitth/ com of Keae--ernelBBandidthaa in- Muantun-Machhne--eene
Kernel Ridge Regression with Realistic Quantum Kernels
Apart from the classification task shown in the main text, we also use the same quantum kernels to perform kernel ridge regression on real data as shown in Figure A.2 We again find that there is an optimal bandwidth for both kernels signaled by low test loss.
Optimal Bandwidth in Realistic Quantum Kernels
We have obtained the optimal bandwidths through k-fold cross-validation for the SVM task. In Figure A.3 report results for each kernel method on all three datasets. Furthermore, we present the eigenvalues lues and target weights corresponding to both quantum model on all three dataset domains in Figure A.4 and Figure A.5] respectively. We find that the spectrum in all cases are flat without the bandwidth, and that the bandwidth improves the spectral properties in all cases. However, the task alignment with the quantum kernels depends significantly on the choice of the dataset, and it remains poor even with the bandwidth cure. This is in agreement with our arguments that bandwidth does not guarantee generalization, but only enables model to potentially generalize if the target is suitable.
26

---

Published in Transactions on Machine Learning Research (06/2023)
IOP fmnist
IOP kmnist
IQP plasticc
4
rold S-faldicv
told
3x
5-taldicv 10-fold-cv test rest_loss
4x
5-taldicv
Test Loss
10-fold-cv
Test Loss
Test Loss
10-fold-cv
1x
test_
jest_loss Joss
test, rest_loss Joss
10:1
10-1
xx
6x 2.
10
10
10-a
10a
10-3
10-a
10-
10a
10
10-2
10at
10a
Bandwidth c
Bandwidth c
Bandwidth c
DVO fmnist
DVO kmnist
DVD VVO_paasticc
2-fald-cv 5-fold-cV
2-fald-cy
6x
2-fold-cy
S-fold-cv
5-fold-cv
Test Loss
to-lold
Test Loss
10-told-cv
Test Loss
10-
10 10-toldizvv
test_lost
test_loss
3x-10-)
10:1.
20-1
10"3
10"2
10"1
100
10:3
10
10"
109
10-3
10:2
10"2
10
Bandwidth
Bandwidth
Bandwidth
Figure A.2: Kernel Ridge Regression performed with k-fold cross-validation and = 0.1 ridge parameter yiclds the optimal bandwidth. The vertical axis shows the test loss of the estimator when evaluated on held-out data.
Here, also empirically show that the optimal bandwidth scales inversely with the number of qubits et ~ O(n=a), where 0.5. Using the data provided by Shaydulin & Wild (2021). b we first extract the maximum kernel eigenvalue for the IQP kernel on FMNIST dataset. The IQP kernel is evaluated for various input dimensions n (also the number of qubits) and various bandwidth paramcters.
First, we normalize each top eigenvalue (m)r(() as function with the maximum eigenvalue corresponding the smallest qubit size Mmaz (no), and define the quantity
Tmaa (n) Mmnax (n
Mmaa (no)
where no 4 in this case. In Figure A.6., we plot these normalized eigenvalues against the number of qubits, and we fit exponential curves to extrapolate the behavior for large qubits which are not accessible experimentally. As the number of qubits increase, the maximum eigenvalue corresponding to c kernel falls much faster than the kernels with c bandwidth as expected. Note that in Appendix [ we found that the bandwidth prevents the maximum eigenvalues to fall exponentially fast n using our toy model, and this is also what we observe here.
Next, consider fixed eigenvalue V/ 0.8 line in Figure A.6a, and in Figure A.6 we analyze where this line intersects each of the normalized eigenvalues (n) corresponding to different bandwidth parameters Similar to our calculation in Appendix B for the toy kernel, we aim to find the scaling of the bandwidth with the number of qubits such that the maximum eigenvalue stays constant. By identifying the intersection points in Figure A.6,, we obtain a relation between the optimal bandwidth and the number of qubits as shown in Figure A.6 this case, we numerically find that the optimal bandwidth scales as:
c² ("(n) x n 0.506
(A.16)
This is in agreement with the bound for the exponent we derived in Eq. A.10 Finally, in Figure A.7 and Figure A.S for both models when evaluated on the FMNIST data, we show the empirical scaling of the optimal bandwidth keep their top cigenvalues constant for varying no 's. Again, we find that the decay exponent violates a 2 0.5.
27

---

Published in Transactions on Machine Learning Research (06/2023)
IQP fmnnitt
IOP kmnist
IQP plastice
x0
9x10-1.
8x
Test Scores
Test Scores
Test Scores
8x10
xx
10-1
6'x -0
2-
2-fold-cv
d-feldevv folddccv
5-fold cv
6x10-1
5-foldicv
7x
10-fold-cv
10-fold-rv
10-fald-cv
-0
scares
5x10-1
test sct_ss
test scores
10
10-2
10-1
16
10
10-4
10-1
109
10-1
10-1
10
10
Bandwidth
Bandwidth c
Bandwidth с
EVO fmnist
EVO_ 10__kisttt
EVO_plasticc
x 10
7,6 10-
9x10-1
Test Scores
10
Test Scores
8x10-1
Test Scores
7.4 10
10
10-1
x10-
60
2-fold-cv
2-foldicv
7x
d-feldecv
S-fold-cv
5-fold-cv
5-fold-cv
10-fold-cv
10-fold-cv
6.8 10
10-fald-cv
-0
test scores
xx10
test_ scorcs
6.6x
test scores
10
10t3
10
10a
10
10
10
10a
10
10
10"
10a
Bandwidth
Bandwidth
Bandwidth c
Figure A.3: SVM performed with k-fold cross-validation yields the optimal bandwidth.
IQP fmnist
plastice
Eigenvalue nk
Eigenvalue пą
10-1
Eigenvalue nk
10-1
10
0.0.01
0.0.01
10 0.05
10
0.05
0=0.05
c.0.1
- 0.1
0.1
10
10
10-11
c=1.0
c= 1.0
c=100 1.0
10a
10
10a
16a
101
10
102
10a
10
10
10a
102
k
EVO fmnist
kmnist
CVO_plasticc
Eigenvalue nlk
10-2
Eigenvalue nkk
10:1
Eigenvalue Nk
10-1
10
C- 0.05
10
0.05
10-1
0.05
0.1
0.1
0.1
10-13
0.5
10-28
10
<= 1.0
1.0
C 1.0
10a
10a
10a
16a
10a
10:
10a
10a
10
10:
10a
10a
k
Figure A.4: Eigenvalues of the quantum kernels are always flat when the bandwidth not tuned.
28

---

Published in Transactions on Machine Learning Research (06/2023)
IQP fmn_fmnist
IQP kmnist
IQP IQP__lasee pll_stisscc
1.0
1,0
1.0
0.9
0.8
C(k)
0.8
0.8
c
c-0.1 0.1
0.1
0-1.1
0.6
0.5
0.6
10
1.0
c-100
0.5
10a
10:
10a
10
10
10-
10a
10a
10a
10:
10a
10
k
k
EVO fmnist
EVO kmnist
EVO plastice
1.0
1.0
1.0
0.8
0.8
C(k)
0.6
0.6
0.4
c= 0.05
c= 0.05
0.6
0.0.05
0.1
c= 0.1
c= 0.1
0.5
0.5
C=100
1.0
C- 1.0
c 1.0
10a
10:
10P
10a
10
10-
10a
10
10a
10:
10a
10
k
Figure A.5: Task-model alignment improves with bandwidth tuning. Note that a decaying cigenspoctrum is not enough alone for generalizability. Empirically, we find that bandwidth improves both the eigenspectrum and the task-model alignment.
a)
Largest Eigenvalue vs. Qubits)
b) 10a
c=0.001
109
0.001
10
c=0,005
0.005
c=0.01
(max(n)
9x
0,01
10
c=0.05
(max(n)
10
c=0.1
0.1
10-4
10.5
7 10-1
10
102
10a
10
10'
10a
100
10a
n
n
c)
10-1_
n 0.506
10
10-3
107
102
10a
10a
107
Figure A.6: Empirical scaling of the optimal bandwidth with the number of qubits.
29

---

Published in Transactions on Machine Learning Research (06/2023)
10
(no 0.10) c' on
16-1
Ino 0.201 c'
10"1.
(do 0.30) c
G 10-2
10
10
10
10
107
10
10a
10
10a
10a
10a
10a
10a
10'
10'
n
10-1
10-1
10
(/ = 0.40) =n 0512
U/o = 0.50) c" =n -8.50
(Op = 0.60) c
10
10
10-3
10-3
10
10
n
10-h
(1) 0.70) xn 2502
10"2
0.80)
10-1
(Op = 0.90) c" 0.515
0 10
10-2
10-3
10-1
10a
101
102
10'
10"
10'
n
n
Figure A.7: IQP Kernel: Empirical scaling of the optimal bandwidth with the number of qubits for all no- Note that the empiriaal scaling never exceeds = 0.5 for the optimal bandwidth et s n
30

---

Published in Transactions on Machine Learning Research (06/2023)
10
(no 0.10) c* on
Ino 0.20) c*
(d) 0.30) c
G 10
10-2
10
10
10a
103
10a
102
10a
107
10a
107
10
107
10
107
n
10-1
10-1
10
(/ = 0.40) =n 0500
U/o = 0.50) c" =n -850
(Op = 0.60) c
10-2
10-2
10
10
10
n
10-h
(1 0.70) xn 2014
10"
0.80) c' -0
10-1
(Op = 0.90) c" 0.532
10
10-2
10
10-1
101
10a
107
10
10"
n
Figure A.8: EVO Kernel: Empirical scaling of the optimal bandwidth with the number of qubits for all no- Note that the empirical scaling never exceeds 0.5 for the optimal bandwidth ot s n
31


Reviews:
[{"review_id": "sXvMLhyxTy", "reviewer": "Reviewer_wb6i", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "From my perspective, the main advantage of this work is that it provides a framework for studying generalization properties of quantum machine learning algorithms with theoretical guarantee. Relevant such works are sparse as far as I know, and it’s nice to see a solid contribution along this line.\n\nIn terms of weaknesses, I think the paper can be further improved from the following two perspectives.\n\nIn theory, it would be helpful to discuss how general the kernel in Eq. (6) is. In particular, does the result also apply to other kinds of kernels, and will there be a similar bandwidth parameter c for characterizing generalization?\n\nIn practice, it would be helpful to explain how the theoretical results in this paper can be helpful for near-term quantum devices. For instance, does the result in this paper further imply generalization guarantees for VQE or QAOA algorithms?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies generalization properties of quantum kernel methods. In particular, this paper considers the kernel method with a trigonometric kernel as in Eq. (3), and studied the generalization property of such a kernel in terms of a parameter c, named as the bandwidth of the kernel. It is observed that the smaller c is, the better the generalization is.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It would be helpful if the authors can contribute to my comments above related to both theory and practice sides.\n\nIn addition, I notice the following two minor points:\n\n- In intro, the authors may also briefly discuss about Li et al. in ICML 2019, https://arxiv.org/abs/1904.02276, which studied quantum algorithms for supervised learning and also used kernel methods, in particular kernel-based classification. \n\n- Typo: title of Appendix A: Review of Classical and Quantum Data operators -> Review of Classical and Quantum Data Operators\n", "broader_impact_concerns": "Not applied in general. Nevertheless, it would be helpful if the authors can briefly discuss about the impact to near-term quantum computing devices (see also my comment above).", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "26R8VxjC8r", "reviewer": "Reviewer_VUNb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**: this paper focuses on the important and timely problem of quantum kernel method and discusses its generalization performance. The idea of kernel bandwidth is of interest.\n\n**Weaknesses**: While the core idea of this paper is not difficult to grasp, the presentation of this paper (examples instead of formal theorem, etc) makes it difficult for readers to go deeper, and in particular, makes one feel that this paper only studies special cases. See my detailed comments below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors focus on the generalization properties of quantum kernel methods. \nBy introducing the hyper-parameter of quantum kernel bandwidth and by studying its impact on the (eigen-)spectrum of the resulting kernel integral operator, the authors show that even in the setting of large qubit, quantum kernel methods can generalize well with an appropriate choice of kernel bandwidth.\n\nEmpirical results on real-world datasets are provided to validate the theoretical results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* The term \"kernel bandwidth\" is reminiscent of the kernel (e.g., Gaussian) bandwidth in the literature of classical (non-quantum) kernel, it may of interest to discuss and compare how they are similar and/or different.\n* Second paragraph of Section 3, starting with \"One example of how high dimensionality ...\": In general, I am confused by this paragraph, I do NOT really understand under which mathematical assumption the results hold (it should not be \"$\\phi$ consisting entirely independent Gaussian features,\" in which the covariance may different from identity) and I do NOT understand in which part of Appendix A is the fact \"$\\Sigma$ shares the eigenvalues with $T_k$\" proved, and which specific result in (Rosasco et al., 2010) is cited. I would suggest that the authors should re-organize this part (and possible a few parts that follow) to state the theoretical results in a very clear manner.\n* the whole section 3.1 is mainly on the example considered in (Huang et al., 2021). I am wondering if something can be said beyond this example. The same holds for Section 4.1.\n", "broader_impact_concerns": "The contribution of this paper is a theoretical and I do not see any ethical concerns for this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "F7ZpZTQ5Iy", "reviewer": "Reviewer_E8KY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper is well written, and the idea is interesting. The paper has done reasonable results based on their idea of quantum kernel bandwidth.\n\nWeaknesses are summarized as follows. While the paper demonstrates some interesting aspects of quantum kernel methods, I cannot recommend acceptance for the following points:\n\n1. Limited novelty: The effect of the bandwidth is indeed equivalent to a linear pre-processing of the data, which is a normal technique in classical machine learning. Moreover, in quantum machine learning, applying a function to the data before the encoding circuit was previously mentioned in Robust data encodings for quantum classifiers (arXiv:2003.01695). It is quite expectable that the hyperparameter could lead to different performances. The overall result does not provide any substantially novel insights or results to the quantum kernel model as well as its potential quantum advantage.\n\n2. Limited applicability: The work mainly focuses on the tensor product quantum kernel model, which is a toy model with certain restrictions. The encoding map in this model is very costly in circuit width and can also be classically simulated. The paper needs to provide a clear and convincing explanation of how their assumptions are more general or realistic. The theoretical part needs to go deeper into the applicability and quantum advantage. This lack of clarity weakens the paper's main arguments and makes it difficult to assess the impact of their findings.\n\n3. Not sufficient numerical simulation and its information: Although the authors claimed that \"To evaluate our theory in a practical setting\", the numerics are insufficient for practical purposes. For example, the information about the numerical experiments lacks clear information. Are the simulations under ideal assumption? What is the number of shots in the measurement part? Does the simulation consider any noise effects?\n\nIn summary, although the paper addresses interesting progress on quantum models, the lack of novelty, limited applicability, and insufficient numerical validation, prevent it from making a significant contribution to the field of quantum machine learning. I recommend rejection in its current form. The paper may be worth publication in a more specialized journal.\n\nMinor comments:\n- In the preliminaries, the authors introduced that a quantum state can be described by a positive definite matrix. However, it should be a positive semi-definite matrix. Similar changes should be applied to the related Hilbert space.\n- The same H for feature space and quantum Hilbert space is a little bit confusing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission investigates a variant of quantum kernel models by introducing the quantum kernel bandwidth (add a hyperparameter in the encoding or feature map). The paper follows a toy model of the quantum kernel that can be classically simulated and studies the effect of adding the hyperparameter. The paper further considers how this hyper-parameter affects the spectra and generalization error, and shows numerical experiments of the improvements of the quantum kernel model compared with the simple case. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Refer to the above Strengths And Weaknesses.", "broader_impact_concerns": "NA.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9YJfzJUR7y", "reviewer": "Reviewer_6SfK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Weakness: \n1. The submission focuses on large-qubit quantum kernels, which may raise trainability issues, leading to the concentration phenomenon where all kernel entries become identical. This phenomenon has been discussed in a recent study by Thanasilp et al. [\"Exponential concentration and untrainability in quantum kernel methods.\" arXiv preprint arXiv:2208.11060 (2022)]. It would be beneficial if the authors could address whether their findings are susceptible to such trainability issues and discuss any potential implications.\n\n2. In the context of modern noisy quantum machines, the implementation of a large-qubit quantum kernel may suffer from degraded generalization ability, as demonstrated in a previous study [Wang, Xinbiao, et al. \"Towards understanding the power of quantum kernels in the NISQ era.\" Quantum 5 (2021): 531.]. Therefore, it would be valuable for the authors to comment on whether their findings can potentially alleviate this issue.\n\n3. The submission's theoretical analysis seems to rely on a particular ansatz, such as Eq (6). This raises two questions: Firstly, since this ansatz can be efficiently simulated by classical computers, it may not offer any significant quantum advantages. Secondly, it is unclear how the findings can be extended to other ansatzes. More discussions are expected.\n\n\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission presents an argument for the enhanced generalization ability of quantum kernels when their bandwidth is controlled. While the authors provide a theoretical analysis of a specific Ansatz, they also conduct numerical simulations on other Ansatzes to demonstrate the practical relevance of their findings. Through experiments on real-world datasets, the authors showcase that controlling the bandwidth of many types of quantum kernels can significantly improve the performance of quantum machine learning models.\n\nThe paper is well-structured and presents some interesting results that have potential implications for the advancement of quantum machine learning. I think the paper could be published in TMLR if the issues listed in Weakness are well addressed. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The comments in Weakness should be addressed in the revised submission. ", "broader_impact_concerns": "The submission targets both the machine learning and quantum machine learning communities, with potential benefits for researchers interested in designing effective quantum kernels for learning real-world datasets. However, a limitation of the paper stems from the inherent framework of quantum kernels. A recent study [Jerbi, Sofiene, et al. \"Quantum machine learning beyond kernel methods.\" Nature Communications 14.1 (2023): 517.] has suggested that in certain scenarios, quantum kernels may be inferior to quantum neural networks. This raises questions about the necessity of using quantum kernels to tackle practical tasks.  \n\n\n\n", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper explores the generalization properties of quantum kernel methods. It introduces that the hyperparameter "quantum kernel bandwidth" is important for improving the generalization of a quantum model. After rebuttal, all reviewers had a positive view of the work and  recommended acceptance, acknowledging its theoretical rigor and the relevance of the topic.

These reviewers noted the authors' theoretical analysis and empirical validation of the impact of the quantum kernel bandwidth on generalization. Reviewer wb6i also highlighted that this work is particularly significant due to a lack of existing literature on theoretical guarantees for the generalization properties of quantum machine learning algorithms. Reviewer 6SfK further recommended the Featured Certification. In light of these recommendations and discussions, I support the acceptance of this paper for publication in TMLR. Their work may open up new avenues for research and practical applications in quantum machine learning.



Decision: Accept (poster)