Bandwith Enables Generalization in Quantum Kernel Models
Authors: Abdulkadir Canatar
Evan Peters
Cengiz Pehlevan
Stefan M. Wild
Ruslan Shaydulin
Venue: Submitted to ICLR 2023 (2023)
Keywords: kernel methods
generalization error
quantum machine learning
spectral bias

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 practically interesting problems. 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 bandwidth can take a model from provably not being able to generalize on 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.

Under review as a conference paper at ICLR 2023
BANDWIDTH ENABLES GENERALIZATION IN QUANTUM KERNEL MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
Quantum computers are known to provide speedups over classical state-of-the ahr- 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 exponen- tial 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 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 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.
INTRODUCTION
Quantum computers have the potential to provide computational advantage over their classical counterparts (Nielsen Chuang 201T), with machine learning commonly considered one of the most promising application domains. Many approaches to leveraging quantum 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, consider 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 al. 2018
Farbi & Neven 2018) and quantum kernel methods (Havlíček 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 model optimized on a classical computer (c.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, 202T). Since the kernel perspective is more amenable to theoretical analysis, in this work we focus only on the subset of models that can be reformulated as kernel methods. A support vector machine (SVM) with a quantum kernel based on Shor's s algorithm has been shown to provide exponential (in the problem size) speedup over any classical algorithm for version of the discrete logarithm problem (Liu et al.) 202T), suggesting that a judicious embedding of classical data into the quantum Hilbert space can enable quantum kernel method to learn functions that would be hard to learn otherwise.

---

Under review as a conference paper at ICLR 2023
While the quantum kemnlss provide a 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. (202I) show that generalization is impossible the largest eigenvalue of the kemel integral operator is small, and Huang et al. (2021) show that generalization is unlikely if the rank of the kernel matrix is large. The two conditions are connected since for positive-definit kernel with fixed trace, a small value of the largest eigenvalue implies that the spectrum of the kernel is "flat" with many nonzero eigenvalues. Under the assumptions used by Kübler et al. (2021); y; Huang et al. (02T). 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. (202T); Huang et al. T 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. (2022) inherent in quantum kernels. However, Shaydulin & Wild (202I) 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 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] (018)) 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 et al., 1992 Dietrich et al. 1999; Mezard & Montanari 2009 Advani et al.) 2013). While nonrigorous, this framework was shown to capture various generalization phenomena accurately compared with the vacuous bounds from statistical learning theory. Together with the spectral biases of the model, task-model alignment quantifies the required amount of samples to learn task correctly. A "flat" kernel with poor spectral bias implies large sample complexities to learn each mode in task, while poor task-mode alignment implies large number of modes to learn. On an analytically tractable quantum kernel, we use this framework to show generalization of bandwidth-eog euuiippee models in the limit of an infinite number of qubits. Generalization in this infinite-dimen dimensional limit contrasts sharply with previous results suggesting that high dimensionality of quantum Hilbert spaces precludes learning.
Our main contribution is an analysis showing explicitly the impact of quantum kernel bandwidth on the spectrum of the corresponding integral operator and on the generalization of the overall model. On a 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 eigenvalue and to a less "flat" spectrum. We show that for an aligned target function the kernel can generalize if bandwidth optimized, whereas if bandwidth is 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 compatible, 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*", y²) I containing P
observations, with x drawn from some marginal probability density function X - IR defined on X' C RR and y produced by a target function f X + R as y fxx).
Learning with kernels Given data in X' distributed according to a probability density function p: X + R. we consider a -imeessoian complex reproducing kernel Hilbert space (RKHS) H. and corresponding feature map e X + H. This feature map gives rise to a kernel function k(x,x') = (x()), ((x'))xx The RKHS H. associated with is endowed with an inner product ( ) satisfying the reproducing property and comprises functions f X R such that (S. S'x < co
2

---

Under review as a conference paper at ICLR 2023
(Schölkopf al. )002). Given set of P data points x" E X, the positive semidefinite Gram matrix is defined elementwise by w = k(x",, ) The continuous analogue to the Gram matrix K is the integral kernel operator T& (x()) + L2( defined according to its action:
(Tx = / k(xx x' (fxxxx))(xx)xxxxx)
By Mercer's 's theorem (Schölkopf et al. 2002). the eigenfunctions of Th satisfying TeOx m.dx are orthonormal (i.e.. (Øx. 01) = 0kt), span Lz(x²), and give rise to an eigendecomposition of k given by x(x,x') = Σx (x)x(()) (x'), where {m- are realevalued, nonnegative eigenvalues of the integral operator due to its Hermiticity. The inner product (5 in the RKHS of k may be computed with respect to the integral kernel operator of Eq. as (f.9)H = (J, TE g) La(x), with the null space of Th 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) = Σx 04 (x), where āg = (f, Φu) x are the target weights. We comment on the case where the target lies outside of the RKHS in Appendix C
Kemel ridge regression (KRR) is convex optimization problem over functions that belong to a Hilbert space H and stated as follows:
(f(x)) - v²²² + A 1 1 2
= arg min JEH 2
(2)
p=1
where |1-11, denotes the norm with respect to the inner product (:, )) defined on the Hilbert space and A 2 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 (x) k(x) (K + AI) y. where k(x) is a vector with elements k(x),, = k(x, x") and yr y The kernel trick (Schölkopf et al. (002)) allows
perform regression without explicitly computing the features if one has access to the analytical kernel function. While providing rich class of kernels, quantum kernels are typically not expressible analytically and hence require explicit representations of the feature maps.
Machine learning with quantum computers The central motivation for applying quantum com- puters 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 2 x 2" density matrix with unit trace and contained in the quantum Hilbert space where L(C") denotes bounded linear operators of the form Cd + Cd or, equivalently, d x d complex matrices. is endowed with the inner product (p, p²) given by the Hillbert-Schmic inner product (A, Hs = Tr ( B} for A, B L(Cd).
{p I > 0. Tr(p) = 1. p E L(C²") }}.
The dynamics of quantum states are described by applying linear operators to and we here will specifically consider unitary operations (represented by a 2n 2" unitary matrix U). Then, the quantum states that we are interested in may be prepared by applying unitary operator to the vacuum state (0). where the "ket" notation Ij) represents the jth standard basis vector é, in IR?". When n quantum states may be represented by the Bloch sphere: the constraints Tr(p) = 1 and p = p mean that the components of a density matrix are parameterized by three real parameters = (Mz, Ny n.) and the density matrix can be written in terms of Pauli matrices ø as
(1 (1+10 +1+nn- n Ø). Since ||||| < 1 required for p 2 subject to (r(p) 1, we can identify any single-qubir state p with a vector n in the unit sphere 2 C R3, Similarly, any unitary operation acting on a single qubit may be represented as sequence of rotations on the Bloch sphere (Nielsen & Chuang [20 T), thus making this representation convenient for visualizing feature maps associated with quantum kernels.
By associating the quantum Hilbert space with a feature space H. we can define a feature map that gives rise to quantum kernel (Havliček et al. 2019 Schuld & Killoran 2019). We consider a data- data-deeendent unitary operator (xx and prepare a density matrix p(x) = U(x) (0) (x). where (0) (0) represents the 2n x 2" 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 (x)) p(x) with the corresponding inner product (p. p') Th(pp'). Under
3

---

Under review as a conference paper at ICLR 2023
this feature map, the quantum kernel is defined as k(xxx')) x') (x)(x), m -r(x(x))(('))
which inherits symmetry in its arguments from ( With this association between the feature map (x) 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 A 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 probabilistic nature of quantum operations. In practice, a quantum kernel method computes the kernel matrix entries a quantum computer by evaluating the value of the observable [0} {0) on the state (x)) (0) [o) U (x'(xx))) (x))U(x).
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 al. 2021 Hubregtsen et al.] 2021). it is often still unclear how to construct a quantum kernel that will be suitable for learning on a 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. this section we discuss simple example where the high dimensionality of the feature 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 i consisting entirely of indepedennt Gaussian features, the operator Σ
Ex [ybns is proportional the identity operator. Since Σ shares eigenvalues with Tg of Eg. 1 (Appendix A), the eigenvalues of K concentrate around unity a rate O(P-1/2) (Rosasco let al. 2010). Analogously, we consider a quantum feature map where states p(x) are prepared by 2 dimensional random unitaries U (x), with the uniform distribution over unitaries being described (e.g.,Colllins Collins & Nechita (2016)). Then, identifying a correspondence Σ - Be-ut2 (p(x)) 2 (x)) in the quantum case and applying standard results from measure theory, one can directly compute the spectrum of Σ (Appendix A.. This computation yields 2n (2"+1) nonzero eigenvalues with magnitude 2 ""(2" (2" + 1) and thus the nonzero eigenvalues of K again become uniform as n >> oo. Since the largest eigenvalue exponentially small n. generalization requires the number of data points to be exponentially large in n. The connection between the magnitude of the largest eigenvalue and the required number of training samples can be seen directly from Kübler et al. 2021 Thcorem 3), although it is straightforward consequence of many older results, for example, (Dictrich et al., 1999 Bengio et al. 2005 Liang et al. 2019; Bordelon et al. 2020 Canatar al. 2021p. 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.
by the Haar measure (e.g..
3.1 LIMITATIONS OF FIXED QUANTUM EMBEDDINGS
To make the example concrete, we consider the following learning problem. This learning problem and the failure of fixed quantum embeddings on it were considered in |Huang al. (202T) Supplementary
Information 9). For input E (0,
n) the goal is learn target function f(x) cos (sr(m))
where (n)) the last element of the vector x. Since learning this function is 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 a badly designed quantum kernel fails on 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
cos (z((0/2)
isin (2(5) (2)0)/2)
(x)
U1)
U(rli)) R. (a())=
(3)
isin (2000/2 /2) cos (2000/2
1=1
4

---

Under review as a conference paper at ICLR 2023
xx))x))
0-6 R(
10) (ex) Rg (cx')
Fxt
0- 160
e<1
Figure I: 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 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. 6 with
50 and
(top) e = (bottom) = 0.25) Tuning bandwidth escapes the "curse dimensionality" associated
with high-dimensional feature space. For = 50 and f(x) cos (5)) quantum features that nearly orthogonal result in narrow kernel (c top) and failure to generalize, while tuning bandwidth (c 1, bottom) recovers KRR generalization performance.
where x j=1 is the tensor product single-qubit operations and (g) represents rotation of about the a-axis of the single-qubit Bloch sphere (see Fig. [T). For this feature map, the embedding factorizes qubits p(x) (xx)) 8 f= p(x(1)), and
(2l1) icos (200) (2(5)/2) /2) sin (z(5))
-i (x/6)/12 sin (2060) (60112) sin (z(1) /2)
((x(0))
(4)
with the kernel given by
II cos? ((25)- 1=1
x(x,x' = Tr(p(x)p(x'))
(5)
While this kernel is obtained via quantum operations, the fact that has closed form expression makes it classically easy to simulate. Nevertheless, it is useful toy model (Kübler et al. 2021 Huang et al. 2021) for the analytical analysis of exponentially large quantum feature spaces. Since the input data is E {0, ))",, the kernel becomes delta function: k(x, x') 8x.x'. Therefore, any two points in the feature space p(x) and p(x') ) for x F 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 a subexponential (in n)) training set size.
3.2 BANDWIDTH ENABLES LEARNING
The preceding example highlights how quantum kernel methods utilizing high- sigee-iiensional spaces can fail to generalize. Our central technique for mitigating this limitation will be to introduce bandwidth to quantum kernels (Shaydulin Wild 2021). We now reconsider the kernel with the feature map of Eq. and introduce a scaling parameter É [0, 1] that controls the bandwidth of the kernel. The feature map and the kernel become
((x(i)) Rrg (coli), xxxx')) II cos² (c(z5)- (2)6)))2)
n
(6)
Geometrically, the factor restricts features p(x) to smaller region of the Bloch sphere (Fig. [A]. Consequently, the kernel matrix is no longer diagonal, and we can straightforwardlyy check that simply tuning allows KRR with kernel Eq. to generalize (see Fig. B))
5

---

Under review as a conference paper at ICLR 2023
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 of quantum kernels equipped with bandwidth. We derive explicitly the spectrum of the bandwidth-eeuipped quantum kernel with the feature map Eq. and show how the bandwidth makes the spectrum less "flat," thereby enabling learning. Our main tool is the theory developed in [ordeloo et al. (2020); Canatar et al. al.] (202T) where the generalization error, as 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- KERNELS
We consider the quantum kernel with the feature map given by Eq. 6 and the input distribution x ~ Unif([-n,, ")",, as previously studied by Kübler et al. (202)) ). For a single qubit, the kernel
becomes k(x, r') cos? (c(x r2)/2) with bandwidth parameter and the eigenvalues can be
computed as follows (see Appendix B):
A1
+ (2nc)2 + v(1 sinc(2nc))2 + (6sinc(Te)²
A 4 4
sinc (2Tc),
8
8
8
3
1
1
A
+ sinc((To))
8 V sine(2nc))² + 16sinc(Te)3,
1= 0.
8 8
For an n-qubit system, the largest eigenvalue 1/max of the kernel in Eq. falls exponentially with n for c (1) and makes generalization impossible with P poly(n) amount data (Kübler et al. 2021) (see Appendix. BB). To prevent Mmax decreasing with we choose bandwidth that scales with (i.e., c= an with a ~ O(1) and 0). In Appendix B we show that a 1 is required for generalization. We consider
1/2 henceforth. Then, all nonzero eigenvalues of the n--ubit kernel 6 be expressed as 1 X A with kn + k2 + ka asymptotically (with n) look like
where the single-qubit eigenvalues
a 2
A R 1,
6n
180n2
Starting from A = n and K2- = h3 = O, the hierarchy of cigenvalues obtained in this way are given in Table T We denote each of these eigenvalues 7 and their corresponding eigenfunctions as
Table 1: Hierarchy of eigenvalues based on their scaling. N ((n,k) denotes the degeneracy of cigenvalues with scaling n -k and n, k) denotes the form of the corresponding eigenstates.
n h
Degeneracy (n,
Eigenstate In, k)
n
n
( +
(oh) 1b)) (0(-1) 1)
[2/2]
n 2 n
(eb)) (0( 2)
((be) 002 (w/)) (0 Wks)
|bb 0(m-3)
(1b2) 18 (1)) ((n (122) (&a)
(x), where & indexes the overall scaling of the eigenvalue and z indexes each of the individual eigenvalues with scaling n kk The degeneracy N(n, k) ~ O(n²) denotes the number of eigenvalues Mi, Okn for each k. Notice that the quantity Tjk. ((n, k)mj,2 ~ (,(() with respect the
input dimension and its value depends on and k. For each k. we will further make the approximation Thi 2 s for all pairs 2, since the spectrum is almost flat at each scaling k (see Figure A
We obtain the projections of target function f(z) the kernel eigenfunctions as āk,z I (()))).. We also define the total target power at each scaling aZ = -E With the eigenvalues and the target weights ag. the generalization error is given by CCanatar et al. 202T) (Appendix C)
Ni(,k) kg
2
TTk
a T
Eg 1 7 k
K = X 1+
(K )17))
KC + Or
( agijk)

---

Under review as a conference paper at ICLR 2023
where À is the KRR regularization parameter, should be solved self-consistently, and we have
defined ag; = N(n.))' Taking the large qubit and large data limit (n - oo and P + oo) while
keeping ay 0, for some mode (meaning Onn)), the generalization error decouples
across different scaling limits and becomes
R² 1 7 (n (k)))))
Eg(ai)=
dE
2
(10)
The target modes with k >> remain unlearned since 0432- 0 and the modes k < have already been learned using the provided data since 0ggec 0o. This scaling defines learning stages where each stage single mode is being learned, and the remaining modes contribute as constant error. The term in the parentheses goes to zero as a + oc (see Appendix C). Hence, when the mode / is completely learned, the ratio of the generalization error to its initial value becomes Ea(a==x)
E,10) = (E / x.) Therefore, given a data budget P ~ Onn)), the quantum kernel amount of power placed in the first modes and quantifies the task-model aligmment.
is guaranteed to generalize to target functions whose weights beyond mode | are vanishing. The quantity C())
(ay =oo) called the cumulative power (Canatar et al. 2021 describes the
[0]
It was shown in Canatar al. (2021) that kernels generalize better for target functions with sharply rising C()). In our case, for generalizability at P ~ Onn') samples, it is a necessary but not sufficient condition for target functions have good task-model alignment for which C(I) =s 1. Note that the trace of this kernel is (xx x)p(x)dx = 1, and therefore the eigenvalues satisfy Σx,= This 1.
Flatness of the spectrum, then, implies 1/k.z (33")) since there are 3 nonzero modes of the kernel in Eq. (sce Appendix B). Equation | suggests that even if the target is aligned well with the kemnel, 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. shows that P ~ Onn') samples yield an excess generalization error Eg = - C(I). In Figure 2
show the results of simulating the kernel of Eq. with 40 qubits for a target function
given by f(x) e =|1 For c = 1, the kernel has a flat spectrum (Figure 2/ with poor
alignment with the task (Figure BB). 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. Figure 2C, 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 very few eigenmodes become learnable while the target cannot be fully explained by those
modes. In Figure 2 we find that the optimal bandwidth parameter is c" Rs (see Appendix
In
10-4
10-3
1.00
1.00
10
10r4
10-5
0.10
67 B.G
polyin-
0.00
BLGG
0333
003
0.11
10
G.1
11
10
13A
1PP
10
Figure 2: A Eigenvalues of the kernel Eq. with respect to data x ~ Unif([-x, m)))). Learnability is explained by the preservation of large-eigenvalue eigenspaces; without bandwidth, the model provably cannot learn in poly(n) complexity due to the flat spectrum. B The projections of the target f(x) = - xi| /m² on the eigenvectors of the kernel for each bandwidth. Apart from the flatness of the c kernel, its eigenfunctions align poorly with the target. C Generalization error as function of the number of training samples computed by using theory (solid lines) (Eq, (9) and performing kernel ridge regression empirically (dots). Bandwidth e yields constant learning curve. While all < kernels provide improvement, an optimal bandwidth parameter c* z 2/n gives the best task-model alignment.
7

---

Under review as a conference paper at ICLR 2023
4.2 EVIDENCE OF PERFORMANCE GAINS REAL DATASETS
To evaluate our theory in a practical setting, we consider two previously proposed quantum kernels that have been conjectured be hard to simulate classically: kemnl with feature map inspired by instantaneous quantum polynomial-ting (IQP) circuit (Shepherd & Bremner) 2009; Hav liek 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 et al. 2017), KMNIST CCanuwat 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 Shaydulin & Wild (202T); Huang al, (202T); Peters et al. (202T). We use the kernel values reported in Shaydulin & Wild (2021), which were evaluated with high precision using idcalized (moiscless) simulator. In practice, an additive error is introduced when evaluating the kernel values on fault-tolerant quantum computer. Bandwidth-equipped kernels are robust against this error; see the discussion in Shaydulin & 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 e = for the IQP and EVO kernels. We also report the test performance with bandwidth parameters e* optimized by hyperparameter tuning for each kernel using cross validation (see Appendix Eb. For both kernels, bandwidth significantly improves the test performance.
IQP
EVO
Random Guess
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 over out-of-the- fie-theeboxx quantum models, opening up the possibility of better workflows for general quantum machine learning on many qubits via hyperparameter tuning.
To test intuition, present in Fig. 3A 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. BC), thus implying, together with the previous point, possible generalization.
10
04 6:01
0.6
0.4-
10/7
10-39
0.01
66-
17
167
Figure A IQP kernel function example: Intuitive behavior of bandwidth persists even when quantum kernel is not strictly shift-invariant. B IQP with the addition of bandwidth is capable of recovering significant target alignment with FMNIST dataset. While the spectrum for c IQP 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 generalization of quantum kernel methods, and they provide upper bound on generalization 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 measure of "approximate dimension" of
8

---

Under review as a conference paper at ICLR 2023
the span of the training set given by Σx=1 Ei where (tt)==1 are the eigenvalues of the kernel matrix. This number is effectively a measure of the flatness of the spectrum of the kernel and is used in numerical experiments in Huang et al. (202T) An alternative analysis is given by [Banchi et al. (021), who derive bounds generalization error using quantum information techniques and show that near-identity kernels resulting from large dimensionality of the feature space preclude generalization. We use the construction from Huang et al. (2021 Appendix I) as our
motivating example in Sec. E
Kübler al. ( 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 purity of the mean embedding provides an upper bound on the largest eigenvalue of 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 method for controlling the inductive bias of quantum kernels. Our contribution is using the techniques of Kübler et al. (202I) to derive the spectrum of the bandwidth-equipped kernel Eq. and explicit formulas for the expected generalization error.
Shaydulin & Wild (202I) introduce the concept of quantum kernel bandwidth and provide numerical 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 no analytical results for generalization. We reinterpret the data from (Shaydulin & Wild (202I) 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 least n qubits (where n 10 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 a 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 is that thoughtfully chosen hyperparameters can significantly improve the performance of quantum machine learning methods. Identifying such hyperparameters 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 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 is guaranteed to improve the spectrum, it does not necessarily lead to good alignment. For example, in the limit of - the spectrum has only one nonzero eigenvalue, although learning is still not possible (see Appendix DD. 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 noisy quantum computer, the quantum hardware noise would affect the spectrum of the kernel. Hardware noise reduces the purity of embedding, leading to trivial lower bound generalization error from Kübler et al. (2021) Theorem 1). |eeyraud et al. (2022) give a more detailed analysis. While outside the scope of this work, the impact of noise on generalization is nonetheless important consideration for near-term prospects of quantum kernl methods.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Héctor Abraham, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, Thomas Alexander, Alexandrow- ics, Arbel, A Asfaw, C Azaustre, P Barkoutsos, G Barron, et Qiskit: An open-source framework for quantum computing. URL https://doi. org//0.528//zemodo. 1562111, 2019. doi: 00.5281//zeoodo2522111
Madhu Advani, Subhaneil Lahiri, and Surya Ganguli. Statistical mechanics of complex neural systems and high dimensional data. Journal of Statistical Mechanics: Theory and Experiment, 2013(03):P03014, 2013. doi:
Leonardo Banchi, Jason Percira, and Stefano Pirandola. Generalization in quantum machine learn- ing: A quantum information standpoint. PRX Quantum. 2(4), November 2021. doi: 10.1 10.1103/ 10. pixquaatuu.22.40322.. URL https:://do. org 110 1103/ prxquant um. 040321
Yoshua Bengio, Olivier Delalleau, and Nicolas Le Roux. The curse of dimensionality for local kernel machines. Technical Report TR-1258, Université de Montréal, March cat. on/
2005.
the fo---orreeoddddaaessssaaaa--oooo
Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learn- ing. pp. 1024-1034. PMIR, 2020. URI. htttps://proceeediggggg http://eeeeinnn........rsss///// wtt....e/rs.s/////
borde on20a ht.l
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model align- ment explain generalization in kernel regression and infinitely wide neural networks. Nature Communications, 12(1):1-12, 2021. doi: 10.1038/s41467-000 -2121103--.
Tarin Clanuwat, Mikel Bober-Irizar, Asanobu Kitamoto, Alex Lamb. Kazuaki Yamamoto, and David Ha. Deep learning for classical Japanese literature. arXiv:1812.00118,, 2018. doi: 10.20676/ 00000341.
Benoît Collins and Ion Nechita. Random matrix techniques in quantum information theory. Journal of Mathematical Physics, 57(1):015215, January 2016. doi: 10.1063/1
1031003/1.4936880. 49936880.
Rainer Dietrich, Manfred Opper, and Haim Sompolinsky. Statistical mechanics of support vector
networks. Physical Review Letters, 82(14))2975, 1999. doi: 10. 10.11000 1013//hhyseeeL.ee.....2.7 82.2995..
Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term 2018. doi: 10.485550/axxiv1.882.66000
processors, /802vv
Jennifer R. Glick, Tanvi P. Gujarati, Antonio D. Corcoles, Youngseok Kim, Abhinav Kandala, Jay M. Gambetta, and Kristan Temme. Covariant quantum kernels for data with group structure. arXiv:2105.03406, 2021. doi: 10.48550/arXii:21155.44000
Vojtéch Havlfček, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta. Supervised learning with quantum-enhancee enhanced feature spaces. Nature, 567(7747::29--212 March 2019. doi:
Valentin Heyraud, Zejian Li, Zakari Denis, Alexandre Le Boité, and Cristiano Ciuti. Noisy quantum kernel machines. arXiv:2204. 12192, 2022. doi: 4145500/
Zoë Holmes, Kunal Sharma, M. Cerezo, and Patrick J. Coles. Connecting ansatz expressibility to gradient magnitudes and barren plateaus. PRX Quantum, 3(1), January 2022. doi: 10.1103/ prxquantum.3.01133
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 Communica- tions, 12(1). May 2021. doi: 10.1038/s41466 0088//444670021111 -207--22--255999
Thomas Hubregtsen, David Wierichs, Elies Gil-Fuster, Peter-Jan H. S. Derks, Paul K. Faehrmann, and Johannes Jakob Meyer. Training quantum embedding kernels on near-term quantum computers. arXiv:2105.0222 2021. doi: 10.48550/arXiv 10000000
10

---

Under review as a conference paper at ICLR 2023
Jonas Kübler,
Simon
Buchholz, and Berharrd Schölkopf.
The inductive bias
of quantum kernels. URL
Advances in Neural Information Processing Systems. 34.
2021.
pttp::/proceddngg https///pooeellunssouuo.s......o newrips.eeppp.....
httpp/pp....pppe///////101 pappr//02// /0le/
Pape:
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels. arXiv:/908. 10292, 2019. doi: 10.48550/
Seiiv1990..1299
Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics, 170))1013-1017, July 2021. doi: 10. 1038/
s41567-021-01287
Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9(1,, November 2018. doi: 10. 04788/441477-01--07000
M. Mezard and A. Montanari. Information, Physics, and Computation. Oxford University Press, 2009, doi: 10. 001099/appot1000/770999777777770
K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii. Quantum circuit learning. Physical Review A, 98
(3), September 2018. doi: 10.1 1..1133pyyyrevv.9..222222
Michael A Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cam- bridge University Press, 2011. doi: 00.1017/CB09988511197766
Evan Peters, João Caldeira, Alan Ho, Stefan Leichenauer, Masoud Mohseni, Hartmut Neven, Pana- giotis Spentzouris, Doug Strain, and Gabriel N. Perdue. Machine learning of high dimensional data on noisy quantum processor. npj Quantum Information, 7(1), November 2021. doi: 10.10888/415344-21-00000
Zbigniew Puchala and Jarostaw Adam Miszezak. Symbolic integration with respect to the Haar measure on the unitary group. Bulletin of the Polish Academy of Sciences: Technical Sciences, 65 (1):21-27, 2017. doi: 10. 1.1115//pasts-2277-0000 2017-0003.
Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integral operators. Journal of Machine Learning Research, 11(30):005-33,, 2010. URL httt:://tmmmm// www.mmlrrrrrrgro.e.m org. pagepapers//////
@11/rosascol0a.ie
Berhhard Schölkopf, Alexander J Smola, Francis Bach, et al. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, 2002. doi: 10.755 I/mipress
4175.001.0000
Maria Schuld. Supervised quantum machine learning models are kernel methods. arXiv:2101.11020, 2021. doi: 00448550/aXx..2201.10000
Maria Schuld and Nathan Killoran. Quantum machine learning in feature Hilbert spaces. Physical Review Letters, 122(4), February 2019. doi: s0.1103/physrevlettt 122.040504.
H. S. Seung, H. Sompolinsky, and N. Tishby. Statistical mechanics of learning from examples. Physical Review A, 45:6056-6091 Apr 1992. doi: 10.1 w...///hysee...5.600000
Shawe-Taylor, C.K.I. Williams, N. Cristianini, and Kandola. On the eigenspectrum of the Gram matrix and the generalization error of kernel-pca. IEEE Transactions on Information Theory, 51 (7):2510-253) 22222, 2005. doi: 10. 109/TIT.2005.850000
Ruslan Shaydulin and Stefan M. Wild. Importance of kernel bandwidth quantum machine learning. arXiv:2111.05455 2021. doi: 10.48550/arxiv22111 11.05551.
Dan J. Shepherd and Michael J. Bremner. Temporally unstructured quantum computation. Proceed- ings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 465:1413-1439, 2009. doi: 10. 10.1098/rspa.200 wtt.://p.p.00.044...... 0408.
Bernard W Silverman. Density estimation for statistics and data analysis. Routledge, 2018.
11

---

Under review as a conference paper at ICLR 2023
The PLAsTiCC team, Tarek Allam, Anita Bahmanyar, Rahul Biswas, Mi Dai, Lluís Galbany, Renée Hložek, Emille E. O. Ishida, Saurabh W. Jha, David O. Jones, Richard Kessler, Michelle Lochner, Ashish A. Mahabal, Alex I. Malz, Kaisey S. Mandel, Juan Rafael Martinez-Galarza, 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- series classification challenge (PLAsTiCC): Data set. arXiv:1810.00001, 2018. doi: 10.48550/ a8Xiv. 10.00001.
John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. doi: 00.1017797813118481122
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 KI. Barkoutsos, Stefan Woerner, Ivano Tavernelli, Federico Carminati, Alberto Meglio, Andy C. Li, Joseph Lykken, Panagiotis Spentzouris, Samuel Yen-Chi Chen, Shinjac Yoo, and Tzu-Chich Wei. Application of quantum machine learning using the quantum kernel algorithm on high energy physics analysis at (at.rssrreereearrc...3333211
the LHC. Physical Review Research, 3(3), sep 2021. doi: 10.
Han Xiao, Kashif Rasul, and Roland Vollgraf. MNNS:: novel image dataset for bench- marking machine learning algorithms. /7X8.0/70..077477 2017. doi: 10.48550/arXiw1
Kaining Zhang. Min-Hsiu Hsich, Liu Liu, and Dacheng Tao. Gaussian initializations help deep
variational quantum circuits escape from the barren plateau. arXiv:2203.09376, 2022. doi: 2..550//rXi..2203.9999..
12

---

Under review as a conference paper at ICLR 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 finite-dimed diftesiiinnii 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 affect the learnability of distribution.
Given symmetric positive semidefinite kernel function k X'x X + R. the integral kernel operator Tk (2(x) > (2) is defined according to its action f T2((X))
(Tx / (xx,,)))(
(A.1)
quantum kernel defined as the inner product of two quantum states,
kxx, x') = (p(x)) (x Tr (T(((x)((x')) = Vec (p(x)) Vee (p(x'))
where we have introduced the vectorization map (e.g., Watrous 2)18)) Vec I(CC) - Ed which stacks of d x d matrix into d² column vector and where I.(C4) denotes the space of linear operators of the form (d' + Cd. Throughout this section we will consider d-dimensional quantum states and operations (where d 2n in the case of n qubits). We will frequently use the identity
Vec (A)* Vec (B) = (A, B) Tr A
VA, E L(C").
Observing that the RKHS of kernel A is defined (see, e.g.. Schuld 2021)) by functions of the form f(x) <p(x), H),
we can rewrite Eq. A. as
(T&))()) = Vec (p(x)) / Vea (p(x') Vea (p(x')) Vee (H) u(dx')
(Vec (p(x)) E Vea (H)),
(A.2)
where we have defined the covariance operator,
= / Vec (p(x') Vec (p(x')) p(dx') = . p(x') @ p(x')'((dx'),
u(dx')
(A.3)
and the last equality in Eq. A.2 holds whenever the quantum embedding is pure state (i.e., p(x)
[x((x))()(xx) for some (x)). We can intuitively understand this operator by analogy to linear feature maps: If we consider re-dimensional real-valued input vectors X' c I2 and assume x are centered such that Ex(xx = 0, then the covariance operator defined as = [xxxx such that
(E)y- E[r,,,]. Equation A.3 therefore describes a 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 [t(() 1.
We are interested in the eigenvalue equations
Vec (H) 1) Vec (H) (Tx+) = 1)0(x).
Given the operators defined in Eq. A.1 and Eq. A.3 one may verify (see, c.g., Shawe- Taylor et al. (2005)) that the following statements hold under the identification xx(x) + Vec (p(x)) described above.
(S1) For every eigenfunction ø satisfying (TxΦ)(x) ())())) there is corresponding eigenvec- tor Vee (H) of Σ given by
Vec (11) o(x) Vec (p(x)) u(dx)
such that Σ Vec (H) Vee (H). Furthermore, from the bijectivity of the Vec operation and the fact that Hermiticity is preserved under convex combination, it follows that H is Hermitian.
13

---

Under review as a conference paper at ICLR 2023
(S2) For every eigenvector Vec (H) of E satisfying E Vec (H) 17 Vec (H), there is conre- sponding eigenfunction T& given by
(xx) Tr(p(x)H} = Vec (p(x)) Vec (H)
such that (T) - n)))).
(S3) Assuming that eigenfunctions Φy of Tk indexed by eigenvalue 7/ are orthonormal,
(Øx: (1) = J on (x)" di (x) = dst,
the eigenvectors Vec (H&) of indexed according to eigenvalue 77 satisfy
Vee (Hx) Vee (H1) Tr [ 7/2 Eeg
whenever 7/ (when TiK may safely ignore Vec (H&) in the null space of E).
Letting spec (A) denote the sequence of eigenvalues of an operator A sorted nonincreasing order, it then follows from (S1) and (S2) that
spec (Tk) spec (E)-
The mean embedding is defined the average state with respect distribution over X':
Pu p(x)u(dx).
As shown in Kübler et al. (2021 Lemma 1), the inequality 1mmax (E) S V Tr 2 for the largest eigenvalue of Σ. Let be the Bloch vector for Py defined be parameterized as
provides a bound qubits, which can
n (sin f cos Φ sin sin o, cos
(A.4)
Then Tr (1 11 This provides geometric argument for the use of bandwidth in a single-qubit system (or product thereof). For instance, consider each shaded region in Fig. TA representing the subspace spanned by quantum states associated with the feature map giving rise
Then we have that the maximum eigenvalue of suppressed like 7/max
(Σ) S (1 ||n|| 1/12///////3 as the centroid n of each region (representing Pp.) approaches the center of the Bloch sphere. By
limiting bandwidth (and therefore restricting the shaded region of Fig. [ to a polar cap of the Bloch
sphere), the upper bound on Mmma (2) is lifted, and the possibility of learning on data is restored.
A.1 SPECTRUM OF A RANDOM QUANTUM EMBEDDING
foundational observation for this work is that using a kernel associated with a feature map that completely utilizes a high-dimensional feature space leads poor learning guarantees due the flatness of the corresponding spectrum. Here, we present an extreme (and somewhat contrived) example where a quantum feature map associated with random state vectors leads flat kernel spectrum. We assume the existence of a data distribution and feature map x - U (x) (x) (x) for which unitaries U (x) are sampled uniformly over the space of n-qubit unitaries (2 Such distribution may be achieved by sampling uniformly with respect to the Haar measure ((dU) (e.g.. Collins & Nechita (2016). As described in Rosasco et al. (2010), the spectrum of K concentrates around the spectrum of Σ. We therefore explicitly compute the spectrum of Σ corresponding to random quantum features. Using standard results for integration with respect to the Haar measure (Puchala & Miszczak 2017), compute the average elements of Σ as
[IkE] Jeren
(
[ Ju(zm)
2n -
2m222n (da.5ee 5zedzz)
(A.5)
14

---

Under review as a conference paper at ICLR 2023
The terms associated with 6 1 correspond to the identity operator Ign, while the terms dzeds
contribute to either 2 diagonal components Eūs,ä for 1, 1.....2" 22 or 2" 1) mama off-diagonal components Ejj.ji whenever *
2
2
Σ 4
(i
(A.6)
Equation iA.6iis therefore a direct sum of subspaces proportional to 21g and subspaces proportional to + X2, the latter of which may be easily diagonalized. Combining with Eq. Ai5]yields the spectrum
with multiplicity 2 -2" 2
spec (Σ) = 2"
with multiplicity (2"--11)
Coincidentally, the mean embedding associated with this feature map proportional to the identity; that is, Pa Ex [x()]] 1/2".
B SPECTRUM OF THE BANDWIDTH- KERNEL
Here we derive the spectrum of the integral operator for kernel discussed in the main text. We follow the technique diagonalizing Σ described in Appendix and used Kübler al. (2021] Appendix
C). We first derive the spectrum for the single-qubit cone-dimensional data) case. Then we leverage the observation that the kernel factorizes over the qubits obtain the full spectrum for the general n--dmeensiona case.
We begin by considering the input æ E Uniform[-T, n|. by the unitary
Recall that the feature map p(x) generated
car ssn
Co
((x) = cos
2
2
Then, the vectorization of the image of a data point x in feature space p(x) = U(x) (0) (0) is
cos? (cr
-i cos
sin
Vec (p(x)) =
i cos
sin car
sin
2
and the corresponding kernel is
x'x Vec (p(x)) t Vec (p(x') cos? ( x²)
(A.7)
Our goal is to compute the eigenvalues of the integral operator T3 defined
(Tx)))<)) = p(d=') z')x Dou (z)x(z).
(A.8)
Here refer single-qubit eigenvalues as A and many-qubit eigenvalues as иы- As described in Appendix A this is equivalent to computing the eigenvalues of the covariance operator Σ given by
Σ = /
Vec (p(w)) Vec (p(v)) ((dy)
cos't (
cos sin 4M
cooos sone"(() sin(
cos ( (#)sinn sin"
- cos ( (
sin
oos ( 4 sin ( cos sin 2 (*)
- cos (in)snnn (+)
dy
2TT
3
cy
sin
cos
sin cos't ( sin?
ccos + sin (
cos'
sin
cos 2 sin -ocos (in"
siu
0
0
02
02
0
02
0
03
15

---

Under review as a conference paper at ICLR 2023
where
1
01 + sinc(cT):: + (sinc(2cr)
2
1
02 Sine(2cT)
1
sinc(eT) + (2nT
03 2
We can easily obtain the eigenvalues of this matrix, which are
3
A1
+
sinc(2 (2Tc) + (1 -iin((2r))) + 16sinc(Te))
8
8
1
sinc(2Tr))
4
3
A
(inc(2
(11 sinc(2 + 16sinc(Tcc)
8
4 0,
(A.9)
where A A2 As A for all [0. With 1, the cigenvalues become 1, á 4. O. respectively. Now we can examine the impact of bandwidth on the eigenvalues (see Eq. A.9) of the integral operator. We first observe that for -> 0, all eigenvalues except the top eigenvalue become zero; that is, A1 -> 1 and 22, X3, A + 0. 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 is consistent with the observation that in 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. O has eigenvalues of the form
Mhingnana X 2
71 + 72 + 12 n4 n2
11, 72 n3 T4 Z U (0),
where the nonzero eigenvalues are obtained by setting n4 = 0 since a = O. Here, we note that the number of zero eigenvalues grows exponentially with number of qubits 4 3 However, its ratio to the total number of eigenvalues vanishes since
Umingnams 00
- 3
n 100
O;
(Manngnnna
therefore the bulk the spectrum remains nonzero.
For (1), the spectrum remains flat as + This can be easily seen with the case 1 where the eigenvalues are given by
7k 2-
where & = n2 n1 and takes values in (O.... nt.. Each eigenvalue is degenerate with N (n,,k) k)
2 (*),, and of course Σh=o (n, kt) = 3 gives the number of nonzero eigenvalues. To obtain nonflat spectrum, need eigenvalues scale with the number of qubits n. In the next section, do so by imposing scaling conditions on the eigenvalues.
For completeness, also provide the unnormalized eigenfunctions of the kernel using the eigenvec- tors Σ. Inverting the Vec operation, we get the matrices
H Asine(me)+ / (1 sinc (2xc)) (we)
1)
H₂ 0
(2rc)
4sino(ste) / (1 sinc (2re)) 3 (
9)
(1 0)
0
H₃
sincl (2xc)
H4
16

---

Under review as a conference paper at ICLR 2023
The corresponding eigenfunctions are given by (1(x) H), and become
4sinc( + v sinc((2rc) 16s)
(1(x) sin"
cos²
sinc(2
(2(x) sin(car)
(1(r) = sin?
c
+ cos?
c
4sinc(ne)
v(1 sinc(2 16sinc(Te)*
2
1 sinc(2
(x) =
Setting = 1, we obtain the eigenfunctions given Kübler et al. (2021): Φ1(x) = L, Φ2(x) i sin(x), 53 cos(2), and Φ4 = O. Note that unlike the I case, the eigenfunction (z)
general is not constant.
B. 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 lower bounded by the L2 norm of the target function with probability least
Eg (1 - -
which matches our result from Sec. The result in Kübler al. (202T) depends the exponentially small largest eigenvalue of the kernel compared with the amount of training samples. In fact, from Eq. it easily follows that for polynomial number of training samples P n' and exponentially suppressed largest eigenvalue Mmux ~ 2-", the learning is impossible as - oc. Kübler et al. (2021 Lemma proves that the largest eigenvalue of the kernel is upper bounded by the so-called purity:
Mmax S MMp
where purity is given by M, ((dx))u(xx)(((s x'). We also demonstrate their proof here for the reader's is convenience. Consider normalized kernel satisfying k(x, x) = for all x. The normalized eigenfunction @max (x) corresponding the largest eigenvalue Mmna L.2 bounded by the constant 1/2 function 1/nax (x) since
= k(xxx(xx Mmxx max (x))
Here 1xx 1 the constant function. This immediately implies that
Mmax -f (dxx)) x') Dmax (x) (x)xmxxxxx)
/ [(dx))((dx')) ((x, xx)((x)(((()))))))) = Trule
S -1
Vmuxx
Given this bound, we demand that the bandwidth should scale such that the purity stays constant with respect to the number of qubits For our example kernel, this condition translates into
M
2 (1 + sinc(Te(n)))".
Inverting this equation is not possible. However, its numerical solution yields scaling for bandwidth as
<(n) = a /n"
(A.10)
where O,, depends on the fixed purity Mn. Note that this is lower bound for the bandwidth to keep purity from inversely scaling with n. In principle, we could allow purity to increase with n depending the target function. For example, c(n) ao 0 yields perfect purity since there only a single mode. Hence, we conclude that the bandwidth should at least scale as
1
an
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 specific target functions.
17

---

Under review as a conference paper at ICLR 2023
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 n + co. Asymptotically, the kth power of these cigenvalues looks like
a²x²²
X
6n
n
a π
a²
1
X2
+
O
6n
5n
n²
t x
n² k +
1 +
O
180n²
42n
n
Notice that with this scaling of the bandwidth parameter, the largest eigenvalue remains constant asymptotically. We also remark that eigenvalues composed of large number (k R n) of X and X scale as e em log n, and we consider them decoupled since none of these modes can be learned with polynomial amount of data. Hence, we conclude that the spectral bias induced by the bandwidth restricts the space of learnable functions to lie the space spanned by eigenfunctions of the form
(1n) 0(n-=2-na (222) 8m2 lebs) 8m3
such that n2 + n2 < n. It can be shown that the hierarchy of eigenvalues obtained in this way scale polynomially with n, as discussed in Sec. g In [.2 we present the first few eigenvalue scalings where N(n, k) denotes the number of eigenvalues with scaling lkk, O and (v) denotes the corresponding states. We denote each eigenvalue T),, with two indices: is corresponds to the scaling of the eigenvalue as n and z = =1,... 1,.....N Nn, k) indexes the N (n,kk) k) eigenvalues with the same
scaling.
Table Degeneracies ((n, k) of quantum states for the first few scalings. Degenerate States and Spectrum Scaling
Scaling
Degeneracy M(n,)) k)
States (V)
n
w1
n
w1 ((- 1)
[z/2]
2
(2 + (
11) (n 2)
[1/2]
(x/) (0 1) (15))
n
3 + (7)) )
(1)) (mn-3) [1/2)
63
(xb)) ((a-2) (1b2) ((/a)
n
( (")
(1)) ((n-1)
(1/22) 01
(24)) ((n-3) (1/z2) 02 lsbs), (w/ (0))((12) 1 02
B.3 BANDWIDTH AND PROJECTED (BIASED) KERNELS
An alternative way to control the inductive bias of the quantum model is to define the kernel in terms of the reduced density matrix (e.g., single-qubit): p(z) Trp...n11 (p(z)), where Trp...-11 (-) denotes the partial trace over qubits 1....,n of n--ubit system. For detailed discussion of
such kernels, the interested reader is referred Kübler al. (02T):Huamn al. (202T). Here, we
briefly comment on the similarities and differences between the impacts of projection and bandwidth tuning on the spectrum of the kernel.
As shown in (Kübler et al., 2021 Theorem 2), the spectrum of generic projected kernel has one constant (with 7)) eigenvalue, and the rest are exponentially small with n. Contrast that with the spectrum of the Sandwidth-equipper kernel given in Table B.2 Similarly to projected kernels, in hondwitth-equipped kernels the first eigenvalue stays constant as the number of qubits grows. However, the spectrum decay 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.
18

---

Under review as a conference paper at ICLR 2023
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 in quantum neural networks (QNNs) (McClean al. 2018) since both stem from the exponential dimensionality of the space in which the classical data points are embedded (Kübler) al., 2021; [olmes et al. 2022). "Barren plateaus" in the context of QNNs refers 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 high-dimensional quantum Hilbert space. Notably, a mechanism analogous to rescaling the bandwidth has been observed to enable training of quantum neural networks. Zhang et al. (2022) show that if the parameters are initialized from Gaussian distribution with zero mean and variance O for circuits of depth L, the barren plateaus are provably avoided. Rescaling the initialization of trainable parameters avoids barren plateaus by limiting the effective dimensionallty 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 quantum kernels, with the connection coming from the equívalency between quantum kernel methods and infinitely deep QNNs (Schuld) 202T).
C GENERALIZATION ERROR IN KERNEL RIDGE REGRESSION
In this section we review the theoretical generalization error curves for kernel ridge regression developed by Bordeloo al. ) Canatar al. (202T) and extend results to the cases with nonzero ridge parameter and noise on the labels. For kernel machines, reproducing kernel Hilbert space H defines a of functions over which the empirical loss function minimized. Consider a training set D = {x", y } where the inputs are drawn i.i.d. from a distribution p(x) on generated through target function f(x) as yd f(x*) + et,, where et ~ (N( )²) is an additive noise with variance o². Then the predictor is given by minimizing the empirical wran-squared-erron over H:
E X and the labels
J arg min fEH
-((x)) -
A -")²+11"))+ +1
(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') x') satisfying the reproducing property:
(k(x, ). f()) fxx),
where 24 is the Hilbert inner product on H. basis for H can be obtained by solving the integral eigenvalue problem with respect to the input distribution p(x):
f M(x x6 (x' (ippp("'dxx'' = nx)x(x),
/ fo (x()))(()))(() = 5kg,
where {x) is basis for (xX)) with respect to the distribution p(x). A normalized basis for the RKHS H is obtained by the features (x) VTERR (x) that satisfy
(wa (.), v)(()) 8ms
With these bases, the kernel can be decomposed as
x(x, x') Σ nera (x)(b(x)) Σ (x))xxx)
Furthermore, any target function in Ly (xt) can be decomposed
f(x) = Σ (x))(()== = E as
(x),
|1
x
Note that a function belongs to the RKHS only if [| < 0c. In the case where K(x,xt x') has zero eigenvalues while the function f has components along the corresponding cigenfunctions, this function is said to be oft-of-RKKS (since Iifll, = 20), and a kernel machine can learn only the components along the nonzero eigenvalues. We show that the formula for generalization error in
19

---

Under review as a conference paper at ICLR 2023
Canatar al. 22021 Eq. 4) also extends to out-of-RKHS targets by appropriately taking the 7 0 limit.
Given the Px P kernel Gram matrix Ku xx)x the solution to the kernel regression problem Eq. A.II is
(x)) = k(x) (K AI)
where k(x) is P-dimensional vector with components k(x), = k(x, x*) and yı, = y" is P- dimensional vector of the labels. Then generalization error, as function of number of training samples P and the dataset D, is defined
E2( - (fx) 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) D over the datasets of size P. which has been calculated using replica theory in Canatar et al. (202 I.
As function of number of training samples P. ridge parameter X, and variance of label noise o² as well as the kernel eigenvalues }me) and the target weights {āx), the result for (P, D)) becomes
(Canatar et al. 2021):
R²
0x
+ t 7
(A.12)
1
(Pss + k)²
1-7
where
K ==
x
PTR +
(PTr + K)2
Here is to be solved self-consistently and it acts as an effective ridge parameter that depends on the kernel eigenvalues and number of training samples. Even in the absence an explicit ridge parameter (i.e. À = 0), implicit regularization prevents the predictor from having large variance.
C.1 DERIVATION OF EQ. 9 IN MAIN TEXT
In Sec. 4 the main text and in Appendix we have shown that the top eigenvalues Tkk of the kernel in Eq. 6 scale polynomially with the number of input dimensions, that is, TJk,z ~ O(n where the index A: 1, 2.... represents different scalings and index = 1, 1,..., [(n, k) represents the degenerate modes in scaling &. Note that the number of degenerate modes (n, k) grows as (n*)) such that Fj&- N (n, k)) O(1). We also decomposed the target function onto the kernel basis as
ŌR -
(x))xxx
and defined az Σ ((nk) Ex=1
ah as the total weight scaling k. Plugging these quantities in Eq, A.12
we get
2
N(n.k)
a
+ 7
Ep(P) =
+
(Pik. + n:)
1 1-7¹
((n,k)
N(nk))
Pmi.=
-=
- Σ
Σ
mke
7 Σ
Σ
PTle: +
(Pija + k)²
Furthermore, we made the approximation that lık.z R TJk.2' for z, z' since,, large n limit, modes in the same scaling differ from each other with some (I) quantity. Hence, we drop the index Then, in terms of πhp- (nn, k) k))TK generalization error simplifies to
x²
a
(P) =
Th + R)Z + 0o2
The
aA Th
OE T7
(aue7 + x)2²
20

---

Under review as a conference paper at ICLR 2023
where we define og N(n,k) denoting the learning stage. Now, consider the number of samples P to scale with (n²') for some integer Since (n,, k) ~ O(n'), as n. + oc the quantity og becomes
ak<l = 00,
@k ~ O(),
ak<d 0.
Therefore, in the large n. limit, generalization error simplifies greatly and becomes
x² of
anii
Eg(P) = 1 --7 (apT) + x)²
(arT) + x)2²
k>
where 8² = 0² + +E Ex>t dx is the effective noise and k has an explicit solution:
2 (A ` mani
1 +
+
4x (A++
1n S 1 A/i
k= ==
1 + ` - mai)
1 11-1
4Ampos
aj 2 1+ 2 A/T
-faa))
where kzl Mh is the effective ridge parameter and describes the implicit regularization of the kernel model. Note that the total power beyond mode-l acts label noise and also irreducible error.
C.2 OUT-OF-RKHS TARGET FUNCTIONS AND LABEL NOISE
We treat the case where target 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, 7kez 0:
(g = k²
+
Pikk
+ K)2
1 1-
k²
(Pils x))2
+
0²
Σ
ak
7
Σ
ag
kgz
KEI
KEI
where & and y are again
P
PTk
+ 7
(Pnl + R)2²
RdT..
AgT
Notice that target power placed on the modes corresponding to zero eigenvalues act both as label noise and irreducible error (Canatar et al. 2021). This implies that the inaccessible modes in target function due to small training set sizes simply lie outside the effective RKHS defined by the accessible, large eigenvalues. This also implies that very large bandwidths can also impair generalization; for e 2 0 only a single non-zero eigenvalue survives and therefore generic targets which may have many modes corresponding the remaining zero cigenvalues lie outside the effective RKHS. Therefore, the extreme case of very large bandwidth also creates problem. This is just a restatement of the well-known bias-variance trade-off.
D BANDWIDTH MAKES BOUNDS ON GENERALIZATION VACUOUS
The following is sketch of how the main theorem of Kübler et al. (021) becomes vacuous ("fails") in a certain context where we can guarantee that k(x, x ) is lower bounded by some bandwidth- dependent constant.
We first note that this cannot be a positive proof: nothing about lower bounding k( x') can provide guarantee classifier accuracy. Rather, this scenario just shows context in which a lower bound on the ridge regression classifier accuracy based on the largest eigenvalue 7max is no longer effective showing failure of quantum kernel methods.
21

---

Under review as a conference paper at ICLR 2023
Now, we suppose that use bandwidth require that states "not too far away" in Hilbert space. More specifically, we suppose that there is some function A. such that
k(x**
A.
(A.13)
Note that this does not interfere with the requirement that & is L' integrable since we assume that defined a restricted support x E =="" (without this assumption, k integrable in more general treatment). We will show that some choice of A, always ensures that the largest eigenvalue of K (and therefore the largest eigenvalue of T3 with high probability) is bounded. Denote the cigenvalues of K as T), and in particular let Mmax be the largest eigenvalue of K and Ku = Mmax for some eigenvector R... By definition, 7max particular
| =1 (v, Kv) for all R²", and in
(u, Ku) (u, u)
K1
P
Tmax
Σ
KNv 2 (P- 1)4c.
11,
1,P=1
where 1 is the vector of all ones and we have applied the inequality of Eq. A.13 Rosasco et al. (2010) states that
Proposition 10 of
log (4/82)
Pr
sup k
7h S 21
2 21-8, 8,
P
P
where we contrast the empirical eigenvalues 7) with the eigenvalues 7 the integral operator Tk- Note that the empirical eigenvalues 7)k Yi P - co. Hence, with probability at least - 5 it holds that
( P
log (4/62))))
Mmax
A S
(A.14)
P
Theorem of Kübler et al. (2021) states that, with probability at least - c- Thuax P4 the empirical
risk for KRR with penalty À and P training data is lower bounded by
mmax P2
Remp (frt)
lifll..
(A.15)
that Mmax approaches constant A. at rate of O(1/VP); for sufficiently large P. A.15 holds with vanishing probability, and for all other choices of P the bound becomes vacuous with high probability under the condition that v 22 P2/e 2 1, which may be achieved within O(L/VP) precision by choosing
From Eq. A. 14
however,
P P 2P
A.
Importantly, this outcome does not guarantee that KRR using satisfying the inequality in Eq. A.13 will achieve good generalization error. In particular, the choice A. = will result in T3 having a single nonzero eigenvalue associated with the constant function. Rather, this demonstration reemphasizes that there 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 condition (ii); however, successful generalization will still depend on a choice of k satisfying condition (i).
conditions successful classification using quantum kernels: (i) the
this way, we can guarantee
NUMERICAL METHODS
E. EXPERIMENTS WITH TOY MODEL
In Figs. and the main text, we consider the toy kernel k(x,x') x') -I cos ( for varying bandwidth parameter and n-dimensional input data [-T, wr"" and drawn uniformly
22

---

Under review as a conference paper at ICLR 2023
(Kübler et al. 2021). We generate dataset of size P by uniformly sampling P imput points and computing the corresponding labels using a target function fxx). We denote the vector of labels by Rº and denote the kernel Gram matrix by K whose elements are K,, k(x", x"). We obtain the eigenvalues and eigenvectors of the kernel by solving the empirical eigenvalue problem:
Σ P
po Pu. Mh u.
u.b 4 nLl Ó41,
P
where o Pp,kk is the matrix of eigenvalues whose columns are the orthonormal eigenvectors and (mn )== are the eigenvalues. Note that we obtain at most P eigenmodes with P samples and hence runs from I,..., P. Finally, we obtain the target weights by projecting the targets on the eigenvectors of K:
P $ TTy. y.
Using the eigenvalues {m7 k==1 and target weights directly compute the generalization error by plugging them in Eq. A.12 To perform the experiments, we used the Kernel Generalization code by Canatar al. 2 and utilized single NVIDIA V100 GPU with 32 GB of RAM. In Fig. E. present the same experiment as Fig. but for different input dimensions n. We find that the optimal bandwidth parameter e* 2/n. Therefore, the optimal scaling of the bandwidth parameter is ((n=a) for a = 1 in this special case. Note that bandwidth changes both the eigenvalues and the eigenfunctions of the kernel that affect spectral bias and masklmoel alignment, respectively. For alignment and hence yield
certain tasks, faster decaying bandwidths might improve the better generalization.
= 20
n 40
10a
10-2
10-2
10-1
(g(P)
10
(P)
10-6
1e+00
1e+00
10-4
c 1e:01
10-1
1e-01
c 5e-02
Se-02
10
3e-02
3e-02
1e-02
1e-02
10'
10?
10
10'
10a
10a
P
P
= 80
n = 200
10-1
10:1
10-1
10-1
10-1
Fg (P)
10-5
(P)
10-7
10-7
1e400
1e+00
c
1e-01
10-
1e-01
10-4
5e-02
10 31
Se-02
10
3e-02
1e-02
10-13
1e-02
3e-02
10'
10a
10
16a
10a
10'
P
Figure A.1: Generalization error 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 [x]]] /n. and data is drawn uniformly from Unif([-m,,4 x) for 20,40. 40, 80, 200. yields constant learning curve. While all e kernels provide improvement, there is an optimal bandwidth parameter c* ~ 2/n that gives the best task- model alignment. Regularization with small ridge parameter À = 10-10 10 is applied for numerical stability.
Bandwidth
23

---

Under review as a conference paper at ICLR 2023
E.2 BANDWIDTH QUANTUM MACHINE LEARNING ARCHITECTURES
We use the experimental data provided by Shaydulin & Wild 2021 We use the kernel given by the instantaneous quantum polynomial- time (IQP) circuit feature map (Shepherd & Bremmer 2009; Havlicek et al., 2019; Huang et al., (021) and Hamiltonian evolution circuit (EVO) feature map(Huang et al., 2021: Shaydulin & Wild (021) and real datasets FMNIST (Xiao et al. 2017).
KMNIST (Clanuwat et al. 2018), and PLASTICC (The PLASTICC team et al. 2018).
Since the dimensionality of the datapoints in these datasets is too large (e.g.. 784 for FMNIST and KMNIST) and leads to quantum circuits that cannot be simulated by using available tools, the inputs were downsized to 22 22-dimensions by using PCA (Shaydulin Wild (02T). Following Shaydulin
Wild (2021) ;; Huang et al. (2021), consider binary classification problem where for each dataset,
only two classes were chosen (see (Shaydulin & Wild (20T)) for the details on data preprocessing).
For n-dimensional inputs, the quantum circuit used compute the n-qubit IQP kernel is given by
UIQP(x) U2(x)11 (z) U Uz(x) exp >
Σ 5-'=1
ZfzzZZz
where is the Hadamard gate and is the Pauli Z-gate (see Havliček et (2019), This unitary acts
on the n-qubit ground state to embed an input x" a quantum state xx)
(x(") |0) 80" Then
the resulting feature map is given by PIop(x") = |xx) (x"] with the corresponding quantum kernel Kxop(x", (x",'") x") = 'Tr (prop (rOP=))))
For n-ddmmnnsional inputs. the quantum circuit used compute the EVO kernel (Huang al. 2021 Shaydulin & Wild 2021 has n + 1 qubits and is given by
(xvo(x) = II
j=1
Here, c parameterizes time evolution and corresponds to the bandwidth of the resulting kernel. The initial (n + quuit state is given by
Mu)
(b)))
where each (b))) is randomly generated with respect to single-qubit Haar measure (Huang et al. 2021). Then the quantum embedding of a sample x" is xx*) Ux") (V)) with the feature map Pevo(x")) = xxx) (xx) and kernel (x"" x²) = Tr (x"vo (xvoxxx
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 (02T) using Qiskit (Abraham et al. 2019) software to compute the kernel Gram matrices on the data. 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 down- sized to 22 dimensions using PCA, which leads to 222_ and 223 dimennsnsla Hilbert spaces for IQP and EVO circuits, respectively (Shaydulin & Wild 2021). The code for accessing and processing the data was obtained https:: /ittubb. cwmeroo/lnnnoeeee s/ Importance of -oacccee-o-eeeeeelle Keenee-BBnddiddaee Bandwidth in Quant um Machine Learniing
KERNEL RIDGE REGRESSION WITH REALISTIC QUANTUM KERNELS
Apart from the classification task shown in the main text, 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.
'The code and the data are publicly provided by Shaydulin & Wild 2021 at httpt:tpp///ggt comb s/ www.rrtttcccee..... wf--eereelle -Handel-Haddwddrr Qwanuuuuuuuuuuuuu Machi lelrnni
24

---

Under review as a conference paper at ICLR 2023
IOP tmnlst
10P kmalst
I0P plastice
4x 10
30
4x100
Test Loss
10 to cV
Test Loss
fold cV
Test Loss
10 rold co
3x-0
lest loss
lust Joxs
inal Josa
10"1
2x10
60 2.
10
10
100
10-3
10
10
10
10f
Bandwidth C
Bandwidth c
Bandwidth C
EVO tmnist
EVO kmmist
EVO plasticc
60
S-
5-fo
cv
Test Loss
10-to
Test Loss
10-bold
Test Loss
10-1otd-cy
tesk, Joss
lexi, Jous
uea Josa
3x10
10
2x10
10
10
10-1
10t1
10
10"
10
10
10-1
10"
Bandwidth
Bandwidth c
Bandwidth C
Figure A.2: Kernel Ridge Regression performed with k-fold cross vrass-aaliattion and À = 0.1 ridge parameter yields the optimal bandwidth. The vertical axis shows the test loss of the estimator when evaluated on held-out data.
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 we report our results for each kernel method on all three datasets. Furthermore, we present the eigenvalues and target weights corresponding to both quantum model on all three dataset domains in Figure AA4 and Figure [..5 respectively. We find that the spectrum in all cases are flat without the bandwidth, and that the bandwidth improves the spectral properties 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 a model to potentially generalize if the target is suitable.
Here, we also empirically show that the optimal bandwidth scales inversely with the number of qubits n as c* ~ O(n-)), where a 2 0.5. Using the data provided by (Shaydulin & Wild (2021), first extract the maximum kernel eigenvalue for the IQP kernel FMNIST dataset. The IQP kernel is evaluated for various input dimensions n (also the number of qubits) and various bandwidth parameters.
First, we normalize each top eigenvalue Mmar (n) as function of n with the maximum eigenvalue corresponding to the smallest qubit size Mmaz (mo). and define the quantity
Imaa (n) Mmar (71)
Tmmaa (To)
where no = in this case. In Figure A.6 we plot these normalized eigenvalues against the number of qubits, and fit exponential curves extrapolate the behavior for large qubits which not accessible experimentally. As the number of qubits increase, the maximum eigenvalue corresponding to kemel falls much faster than the kernels with Appendix B we found that the bandwidth prevents the maximum cigenvalues to fall exponentially fast in n using our toy model, and this is also what we observe here.
bandwidth as expected. Note that in
Next, we consider a fixed eigenvalue To = 0.8 line in Figure A.6p, and in Figure A.6p we analyze where this line intersects each of the normalized eigenvalues Tmaa (n) corresponding to different bandwidth parameters c. Similar to our calculation in Appendix 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.6p. this case, we numerically find that the optimal bandwidth scales as:
(n)) 0.500
(A.16)
25

---

Under review as a conference paper at ICLR 2023
This is in agreement with the bound for the exponent derived in Eq. A.10 Finally, in Figure A.7 and Figure ( for both models when evaluated on the FMNIST data, we show the empirical scaling of the optimal bandwidth keep their top eigenvalues constant for varying noo s. Again, we find that the decay exponent never violates a 2 0.5.
IQP Jmnnis
IQP kmnist
10P_ 1PP_plastic
10
Test Test Scores
Test Scores
8 -.10--
10
8x
2-caBk-vv
2-fod--v
2-ok--c
S-fold-cv
0x-0-1
S-foid-cy
7
S.fol-cc
10
fold
5x 10-1
scones
5x10
30
10
10
10
10
30'
10
10
16
10
10
Bandwidth
Bandwidth
Bandwidth
EVO Imnist
EVO kmnist
EVO plasticc
10-1
9 10
7.
Test Test Scores
10-1
Scores
Test Test Scores
10-1
x
2
6x-10-
5-obbkcy 10fellicv
5-fuib-cy 10fold-cv
S-olscc
10.folicy
5x
test scones
twat srores
6.
tent sesees
10-1 Bandwidth
Bandwidth c
Bandwidth
Figure A.3: SVM performed with k--fold cross validation yields the optimal bandwidth.
IOP fmnist
kmnist
IQP plasticc
Eigenvalue ffx
10-1
Eigenvalue fll
10"1_
Eigenvalue fx
10-4.
10-h
0.01
10
10-11
1.0
0.5
10:93
C.5.5
1.0
10-11
EVO_ fmnist
EVO kmnist
EVO_ ylo_ppasticc
10-
Elgenvalue f]K
Eigenvalue U0
10
Eigenvalue
10-4
10-4
C-
0.01
C- 0.01
C- 0.01
0.05
2
G.05
10-4
C- 0.05
20
10+l
10a
10
107
30
10
107
10
10'
10"
10'
307
10
k
Figure A.4: Eigenvalues of the quantum kernels are always flat when the bandwidth is not tuned.
26

---

Under review as a conference paper at ICLR 2023
IOP fmnist
jmnistt
IQ plasticc
6.9
0.9
C(k)
0.8
0-0.01
0.8
0.1
0.5
0.5
0.5
100
C=10
1.0
k
k
EVO /mnisst
kmnist
EVO plasticc
1.0
1.0
1.
0.8-
6.8-
0.8
C(k)
0.6-
C- 0.01
0.6
0-0.01
c- 0.0.1
0.4
C- 0.05
0.4
C- 0.05
0.055
0.2
10
16
10
30
15a
107
10'
10
10"
101
10
10
k
k
k
Figure A.5: Task-model alignment improves with bandwidth tuning. Note that decaying eigenspec- trum is not enough alone for generalizability. Empirically, we find that bandwidth improves both the eigenspectrum and the model alignment.
a)
Largest Eigenvalue vs. n (# Qubits)
b)
c-0.001
109.
10
0=0.005
0.005
@ 10
c-0 01
(max())
10-
0.01
cm0.05
10
t=0.1
0.1
10-
10-5
7x100
1
10a
10a
10P
107
1.0
n
n
c)
10
C²
an
10-2
10-1
10:
107
107
10a
Figure A.6: Empirical scaling of the optimal bandwidth with the number of qubits.
27

---

Under review as a conference paper at ICLR 2023
1011
lig = 0.10) kpmii
Ine 0.201 #2-
Ine = 0.30)
10
10
10-2
10"3
10a3
10:14
0.40) c kp
10a
Ine 0.50) c" -100
10--
0.60) w1
10-2
10-2
10
10
30
10
30
104
301
12
10
10'
301
10-4
Up 0.70) 0550
10
In 0.801 c" 1500
10-4
In 0.90) 4.-55
20
10
10"2
10"
102
107
107
267
Figure A.7: IQP Kernl:: Empirical scaling of the optimal bandwidth with the number of qubits for all Njo. Note that the empirical scaling never exceeds a = 0.5 for the optimal bandwidth c* zo n
(0g 0.10)
Ine 0.201 225
Ide 0.30)
10
15
10-2
10-3
184
16
16
169
Int = 0.40) 20
10-1
(d 0.50) c" 5t0
10
0.60) w n-11
10
10
30
101
127
267
123
12
201
30
10'
(ft 0.70) 0014
10
Iit 0.80) c*
10
In 0.90) 5331
10
10.2
30
10
10"
10
20
10"
Figure A.8: EVO Kernel: Empirical scaling of the optimal bandwidth with the number of qubits for all 7pp. Note that the empirical scaling never exceeds = 0.5 for the optimal bandwidth et as n
28


Reviews:
[{"review_id": "ZjvtWJmB7c_", "reviewer": "Reviewer_em9T", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Prior works have shown that quantum kernel methods may not generalize well on machine learning tasks because the spectrum of the kernel operator is too flat. This work shows that by tuning an appropriate bandwidth parameter in the kernel, the spectrum can be made less flat, hence enabling generalization.", "summary_of_the_review": "Although the analysis in this work should be viewed as preliminary and awaits more detailed study, nevertheless I found the submission to be illuminating and well-written, and hence I recommend acceptance.", "strength_and_weaknesses": "The paper is very well-written with clear, intuitive explanations, and gives compelling reasoning for the use of bandwidth in quantum kernels.\n\nThe main weakness of the work is that the theoretical results are very specific, pertaining to a specific kernel, and the analysis seems hard to generalize to more realistic kernels; also, the result is not a fully rigorous analysis of the generalization error. Nevertheless I believe that addressing these issues is best left as future work, and the current paper already makes a solid contribution by providing elucidating intuition.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZdLPK9GG9i", "reviewer": "Reviewer_P99u", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a way to make quantum kernels generalizable through a bandwidth parameter that can restrict features in the Bloch sphere. They also provide some evidence on real datasts that these kernels can generalize unlike the ones without the bandwidth parameter. ", "summary_of_the_review": "A simple and interesting idea but given that the theoretical part is not really novel and the experimental evidence is preliminary the work is not strong enough for ICLR.", "strength_and_weaknesses": "+ it's a simple but possibly powerful way to increase the ability of quantum kernels to generalize\n- the idea of bandwith for quantum kernels has appeared before (Shaydulin & Wild, 2021).\n- the experimental evidence is not strong enough to be able to draw any significant conclusions", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XYeKiXrsqI", "reviewer": "Reviewer_YWYZ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studied the failure of the generalization of the quantum kernel method by focusing on the major cosine kernel function. The authors proposed introducing the bandwidth to control the spectrum of the cosine kernel. The authors derived the formula of the spectrum for that kernel. Then the authors showed that introducing the bandwidth improves the generalization by combining the generalization error bound of the existing work and deriving the spectrum formula. ", "summary_of_the_review": "As I wrote in the weakness, the contribution of this paper is not significant and novel. Using the bandwidth is not new and the derived generalization error bound is the simple application of existing work. The derived scaling law of the spectrum seems new and interesting, but the numerical experiments are conducted with different kernel functions from the theory; thus hard to see the usefulness of the theoretical analysis.", "strength_and_weaknesses": "# Strength\n- The authors rigorously evaluated the eigenvalues of cosine kernel under the large qubit settings and showed how the bandwidth affects the spectrum. Then the authors also derived the scaling laws of the spectrum. As far as I know, the derived scaling laws are new and meaningful.\n- Combined with the spectrum, the authors derived the generalization error of the kernel regression task and showed that introducing the bandwidth improves the generalization. \n\n# Weakness\n- The idea of using bandwidth is not new.\n- The generalization analysis is not novel; it just substitutes the derived spectrum formula into the Theorem in Canatar 2021.\n- The analysis and numerical experiments are not consistent. The generalization analysis focuses on the regression task, but numerical experiments are the classification task. Also, the authors used different kernel functions from the theoretical analysis. Thus, it is hard to judge how significant the theoretical analysis is in a real-world application.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "AuVuZ5ww96-", "reviewer": "Reviewer_jwdc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies quantum kernel learning. Their observation seems that the dimension of the feature maps associated with quantum kernels is exponential but can be processed by quantum boxes. The problem with these kernel is that their leading eigenvalues are too small so that these models do not generalize well. The authors then observe that if one change the ``bandwidth’’ of these kernel functions, then distribution of the eigenvalues becomes more benign. I am not sure whether I interpret the result correctly, but it appears that the authors provide analysis for one specific kernel (with closed forms) and argued that tuning bandwidth could be beneficial for other kernels. \n\nThe paper is quite well written and provided careful exposition to both kernel learning and quantum computing (I was able to follow more than 50% of the paper). The results also appear to be quite significant, especially in a new area. I am leaning towards acceptance.\n\n\nIs the number of cubits needed the same as the dimension of the data? That sounds quite painful? \nFor the problem analyzed (eq. 5), because the kernel can be explicitly written, what’s the reason that this kernel cannot be solved by classical computers? \nIn the experiment, it was stated that pre-computed kernels are used. But if kernel bandwidth needs to be tuned, wouldn’t that just mean pre-computed values could be mostly irrelevant? \n", "summary_of_the_review": "(+) it gives a fairly reasonable overview of quantum kernel learning. \n(+) it appears to be a significant result for quantum kernel learning. \n\n(-) Probably most people in iclr wont understand quantum part. \n(-) I cannot calibrate the technical depth of the result. ", "strength_and_weaknesses": "\nStrength: the paper gave a quite clear exposition to quantum kernel learning and the paper’s result appears to be quite significant. \n\n\nWeakness: I am still not sure about whether I understand the big picture (perhaps just me not knowing enough about quantum). See the questions above. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject