Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization

Yuqi Huang1

Vincent Y. F. Tan1,2

Sharu Theresa Jose3

arXiv:2607.01080v1 [cs.LG] 1 Jul 2026

Department of Mathematics, National University of Singapore, Singapore Department of Electrical and Computer Engineering, National University of Singapore, Singapore 3 School of Computer Science, University of Birmingham, Birmingham, United Kingdom

Abstract We investigate Gaussian process (GP) bandit optimization with quantum kernels, assuming the mean reward function lies in the reproducing kernel Hilbert space (RKHS) induced by the quantum kernel. This setting is motivated by NISQera tasks such as quantum control, state preparation and variational quantum algorithms. While quantum kernels can offer a ‘quantum advantage’ via domain-speciﬁc inductive biases, naïvely using full, high-dimensional kernels increases model complexity and information gain, leading to higher cumulative regret and poor learnability. To address this, we propose projected quantum kernels and classical kernel approximation techniques that reduce feature dimensionality while preserving key quantum properties. Using these approximate kernels, we develop misspeciﬁed GP bandit algorithms and derive regret bounds that characterize the trade-off between approximation error and information gain. The regret bounds provide principled guidance for selecting the optimal model complexity. Empirically, our methods outperform full quantum kernels in sample efﬁciency, while substantially reducing computational overhead, enabling scalable GP optimization for quantum-native applications.

INTRODUCTION

Recent advances in quantum hardware have ushered in the era of noisy intermediate-scale quantum (NISQ) computing, characterized by quantum devices with limited qubits and high noise levels. Within this regime, quantum machine learning has emerged as a promising application, aiming to leverage these NISQ-era devices to accelerate learning from classical or quantum data. This includes discrimina-

tive and generative learning approaches based on quantum neural networks Schuld [2021] and quantum kernel methods Blank et al. [2020], Rebentrost et al. [2014], as well as sequential decision making problems. Recently, there has been growing interest in developing quantum algorithms for classical bandit learning problems, aiming to achieve speedups in sequential decision-making. These include quantum algorithms for best arm identiﬁcation [Casalé et al., 2020, Wang et al., 2025, Buchholz et al., 2025, Wang et al., 2021a], and for addressing explorationexploitation tradeoff under both linear [Lumbreras et al., 2022, Wan et al., 2023, Wu et al., 2023] and non-linear reward models [Hikima et al., 2024, Dai et al., 2023]. However, these approaches assume access to a quantum reward oracle, which simpliﬁes quantum algorithm design, but limits applicability in realistic settings where the classical reward distribution must be encoded into a quantum state. In this work, we depart from this oracle-based paradigm, and study the quantum kernel bandit problem. Here, the learner interacts sequentially with an unknown reward function through noisy evaluations. We assume that the unknown mean reward function f ∗ : X → R lies in the RKHS HκQ induced by a quantum kernel κQ (·, ·). At each round t, the learner selects an action xt ∈ X and observes a noisy reward yt = f ∗ (xt ) + ηt , where ηt is zero mean noise. The objective of the learner P is to minimize the cumuT lative regret over T rounds, RT = t=1 (f ∗ (x∗ )−f ∗ (xt )), ∗ ∗ where x = arg maxx∈X f (x) denotes the optimal action in hindsight. This formulation naturally captures a range of NISQ-era optimization tasks, including state preparation in quantum sensing [Schuff et al., 2020], experimental quantum control [Bukov et al., 2018], and the optimization of variational quantum algorithms [Wanner et al., 2025]. Here, actions x correspond to continuous parameters (e.g., gate angles or pulse amplitudes), and a ﬁxed quantum embedding map ρ(x) induces a corresponding quantum kernel. The resulting quantum RKHS provides a natural hypothesis space for

Classical RBF Kernel Full Quan um Kernel Our Bes Approxima e Kernel

Cumula ive Regre

20 15 10 5 0

T (Time S ep)

100

Figure 1: Cumulative regrets over T = 100 rounds (using the EC-GP-UCB algorithm) with three different modelling kernels on a synthetic task where the unknown reward function lies in a quantum RKHS. While the full quantum kernel beats the classical RBF kernel, our proposed projected quantum kernel-based approximation achieves an even smaller regret. See subsection 4.1 for experimental details. modelling the mean reward function f ∗ (x), while reward feedback is obtained from noisy ﬁnite-shot measurements. We approach this problem using quantum Gaussian process (GP) models. Leveraging the duality between RKHS and GPs [Kanagawa et al., 2018], we encode the inductive bias (i.e., f ∗ ∈ HκQ ) by placing a GP prior with the kernel κQ . While such models can theoretically outperform classical GPs with standard kernels such as RBF or Matérn (see Figure 1) [Smith et al., 2023], they face two unique challenges: • The expressivity of quantum kernels on n-qubit systems scales exponentially with n, leading to high information gain and, consequently, excessive cumulative regret. This hinders the learnability of the quantum GP models. • As the quantum system size n grows, kernel values concentrate exponentially, requiring exponentially many quantum measurements for accurate estimation [Thanasilp et al., 2024]. To address these challenges, we propose new GP algorithms that approximate the full quantum RKHS using either lower-dimensional quantum subspaces or quantuminspired classical approximations. These methods reduce the model complexity, and thus the information gain, at the cost of kernel misspeciﬁcation, which can impact the regret [Bogunovic and Krause, 2021]. Our main contributions are: • Quantum-Speciﬁc Learnability Barrier: We identify the exponential scaling of the maximum information gain with the number of qubits n as the fundamental learnability barrier for GP bandits with ﬁdelity quantum kernels. This statistical barrier, together with kernel concentration as n grows, motivates the use of approximate quantumkernel bandit algorithms. • Algorithmic Framework: We develop a new framework

for approximate GP optimization in quantum kernel bandits by combining quantum kernel approximation techniques with GP (and linear) bandit algorithms. Our approximation approaches include: linear projected quantum kernels (LPQKs), operating on reduced quantum subspaces, and quantum-inspired classical approximations – Random Fourier Features (RFF) and Newton basis expansions. • Quantum-Structured Trade-off Analysis with Regret Bounds: We then derive regret bounds that quantify the trade-off between information gain and kernel misspeciﬁcation. In regimes where the full quantum kernel is excessively high-dimensional, we show that a suitably chosen approximate kernel achieves strictly lower regret than the full model (Figure 1). The bounds also guide the choice of approximation parameters, such as the number of qubits traced out in projected quantum kernels, or the number of random features used in RFF. Although some approximation and misspeciﬁed-bandit tools used in this work are kernel-general, our analysis specializes them to quantum kernels by exploiting the structure of quantum feature maps. In particular, LPQKs correspond to Pauliweight projections of the n-qubit density-matrix feature space. For quantum encodings that admit a Fourier form, the frequencies are determined by eigenvalue gaps of the encoding generators. Thus, our results connect circuit and observable structure directly to the informationgain/misspeciﬁcation trade-off in regret. • Computational Efﬁciency: While naive GP optimization with a full quantum kernel incurs O(T 3 ) time complexity and costly circuit evaluations, our approximationbased methods leverage a D-dimensional feature map (D ≪ T ) to reduce the time complexity to O(T D 2 + D3 ); or rely on smaller qubit subsystems, thereby enhancing the scalability. • Experimental Validation: We evaluate our methods on synthetic and real quantum tasks (e.g., phase classiﬁcation, variational quantum eigensolver optimization), showing that our approximations often outperform the full quantum kernel both in sample efﬁciency and computational cost, and that theoretical insights into approximation error can guide dimension selection, yielding nearoptimal performance in practice. Related Works: A common approach to optimizing the NISQ-era objectives is to use variational quantum algorithms (VQAs), which directly update the parameters of a parameterized quantum circuit [Cerezo et al., 2021]. These methods often rely on gradients estimated by ﬁnite differences or the parameter-shift rule, such gradient estimates can be measurement-intensive, and may suffer from barren plateaus [McClean et al., 2018, Wang et al., 2021b]. We take a different, gradient-free surrogate-optimization viewpoint: the energy or reward is treated as a noisy black-box function, and a quantum-kernel GP surrogate is used to se-

lect queries to balance exploration and exploitation. Kernelized bandits (including GP bandits) traditionally assume realizability: the unknown reward function f ∗ either lies in the RKHS associated with the kernel κ(x, x′ ), or is drawn from a mean-zero GP prior GP(0, κ(x, x′ )) [Valko et al., 2013, Srinivas et al., 2009]. However, in practice, the true RKHS or the exact kernel function is often unknown, making the realizability assumption too restrictive. Our work belongs to the misspeciﬁed kernelized bandit setting, where the learner optimizes using an approximate kernel rather than the ground truth. This paradigm was ﬁrst formalized for linear bandits by Ghosh √ et al. [2017], who established a regret lower bound of Ω(ε dT ) for ε-perturbed additive reward models with d-dimensional vectors x. Subsequent research has deepened the understanding of misspeciﬁcation in linear bandits Zanette et al. [2020], Neu and Olkhovskaya [2020]. More recently, Bogunovic and Krause [2021] and Camilleri et al. [2021] extended these insights to kernelized settings, demonstrating that misspec√ iﬁcation introduces an additive regret term of O(ε γT T ), where ε is the misspeciﬁcation error and γT is the maximum information gain of the kernel. While quantum kernels have been widely used in supervised and generative learning settings, their integration into probabilistic models like GPs remains relatively underexplored. Smith et al. [2023] pioneered the use of GP surrogates with quantum kernels for variational quantum eigensolver (VQE) optimization, showing that encoding physical knowledge into the kernel can outperform GPs using classical kernels (e.g., RBF, Matérn). Nicoli et al. [2023] proposed a quantum-inspired classical kernel, termed the VQE-kernel, for Bayesian optimization of VQE problems. Other recent works, such as Rapp and Roth [2024] and Guo et al. [2024], explore quantum GP regression with NISQcompatible quantum kernels, highlighting the promise of quantum probabilistic models in practical settings. In contrast to prior work, we study GP bandit optimization with quantum kernels under kernel approximation, bridging the misspeciﬁed kernel bandit literature with quantum kernel methods. Our analysis explicitly characterizes how approximating high-dimensional quantum kernels impacts information gain, regret, and computational complexity.

PROBLEM SETTING

2.1

QUANTUM KERNEL BANDIT LEARNING

We consider a sequential online learning problem where at each round t, the learner chooses an action xt ∈ X from the ﬁnite action set X . Corresponding to the chosen action, the learner observes a noisy reward yt = f ∗ (xt ) + ηt ,

(1)

where f ∗ : X → R is the true unknown reward function and ηt is the i.i.d. zero-mean noise. The goal of the learner is to minimize the cumulative regret over T rounds, RT =

T X t=1

f ∗ (x∗ ) −

T X

f ∗ (xt ),

(2)

t=1

with respect to the optimal x∗ = arg maxx∈X f ∗ (x). We assume that the f ∗ belongs to the RKHS HκQ (X ) deﬁned by a quantum kernel κQ (x, x′ ), with bounded RKHS norm, i.e., ∥f ∗ ∥HκQ ≤ B for some B < ∞. Speciﬁcally, we consider the global ﬁdelity quantum kernel, deﬁned via a quantum feature map ρ : X → H. Here, H denotes the Hilbert space of 2n × 2n Hermitian matrices with the inner product ⟨A, B⟩H = Tr(AB† ). The feature map ρ is realized through a quantum circuit S(x), which maps x ∈ X to an n-qubit quantum state ρ(x) by operating on the initial state |0⟩ as ρ(x) = S(x)|0⟩⟨0|S(x)† .

(3)

The resulting quantum state ρ(x) is represented as a 2n × 2n -dimensional density matrix (i.e., a positive semideﬁnite, Hermitian matrix with unit trace). For x = (x1 , . . . , xd ) ∈ Rd , the quantum circuit S(x) can be constructed by interleaving ﬁxed unitary evolutions W with data dependent encoding gates e−ixj Gj , 1 ≤ j ≤ d as [Schuld and Petruccione, 2021]: S(x) = W(d+1) e−ixd Gd W(d) · · · e−ix1 G1 W(1) .

(4)

Here, each Gj is a dGj ≤ 2n -dimensional Hermitian operator serving as the generator for the encoding gate, while W(1) , . . . , W(d+1) denote arbitrary unitary evolutions before and after the encoding gates. This construction naturally generalizes to multiple repeated layers of S(x) [Schuld et al., 2021]. The quantum feature map induces the global ﬁdelity quantum kernel [Huang et al., 2021], κQ (x, x′ ) = Tr(ρ(x)ρ(x′ )† ).

(5)

The kernel evaluates the similarity between x, x′ using global evaluation on the n-qubit quantum state. The associated quantum RKHS HκQ (X ) is the Hilbert-space completion of span{κQ (·, x) : x ∈ X } with inner product satisfying ⟨κQ (·, x), κQ (·, x′ )⟩HκQ = κQ (x, x′ ). Consequently, every f ∈ HκQ (X ) satisﬁes the reproducing property f (x) = ⟨f, κQ (·, x)⟩HκQ . For the global ﬁdelity kernel, this RKHS corresponds to reward models that are linear in the quantum feature space, i.e., f ∗ (x) = Tr(Hρ(x)) for some Hermitian operator H ∈ H [Schuld and Petruccione, 2021]. Such models arise in many quantum machine learning applications. For instance, the variational

quantum eigensolver (VQE) aims to ﬁnd the parameterized quantum state ρ(x∗ ) that approximates the ground state of a quantum Hamiltonian H, based on noisy observations yt = f ∗ (xt ) + ηt of the energy function f ∗ (x) = Tr(Hρ(x)), where the noise stems from measurement uncertainty [Nicoli et al., 2023]. 2.2

QUANTUM GP BANDIT OPTIMIZATION

We approach the quantum kernelized bandit problem using quantum GP models. Leveraging the equivalence between RKHS and GPs, we encode the inductive bias f ∗ ∈ HκQ by placing a GP prior over f ∗ with the quantum kernel, i.e., f ∗ ∼ GP(0, κQ (·, ·)). Assuming Gaussian noise ηt ∼ N (0, σ 2 ), the posterior over f ∗ (x) is also a GP, with mean µT (x) and variance σT (x, x) given by standard formulas (see Appendix A). In this setting, a natural bandit algorithm is GP-UCB [Srinivas et al., 2010] applied with the quantum GP model. At each round t, GP-UCB selects an action xt that maximizes an upper conﬁdence bound (UCB) that contains f ∗ (x) with high probability over the time horizon: p xt = arg max µt−1 (x) + βt σt−1 (x) , x∈X

where βt is an exploration parameter and σt−1 (x) is an estimate of the standard deviation of the process at point x. Theorem 1 ((Simpliﬁed) [Srinivas et al., 2010]). Under mild regularity conditions on the kernel κQ (·, ·), there exists a suitable sequence {βt } such that quantum GP-UCB satisﬁes, with high probability, p RT = O T β T γ T , where γT =

max A⊂X ,|A|=T

I fA ; y A

is the maximum information gain, with fA = [f ∗ (x)]x∈A and yA the corresponding noisy observations. Challenges of Quantum GP Bandit Optimization: Theorem 1 shows that the cumulative regret scales with the maximum information gain γT , a kernel-dependent quantity that measures how informative the noisy observations are about the unknown f ∗ . In particular, GP models with large γT are harder to learn and typically incur higher regret. For GPs equipped with an n-qubit ﬁdelity quantum kernel as in (5), the information gain scales as γT = O(4n log T ) since the model is equivalent to a linear model with 4n dimensional features (see Appendix B). This scaling is exponential in the number of qubits n, and is tight for many practical data-encoding circuits [Schuld and Killoran, 2019, Havlicek et al., 2019].

As an illustrative example, consider the quantum feature map in (3)-(4) with W = I and generators Gi ∈ {X, Y, Z} given by single-qubit Pauli operators. This feature map, called the rotation encoding, generates a feature space whose dimension grows exponentially in n. For example, even without entangling gates, a product of single-qubit ﬁxed-axis rotations, e.g., Ry (xi ), has a threedimensional local span generated by {I, X, Z}, and therefore gives feature dimension 3n when applied independently to n qubits. Richer encodings, such as two noncommuting Pauli rotations or data re-uploading, can yield a feature dimension of exactly 4n [Kübler et al., 2021]. We empirically validate this exponential dependence in Figure 2, where we plot the information gain γT as a function of the number of data samples T for different values of n (left); and as a function of n for ﬁxed T = 1000 (right). The latter clearly illustrates the exponential dependence of γT on n. We use Pauli-Y and Pauli-Z encoding, similar to our experiments in Section 4. Consequently, applying naïve GP-UCB algorithm with high-qubit quantum kernels can lead to prohibitively large regret. Moreover, as n increases, kernel values for different data pairs can concentrate exponentially around a ﬁxed value, requiring an exponential number of quantum measurements to accurately estimate the kernel [Thanasilp et al., 2024]. To overcome these challenges, we propose surrogate GP models that use a lower-dimensional RKHS Hκapp , induced by a suitably chosen kernel κapp . In particular, we assume that there exists an approximation f˜ = arg min ∥f − f ∗ ∥∞ f ∈Hκapp (X )

that has small uniform error, i.e., ∥f˜ − f ∗ ∥∞ ≤ ε for small ε > 0. The surrogate GP then models f˜ ∼ GP(0, κapp ). While such approximations can substantially reduce information gain, they typically introduce kernel misspeciﬁcation relative to the full quantum model. This misspeciﬁcation can adversely affect cumulative regret [Bogunovic and Krause, 2021]. This motivates designing approximate RKHS for surrogate GP models that balance information gain with misspeciﬁcation error to achieve more favorable regret.

BALANCING INFORMATION GAIN AND MODEL MISSPECIFICATION

This section proposes quantum GP surrogate models based on approximate kernels κapp , designed to balance information gain and model misspeciﬁcation error. A key challenge in designing effective approximations is to preserve the quantum properties of the full kernel while avoiding exponential model complexity. We consider three low-rank

Max Information Gain γT

N mber of Q bits

n=1 n=2 n=3 n=4 n=5

101 0

200

400

600

800

T (N mber of Samples)

1000

(a) γT against T for diff. n

γT

103

102

100

Theorem 2. Let HκSb (X ) be the RKHS induced by the summed LPQKs κSb , and let HκQ (X ) be the RKHS induced by the full quantum kernel in (5). Then,

γT, T = 1000

103

(i) HκSb (X ) ⊆ HκQ (X ),

102 1

Number of Qubits

(b) γT at T = 1000 against n

Figure 2: Plot of γT as a function of (a) the iterations T for varying system qubit size n, with Pauli-Y and Z rotation encoding feature maps, and (b) the number n of qubits with T = 1000, verifying the exponential increase of γT with n.

(ii) If the true function f ∗ (x) = Tr[Hρ(x)] is generated by an observable H drawn uniformly at random from the sphere of operators with Hilbert–Schmidt norm B (equivalent to normalized Gaussian, see Appendix C), then with probability at least 1 − δ, the misspeciﬁcation error is bounded as εb :=

inf

f ∈HκS (X )

∥f − f ∗ ∥∞

v ! r u Pb n w u ln(1/δ) w=0 w 3 + . ≤ Bt 1 − 4n 4n b

approximation approaches: (a) projected quantum kernels via reduced quantum circuits; (b) classical Random Fourier Features (RFFs) for efﬁcient kernel approximation; and (c) P-greedy kernel approximations via data-dependent subset selection. While projected quantum kernels still rely on quantum hardware, RFF and P-greedy are fully classical, offering scalability and implementation ﬂexibility. 3.1

LINEAR PROJECTED QUANTUM KERNELS-BASED EC-GP-UCB ALGORITHM

Linear projected quantum kernels (LPQK) [Huang et al., 2021, Kübler et al., 2021] compare quantum states at the level of individual sub-systems, by projecting the global quantum state onto a reduced subspace. Speciﬁcally, for a sub-system s ⊆ {1, . . . , n} (indexed by a subset of qubit labels), the LPQK is deﬁned as κsQ (x, x′ ) = Tr ρs (x)ρs (x′ ) , (6) where ρs (x) = Trsc ρ(x) is the reduced density matrix obtained by tracing out the complement sub-system sc . The resulting state ρs (x) lies in a Hilbert space of dimension 2|s| × 2|s| , which is exponentially smaller than the full state dimension 2n × 2n . While projection onto one sub-system may discard significant information about the global state ρ(x), this loss can be mitigated by aggregating information across multiple sub-systems. To this end, we deﬁne a summed LPQK over a collection Sb = {s1 , . . . , sw } of all sub-systems satisfying |si | ≤ b, for i = 1, . . . , w, as κSb (x, x′ ) = P 1 s ′ s∈Sb |Sb | κQ (x, x ) [Gan et al., 2023]. The resulting kernel has effective dimensionality upper bounded by the sum of the dimensions of the individual projected subspaces. LPQK with Misspeciﬁed Bandit Algorithm. We use the summed LPQK κSb as the approximate kernel in a surrogate GP model, with f˜ ∼ GP(0, κSb (·, ·)). The next theorem shows that the RKHS HκSb (X ), deﬁned by the summed LPQKs for 1 ≤ b < n, is a natural surrogate for approximating the full quantum RKHS HκQ (X ), and provides an explicit bound on the misspeciﬁcation error.

Moreover, if (b + 1)/n ≥ 3/4, then s 2 r εb ≤ B

− 8n 3

b+1 3 n −4

ln(1/δ) . 4n

(7)

See Appendix C for the proof. Part (i) shows that the RKHS induced by LPQKs is a subspace of the full quantum RKHS. Part (ii) should be interpreted as a conservative baseline: for a dense uniformly random observable, the error scales with the fraction of Pauli-weight components discarded by the projection. Thus aggressive dimension reduction is not guaranteed to have small error in this worstcase model. Instead, the practical beneﬁt of LPQK arises when the target observable or circuit has additional structure, such as locality or a rapidly decaying high-weight Pauli tail; see Appendix C.5 for more details. For this misspeciﬁed setting, where the true reward function f ∗ ̸∈ HκSb (X ), we can leverage the EC-GP-UCB algorithm of Bogunovic and Krause [2021], which yields the following cumulative regret with probability at least 1 − δ, p p √ RT = O B γT T + (ln(1/δ)+γT )γT T +εb T γT , (8) where B < ∞ is the RKHS-norm of the approximating function f , i.e., ∥f ∥HκQ ≤ B. Compared to the regret achieved in the realizable setting (Theorem 1), there √ is an additional O(εb T γT ) term in the regret that depends on the misspeciﬁcation error εb . For the summed LPQK kernel, this misspeciﬁcation error depends on the sub-system size b as shown in (7). Additionally, as shown in Appendix C, the information gain of the approximate Pb n w kernel κSb scales as γT = O ( w=0 w 3 ) log T with Pb n w ≪ 4n , signiﬁcantly smaller than using the w=0 w 3 n-qubit full ﬁdelity kernel. Consequently, the cumulative regret of EC-GP-UCB algorithm with summed LPQK kernel can be optimized by effectively balancing the information gain γT and the misspeciﬁcation error εb by choosing appropriate size b of the sub-system. For structured observables with small or rapidly decaying high-weight Pauli

components (cf. Appendix C.5), much smaller values of b can substantially reduce the effective dimension while keeping εb small. 3.2

RFF-BASED SQUARECB ALGORITHM

We now investigate RFF-based approximation of the quantum ﬁdelity kernel κQ (x, x′ ) [Landman et al., 2022], leveraging the Fourier representation of quantum kernels [Schuld and Petruccione, 2021]. For exposition, we focus on the simple circuit family in (4), where Gi = G for all i with an eigenspectrum {λ1 , . . . , λdG }, and dG ≤ 2n . Extensions to repeated and multi-layer data encodings admit analogous Fourier expansions and can be derived similarly [Schuld et al., 2021]. Under this P encoding, κQ admits the Fourier expansion κQ (x, x′ ) = s,t∈Ω cs,t exp(i s · x) exp(i t · x′ ), where the frequency set Ω contains vectors of the form {Λj − Λk }, with Λj = (λj1 , . . . λjd ) for indices j1 , . . . , jd ∈ {1, . . . , dG }, and the Fourier coefﬁcients cs,t ∈ C satisfy cs,t = c∗−s,−t . The frequency spectrum depends solely on the eigenspectrum of the generator G. When the quantum kernel κQ (x, x′ ) is shift-invariant, i.e., κQ (x, x′ ) = g(x − x′ ) [Schuld and Petruccione, 2021] for some function g : Rd → R, Bochner’s theorem [Rudin, 2017] ensures that κQ admits a Fourier integral represenR ⊤ ′ tation: κQ (x, x′ ) = Ω p(ω)eiω (x−x ) dω, where p(ω) is a probability distribution over ω ∈ Ω (assuming κQ is normalized). For the circuit family above, shift-invariance arises when each generator Gi = G encodes input xi into distinct, non-overlapping qubits. RFF approximates this kernel as [Rahimi and Recht, 2007]

reward function as f˜(·) = w⊤ ϕRFF (·) ∈ HκRFF (X ) such that the true reward function f ∗ (x) = f˜(x) + ξ(x) with supx |ξ(x)| ≤ εD . In this setting, the SquareCB algorithm Foster and Rakhlin [2020] achieves an expected regret of √ √ E[RT ] = Õ( DKT + εD KT ), where the expectation is over the randomness of action policy and K = |X | is the number of actions. Theorem 3. Let f ∗ ∈ HκQ (X ) with ∥f ∗ ∥HκQ ≤ B < ∞, where κQ (·, ·) is an n-qubit shift-invariant quantum kernel. Consider HκRFF (X ) as in (10) obtained by sampling D Fourier features of κQ . Then, with probability at least 1 − δ over the sampled Fourier features, there exists f˜ ∈ HκRFF (X ) such that the misspeciﬁcation error satisﬁes sup |f ∗ (x) − f˜(x)| < εD where r 4B|Ω| 1 εD := √ log + 4BX ωmax , δ D

(11)

x∈X

and where BX := supx∈X ∥x∥2 and ωmax := maxω∈Ω ∥ω∥2 are the domain and frequency radii respectively. Using SquareCB with HκRFF (X ) yields an expected cumulative regret of nq p √ E[RT ] ≤ min 2 4n KT log 1+ 4Tn , 2 KT 3/4 log T p o √ + 20 KT 3/4 B|Ω| log T + 4BX ωmax , (12) where the expectation is over SquareCB’s random action sampling, the stochastic rewards, as well as the sampled Fourier features.

See Appendix E for proof. In the regret bound in (12), the ﬁrst term corresponds to applying SquareCB with κQ (x, x′ ) ≈ ϕRFF (x)⊤ ϕRFF (x′ ) =: κRFF (x, x′ ), (9) the√full quantum model (no misspeciﬁcation), scaling as Õ( 4n KT ). The second term arises from using SquareCB where ϕRFF : X → RD is the feature map obtained by in the misspeciﬁed setting, with the misspeciﬁcation er√ drawing D frequency samples {ω j } from p(ω) and ranror in (11) optimized with the choice of D = T , giv√ dom phases {bj } from the uniform distribution over [0, 2π]: ing√a regret of Õ( KT 3/4 ). This √ term is smaller than the n KT ) regret when 4n ≳ q Õ( 4 T , i.e., for n = Ω(log T ). ⊤ 2 cos ω 1 ·x+b1 . . . cos ω D ·x+bD ϕRFF (x) = D . This analysis demonstrates that RFF-based surrogate models outperform full quantum ﬁdelity kernel methods in For many standard quantum circuits, the frequency set Ω regimes where the kernel complexity grows faster than the and coefﬁcients {cs,t } can be derived explicitly, allowing required approximation capacity. Furthermore, the analysis one to directly sample frequencies from Ω for RFF [Schuld provides a theoretical prescription for selecting the optimal and Petruccione, 2021]. See Appendix D for more details. dimension D to balance approximation error and model complexity. Misspeciﬁed Linear Bandit via RFF. The RFF kernel (9) induces the following RKHS, We remark that, if the horizon T is not known in advance, it can be chosen in an anytime manner via a standard douHκRFF (X ) = {f (·) = w⊤ ϕRFF (·) : w ∈ RD }, (10) bling trick (cf. Besson and Kaufmann [2018]), which preserves the regret order up to logarithmic factors in T . consisting of functions linear in ϕRFF (·). While κRFF can deﬁne a GP model, its ﬁnite dimensionality also allows us Alternative Sampling and Possible Faster Error Decay. to treat the problem as a misspeciﬁed linear bandit with In practice, instead of sampling ω ∼ p(ω), one can use the RFF feature. Concretely, we model the unknown mean structured sampling (e.g., prioritizing frequencies with the

largest Fourier coefﬁcients). When the Fourier expansion of the kernel is explicitly known, this can tighten misspeciﬁcation bounds [Schuld, 2021], particularly if the coefﬁcients decay rapidly—such as polynomially: εD = O(1/D) or exponentially: εD = exp(−Ω(D)). In these regimes, both SquareCB and EC-GP-UCB beneﬁt from faster convergence and improved regret guarantees. Computational Complexity. GP or kernelized regression typically require matrix inversion operations with O(T 3 ) cost. In contrast, approximating κQ with a D-dimensional feature map yields a linear model, solvable by ridge regression in O(T D2 + D3 ). As long as D < T , the RFF approach provides substantial computational savings. Additionally, for quantum kernels involving a large number of qubits n, kernel evaluations can become expensive; in such cases, RFF-based methods are more practical and scalable (more details are provided in Appendix F). 3.3

P-GREEDY KERNEL APPROXIMATION

While RFF is effective for shift-invariant kernels with accessible feature maps, many quantum kernels lack these properties or are challenging to analyze. As an alternative, P-greedy [Marchi et al., 2005, Takemori and Sato, 2021] requires only access to kernel evaluations κQ (x, x′ ). The P-greedy algorithm constructs a low-dimensional subspace V (XD ) = span {κQ (·, ξ 1 ), . . . , κQ (·, ξ D )} ⊂ HκQ (X ), spanned by kernel evaluated at a chosen subset of points XD = {ξ 1 , . . . , ξ D } ⊂ X . This subspace is selected iteratively: At each iteration k, the algorithm greedily selects the point ξ k ∈ X that maximizes the power function: PV (Xk−1 ) (x) :=

|f (x) − (ΠV (Xk−1 ) f )(x)| , ∥f ∥HκQ f ∈HκQ (X )\{0} sup

which identiﬁes where the current subspace approximates the quantum RKHS worst. Here, ΠV (X) : HκQ (X ) → V (X) denotes the orthogonal projection onto V (X). After D iterations, the algorithm returns XD , deﬁning a subspace V (XD ) that approximates the full quantum RKHS. The ﬁnal feature map corresponds to the Newton basis formed via Gram–Schmidt orthonormalization of basis {κQ (·, ξ 1 ), . . . , κQ (·, ξ D )}, yielding an efﬁcient low-rank approximation of the quantum kernel. Performance and Spectral Decay. The effectiveness of the P-greedy algorithm is governed by the spectral decay of the target quantum kernel [Jordão and Menegatto, 2018]. For kernels with rapid eigenvalue decay, the algorithm may admit polynomial or exponential improvement with each greedily chosen point [DeVore et al., 2013]. Nevertheless, P-greedy typically achieves near-optimal performance: The misspeciﬁcation error using√2D points satisﬁes [DeVore et al., 2013] ε2D ≤ B/γ · 2dD for some 0 < γ < 1,

where dD is the D-dimensional Kolmogorov width, representing the best possible D-dimensional approximation of the quantum RKHS HκQ (X ). As an example, consider quantum kernels κQ with a Fourier expansion, X ′ κQ (x, x′ ) = cω ei⟨ω,x−x ⟩ . ω∈Ω

The Kolmogorov width dD is controlled by the spectral tail with X X d2D = cj = cω , j>D

ω ∈Ω / D

where {cj }j≥1 are the eigenvalues in non-increasing order and ΩD indexes the top-D eigenvalues (see Appendix H for a proof). Without additional circuit structure, fast spectral decay is generally not guaranteed. However, there exist many circuit families that produce non-uniform spectra, often leading to exponentially decaying dD , and consequently, εD (see Appendix G for examples). Once an instance-speciﬁc (or circuit-speciﬁc) bound εD is available for the P-greedy surrogate class, it can be directly integrated into the regret bounds of misspeciﬁed bandit algorithms to obtain a theoretically principled choice of the approximation dimension D.

NUMERICAL EXPERIMENTS

We demonstrate the effectiveness of our kernel approximation approach on a variety of tasks using classical bandit algorithms such as EC-GP-UCB [Bogunovic and Krause, 2021] or SquareCB [Foster and Rakhlin, 2020]. Further implementation details are in Appendix J. 4.1

GP OPTIMIZATION WITH SYNTHETIC QUANTUM FUNCTIONS

Our ﬁrst synthetic task uses a true reward function f ∗ sampled from a three-qubit quantum kernel (extension to larger n = 6 qubit systems can be found in Appendix K). We construct a parameterized quantum circuit in PennyLane with Pauli-X data-encoding gates followed by random rotation and entangling gates. This circuit deﬁnes a global ﬁdelity quantum kernel κQ , which we use to generate random functions f ∗ over the domain [0, 2π]3 . Observed rewards are corrupted with i.i.d. Gaussian noise (variance σ 2 = 0.01) and normalized to [0, 1]. We evaluate three kernel-approximation strategies: projected quantum kernels, RFF, and P-greedy, each paired with SquareCB and EC-GP-UCB. Model complexity is controlled by the number of summed LPQKs, the RFF dimension D, or the number of basis elements in P-greedy. Figures 3 and 4 plot the cumulative regret as a function

Regret

20 18

28 26 24 22 20 18 16 14

Regret, T = 100 ±1σ Theoretical optimum

50 40 30

14 1

Number f Pr jected Kernels Summed

(a) Projected Quantum Kernels

Regret, T = 100 ±1σ Theoretical optimum

Regret

Regret, T = 100 ±1σ The retical ptimum

Regret

Dimension of Approximate Kernel

Dimension of Appro imate Kernel

(b) Random Fourier Features

Figure 3: Cumulative regret of SquareCB against approximation model complexity for (a) projected quantum kernels, (b) RFF and (c) P-greedy approximation. 30

Regret, T = 100 ±1σ

15 10 1

Number of Projected Kernels Summed

(a) Projected Quantum Kernels

Regret

Regret, T = 100 ±1σ

Regret

70 60 50 40 30 20 10

25 20 15 10 5

Dimension of Approximate Kernel

(b) Random Fourier Features

Figure 4: Cumulative regret of EC-GP-UCB against approximation model complexity for (a) projected quantum kernels, (b) RFF and (c) P-greedy approximation.

Across all settings, we observe the characteristic “Ushaped” trend in regret. At low model complexity, the surrogate kernel is too coarse to capture f ∗ accurately, leading to underﬁtting and high regret. As model complexity increases, the approximation error decreases, improving performance. However, beyond an optimal point, further increase in complexity leads to higher regret due to increased information gain, mirroring overﬁtting in classical learning. Choosing the approximate kernel dimension. √ Theorem 3 suggests setting the RFF dimension D = T to minimize the regret bound. For T = 100, this yields D = 10, which is highlighted by the red vertical line in Figure 3(b). Note that our theoretical choice of D aligns perfectly with the best empirical performance. For P-greedy, the relationship between the approximation dimension D and the misspeciﬁcation error ε is circuit-dependent. One can analyze the circuit structure— empirically or analytically—to estimate how ε varies with D. Plugging this estimate into misspeciﬁed bandit regret

Max Norm Error

0.5

Max Norm Error

0.4

Max Norm Error

0.40 0.35 0.30 0.25 0.20 0.15 0.10 0.05 0.00

Max Norm Error

of model complexity for the three approximation methods, using SquareCB and EC-GP-UCB respectively. The rightmost point in each plot corresponds to the full quantum kernel (i.e., maximum model complexity). Each algorithm was run for T = 100 rounds, with results averaged over 30 trials.

0.3 0.2 0.1

0.0

Feature Dimension for Summed Projected Kernel Dimension of Approximate kernel

(a) Projected Quantum Kernels

(b) P-greedy

Figure 5: Uniform (max-norm) approximation error against the kernel dimension (or effective dimension) for (a) projected quantum kernels and (b) P-greedy algorithm.

bounds (e.g., SquareCB) then allows us to select the optimal D. Figure 5 illustrates the empirical relationship between ε and D for both the projected kernel and P-greedy methods. Substituting these estimates into SquareCB’s regret bounds yields a theoretically optimal D, marked in red in Figures 3(a) and (c). These values closely match the observed performance peaks, validating the approach. The same principle applies to EC-GP-UCB.

4.2

PHASE CLASSIFICATION

We next evaluate our approach on a quantum phase classiﬁcation task inspired by Caro et al. [2022]. We consider the

100

Regre

Regret

6 5

Regre , T = 100 ±1σ

4 1

Regret, T = 100 ±1σ

40 20 0

Dimension of Approximate Kernel

Number of Projec ed Kernels Summed

(a) Projected Quantum Kernels

of EC-GP-UCB over T = 100 iterations against model complexity. Both approximation methods signiﬁcantly outperform the full quantum kernel (rightmost points) at their optimal complexity. This suggests that lower-dimensional kernels sufﬁce to distinguish phase II, while avoiding the higher information-gain penalty of the full kernel.

(b) P-greedy

4.3 Figure 6: Cumulative regrets of EC-GP-UCB after T = 100 iterations as a function of the model complexity for (a) projected quantum kernels and (b) P-greedy approximation for quantum phase classiﬁcation.

E ergy

−2.0 −2.5

Mi imum E ergy, steps = 50 ±1σ Grou d state

−3.0 −3.5

−1.50 −1.75 −2.00 −2.25 −2.50 −2.75 −3.00 −3.25 −3.50

Number of Projected Ker el Summed

(a) Projected Quantum Kernels

In our ﬁnal experiment, we follow the setup in Nicoli et al. [2023] to approximate the ground state of the XYZ Heisenberg Hamiltonian:

Regret, T = 100 ±1σ Ground tate

Energy

−1.5

H=−

(JX Xj Xj+1 + JY Yj Yj+1 + JZ Zj Zj+1 )

− 0

10 20 30 40 50 60 Dimension of Approximate Kernel

(b) P-greedy

(Zj − J1 Xj Xj+1 − J2 Xj−1 Zj Xj+1 ),

j=1

where Xj and Zj are Pauli-X and Pauli-Z operators, respectively, acting on qubit j. By varying the coupling coefﬁcients J1 and J2 , the ground state of the Hamiltonian can fall into one of four distinct phases: symmetry-protected topological (I), ferromagnetic (II), anti-ferromagnetic (III), or trivial (IV). Our task is to identify parameters (J1 , J2 ) corresponding to the ferromagnetic phase (II). In each round, we sample a point x = (J1 , J2 ), compute the ground state |ψx ⟩ of HC , and observe y = f ∗ (x) + ηt where ηt ∼ N (0, 0.01). Crucially, for this physical system, the reward function f ∗ (x) can be represented within a quantum RKHS via the normalized total magnetization squared, n 1 X H= 2 Xj Xk , n j,k=1

(hX Xj + hY Yj + hZ Zj )

j=1

We employ a 3-qubit “Efﬁcient SU(2)” circuit [Nicoli et al., 2023] as the parameterized ansatz U(x), acting on an initial state |ψ0 ⟩. Our goal is to ﬁnd the parameters x that minimize the energy function f ∗ (x) = ⟨ψ0 | U(x)† HU(x) |ψ0 ⟩ .

generalized cluster Hamiltonian n X

n−1 X

j=1 n X

Figure 7: Bayesian optimization of VQE with different kernel approximation approaches, n = 3

HC (J1 , J2 ) =

VARIATIONAL QUANTUM EIGENSOLVER

We use a GP model with kernel from the SU(2) circuit, performing Bayesian optimization with the Expected Improvement (EI) acquisition function, optimized via L-BFGS. Each run consists of 50 optimization steps, averaged over 30 trials. Figure 7 illustrates the energy landscape as a function of model complexity for the projected quantum kernel and P-greedy approximations. The full kernel appears excessively complex for this task, leading to slower convergence. In contrast, simpler approximations achieve faster convergence. While this is an optimization task (minimizing energy) rather than a regret-minimization bandit problem, the results still show that choosing an appropriate kernel complexity is crucial for efﬁciency. This demonstrates that the balance between expressivity and sample efﬁciency extends beyond standard bandit optimization contexts.

CONCLUSION

∗

as f (x) = Tr(H|ψx ⟩⟨ψx |), which is approximately 1 within the ferromagnetic phase and 0 elsewhere. The objective is to minimize regret for choosing points not in phase II. We apply EC-GP-UCB using approximate kernels (projected kernels and P-greedy) derived from a three-qubit quantum kernel implemented via a parameterized circuit with random single-qubit rotations and entangling gates acting on the initial ground state. Figure 6 shows the regret

We developed approximate GP algorithms for quantum kernel bandits, addressing the challenges of scalability and sample efﬁciency in NISQ-era learning tasks. By exploiting reduced quantum subspaces and classical approximations, our methods achieve a practical trade-off between information gain and model misspeciﬁcation. Theoretical regret bounds, supported by empirical results on both synthetic and quantum tasks, demonstrate the effectiveness of our approach. Finally, the techniques discussed here

are applicable to high dimensional classical kernels, offering lower regret and reduced computational complexity (see Appendix I). For limitations and future work, see Appendix L. Acknowledgements V. Y. F. Tan is supported by a Singapore Ministry of Education (MOE) AcRF Tier 1 grant (A-8002934-00-00) and an AcRF Tier 2 grant (A-8004062-00-00). S. T. Jose is supported through Royal Society International Travel Grant (Reference no: IES\R2\242104) and through EPSRC Quantum Technologies Career Acceleration Fellowship (UKRI1218).

References Alice Barthe and Adrián Pérez-Salinas. Gradients and frequency proﬁles of quantum re-uploading models. Quantum, 8:1523, November 2024. ISSN 2521-327X. doi: 10.22331/q-2024-11-14-1523. URL https://doi. org/10.22331/q-2024-11-14-1523. Lilian Besson and Emilie Kaufmann. What doubling tricks can and can’t do for multi-armed bandits, 2018. URL https://arxiv.org/abs/1803.06971. Carsten Blank, Daniel K Park, June-Koo Kevin Rhee, and Francesco Petruccione. Quantum classiﬁer with tailored quantum kernel. npj Quantum Information, 6(1):41, 2020. Ilija Bogunovic and Andreas Krause. Misspeciﬁed gaussian process bandit optimization. Advances in neural information processing systems, 34:3004–3015, 2021. Simon Buchholz, Jonas M. Kübler, and Bernhard Schölkopf. Multi-Armed Bandits and Quantum Channel Oracles. Quantum, 9:1672, March 2025. ISSN 2521327X. doi: 10.22331/q-2025-03-25-1672. URL https: //doi.org/10.22331/q-2025-03-25-1672. Marin Bukov, Alexandre GR Day, Dries Sels, Phillip Weinberg, Anatoli Polkovnikov, and Pankaj Mehta. Reinforcement learning in different phases of quantum control. Physical Review X, 8(3):031086, 2018. Romain Camilleri, Kevin Jamieson, and Julian KatzSamuels. High-dimensional experimental design and kernel bandits. In International Conference on Machine Learning, pages 1227–1237. PMLR, 2021. Matthias C. Caro, Hsin-Yuan Huang, M. Cerezo, Kunal Sharma, Andrew Sornborger, Lukasz Cincio, and Patrick J. Coles. Generalization in quantum machine learning from few training data. Nature Communications, 13(1), August 2022. ISSN 2041-1723. doi: 10. 1038/s41467-022-32550-3. URL http://dx.doi. org/10.1038/s41467-022-32550-3. Balthazar Casalé, Giuseppe Di Molfetta, Hachem Kadri, and Liva Ralaivola. Quantum bandits. Quantum Machine Intelligence, 2:1–7, 2020. Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. Nature Reviews Physics, 3(9):625–644, 2021. John B. Conway. Springer, 2007.

A Course in Functional Analysis.

Zhongxiang Dai, Gregory Kang Ruey Lau, Arun Verma, Yao Shu, Bryan Kian Hsiang Low, and Patrick Jaillet. Quantum bayesian optimization. Advances in Neural Information Processing Systems, 36:20179–20207, 2023. Ronald DeVore, Guergana Petrova, and Przemyslaw Wojtaszczyk. Greedy algorithms for reduced bases in banach spaces. Constructive Approximation, pages 455– 466, 2013. Dylan J. Foster and Alexander Rakhlin. Beyond ucb: optimal and efﬁcient contextual bandits with regression oracles. In Proceedings of the 37th International Conference on Machine Learning. JMLR.org, 2020. Beng Yee Gan, Daniel Leykam, and Supanut Thanasilp. A uniﬁed framework for trace-induced quantum kernels. arXiv preprint arXiv:2311.13552, 2023. Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Misspeciﬁed linear bandits. In Proceedings of the Thirty-First AAAI Conference on Artiﬁcial Intelligence, pages 3761–3767, 2017. Xuyang Guo, Jun Dai, and Roman V Krems. Benchmarking of quantum ﬁdelity kernels for gaussian process regression. Machine Learning: Science and Technology, 5 (3):035081, 2024. Vojtech Havlicek, Antonio D. Corcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta. Supervised learning with quantum-enhanced feature spaces. Nature, 567(7747): 209–212, March 2019. ISSN 1476-4687. doi: 10.1038/ s41586-019-0980-2. URL http://dx.doi.org/ 10.1038/s41586-019-0980-2. Yasunari Hikima, Kazunori Murao, Sho Takemori, and Yuhei Umeda. Quantum kernelized bandits. In The 40th Conference on Uncertainty in Artiﬁcial Intelligence, 2024. Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R McClean. Power of data in quantum machine learning. Nature communications, 12(1):2631, 2021. T. Jordão and V.A. Menegatto. Kolmogorov widths on the sphere via eigenvalue estimates for hölderian integral operators, 2018. URL https://arxiv.org/abs/ 1805.08476. Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K Sriperumbudur. Gaussian processes and kernel methods: A review on connections and equivalences. arXiv preprint arXiv:1807.02582, 2018. Jonas Kübler, Simon Buchholz, and Bernhard Schölkopf. The inductive bias of quantum kernels. Advances in Neural Information Processing Systems, 34:12661–12673, 2021.

Jonas Landman, Slimane Thabet, Constantin Dalyac, Hela Mhiri, and Elham Kasheﬁ. Classically approximating variational quantum machine learning with random fourier features, 2022. URL https://arxiv.org/ abs/2210.13200. Josep Lumbreras, Erkka Haapasalo, and Marco Tomamichel. Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states. Quantum, 6:749, 2022. Olivier Marchal and Julyan Arbel. On the sub-gaussianity of the beta and dirichlet distributions. Electronic Communications in Probability, 22(none), January 2017. ISSN 1083-589X. doi: 10.1214/17-ecp92. URL http: //dx.doi.org/10.1214/17-ECP92. Stefano De Marchi, Robert Schaback, and Holger Wendland. Near-optimal data-independent point locations for radial basis function interpolation. Advances in Computational Mathematics, 23:317–330, 2005. 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):4812, 2018. Gergely Neu and Julia Olkhovskaya. Efﬁcient and robust algorithms for adversarial linear contextual bandits. In Conference on Learning Theory, pages 3049–3068. PMLR, 2020. Kim Nicoli, Christopher J Anders, Lena Funcke, Tobias Hartung, Karl Jansen, Stefan Kühn, Klaus-Robert Müller, Paolo Stornati, Pan Kessel, and Shinichi Nakajima. Physics-informed bayesian optimization of variational quantum circuits. Advances in Neural Information Processing Systems, 36:18341–18376, 2023. Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Proceedings of the 21st International Conference on Neural Information Processing Systems, pages 1177–1184. Curran Associates Inc., 2007. Ali Rahimi and Benjamin Recht. Uniform approximation of functions with random bases. In 2008 46th Annual Allerton Conference on Communication, Control, and Computing, pages 555–561, 2008. doi: 10.1109/ ALLERTON.2008.4797607. Frederic Rapp and Marco Roth. Quantum gaussian process regression for bayesian optimization. Quantum Machine Intelligence, 6(1):5, 2024. Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classiﬁcation. Physical review letters, 113(13):130503, 2014.

Walter Rudin. Fourier analysis on groups. Courier Dover Publications, 2017. Jonas Schuff, Lukas J Fiderer, and Daniel Braun. Improving the dynamics of quantum sensors with reinforcement learning. New Journal of Physics, 22(3):035001, 2020. Maria Schuld. Supervised quantum machine learning models are kernel methods, 2021. URL https://arxiv. org/abs/2101.11020. Maria Schuld and Nathan Killoran. Quantum machine learning in feature hilbert spaces. Physical Review Letters, 122(4), February 2019. ISSN 1079-7114. doi: 10. 1103/physrevlett.122.040504. URL http://dx.doi. org/10.1103/PhysRevLett.122.040504. Maria Schuld and Francesco Petruccione. Quantum models as kernel methods. Machine Learning with Quantum Computers, pages 217–245, 2021. Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer. Effect of data encoding on the expressive power of variational quantum-machine-learning models. Physical Review A, 103(3), March 2021. ISSN 2469-9934. doi: 10.1103/physreva.103.032430. URL http://dx. doi.org/10.1103/PhysRevA.103.032430. Alistair WR Smith, AJ Paige, and MS Kim. Faster variational quantum algorithms with quantum kernel-based surrogate models. Quantum Science and Technology, 8 (4):045016, 2023. Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995, 2009. Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In International Conference on Machine Learning (ICML), pages 1015–1022, 2010. Sho Takemori and Masahiro Sato. Approximation theory based methods for rkhs bandits. In International Conference on Machine Learning, pages 10076–10085. PMLR, 2021. Supanut Thanasilp, Samson Wang, Marco Cerezo, and Zoë Holmes. Exponential concentration in quantum kernel methods. Nature communications, 15(1):5200, 2024. Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint arXiv:1309.6869, 2013.

Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang, and Xiaoming Sun. Quantum multi-armed bandits and stochastic linear bandits enjoy logarithmic regrets. In Proceedings of the Thirty-Seventh AAAI Conference on Artiﬁcial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artiﬁcial Intelligence and Thirteenth Symposium on Educational Advances in Artiﬁcial Intelligence, AAAI’23/IAAI’23/EAAI’23. AAAI Press, 2023. ISBN 978-1-57735-880-0. doi: 10.1609/aaai. v37i8.26202. URL https://doi.org/10.1609/ aaai.v37i8.26202. Daochen Wang, Xuchen You, Tongyang Li, and Andrew M. Childs. Quantum exploration algorithms for multi-armed bandits. Proceedings of the AAAI Conference on Artiﬁcial Intelligence, 35(11):10102–10110, May 2021a. ISSN 2159-5399. doi: 10.1609/aaai.v35i11. 17212. URL http://dx.doi.org/10.1609/ aaai.v35i11.17212. Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J Coles. Noise-induced barren plateaus in variational quantum algorithms. Nature communications, 12(1):6961, 2021b. Xuchuang Wang, Yu-Zhen Janice Chen, Matheus Guedes de Andrade, Jonathan Allcock, Mohammad Hajiesmaili, John C.S. Lui, and Don Towsley. Best arm identiﬁcation with quantum oracles. In Proceedings of the Thirty-Ninth AAAI Conference on Artiﬁcial Intelligence and Thirty-Seventh Conference on Innovative Applications of Artiﬁcial Intelligence and Fifteenth Symposium on Educational Advances in Artiﬁcial Intelligence, AAAI’25/IAAI’25/EAAI’25. AAAI Press, 2025. ISBN 978-1-57735-897-8. doi: 10.1609/aaai.v39i20. 35432. URL https://doi.org/10.1609/aaai. v39i20.35432. Marc Wanner, Johan Jonasson, Emil Carlsson, and Devdatt Dubhashi. Variational quantum optimization with continuous bandits. arXiv preprint arXiv:2502.04021, 2025. Yulian Wu, Chaowen Guan, Vaneet Aggarwal, and Di Wang. Quantum heavy-tailed bandits. arXiv preprint arXiv:2301.09680, 2023. Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978–10989. PMLR, 2020.

Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization (Supplementary Material)

Yuqi Huang1

Vincent Y. F. Tan1,2

Sharu Theresa Jose3

DETAILS ON GAUSSIAN PROCESSES

Suppose we have a set of noisy samples

⊤ y T = y1 , . . . , y T

at the points

AT = x 1 , . . . , x T ,

where yt = f (xt ) + ηt with ηt ∼ N 0, σ 2 i.i.d. Gaussian noise. Then the posterior on f is again a GP distribution with mean µT (x) and variance σT2 (x) given by the standard formulas: µT (x) = kT (x)⊤ KT + σ 2 I

−1

yT ,

(13)

−1 σT2 (x) = κ(x, x) − kT (x)⊤ KT + σ 2 I kT (x),

(14)

where kT(x) is the length-T -vector [ κ(x1 , x), . . . , κ(xT , x) ]⊤ , and KT is the positive semideﬁnite kernel matrix κ(x, x′ ) x,x′ ∈A . T

B INFORMATION GAIN OF QUANTUM FIDELITY KERNEL Consider a n-qubit system, where each classical input x produces a density matrix ρ(x) ∈ C2 ×2 . Let us deﬁne the quantum ﬁdelity kernel as κQ (x, x′ ) = tr ρ(x)† ρ(x′ ) . n

Note that the associated RKHS has dimension at most 4n [Kübler et al., 2021]. It is well known that for any D-dimensional linear kernel, the information gain γT scales as O(D log T ) [Srinivas et al., 2010]. A similar argument reveals that γT of κQ is O(4n log T ). Concretely, we can deﬁne the feature map ϕ(x) = vec ρ(x)

∈ C4 ,

satisfying ∥ϕ(x)∥ ≤ 1 [Schuld, 2021], where vec(·) ﬂattens a 2n × 2n matrix into a vector of dimension 4n . Subsequently κQ (x, x′ ) = Tr ρ(x)† ρ(x′ ) = ϕ(x)† ϕ(x′ ). Corresponding to the observed T data points {x1 , . . . , xT }, we then collect the feature vectors into the following matrix:   | | ··· | n XT = ϕ(x1 ) ϕ(x2 ) · · · ϕ(xT ) ∈ C4 ×T . | | ··· |

Recall that, for reward function fA = [f ∗ (x)]x∈A deﬁned on domain A ⊂ X , the information gain on observing T points {x1 , ..., xT } with observations yA is γT = maxA⊂X :|A|=T I(yA ; fA ). Furthermore, 1 log |I + σ −2 KA | 2 1 = log |I + σ −2 X†T XT | 2 1 = log |I + σ −2 XT X†T | 2 4n Y 1 = log (1 + σ −2 λi ) 2 i=1

I(yA ; fA ) =

≤

1 n 4 log 1 + σ −2 · O(T ) 2

where λi ’s are the eigenvalues of XT X†T . The last inequality follows since the largest eigenvalue of XT X†T is O(T ), since all ∥ϕ(x)∥ ≤ 1. Hence, γT for the quantum kernel is upper bounded by O(4n log T ).

PROOF AND DISCUSSION ON THEOREM 2

C.1 PROOF OF THEOREM 2 (I) We will show that the RKHS associated with a (summed) projected kernel is a subspace of the full kernel’s RKHS. Proof. By standard arguments (e.g., the Moore–Aronszajn theorem or see Kübler et al. [2021]), the n-qubit quantum kernel κQ (x, x′ ) = Tr[ρ(x)ρ(x′ )† ] deﬁnes the RKHS HκQ (X ) = {f : f (·) = Tr[ρ(·)H], H ∈ C2 ×2 , H = H† }, n

of real-valued functions f : X → R. Likewise, for the projected quantum kernel onto the set of qubits s ⊆ {1, ..., n} κsQ (x, x′ ) = Tr(ρs (x)ρs (x′ )), where the reduced density matrix ρs (x) is obtained from the full ρ(x) by tracing out the complementary qubits sc as follows ρs (x) = Trsc [ρ(x)]. The associated RKHS Hκs Q (X ) is comprised of functions f s of the form Hκs Q (X ) = {f s : f s (·) = Tr[ρs (·)H′ ], H′ ∈ C2

|s|

×2|s|

, H′ = (H′ )† }.

The deﬁnition of partial trace implies that, for any operator H′ ∈ C2

|s|

×2|s|

f s (x) = Tr[ρs (x)H′ ] = Tr ρ(x) (H′ ⊗ Isc ) . Now note H = H′ ⊗ Isc is an operator in C2 ×2 . Hence any f s ∈ Hκs Q (X ) must also belong to the full RKHS HκQ (X ). P Therefore, we have Hκs Q (X ) ⊆ HκQ (X ). Subsequently, since κSb = |S1b | s∈Sb κsQ , we have HκSb (X ) ⊆ HκQ (X ). n

C.2 EXTENSION OF THEOREM 2 (I) We showed that the RKHS of a projected kernel is a subspace of the full kernel’s RKHS. Here, we present a stronger result: this subspace relationship arises from a simple orthogonal projection in the underlying feature space: Proposition 1. Suppose ϕQ is the feature map corresponding to κQ such that κQ (x, x′ ) = ⟨ϕQ (x), ϕQ (x′ )⟩. Then for each s ⊆ {1, ..., n}, there exists a unique self-adjoint idempotent operator P such that κsQ (x, x′ ) = ⟨P ϕQ (x), P ϕQ (x′ )⟩. This allows us to deﬁne a feature map of κsQ as ϕs := P ϕQ . Proof. By the representer theorem, there is a Hilbert space FQ (feature space) and a map ϕQ : X → FQ (feature map) such that κQ (x, x′ ) = ⟨ϕQ (x), ϕQ (x′ )⟩FQ . It is also standard that the RKHS HκQ (X ) is isometrically isomorphic to the closed linear span of {ϕQ (x) : x ∈ X } in FQ . Speciﬁcally, one can deﬁne an isomorphism Φ : span{ϕQ (x) : x ∈ X } → HκQ (X ) by ! X X Φ αi ϕQ (xi ) = αi κQ (·, xi ). i

Because Hκs Q (X ) ⊆ HκQ (X ) is a closed subspace, we deﬁne, with the above Φ, V = Φ−1 Hκs Q (X )

⊆ span{ϕQ (x)} ⊆ FQ .

Then V is indeed a closed subspace of FQ . By the Hilbert projection theorem [Conway, 2007], there exists a unique linear orthogonal projector P : FQ → FQ , such that P 2 = P , P = P † and Range(P ) = V. We can then use this P to deﬁne a new feature map s ϕ̃Q (x) = P ϕQ (x), and the corresponding kernel, s

κ̃sQ (x, x′ ) = ⟨ϕ̃Q (x), ϕ̃Q (x′ )⟩FQ = ⟨P ϕQ (x), P ϕQ (x′ )⟩FQ . Since P is an orthogonal projector, κ̃sQ is positive semideﬁnite. Let H̃κs Q (X ) be its associated RKHS. We now show that H̃κs Q (X ) = Hκs Q (X ). (i) H̃κs Q (X ) ⊆ Hκs Q (X ). Any f ∈ H̃κs Q (X ) has the form f (·) =

N X

αi κ̃sQ (·, xi )

i=1

N X

αi ϕ̃Q (·), ϕ̃Q (xi ) F

i=1

N DX

i=1

Deﬁne v :=

s i=1 αi ϕ̃Q (xi )

αi ϕ̃Q (xi ), ϕ̃Q (·)

E FQ

∈ V. Then s

fv (·) := ⟨v, ϕ̃Q (·)⟩FQ = ⟨v, P ϕQ (·)⟩FQ . But since v ∈ Range(P ), v = P v, and since P is self-adjoint, fv (·) = ⟨v, P ϕQ (·)⟩FQ = ⟨v, ϕQ (·)⟩FQ

By the isomorphism property of Φ, fv is exactly Φ(v) ∈ HκQ (X ). Furthermore, since v ∈ V, we have Φ(v) ∈ Hκs Q (X ), hence f ∈ Hκs Q (X ). (ii) Hκs Q (X ) ⊆ H̃κs Q (X ). Similarly, each f ∈ Hκs Q (X ) can be written as Φ(v) with some vector v ∈ V, i.e., f (·) = Φ(v) = ⟨v, ϕQ (·)⟩FQ . We have v = P v since v ∈ Range(P ), thus s

f (·) = ⟨v, ϕQ (·)⟩ = ⟨v, P ϕQ (·)⟩ = ⟨v, ϕ̃Q (·)⟩, which, by deﬁnition, belongs to H̃κs Q (X ). The relationships (i) and (ii) together imply that Hκs Q (X ) = H̃κs Q (X ). Finally, as RKHS is uniquely determined by its kernel, κsQ (x, x′ ) = κ̃sQ (x, x′ ), ∀ x, x′ ∈ X . s

This completes the proof that κsQ is realized exactly by the projected feature map ϕ̃Q = P ϕQ . C.3 PROOF OF THEOREM 2 (II) This proof establishes a high-probability bound on the misspeciﬁcation error, ε, when approximating a global function f ∗ (x) = Tr[Oρ(x)] with one constructed from a “low-weight” or “local” observable H. From Function Approximation to Operator Distance. To understand the misspeciﬁcation error, it’s helpful to start with a simple illustrative case. Suppose our approximate model is restricted to information from a single b-qubit subsystem, denoted by the index set s. The function f (x) in this model then depends only on the reduced density matrix ρs (x) = Trsc (ρ(x)), i.e., f (x) = Tr(Hρs (x)), where H is a b-qubit Hermitian observable. This can be rewritten on the full Hilbert space by letting H′ = H ⊗ Isc . Then f (x) = Tr(H′ ρ(x)). The error of the best possible approximation for a given O is: εs (O) = inf ∥f − f ∗ ∥∞ f

= inf′ sup |Tr(Oρ(x)) − Tr(H′ ρ(x))| H ρ(x)

= inf′ sup |Tr[(O − H′ )ρ(x)]| H ρ(x)

≤ inf′ ∥O − H′ ∥op H

Generalization to Low-Weight Observables. Now we generalize the previous setup, to approximate with a combination of subsystems. Let Hn = (C2 )⊗n be the Hilbert space of an n-qubit system, with dimension = 2n . Let An be the vector space of Hermitian operators on Hn , with dimension dim(An ) = 4n . The Hilbert-Schmidt inner product on this space is ⟨A, B⟩ = Tr(A† B). P In a quantum system with n qubits, any observable O ∈ An can be uniquely decomposed in the Pauli basis: O = P cP P, where P are n-qubit Pauli operators (i.e., P is a tensor product of n single-qubit matrices. P = P1 ⊗ P2 ⊗ · · · ⊗ Pn , Pi ∈ {I, X, Y, Z}, each being a 2 × 2 matrix). The Pauli weight of a Pauli operator P, denoted wt(P), is the number of qubits on which it acts non-trivially (i.e., not as the identity) (recall if H′ = H ⊗ Isc is from a b-qubit observable H, H′ acts as identity on qubits outside b). Our goal is to approximate f ∗ with (sum of) projected kernels. For a fully expressive (4n -dimensional) full quantum kernel κQ , this is equivalent to approximating a global observable O using a combination of such “local” (low Pauli weight) operators. We deﬁne the subspace of low-weight operators, A≤b , as the span of all Pauli operators with weight at most b: A≤b = span{P ∈ Pn | wt(P) ≤ b} where Pn is the set of n-qubit Pauli operators.

Now the error of the best possible approximation of O using an operator H′ ∈ A≤b is given by ε≤b (O) =

inf

H′ ∈A≤b

∥O − H′ ∥op

Further, the operator norm is upper-bounded by the Hilbert-Schmidt norm, ∥A∥op ≤ ∥A∥2 . Therefore, we can ﬁnd an upper bound by analyzing the Hilbert-Schmidt distance: ε≤b (O) ≤

inf

H′ ∈A≤b

∥O − H′ ∥2

(15)

The problem is now to ﬁnd the minimum of ∥O − H′ ∥2 over all H′ ∈ A≤b . In a Hilbert space, the point in a subspace that is closest to an external point is its orthogonal projection. Let P≤b : An → A≤b be the orthogonal projection operator. The inﬁmum is achieved when H′ = P≤b (O). inf

H′ ∈A≤b

∥O − H′ ∥2 = ∥O − P≤b (O)∥2

(16)

By the property of orthogonal projections, we have: ∥O − P≤b (O)∥22 = ∥O∥22 − ∥P≤b (O)∥22

(17)

Expected Error for Spherical Operators. Here we assume O is drawn uniformly from the sphere of operators with ∥O∥2 = 1 (For simplicity in this step, we’ll assume the norm is one, i.e., ||O||2 = 1. This analysis can be trivially extended to any arbitrary norm ||O||2 = B by scaling the ﬁnal result by B). Then ∥O − P≤b (O)∥22 = ∥O∥22 − ∥P≤b (O)∥22 = 1 − ∥P≤b (O)∥22 . Taking the expectation: E ∥O − P≤b (O)∥22 = 1 − E ∥P≤b (O)∥22 We use the following result for random projections. Lemma 1. Let O be a random vector chosen uniformly from the unit sphere in a D-dimensional space V . Let PS be the orthogonal projection onto a d-dimensional subspace S. Then, E[∥PS (O)∥22 ] = d/D. Proof. Let {e1 , . . . , eD } be an orthonormal basis for V such that {e1 , . . . , ed } is an orthonormal basis for S. Any vector O PD P Pd on the unit sphere can be written as O = i=1 ci ei with i c2i = 1. The projection is PS (O) = i=1 ci ei , and its squared P P d d norm is ∥PS (O)∥22 = i=1 c2i . By linearity of expectation, E ∥PS (O)∥22 = i=1 E[c2i ]. Because the distribution of O is spherically symmetric, the expected value of its squared component along any basis vector is the same, i.e., E[c2i ] = C PD PD for all i for some constant C. We know E[∥O∥22 ] = E[1] = 1. Also, E[∥O∥22 ] = E[ i=1 c2i ] = i=1 E[c2i ] = D · C. Thus, Pd D · C = 1 =⇒ C = 1/D. Finally, E ∥PS (O)∥22 = i=1 C = d · C = d/D. High-Probability Bound for Spherical Operators. Next we derive a high-probability bound on the error by determining the probability distribution of the squared norm of the projection, ∥P≤b (O)∥22 . Lemma 2. Let O be a random vector chosen uniformly from the unit sphere in a D-dimensional space V . Let PS be the orthogonal projection onto a d-dimensional subspace S. The random variable X = ∥PS (O)∥22 follows a Beta distribution with parameters α = d/2 and β = (D − d)/2. d D−d 2 ∥PS (O)∥2 ∼ Beta , 2 2 Proof of Lemma. A random vector O on the unit sphere can be generated by taking a standard D-dimensional Gaussian vector G = (g1 , . . . , gD ) where each gi ∼ N (0, 1) are i.i.d., and normalizing it: O = G/∥G∥2 . Let {e1 , . . . , eD } be an orthonormal basis for V where {e1 , . . . , ed } is a basis for S. The coefﬁcients of O are ci = ⟨O, ei ⟩ = gi /∥G∥2 . The squared norm of the projection is: Pd d 2 X 2 2 i=1 gi ∥PS (O)∥2 = ci = PD 2 j=1 gj i=1

Pd PD Let U = i=1 gi2 and V = j=d+1 gj2 . By deﬁnition of the chi-squared distribution, U ∼ χ2 (d) and V ∼ χ2 (D − d). Since the gi are independent, U and V are independent. The random variable is X = U/(U + V ). A random variable constructed as the ratio of a chi-squared variable to the sum of itself and another independent chi-squared variable is known to follow the Beta distribution. Speciﬁcally, if U ∼ χ2 (ν1 ) and V ∼ χ2 (ν2 ), then U/(U + V ) ∼ Beta(ν1 /2, ν2 /2). Substituting ν1 = d and ν2 = D − d proves the lemma. 1 The Beta distribution is known to be strongly concentrated around its mean. In fact, it is 4(α+β) -sub-gaussian [Marchal and Arbel, 2017]. Hence we can use Hoeffding’s inequality to obtain a concentration inequality: For a random variable X ∼ Beta(α, β) with mean µ = α/(α + β), a tail bound is given by: 2 t2 P(|X − µ| ≥ t) ≤ 2 exp − 2 ≤ 2e−2(α+β)t 2σ d/2 In our case, µ = D/2 = d/D and α + β = D/2. We are interested in a lower bound on X to get an upper bound on the error. 2 d P X≤ − t ≤ e−Dt D p −Dt2 Setting the failure gives t = ln(1/δ)/D. This means with probability at least 1 − δ, we have p probability to δ = e X ≥ d/D − ln(1/δ)/D.

Corollary 1 (Spherical Error Bound). With probability at least 1 − δ, the squared Hilbert-Schmidt norm of the error is bounded by: ! r Pb n w ln(1/δ) w=0 w 3 ∥O − P≤b (O)∥22 ≤ 1 − + . 4n 4n Proof. From the Pythagorean identity, ∥O − P≤b (O)∥22 = 1 − ∥P≤b (O)∥22 . Let d = dim(A≤b ), using the high-probability lower bound on ∥P≤b (O)∥22 gives: ! r ln(1/δ) d 2 − ∥O − P≤b (O)∥2 ≤ 1 − D D r ln(1/δ) d + = 1− D D Next we show that D = 4n and d =

n w w=0 w 3 in our case.

P Recall any operator O ∈ An can be uniquely decomposed in the Pauli basis: O = P cP P, where P are n-qubit Pauli operators. And it follows directly from our assumption that cP ̸= 0 for all cP with probability 1. The n-qubit Pauli operators form a basis of An , hence D = 4n . d is the dimension of the subspace A≤b , the number of linearly independent Pauli operators with weight at most b. Note the following: n . • The number of ways to choose w qubits to act on from a total of n is w • For each of the chosen w qubits, there are 3 non-identity Pauli choices (σx , σy , σz ). n w • The total number of Pauli strings with weight exactly w is w 3 . The dimension d is the sum over all allowed weights (from 0 to b): d = dim(A≤b ) =

b X n w=0

Substitute the expression for d and D completes the proof.

Now it only remains for us to show that

Pb p := 1 − For this purpose we note that

n w − 8n 3 w=0 w 3 ≤ e 4n

2 b+1 3 n −4

n 1 X n w 3 4n w w=b+1 n X n 3 w 1 n−w = w 4 4

w=b+1

= Pr

n 1 X

n i=1

Zi ≥

b + 1 , n

3 where Zi are independent Bernoulli random variables satisfying Pr(Zi = 1) = 34 . If b+1 n ≥ 4 which is the regime of interest, by the Chernoff bound, b + 1 3 , p ≤ exp − nDKL n 4

where DKL (q∥p) denotes the KL divergence between Bernoulli distributions with parameters q and p. Furthermore, it holds x2 that DKL (q + x∥q) ≥ 2q(1−q) . Thus, DKL

b + 1 3 ( b+1 − 3 )2 8 b + 1 3 2 ≥ n 3 41 = − . n 4 3 n 4 2· 4 · 4

We conclude that

p ≤ exp

−

8n b + 1 3 2 − . 3 n 4

C.4 JUSTIFICATION OF THE RANDOM OPERATOR ASSUMPTION The proof of Theorem 2(ii) relies on the assumption that the global observable O is drawn uniformly at random from the sphere of operators with a ﬁxed norm. While this may seem abstract and restrictive, it can be motivated from an isotropic Gaussian prior on the observable O (which induces a GP prior on f ∗ (x) = Tr[Oρ(x)]). This assumption corresponds to conditioning that Gaussian prior on ∥O∥2 (equivalently, normalizing a Gaussian draw). Here’s the connection: From Gaussian Processes to Operator Priors. A function f ∗ drawn from a GP is deﬁned by a prior distribution over a function space. In our setting, where functions are of the form f ∗ (x) = Tr[Oρ(x)], this prior on functions induces a prior on the operator O. We can represent any observable O by expanding it in an orthonormal basis of Hermitian operators, {Bi } (e.g., the normalized Pauli basis): 4n X O= c i Bi i=1

A simple and common case of GP prior is one where the coefﬁcients ci are assumed to be independent and identically distributed (i.i.d.) Gaussian random variables, i.e., ci ∼ N (0, σ 2 ). This is equivalent to placing a white-noise Gaussian prior on the operator O. From Gaussian Vectors to Uniform Spherical Vectors. The vector of coefﬁcients, c = (c1 , c2 , . . . , c4n ), is therefore a vector whose components are i.i.d. Gaussians. A fundamental property of multivariate Gaussian distributions is that, taking such a vector and normalize it by its length, the resulting direction vector is uniformly distributed on the surface of the unit sphere. So, if we normalize our coefﬁcient vector to get c′ = c/∥c∥2 , the vector c′ will be uniformly random on the unit n sphere in R4 . P ′ Hence, the operator constructed from these normalized coefﬁcients, O′ = i ci Bi , will have a unit Hilbert-Schmidt norm (∥O′ ∥2 = ∥c′ ∥2 = 1) and its “direction” in the space of operators will be uniformly random. This is precisely the assumption made in our proof.

C.5 STRUCTURED OBSERVABLES: LOCALITY, PAULI-WEIGHT TAILS, AND REGRET The bound in Theorem 2(ii) provides a useful worst-case baseline, but it is pessimistic for many physical tasks. In many quantum optimization problems, the observable O has additional structure, such as locality or a rapidly decaying highweight Pauli tail. In this subsection, we show how such structure directly improves the LPQK misspeciﬁcation error and the resulting regret bound. Recall in a quantum system with n qubits, any observable O ∈ An can be uniquely decomposed in the normalized Pauli P basis: O = P cP P, where P are n-qubit Pauli operators. And the Pauli weight of a Pauli operator P, denoted wt(P), is the number of qubits on which it acts non-trivially (i.e., not as the identity). Deﬁne the low-weight and high-weight components X O≤b := cP P,

O>b :=

wt(P)≤b

cP P.

wt(P)>b

The summed LPQK over all subsystems |s| ≤ b retains exactly the observable components of Pauli weight at most b. Therefore, for f ∗ (x) = Tr[Oρ(x)], the best LPQK approximation satisﬁes  εb :=

inf

f ∈HκS (X )

∥f − f ∗ ∥∞ ≤ sup |Tr[O>b ρ(x)]| ≤ ∥O>b ∥op ≤ ∥O>b ∥HS =  x∈X

1/2 c2P 

(18)

wt(P)>b

That is, the LPQK misspeciﬁcation error is controlled by the high-weight Pauli tail of the target observable. Pb n w On the other hand, the effective dimension of the summed LPQK is Sb := w=0 w 3 , and hence its information gain satisﬁes γT (b) = O(Sb log T ). Substituting this into the EC-GP-UCB bound in Eq. (8) gives, suppressing logarithmic factors and constants, p p √ e (B Sb + Sb ) T + εb T Sb . RT (b) = O

(19)

Example 1: k-local observables. Suppose O is k-local, meaning that its Pauli expansion contains no terms of weight larger than k: cP = 0 for all wt(P) > k. Then O>b = 0 for all b ≥ k, and therefore εb = 0

for all b ≥ k.

Thus, choosing b = k makes the LPQK surrogate realizable while using only Sk =

k X n w=0

3w = O(nk )

features for ﬁxed k, instead of the full 4n -dimensional quantum feature space. The regret bound becomes p √ √ e (B Sk + Sk ) T = O e nk T RT (k) = O for ﬁxed k under the EC-GP-UCB bound. Therefore, for local physical observables, LPQK can replace the exponential full-kernel dimension 4n by the polynomial dimension Sk = O(nk ). Example 2: exponentially decaying high-weight Pauli tail. More generally, suppose the total squared Pauli mass at weight w decays exponentially: X Ew := c2P ≤ C0 e−2αw for some C0 , α > 0. wt(P)=w

Then εb ≤ ∥O>b ∥HS =

n X

!1/2 Ew

w=b+1

≤

∞ X

!1/2 e

−2αw

= Cα e−α(b+1) ,

(20)

w=b+1

p where Cα := C0 /(1 − e−2α ). Hence the misspeciﬁcation error decreases exponentially in the retained subsystem size b, while the information gain increases through b X n w γT (b) = O(Sb log T ), Sb = 3 . w w=0 Combining (19) and (20) gives

p p √ e (B Sb + Sb ) T + Cα e−αb T Sb . RT (b) = O

Thus, an optimal subsystem size can be selected by n p p o √ b⋆ ∈ arg min (B Sb + Sb ) T + Cα e−αb T Sb . 0≤b≤n

e Since for small ﬁxed b, Sb = O(nb ), balancing the two terms gives the heuristic scaling b⋆ = O yielding log n e T 21 + 2α+log n . RT = O

log T 2α+log n

, and eventually

Thus, faster Pauli-tail decay, i.e., larger α, permits a smaller subsystem size and regret closer to the realizable rate.

√

T -type

Overall, LPQK is more beneﬁcial when the target observable has most of its Pauli mass concentrated on low-weight terms. In the exact k-local case, the misspeciﬁcation error vanishes at b = k and the exponential full-kernel dimension 4n is replaced by the polynomial dimension O(nk ). For observables with decaying high-weight tails, the optimal b is determined by balancing the information-gain term Sb against the tail error εb . n Remark on Effective Dimensionality It is important to note that the dimensions used in proof of Theorem 2(ii), D = 4 Pb n w and d = w=0 w 3 , are based on the assumption that the quantum feature map is sufﬁciently expressive to span the entire space of n-qubit Hermitian operators. While this is often the case for complex, generic circuits, it may not hold for all feature maps.

In many practical scenarios, a quantum circuit may have speciﬁc symmetries or a limited number of parameters, constraining the reachable states {ρ(x)} to a lower-dimensional subspace. In such cases, the actual dimension of the full space D would be less than 4n , and the actual dimension of the low-weight subspace, d, would likewise be smaller than Pb n w w=0 w 3 .

FOURIER FORM OF QUANTUM KERNELS AND RFF

D.1 FOURIER FORM OF QUANTUM KERNELS Theorem 4 (Fourier Representation of Quantum Kernels, Theorem 1 of Schuld [2021]). Let X = RN and let S(x) = W(N +1) e−ixN G W(N ) · · · W(2) e−ix1 G W(1) be a data-encoding circuit, where each G is a diagonal (d × d) Hermitian operator with eigenvalues {λ1 , . . . , λd }, and W(1) , . . . , W(N +1) denote ﬁxed unitary operations. Deﬁne the quantum state |ϕ(x)⟩ = S(x) |0⟩ and let κQ (x, x′ ) be the resulting quantum kernel, i.e., 2 κQ (x, x′ ) = ⟨ϕ(x)|ϕ(x′ )⟩ . Then there exists a ﬁnite index set Ω ⊆ RN (derived from the eigenvalues {λj }) and coefﬁcients {cs,t }s,t∈Ω such that X κQ (x, x′ ) = cs,t exp i s · x exp i t · x′ (21) s,t∈Ω

Proof. Assume without loss of generality that the encoding generator G is diagonal because any Hermitian operator can be diagonalized as G = VΣV† , where Σ is diagonal. Consequently, an encoding gate e−ixi G can be written as e−ixi G = V e−ixi Σ V† , and thus we may “absorb” V and V† into the preceding and subsequent arbitrary unitaries in the circuit. Hence, we have  −ix λ e i 1  .. −ixi Σ e =  . 0

··· .. . ···

0 .. .

  ,

e−ixi λd

where {λ1 , . . . , λd } are the eigenvalues of G. The quantum kernel can be written as 2

κQ (x, x′ ) = ⟨ϕ(x)|ϕ(x′ )⟩ † † † † ′ ′ = |⟨0| W(1) e− i x1 Σ · · · e− i xN Σ W(N +1) × W(N +1) e− i xN Σ · · · e− i x1 Σ W(1) |0⟩|2 † † † ′ ′ = |⟨0| W(1) e− i x1 Σ · · · e− i xN Σ × e− i xN Σ · · · e− i x1 Σ W(1) |0⟩|2 d d X X = exp − i λj1 x1 − λk1 x′1 + · · · + λjN xN − λkN x′N j1 ,...,jN =1 k1 ,...,kN =1 (1)

(N )

× W1 k1 · · · WkN −1 kN =

XX j

(1) 2

(N )

× WjN jN −1 · · · Wj1 1

∗ exp − i (Λj · x − Λk · x′ ) wk wj

XXXX j

∗

∗ exp − i (Λj − Λl ) · x exp i (Λk − Λh ) · x′ × wk wh wj wl .

(i)

Here, the scalars Wab for i = 1, . . . , N refer to the element ⟨a| W(i) |b⟩ of the unitary operator W(i) . The bold multi-index j summarizes the set (j1 , . . . , jN ) where ji ∈ {1, . . . , d}, and Λj is a vector containing the eigenvalues selected by the multi-index (and similarly for k, h, l). We can now group together all terms where Λj − Λl = s and Λk − Λh = t; in other words, where the differences of eigenvalues amount to the same vectors s, t. Then we have

′

κQ (x, x ) =

s,t∈Ω

−is·x it·x′

wj wl wk wh

∗

j,l: k,h: Λj −Λl =s Λk −Λh =t ′

e−is·x eit·x cs,t

s,t∈Ω

The frequency set Ω contains all vectors of the form {Λj − Λk } with Λj = (λj1 , . . . , λjN ), j1 , . . . , jN ∈ {1, . . . , d}. This result demonstrates that a quantum kernel can be interpreted as a sum of complex exponentials, which are determined by the spectra of the encoding generator G and the unitaries interleaved within the circuit. Although, in principle, this sum may encompass exponentially many terms—stemming from the combinatorial complexity of multi-qubit gates—the speciﬁc structure of G and the unitaries W often introduce patterns or symmetries. These patterns can be leveraged to simplify analysis. More importantly, once the circuit structure is ﬁxed, the coefﬁcients in this sum can be computed explicitly using a formula, as outlined earlier in the proof.

Remark (extension to re-uploading / repeated encodings). Theorem 4 is stated for an encoding sequence in which each scalar input xj appears once. If a circuit re-uploads the same input x ∈ Rd across multiple layers (so that some coordinates are used multiple times), the resulting kernel still admits a Fourier representation of the above form [Schuld et al., 2021]. Next, we will examine how this perspective facilitates the analysis of the feature map corresponding to quantum kernels.

D.2 RFF WITH PAULI ENCODING QUANTUM KERNEL In this section, we consider the special case where the quantum kernel κQ (x, x′ ) satisﬁes two simplifying properties: • The kernel is translation-invariant—i.e., it depends only on the difference x − x′ . • The frequencies Ω in the Fourier representation (cf. Equation 21) are integer-valued. These assumptions hold in many common settings, e.g., when data encoding is implemented by Pauli rotations [Landman et al., 2022]. In this case, one may write κQ (x, x′ ) =

X cω exp i ω ⊤ (x − x′ ) = cω cos ω ⊤ (x − x′ ) ,

ω∈Ω

where Ω ⊂ Zd is a ﬁnite set of frequencies and cω ≥ 0 are real Fourier coefﬁcients. Expressing κ in a Real Feature Space From standard trigonometric identities, each cosine term cos(ω ⊤ x − ω ⊤ x′ ) can be represented as a dot product of some 2 dimensional real feature. Speciﬁcally, C cos(α − β) = C cos α cos β + C sin α sin β √ √ C cos α C cos β √ √ = , C sin α C sin β For example, let ∆i = xi − x′i , cos(∆1 − ∆2 + ∆3 ) = cos ((x1 − x′1 ) − (x2 − x′2 ) + (x3 − x′3 )) = cos ((x1 − x2 + x3 ) − (x′1 − x′2 + x′3 )) cos(x1 − x2 + x3 ) cos(x′1 − x′2 + x′3 ) = , . sin(x1 − x2 + x3 ) sin(x′1 − x′2 + x′3 ) P Hence, if κQ (x, x′ ) = ω∈Ω cω cos ω ⊤ (x − x′ ) , then we can rewrite κQ as ⟨ϕ(x), ϕ(x′ )⟩ for some (potentially highdimensional) ϕ(x) built from the features. Consequently, for a translation-invariant quantum kernel κQ with a ﬁnite Fourier decomposition, κQ corresponds to the real feature set n√

√ o cω cos ω · x , cω sin ω · x

. ω∈Ω

Approximation via Random Fourier Features Following the approach in [Landman et al., 2022], one can sample D frequencies (ω 1 , ..., ω D ) uniformly from Ω, and then construct the approximate kernel κRFF (x, x′ ) := ϕRFF (x)T ϕRFF (x′ ), where

q ϕRFF (x) =

1 D

⊤ cos ω 1 ·x , . . . , sin ω D ·x .

Uniform approximation of the target function via random bases. To control the misspeciﬁcation error induced by replacing the full feature ϕQ with a random low-dimensional feature map, we use the following uniform approximation theorem of Rahimi and Recht [2008]. Theorem 5 (Uniform approximation with random bases [Rahimi and Recht, 2008, Theorem 3.2]). Let X ⊂ Rd be compact and let φ(x; θ) = φ(θ ⊤ x), where φ : R → R is L-Lipschitz, satisﬁes φ(0) = 0, and |φ| ≤ 1. Let p be a distribution over θ with ﬁnite second moment. Deﬁne the mixture class Z α(θ) F(X , Θ, φ, p) = f (x) = <∞ . α(θ)φ(x; θ) dθ : ∥f ∥p := sup p(θ) θ Θ iid

Fix any f ∈ F and let BX = supx∈X ∥x∥2 . Draw θ 1 , . . . , θ D ∼ p. Then for any δ > 0, with probability at least 1 − δ, there exist coefﬁcients c1 , . . . , cD such that D X fˆ(x) = ck φ(θ ⊤ k x) k=1

satisﬁes the uniform bound

∥f ∥p ∥fˆ − f ∥∞ < √ D

1 log + 4LBX δ

! Eθ∼p ∥θ∥22

√ This theorem yields a uniform O(1/ D) approximation rate on the entire compact domain X . In [Rahimi and Recht, 2008], the authors discuss that Fourier features of the form φ(x; θ) = cos(ω ⊤ x + b) satisfy the conditions of Theorem 5. D.3 RFF WITH GENERAL ENCODING QUANTUM KERNEL When one or more encoding Hamiltonians in a variational quantum circuit (VQC) are not trivially diagonalizable, directly identifying and sampling from their associated frequency set can be challenging. To address this, Landman et al. [2022] propose a more ﬂexible grid-based sampling approach to approximate the quantum kernel. The central idea involves sampling from a grid of frequencies evenly spaced between zero and an upper bound, ω max , along each dimension. Here, ω max is chosen as the maximum possible frequency that can appear in the VQC—such as the one inferred via the Shannon criterion or derived from known bounds on the largest eigenvalues of the encoding Hamiltonians. Speciﬁcally, suppose each dimension of x could contain frequencies in [0, ω max ]. We partition this interval into regularly spaced bins of size s > 0, giving ⌈ω max /s⌉d possible frequency values per dimension. Over d dimensions, this yields a regular grid of size [0, ω max ]d . One then sample D frequencies (ω 1 , . . . , ω D ) from the grid, and similarly construct the approximate kernel kRFF (x, x′ ) = ϕRFF (x)⊤ ϕRFF (x′ ) where, as before, q ϕRFF (x) =

1 D

cos ω 1 ·x

...

cos ω D ·x

⊤

Then we have [Landman et al., 2022] Theorem 6 (RFF for Grid Sampling). Let X be a compact subset of Rd , and ε > 0. Consider a training set {(xi , yi )}M i=1 . Let f ∗ be a VQC model with any Hamiltonian encoding, with a maximum individual P frequency ωmax and full freedom on M 1 2 the associated frequency coefﬁcients, trained with a regularization λ. Let σy2 = M i=1 yi and |X | be the diameter of X . Let f˜ be the RFF model with D samples in the grid strategy, trained on the same dataset and the same regularization. Let C = ∥f ∗ ∥∞ |X | and s be the sampling rate as in the grid strategy. Then, for 0 < s < C1 , we can guarantee supx∈X |f ∗ (x) − f˜(x)| ≤ ε with probability 1 − δ, provided the number D of samples satisﬁes C (1 + λ) i dC1 (1 + λ) h 2 log ω max |X | + log 2 − log δ , D=Ω 4 λ (ε − sC)2 λ (ε − sC)

where C1 and C2 are constants depending on σy and X . Note that f ∗ can be equivalently deﬁned to be the Kernel Ridge Regression (KRR) predictor derived from the full quantum kernel κ, and this theorem can be used similarly as Theorem 9

D.4 A DIRECT TRUNCATED KERNEL APPROXIMATION APPROACH Recall that for a translation invariant quantum kernel, we can express its feature map as n√ √ o cs cos s · x , cs sin s · x . s∈Ω

Truncated Features for Kernel Approximation To construct a smaller feature map (or kernel) from κQ , a natural idea is to pick only the largest-magnitude coefﬁcients {cs } and retain those frequencies s in the approximation while discarding others. Concretely, let S ⊂ Ω be a subset of frequencies corresponding to the largest values of {cs } and deﬁne h X i κsmall (x, x′ ) = cs cos s · x cos s · x′ + sin s · x sin s · x′ . s∈S⊆Ω

This kernel κsmall is essentially a truncated version of κQ : it retains only frequencies in S. We now show that a function f drawn from GP(0, κQ ) can be uniformly approximated by a function in the RKHS of κsmall , with an error bounded by the sum of the left-out coefﬁcients. Theorem 7 (Approximation by Truncating Fourier Series). Suppose a quantum kernel admits a Fourier series X κQ (x, x′ ) = cs cos s · (x − x′ ) , s∈Ω

and let f ∗ be a function sampled from GP(0, κQ ). Consider the truncated kernel h X i κsmall (x, x′ ) = cs cos s · x cos s · x′ + sin s · x sin s · x′ , s∈S⊂Ω

with the associated RKHS Hκsmall (X ). Then, the expected uniform approximation error satisﬁes i h X √ ∥f − f ∗ ∥∞ ≤ 2 cs . E min f ∈Hκsmall (X )

s∈Ω\S

Proof. We outline the proof in the following three steps. 1. Sampling f from GP(0, κQ ): By standard Gaussian process theory, a function f drawn from GP(0, κQ ) admits a representation in terms of feature basis corresponding to κQ . Concretely, one may write X f (x) = αω ψω (x), ω∈Ω

√ where αω ∼ N (0, 1), and {ψω } are orthonormal basis functions scaled by cω . In our case, we can take ψω = √ √ √ ( cω cos(ω · x) + cω sin(ω · x)). For notational convenience, we may redeﬁne αω ← cω αω so that ψω is just (cos(ω · x) + sin(ω · x)). 2. Restricting to a Smaller Kernel ksmall : Suppose we now try to approximate f ∗ by a function g lying in the RKHS associated with the truncated kernel κsmall . This space corresponds to a smaller set of frequencies S ⊂ Ω. Consequently, any g(x) ∈ Hκsmall (X ) can be written as X g(x) = βω ψω (x), ω∈S

where {βω } are real coefﬁcients determined by the regression procedure between f ∗ and g. R Since the functions {ψω } are orthogonal on [0, 2π]d (i.e., [0,2π]d ψω (x)ψω′ (x) dx = 0 for all ω ̸= ω ′ ), the best ﬁt to f ∗ in the mean-square sense is achieved by matching coefﬁcients on those frequencies in S. In other words, for each ω ∈ S ∩ Ω, the optimal βω is αω ; frequencies outside S ∩ Ω cannot be matched, leaving those βω = 0.

This can be seen by expanding the objective Z 2

[f (x) − g(x)] dx [0,2π]d

f (x)2 − 2f (x)g(x) + g(x)2 dx

= [0,2π]d

and noting that in Z f (x)g(x) dx [0,2π]d

= [0,2π]N

αω βω ψω (x) +

αs βt ψs (x)ψt (x) dx,

s,t,s̸=t

the second summand is zero by the orthogonality of {ψω }. Thus, the solution matching βω = αω for ω ∈ S ∩ Ω and βω = 0 otherwise minimizes the integral, and hence yields the optimal least-squares approximation. 3. Uniform Approximation Error:

h i Finally, consider the uniform approximation error, E minf ∈ Hκsmall (X ) ∥f − f ∗ ∥∞ . Since the optimal f ∈ Hκsmall (X ) contains coefﬁcients that match the corresponding ones in f ∗ , we obtain min

f ∈Hκsmall (X )

X √

∥f − f ∗ ∥∞

cs (cos(s · x) + sin(s · x))

s∈Ω\S

≤

√ 2 cs ,

s∈Ω\S

which is the statement to be proved.

E PROOF OF THEOREM 3 E.1 INTRODUCTION TO SQUARECB Algorithm 1 SquareCB Parameters: Learning rate γ > 0, exploration parameter µ > 0, online regression oracle SqAlg. 1: for t = 1, . . . , T do 2: Receive context xt . 3: For each action a ∈ A, compute ŷt,a := ŷt (xt , a) 4: Let bt = arg mina∈A ŷt,a P 5: For each a ̸= bt , deﬁne pt,a = µ+γ(ŷt,a1 −ŷt,b ) and let pt,bt = 1 − a̸=bt pt,a t 6: Sample action at ∼ pt and observe loss ℓt (at). 7: Update SqAlg with example (xt , at ), ℓt (at ) . 8: end for

Foster and Rakhlin [2020] considered the following contextual bandit setting: Over T rounds: • Nature or an adversary picks a context xt ∈ X and a loss function ℓt (·) : A → [0, 1]. • Learner observes xt , selects at ∈ A. • Learner incurs and observes loss ℓt (at ).

Note that we are considering the linear bandit setting in this work, which is simply a special case of their setting (with constant xt ). The learner has access to a function class F ⊆ {f : X × A → [0, 1]}. Under realizability, there is an f ∈ F so that E[ℓt (a) | xt ] = f (xt , a). In a misspeciﬁed setting, one relaxes this equality to E[ℓt (a) | xt ] − f (xt , a) ≤ ε,

∀t, a

for some ε > 0. Note this agrees with our deﬁnition for misspeciﬁed setting in the main text, namely that there exists f ∈ F such that |f (xt , a) − f ∗ (xt , a)| ≤ ε. Here f ∗ (xt , a) = E[ℓt (a) | xt ]. Foster and Rakhlin [2020] introduced SquareCB, a contextual linear bandit algorithm. See Algorithm 1 for details. SquareCB uses an online algorithm called SqAlg that provides predictions ŷt (xt , a) ∈ [0, 1], and receives the true label (loss) yt ∈ [0, 1]. Over T rounds, SqAlg aims to do as well as the best function f ∈ F in terms of the square loss, i.e., it satisﬁes a bound of the form T X

ybt − yt

− inf

f ∈F

t=1

T X

f (xt , at ) − yt

≤ RegSq (T ),

t=1

where RegSq (T ) is typically called the square-loss regret of the online forecaster. If F is a simple class (e.g., linear in our case), there are known efﬁcient algorithms that achieve small RegSq (T ). In the misspeciﬁed setting, Foster and Rakhlin [2020] showed the following: Theorem q 8 (Pseudoregret Bound for SquareCB). Under the misspeciﬁed setting, SquareCB with µ = K := |A| and γ = 8KT /(RegSq (T ) + ε2 T ) ensures that sup E

" T X

ℓt (at ) −

t=1

T X

ℓt π(xt )

# ≤2

q √ KT RegSq (T ) + 5ε KT,

t=1

where at is the action chosen with SquareCB at time t, and supπ ranges over all policies π : X → A. Then, by instantiating SquareCB with the Vovk-Azoury-Warmuth forecaster, which has RegSq (T ) ≤ D log(1 + T /D), one gets an efﬁcient algorithm with regret " T # T X X p √ ∗ RT = E ℓt (at ) − ℓt π (xt ) ≤ 2 KT D log(1 + T /D) + 5ε KT. t=1

t=1

with π ∗ being the optimal policy. E.2 CHOOSING OPTIMAL D AND THE PROOF OF THEOREM 3 We now apply the SquareCB algorithm, combined with the Distinct-Sampling RFF technique, to the linear bandit setting where, at each round t, the following hold: • The context xt is now constant. • The reward (or equivalently, the loss function) is linear in the quantum feature map ρ(a). Speciﬁcally, E[ℓt (a)|xt ] = n n Tr[Hρ(a)] for some observable H and known quantum feature map ρ(a) ∈ C2 ×2 . In other words, f ∗ (a) := E[ℓt (a)|xt ] belongs to the RKHS induced by the quantum kernel κQ . By construction, f ∗ belongs to the RKHS induced by the quantum kernel κQ . We now instantiate Theorem 5 for the Pauli-encoding kernel κQ above. Deﬁne the parameter set Θ := Ω × {c, s},

p(ω, u) :=

1 2|Ω|

(uniform over Θ),

and deﬁne the real basis functions φ(x; (ω, c)) :=

1 1 cos(ω ⊤ x) − , 2 2

φ(x; (ω, s)) := sin(ω ⊤ x).

Note that any function f ∈ HκQ can be written as a ﬁnite mixture of these bases: X f (x) = c0 + aω cos(ω ⊤ x) + bω sin(ω ⊤ x) , ω∈Ω

which corresponds to a discrete mixture representation in the class F(X , Θ, φ, p). The scaling by 12 in φ(x; (ω, c)) is merely to match the requirement for Theorem 5 and does not affect the conclusion since it just shifts the result by a ﬁxed constant. We obtain the following corollary, which we will use as the misspeciﬁcation guarantee for SquareCB. Theorem 9 (Uniform misspeciﬁcation bound of RFF approximation of Pauli-induced quantum f ∗ ). Let κQ be a shiftinvariant Pauli-encoding quantum kernel on a compact domain X ⊂ Rd with ﬁnite spectrum Ω ⊂ Zd , and let f ∗ ∈ HκQ . iid

Fix δ ∈ (0, 1) and draw (ω 1 , u1 ), . . . , (ω D , uD ) ∼ p uniformly from Θ = Ω × {c, s}. Deﬁne the random feature map ⊤ 1 ϕRFF (x) = √ 1, φ(x; (ω 1 , u1 )), . . . , φ(x; (ω D , uD )) ∈ RD+1 . D Then with probability at least 1 − δ, there exists a linear predictor f˜(x) = ⟨w, ϕRFF (x)⟩ such that ! r ∗ ∥f ∥ 1 p ∗ (22) εD := sup |f (x) − f˜(x)| < √ log + 4BX ωmax , δ D x∈X where BX = supx∈X ∥x∥2 and ωmax := maxω∈Ω ∥ω∥2 . Note that since Ω is ﬁnite in any ﬁxed-n qubit system, we have assumed ∥f ∗ ∥HκQ is bounded by B and p is uniform, we have that ωmax and ∥f ∗ ∥p are all ﬁnite constants. By q Foster and Rakhlin [2020], under the misspeciﬁed setting, SquareCB with µ = K 8KT /(RegSq (T ) + ε2 T ) guarantees the expected pseudoregret bound " T # T q X X √ sup E ℓt (at ) − ℓt (π(xt )) ≤ 2 KT RegSq (T ) + 5ε KT, π

t=1

:= |A| and γ

t=1

where RegSq (T ) is the square-loss regret of the regression oracle. We instantiate the regression oracle by the Vovk–Azoury–Warmuth forecaster. For a d-dimensional linear class, this gives RegSq (T ) ≤ d log(1 + T /d), hence p √ E[RT ] ≤ 2 KT · d log(1 + T /d) + 5ε KT (23) Case 1: Exact quantum model. model (so ε = 0), and therefore

Using the exact quantum feature map with ambient dimension d = 4n yields a realizable r E[RT ] ≤ 2

KT · 4n log 1 + 4Tn .

Case 2: RFF approximate model. Using a D-dimensional RFF surrogate gives a misspeciﬁcation level ε = εD . Set δ = 1/T in 22, then with probability at least 1 − 1/T (over the sampled Fourier features), ∥f ∗ ∥p p log T + 4BX ωmax . εD < √ D On the (probability ≥ 1 − 1/T ) event above, we substitute the explicit bound on εD as in 22; on the complement event we use the trivial bound RT ≤ T . Taking total expectation gives r √ ∥f ∗ ∥p p T + 5 KT √ E[RT ] ≤ 2 KT · D log 1 + D log T + 4BX ωmax + 1. D √ Choosing D = ⌈ T ⌉ yields p p √ √ √ E[RT ] ≤ 2 KT 3/4 log T + 5 KT 3/4 ∥f ∗ ∥p log T + 4BX ωmax + 1 = Õ KT 3/4 Finally, taking the minimum of the exact-model bound and the RFF-surrogate bound yields the result in Theorem 3.

E.3 BOUND ON ∥f ∗ ∥p Assume the quantum kernel is shift-invariant with a ﬁnite Fourier expansion X κQ (x, x′ ) = cω cos ω ⊤ (x − x′ ) . ω∈Ω

Let f ∗ ∈ HκQ with ∥f ∗ ∥HκQ ≤ B. Then we show that ∥f ∗ ∥p ≤ 4|Ω|B. This, together with the derivation in Appendix E.2, yields the result in Theorem 3. Proof. Recall that if we deﬁned the feature map √ √ ϕ(x) := cω cos(ω ⊤ x), cω sin(ω ⊤ x) ω∈Ω ∈ R2|Ω| , then κQ (x, x′ ) = ⟨ϕ(x), ϕ(x′ )⟩, and every f ∗ ∈ HκQ can be written as f ∗ (x) = ⟨w, ϕ(x)⟩ for some w ∈ R2|Ω| with ∥f ∗ ∥HκQ = ∥w∥2 . Write w = (uω , vω )ω∈Ω such that X X √ √ f ∗ (x) = uω cω cos(ω ⊤ x) + vω cω sin(ω ⊤ x) = aω cos(ω ⊤ x) + bω sin(ω ⊤ x) , ω∈Ω

√

ω∈Ω

√

where aω := uω cω and bω := vω cω . Since κQ (x, x) = ω∈Ω cω ≤ 1, we have cω ≤ 1 for all ω, hence √ √ |aω | ≤ |uω | cω ≤ ∥w∥2 cω ≤ ∥w∥2 ≤ B, similarly, |bω | ≤ B. Now note that φ(0; (ω, c)) = 0, so the centered function g(x) := f ∗ (x) − f ∗ (0) admits the exact mixture representation X X X X g(x) = aω cos(ω ⊤ x) − 1 + bω sin(ω ⊤ x) = 2aω φ(x; (ω, c)) + bω φ(x; (ω, s)). ω∈Ω

ω∈Ω

Thus we may take α(ω, c) = 2aω and α(ω, s) = bω . Also recall that we sampled the Random Features uniformly with 1 , hence p(ω, u) = 2|Ω| ∥g∥p =

n o α(ω, u) = 2|Ω| · max max |2aω |, max |bω | ≤ 2|Ω| · max{2B, B} = 4|Ω|B. ω ω (ω,u)∈Θ p(ω, u) sup

E.4 BOUND ON ωmax Recall ωmax := maxω∈Ω ∥ω∥2 , where Ω is the frequency set in the Fourier/Bochner representation of a shift-invariant quantum kernel κQ (x, x′ ) = g(x − x′ ), appeared in Theorem 3. We hereby give a short discussion on ωmax to show that it is moderate and usually negligible. A simple upper bound. Consider any data-encoding circuit in which each input coordinate xj appears mj times via gates exp(−ixj Gj,ℓ ), ℓ = 1, . . . , mj . Let ∆j,ℓ := λmax (Gj,ℓ ) − λmin (Gj,ℓ ) be the spectral diameter of the generator. Then every frequency vector ω ∈ Ω satisﬁes |ωj | ≤

mj X

∆j,ℓ

(j = 1, . . . , d),

(24)

ℓ=1

and hence ωmax ≤

m1 X

∆1,ℓ , . . . ,

ℓ=1

We next give a concrete bound on ωmax for some example cases.

md X ℓ=1

< ∞.

∆d,ℓ 2

(25)

Example 1. Suppose d = n and each xj is encoded once on one qubit using Gj ∈ {X, Y, Z}, so mj = 1. Since X, Y, Z have eigenvalues ±1, we have ∆j,1 = 2 and thus |ωj | ≤ 2 for all j. Therefore v uX u n √ √ ωmax ≤ t 22 = 2 n = O n . j=1

Example 2. Let d = 1 and encode the same scalar x on each of n qubits once, e.g., |ψ(x)⟩ = (e−ixX/2 |0⟩)⊗n . Then the ﬁdelity kernel is x − x′ 2 κ(x, x′ ) = ⟨ψ(x)|ψ(x′ )⟩ = cos2n . 2 Using cos(θ) = 12 (eiθ + e−iθ ), cos2n

∆ 2

= 2−2n

2n X 2n j=0

ei(n−j)∆ =

n X

cℓ eiℓ∆ ,

∆ := x − x′ .

ℓ=−n

Hence Ω = {−n, −n + 1, . . . , n} and ωmax = n. Example 3. Suppose d = n and each coordinate xj is re-uploaded L times with local Pauli generators (so mj = L and each ∆j,ℓ = 2). Then by (25), v uX u n √ √ ωmax ≤ t (2L)2 = 2L n = O L n j=1

DISCUSSION ON RUNNING TIME

Algorithm 2 GP-UCB Input: Input (Action) space A; GP Prior µ0 = 0, σ0 , κ. 1: for t = 1, . . . , T do √ 2: Choose xt = arg max µt−1 (x) + βt σt−1 (x) , where βt = 2 log(|A|t2 π 2 /6δ) x∈A

3: Sample yt := f ∗ (xt ) + ηt , where ηt is the noise 4: Update posterior mean and variance µt and σt 5: end for

Algorithm 3 EC-GP-UCB (Enlarged Conﬁdence GP-UCB) Input: Kernel function κ(·, ·), domain X , misspeciﬁcation ε, and parameters B, λ, σ. 1: Set µ0 (x) = 0 and σ0 (x) = κ(x, x) for all x ∈ X . 2: for t = 1 . . . T do 3: Choose √ ε t xt ∈ arg max µt−1 (x) + βt + √ σt−1 (x) . λ x∈X 4: Observe reward yt∗ = f ∗ (xt ) + ηt . 5: Update posterior mean and variance µt (·) and σt (·) 6: end for

In this work, we focus on the quantum kernel bandit problem, where the unknown mean-reward function f ∗ resides in the PT ∗ ∗ RKHS induced by a quantum kernel. Our objective is to minimize the cumulative regret RT = t=1 (f (x ) − f ∗ (xt )) where x∗ = arg maxx∈X f ∗ (x) denotes the optimal action in hindsight.

A common approach, assuming the true (quantum) kernel is given, is to apply Gaussian process (GP) based methods such as GP-UCB [Srinivas et al., 2010]; see Algorithm 2. However, the computational burden of GP inference is typically high. Speciﬁcally, at round t, updating the GP posterior naively (as in Appendix A for line 4 in the algorithm) requires O(t3 ) for an exact matrix inversion; or O(t2 ) per round if one employs Sherman-Morrison rank-1 updates. Moreover, computing the next action xt within the action set A = X requires O(t2 |A|) for posterior mean/variance queries. Summing over T rounds yields a total time of order O(T × (T 2 + T 2 |A|)) = O(T 3 + T 3 |A|). Such a cubic dependence on T becomes intractable for large-scale bandit problems. In contrast, our method considers a D-dimensional approximate feature map ϕRFF for the quantum kernel. When using SquareCB with the Vovk-Azoury-Warmuth forecaster in this D-dimensional feature space, the per-round update cost is only O(D2 ). And inference (deciding xt ) over the set A takes O(D × |A|). Consequently, the total cost across T rounds is O(T D2 + T D|A|), which grows linearly in T . Alternatively, one may run EC-GP-UCB [Bogunovic and Krause, 2021] (see Algorithm 3) using the same ϕRFF . Rather than maintaining a full GP posterior, one performs standard Bayesian linear regression in the D-dimensional space. As above, each round’s update can be done in O(D2 ) using rank-1 matrix updates (Sherman-Morrison), and the inference cost is O(D × |A|). Hence, this approach also achieves a total cost of O(T D2 + T D|A|). Thus, by replacing the exact (and computationally heavy) GP posterior inference with a D-dimensional approximation via random Fourier features (or other ﬁnite-dimensional embeddings), one obtains linear dependence on T , which is far more tractable in large-scale bandit settings.

G ABOUT P-GREEDY Algorithm 4 Construction of Newton basis with P-greedy algorithm Input: Kernel K, admissible error e > 0, a subset of points X̂ ⊆ X Output: A subset of points Xm ⊆ X̂ and Newton basis N1 , . . . , Nm of V (Xm ) 1: ξ 1 := arg maxx∈X̂ K(x, x) K(x,ξ1 ) 2: N1 (x) := √ K(ξ1 ,ξ1 )

3: for m = 1, 2, 3, . . . do 2 Pm 2 (x) := K(x, x) − 4: Pm k=1 Nk (x) 2 5: if maxx∈X̂ Pm (x) < e2 then 6: return {ξ 1 , . . . , ξ m } and {N1 , . . . , Nm } 7: end if 2 8: ξ m+1 := arg maxx∈X̂ Pm (x) P m 9: u(x) := K(x, ξ m+1 ) − k=1 Nk (ξ m+1 ) Nk (x) 10:

Nm+1 (x) := √ 2u(x)

Pm (ξm+1 )

11: end for

We provide a more detailed introduction to P-greedy methods along with some established results to facilitate discussion in Appendix I. Let X be a non-empty subset of a Euclidean space Rd , and let K : X × X → R be a symmetric, positive deﬁnite kernel deﬁned on X . For a given discretization X̂ ⊂ X and a function f ∈ HK (X ), the goal is to approximate f using the Pgreedy procedure. This method iteratively selects a small set Xn = {ξ 1 , . . . , ξ n } ⊂ X̂ of n representative points from the candidate set X̂ , which often serves as a discrete approximation of X . These points deﬁne a ﬁnite-dimensional subspace V (Xn ) that approximates the entire RKHS HK (X ).

At each iteration, P-greedy evaluates an “error surface” via the power function PV (X) (x) :=

|f (x) − (ΠV (X) f )(x)| , ∥f ∥HK (X ) f ∈HK \{0} sup

which quantiﬁes the current approximation’s looseness at each point x. The method identiﬁes the point where this error is the largest and adds it to the set X to reduce the worst-case error in subsequent iterations. Speciﬁcally, the next point is chosen as ξ m = arg max PV (Xm−1 ) (x). x∈X̂

Repeating this process for m iterations results in a set of points Xm = {ξ 1 , . . . , ξ m }. These points generate the ﬁnitedimensional subspace V (Xm ) = span{K(·, ξ 1 ), . . . , K(·, ξ m )}, which approximates HK (X ). The resulting approximation effectively yields an approximate kernel whose feature map corresponds to the Newton basis {N1 , . . . , Nm }, obtained via Gram–Schmidt orthonormalization of the basis {K(·, ξ 1 ), . . . , K(·, ξ m )}. We provide the pseudo-code for the P-greedy algorithm, adapted from Takemori and Sato [2021], in Algorithm 4. Furthermore, the following is known from Takemori and Sato [2021]. Theorem 10. Let α, q > 0 be parameters, d be the dimension of input data, and denote by D = Dq,α (T ) the number of points returned by the P-greedy algorithm with error e = α/T q . Then: (i) Suppose K has ﬁnite smoothness (e.g., Matérn kernels) with smoothness parameter ν > 0. Then Dq,α (T ) = dq d O α− ν T ν . (ii) Suppose K has inﬁnite smoothness (e.g., Gaussian kernel). Then Dq,α (T ) = O (q log T − log(α))d .

H P-GREEDY MISSPECIFICATION ERROR In this section, we provide some ways to understand and bound the misspeciﬁcation error from using the P-greedy algorithm. H.1 SETUP Let X be compact and let κ : X × X → R be continuous, symmetric, and positive deﬁnite with RKHS Hκ and norm ∥ · ∥Hκ . For each x ∈ X deﬁne the kernel section κx := κ(·, x) ∈ Hκ and the compact set F := {κx : x ∈ X } ⊂ Hκ . Given points ξ 1 , . . . , ξ D ∈ X selected by P-greedy, deﬁne the associated approximation space VD := span{κξ1 , . . . , κξD } ⊂ Hκ ,

(26)

and let ΠVD : Hκ → VD denote the Hκ -orthogonal projector. We are interested in the misspeciﬁcation between f ∗ ∈ Hκ , and best possible approximation fD ∈ VD : εD := εD (f ∗ ) := inf ∥f ∗ − fD ∥∞ , fD ∈VD

∥g∥∞ := sup |g(x)|. x∈X

H.2 BOUNDING MISSPECIFICATION ERROR BY THE KOLMOGOROV WIDTH εD is controlled by the greedy error σD (F). We ﬁrst recall DeVore et al. [2013]’s deﬁnition of greedy error for the compact set F ⊂ Hκ : σD (F) := sup inf ∥k ∗ − kD ∥Hκ . (27) k∗ ∈F kD ∈VD

Lemma 3 (Greedy error equals worst-case power function). For VD deﬁned in (26), one has σD (F) = sup ∥κx − ΠVD κx ∥Hκ . x∈X

Proof. Fix x ∈ X . Since ΠVD κx ∈ VD and ΠVD is the best approximation in Hilbert norm, inf ∥κx − fD ∥Hκ = ∥κx − ΠVD κx ∥Hκ .

fD ∈VD

Taking supf ∈F , which is equivalent to supx∈X , yields the claim. Lemma 4 (Misspeciﬁcation bounded by greedy error). For any f ∗ ∈ Hκ , εD (f ∗ ) ≤ ∥f ∗ ∥Hκ σD (F). In particular, since we assumed ∥f ∗ ∥Hκ ≤ B, we have εD (f ∗ ) ≤ B σD (F). Proof. Let fD := ΠVD f ∗ ∈ VD . Then εD (f ∗ ) ≤ ∥f ∗ − fD ∥∞ . Fix x ∈ X . By the reproducing property, (f ∗ − fD )(x) = ⟨f ∗ − fD , κx ⟩Hκ . Since ΠVD is an orthogonal projector, ⟨f ∗ − fD , ΠVD κx ⟩Hκ = 0 and therefore (f ∗ − fD )(x) = ⟨f ∗ − fD , κx − ΠVD κx ⟩Hκ . By Cauchy–Schwarz and properties of orthogonal projection, |(f ∗ − fD )(x)| ≤ ∥f ∗ − fD ∥Hκ ∥κx − ΠVD κx ∥Hκ ≤ ∥f ∗ ∥Hκ ∥κx − ΠVD κx ∥Hκ . Taking the supremum over x ∈ X and invoking Lemma 3 yields ∥f ∗ − fD ∥∞ ≤ ∥f ∗ ∥Hκ σD (F).

σ2D (F) is controlled by Kolmogorov width dD (F). Deﬁne the Kolmogorov D-width of F in Hκ : dD (F) :=

inf

sup

inf ∥k ∗ − yD ∥Hκ .

YD ⊂Hκ k∗ ∈F yD ∈YD dim(YD )=D

(28)

It measures the best possible D-dimensional approximates to the full space. We use the following result from DeVore et al. [2013], which √ asserts that P-greedy typically achieves near-optimal performance: the error σ2D using 2D points satisﬁes σ2D ≤ γ −1 2dD for some constant 0 < γ < 1: Lemma 5 (greedy error bounded by Kolmogorov width). (Corollary 3.3 of DeVore et al. [2013]) √ σ2D (F) ≤

2p dD (F), γ

(29)

for some constant γ. Combining Lemma 4 with (29) gives the key implication: √ ε2D (f ∗ ) ≤ B σ2D (F) ≤

2B p dD (F). γ

(30)

H.3 BOUNDING dD (F) FOR FINITE FOURIER-TYPE KERNELS Further assume the kernel is translation invariant and admits the ﬁnite Fourier-type expansion X ′ κ(x, x′ ) = cω ei⟨ω, x−x ⟩ , cω ≥ 0,

(31)

ω∈Ω

where Ω is ﬁnite. Let ΩD ⊂ Ω index the D largest coefﬁcients {cω }. For x ∈ X , the section function satisﬁes κ(·, x) =

cω e−i⟨ω,x⟩ ei⟨ω,·⟩ .

(32)

ω∈Ω

(A) A general upper bound

Consider the D-dimensional subspace YD := span{ei⟨ω,·⟩ : ω ∈ ΩD } ⊂ Hκ .

For each x ∈ X , deﬁne the truncation gD (·; x) ∈ YD by X gD (·; x) := cω e−i⟨ω,x⟩ ei⟨ω,·⟩ . ω∈ΩD

Then by (32), κ(·, x) − gD (·; x) =

cω e−i⟨ω,x⟩ ei⟨ω,·⟩ .

ω ∈Ω / D

Using the triangle inequality in Hκ and |e

−i⟨ω,x⟩

| = 1,

∥κ(·, x) − gD (·; x)∥Hκ ≤

cω ∥ei⟨ω,·⟩ ∥Hκ .

ω ∈Ω / D −1/2

In the ﬁnite-rank RKHS induced by (31), one has ∥ei⟨ω,·⟩ ∥Hκ = cω

(whenever cω > 0), hence X √ sup dist(κ(·, x), YD )Hκ ≤ cω .

x∈X

(33)

ω ∈Ω / D

Since dD (F) is the inﬁmum over all D-dimensional subspaces, we conclude X √ dD (F) ≤ cω .

(34)

ω ∈Ω / D

(B) An improved upper bound for integer-valued frequencies. Assume additionally that X = Td = [0, 2π]d and that √ Ω ⊂ Zd . Then the Fourier characters {ei⟨ω,·⟩ }ω∈Ω yield a Mercer decomposition, and the functions { cω ei⟨ω,·⟩ }ω∈Ω form an orthonormal family in Hκ . Consequently, the residual above is an orthogonal sum in Hκ and Pythagoras’ identity gives, for all x ∈ X , X ∥κ(·, x) − gD (·; x)∥2Hκ = cω . ω ∈Ω / D

Therefore, dD (F) ≤ sup ∥κ(·, x) − gD (·; x)∥Hκ = x∈X

Final misspeciﬁcation bounds.

1/2 cω

ω ∈Ω / D

Combining (30) with (34) yields the general bound √ 2B X √ 1/2 ∗ ε2D (f ) ≤ cω . γ ω ∈Ω / D

Under the integer-frequency assumption, combining (30) with (35) yields the sharper bound √ 1/4 2B X ε2D (f ∗ ) ≤ cω . γ ω ∈Ω / D

(35)

H.4 EXAMPLE CIRCUITS AND THEIR SPECTRAL DECAY We consider the one-dimensional periodic do-

Example: Product single-qubit rotation encoding (exponential tail). main X = T = [0, 2π] and the n-qubit feature map |ψ(x)⟩ :=

Rx (x) |0⟩

⊗n

x ∈ [0, 2π],

(36)

where Rx (θ) = exp(−iθX/2) is a single-qubit rotation about the Pauli-X axis. We deﬁne the corresponding quantum kernel as the squared state overlap 2

κ(x, x′ ) := ⟨ψ(x)|ψ(x′ )⟩ , For one qubit, ⟨0| Rx (x)† Rx (x′ ) |0⟩ = cos

x, x′ ∈ [0, 2π].

x − x′

∆

. 2 2 Taking the n-fold tensor product gives ⟨ψ(x)|ψ(x′ )⟩ = cos(∆/2)n . Squaring the modulus yields, with ∆ := x − x′ , κ(x, x′ ) = cos2n

∆ 2

= cos

(37)

(38)

Since κ(x, x′ ) depends only on ∆ = x − x′ , it is shift-invariant on T and admits a Fourier series κ(∆) =

ℓ∈Z cℓ e

iℓ∆

Moreover, the kernel (38) is a trigonometric polynomial of degree n and therefore has ﬁnite spectrum ℓ ∈ {−n, . . . , n}. Using cos(θ) = 12 (eiθ + e−iθ ), we obtain ∆ 2n cos2n = 2−2n ei∆/2 + e−i∆/2 2 2n X 2n i(n−j)∆ −2n =2 e j j=0 n X

cℓ eiℓ∆ ,

ℓ=−n

where the Fourier coefﬁcients are explicitly cℓ = 2

−2n

2n , n−ℓ

ℓ = −n, . . . , n.

(39)

In particular, cℓ ≥ 0, c−ℓ = cℓ , and the sequence is unimodal with c0 ≥ c1 ≥ · · · ≥ cn . Now, by our previous results, the (squared) Kolmogorov D-width of F is upper bounded by the spectral tail: dD (F)2 ≤

c(j) =

j>D

cℓ ,

ℓ∈Ω / D

where c(1) ≥ c(2) ≥ · · · denotes the non-increasing rearrangement and ΩD indexes the top-D coefﬁcients. Note the top coefﬁcients correspond to the lowest frequencies. In particular, for any integer k ∈ {0, 1, . . . , n}, choosing Ω2k+1 := {−k, −k + 1, . . . , 0, . . . , k} gives

d2k+1 (F)2 ≤

cℓ = 2

|ℓ|≥k+1

Now to bound (40), let S ∼ Bin(2n, 21 ). Then, from (39), cℓ = P(S = n − ℓ).

n X ℓ=k+1

cℓ .

(40)

Hence 2

n X

cℓ = 2 P(S ≤ n − k − 1) = 2 P(S − n ≤ −(k + 1)) ≤ 2 P(|S − n| ≥ k + 1).

ℓ=k+1

Applying Hoeffding’s inequality to the binomial variable S yields (k + 1)2 P(|S − n| ≥ k + 1) ≤ 2 exp − , n and substituting into (40) gives the explicit tail bound (k + 1)2 d2k+1 (F)2 ≤ 4 exp − , n

k = 0, 1, . . . , n − 1.

Equivalently, for any D ∈ {1, 2, . . . , 2n + 1}, letting k = ⌊(D − 1)/2⌋, (⌊(D − 1)/2⌋ + 1)2 D2 dD (F)2 ≤ 4 exp − ≤ 4 exp − . n 16n

(41)

Gaussian frequency proﬁles in quantum re-uploading models and sub-Gaussian spectral tails. Barthe and PérezSalinas [2024] study quantum re-uploading models, i.e., parametrized quantum circuits in which data-encoding unitaries are repeatedly interleaved with trainable gates. They prove that such models output functions with vanishing high-frequency components and, in particular, derive uniform upper bounds on derivatives with respect to the input data (hence limiting sensitivity to ﬁne-scale variations). Moreover, their numerical experiments indicate that when the data-uploading gates are interleaved with random trainable gates, the Fourier transform of quantum re-uploading models exhibits Gaussian proﬁles. P For a kernel with Fourier expansion κ(∆) = ℓ∈Z cℓ eiℓ∆ , if its Fourier weights satisfy a Gaussian (sub-Gaussian) decay cℓ ≤ C0 exp(−aℓ2 ),

∀ ℓ ∈ Z,

for some constants C0 , a > 0. Since the largest coefﬁcients correspond to the lowest frequencies, choosing Ω2k+1 = {−k, . . . , k} gives Z ∞ ∞ X X 2 2 C0 −ak2 e d2k+1 (F)2 ≤ cℓ ≤ 2C0 e−aℓ ≤ 2C0 , e−at dt ≤ ak k |ℓ|≥k+1

ℓ=k+1

where the last inequality uses the standard Gaussian tail bound. Equivalently, for D = 2k + 1 and k = ⌊(D − 1)/2⌋, a C1 dD (F)2 ≤ exp − (D − 1)2 , (42) D 4 for some constant C1 > 0 depending only on (C0 , a). Thus, a Gaussian-shaped frequency proﬁle implies an exponential decay of the spectral tail, and hence of the Kolmogorov width.

I EXTENSION TO THE CASE WHERE THE REWARD FUNCTION LIES IN AN RKHS OF CLASSICAL KERNELS Although we initially presented our approach in the quantum context, it applies equally well to classical kernels, whether they induce ﬁnite- or inﬁnite-dimensional RKHS. In particular, the same analysis used for Random Fourier Features carries over to the classical setting. Moreover, for certain inﬁnite-dimensional kernels, the P-greedy algorithm admits a rapidly decaying error bound—often polynomial or even exponential in the number of selected points—according to Theorem 10. Consequently, in a bandit optimization scenario over a ﬁnite discretized domain, one can directly integrate P-greedy approximations into methods such as EC-GP-UCB [Bogunovic and Krause, 2021] or standard misspeciﬁed linear bandit algorithms. By substituting the resulting ε-term (representing the approximation error), it is possible to derive improved regret guarantees alongside reduced computational overhead.

EXPERIMENTAL DETAILS

We provide more details about the experiments in Section 4.

Figure 8: Example Circuit Structure for generating κQ , where xi are the input data components and αi are randomly sampled parameters for the variational layers

J.1

EXPERIMENT 1

• Quantum Circuit Construction. We generate the synthetic reward function f ∗ using a three-qubit parameterized quantum circuit composed of random layers of rotation gates and entangling operations, implemented via PennyLane. This results in a ﬁnal circuit whose output density matrix deﬁnes our global ﬁdelity quantum kernel κQ (·, ·). The structure of the parameterized quantum circuit that deﬁnes the kernel κQ (for this experiment) is depicted in Figure 8. The architecture begins with a data-encoding layer, by letting each component of the input vector x parameterizes a Pauli-X rotation gate acting on a corresponding qubit. In the notation of Eq. (4), this corresponds to Gj = Xj for the dataencoding layer. Subsequently, the state is evolved through randomly structured layers of rotation and entangling gates, constructed using PennyLane’s RandomLayers template. For a given input x, the resulting n-qubit state is described by the density matrix ρ(x). The kernel is then deﬁned as the Hilbert-Schmidt inner product between two states, κQ (x, x′ ) = Tr[ρ(x)ρ(x′ )], which quantiﬁes their ﬁdelity. • Action Space and Noise. We discretize the input domain [0, 2π]3 on a 10 × 10 × 10 uniform grid, yielding 1000 possible arms (actions). At each round t, upon selecting an arm xt , we observe a noisy reward yt = f ∗ (xt ) + ηt ,

ηt ∼ N (0, 0.12 ).

The observed values are then normalized to [0, 1] across the entire grid. • Algorithms and Hyperparameters. We compare three kernel-approximation strategies—projected quantum kernels, random Fourier features (RFF), and P-greedy—in combination with two bandit algorithms, SquareCB [Foster and Rakhlin, 2020] and EC-GP-UCB [Bogunovic and Krause, 2021]. We use their standard parameter settings from the respective papers, initializing the algorithms at round 1 (no special warm-up phase). • Projected Kernel Details. Given our three-qubit circuit, we construct projected kernels by tracing out subsets of qubits. Speciﬁcally, we consider individual-qubit projections onto qubits {0}, {1}, {2} as well as pairs {0, 1}, {1, 2}, {0, 2}. To create a summed projected kernel of size b, we sum the local projected kernels over b disjoint sub-systems. For instance, having “Number of Projected Kernels Summed” = 3 in the plot means summing the projected kernels on qubits 0, 1, and 2. • Random Fourier Features. For RFF, we sample frequencies uniformly at random from the kernel’s Fourier frequencies. We vary the RFF dimension D, as reported on the horizontal axis of Figures 3(b) and 4(b). • P-greedy. For the P-greedy approach, we greedily select basis points from the same 10 × 10 × 10 grid according to the power function criterion [Marchi et al., 2005], incrementally building a subspace that approximates κQ . • Trials and Metrics. Each algorithm is run for T = 100 bandit rounds. We repeat the entire procedure 30 times with different random seeds. The plotted curves show the mean cumulative regret, with shaded regions or error bars indicating ±1 standard deviation across trials. “Model complexity” on the horizontal axis is the number of summed local kernels for projected quantum kernels, the RFF dimension D for random Fourier features, or the number of basis points (kernel dimension) in P-greedy. The rightmost point in each plot always corresponds to the “Full kernel”, using the unprojected 3-qubit ﬁdelity kernel.

J.2

EXPERIMENT 2

• Parameter Range and Actions. We consider two coupling parameters (J1 , J2 ), each discretized into 20 equally spaced points over [−4, 4]. This yields 20 × 20 = 400 total arms in the bandit problem. At each round t, we select an arm J1 , J2 ∈ [−4, 4]2 and receive a reward corresponding to whether the system’s ground state lies in phase II. • Ground-State Computation. The generalized cluster Hamiltonian for n qubits is given by HC =

n X

Zj − J1 Xj Xj+1 − J2 Xj−1 Zj Xj+1 ,

j=1

where Xj and Zj denote Pauli operators on qubit j. We exactly compute its ground state (i.e., the eigenvector corresponding to the lowest eigenvalue) via sparse matrix diagonalization. • Phase Labeling and Noise. To label each (J1 , J2 ) as “phase II” or “not phase II”, we use the known boundary conditions: phase II if J2 > −1 − J1 and J2 < J1 − 1 . Hence, if (J1 , J2 ) is inside that region, the “ideal” label is 1; otherwise, it is 0. We then add i.i.d. Gaussian noise of variance σ 2 = 0.01, so the observed reward is y = I{phase II} + η,

η ∼ N (0, 0.01).

• Regret Deﬁnition. For each chosen (J1 , J2 ), the instantaneous regret is 1 if that point is outside phase II (i.e., the ideal label is 0), and 0 if it is inside phase II. Thus, the cumulative regret over T rounds equals the total number of times we pick a point out of phase II in hindsight. • Kernel Approximations and Algorithm Setup. We implement a three-qubit parameterized circuit (different from that of Experiment 1) with multiple layers of single-qubit rotations and entangling gates on the ground state of HC as the initial state, yielding a ﬁdelity kernel κQ . We then apply projected kernel and P-greedy with EC-GP-UCB [Bogunovic and Krause, 2021]. We run the algorithm for T = 100 rounds, record the cumulative regret, and then average over 30 runs. The standard deviation across these runs is shown as error bars in our plots. J.3

EXPERIMENT 3

• Hamiltonian Setup. Speciﬁcally, we aim to approximate the ground state of the XYZ Hamiltonian, i.e., JX = −1, JY = JZ = 0, and hX = hY = 0, hZ = −1 in H=−

n−1 X

(JX Xj Xj+1 + JY Yj Yj+1 + JZ Zj Zj+1 ) −

j=1

n X

(hX Xj + hY Yj + hZ Zj )

j=1

where Xj , Yj , Zj are Pauli matrices acting on the jth qubit. We ﬁx n = 3 qubits for all experiments. • Circuit Ansatz and Initial State. Following Nicoli et al. [2023], we employ an “Efﬁcient SU(2)” circuit with PennyLane ⊗3 as a parameterized ansatz U(x). The initial state |ψ0 ⟩ is set to |0⟩ . The circuit outputs f ∗ (x) = ⟨ψ0 | U(x)† H U(x) |ψ0 ⟩ exactly without measurement noise. • Bayesian Optimization Details. We deﬁne a Gaussian Process (GP) model with the ﬁdelity kernel derived from the same 3-qubit circuit architecture, then apply Bayesian optimization using the Expected Improvement (EI) acquisition function. The EI is optimized by L-BFGS at each iteration to propose new circuit parameters. We run 50 optimization steps, repeating the procedure for 30 independent random seeds that affect parameter initialization, random draws in the approximate kernels, etc. • Metrics and Plots. The optimization runs for 50 steps, we record and plot the best (lowest) energy found so far. The error bars (or shaded regions) depict ±1 standard deviation across 30 trials.

900

900 Regret, T = 1000 ±1σ

550

Regret

700 600

Regret, T = 1000 ±1σ

600

500 450

Regret, T = 1000 ±1σ

800

Regret

800

700 600

500 500

400 400

400

350 0

100

200

300

400

500

600

Number of Projected Kernels Summed

Dimension of Approximate Kernel

(a) Projected Quantum Kernels

(b) Random Fourier Features

700

100

200

300

400

500

600

700

Dimension of Approximate Kernel

Figure 9: Cumulative regret of SquareCB algorithm as a function of approximation dimension D for (a) projected quantum kernels, (b) RFF and (c) P-greedy approximation. 1000 Regret, T = 1000 ±1σ

600

Regret

700

500

900 Regret, T = 1000 ±1σ

800 600 400

700 600 500 400

400

300

200

300

Regret, T = 1000 ±1σ

800

Regret

800

200 200 0

100

200

300

400

500

600

Number of Projected Kernels Summed

Dimension of Approximate Kernel

(a) Projected Quantum Kernels

(b) Random Fourier Features

700

100

200

300

400

500

600

700

Dimension of Approximate Kernel

Figure 10: EC-GP-UCB with different kernel approximation approaches for reward functions drawn from GPs with the full quantum kernel

K BIGGER QUBIT SYSTEM FOR EXPERIMENT 1 This section provides additional results to illustrate scalability beyond the 3-qubit setting in Section 4.1. Following exactly the same protocol as Experiment 1 (same reward-generation mechanism, noise model, and evaluation procedure, though we increase T to 1000 here), we increase the number of qubits from 3 to 6, speciﬁcally, we consider a synthetic reward function f ∗ drawn from a GP prior induced by the full 6-qubit product kernel on the domain [0, 2π]6 . We then run the same bandit pipelines (SquareCB and EC-GP-UCB) with the same three kernel-approximation strategies: projected quantum kernels, random Fourier features (RFF), and P-greedy. Figures 9 and 10 mirror Figures 3 and 4 in the main text, each curve reports cumulative regret as a function of the approximation dimension (number of summed projected kernels for LPQK; feature dimension D for RFF; or the number of selected basis elements for P-greedy). As in the 3-qubit experiments, we observe the characteristic “U-shaped” behavior: small approximation dimension underﬁts the true function (high misspeciﬁcation error), while overly large dimension increases the information-gain penalty and can degrade regret. Overall, these results conﬁrm that the qualitative trade-off identiﬁed in Section 4.1 persists at higher qubit counts, supporting the scalability of our approximation framework to larger quantum systems.

L LIMITATIONS AND FUTURE DIRECTIONS • Conservativeness of Regret Bounds. Our theoretical regret bounds provide upper estimates that may be overly conservative in practice. Consequently, using these bounds to select an optimal kernel dimension D might lead to suboptimal or unnecessarily large choices. • Approximation Error Uncertainty. Although Random Fourier Features (RFF) typically yield an error rate of ε = √ 1/ D, this estimate can be pessimistic in many real-world scenarios. Faster decay rates—such as polynomial or exponential—are achievable but generally require problem-speciﬁc analysis. Additionally, for projected kernels and P-greedy methods, there is no universal closed-form bound for ε; each case necessitates empirical evaluation or tailored theoretical analysis.

• Limitations of Fourier Series Representations. Our RFF analysis relies on the assumption that the quantum kernel admits a discrete or tractable Fourier expansion. However, some kernels may lack such a structure, making our current approach inapplicable without signiﬁcant modiﬁcations. • Noise Model and Kernel Estimation. We model the observed reward noise as i.i.d. Gaussian, which is a standard approximation to ﬁnite-shot measurement noise in the large-shot regime. This abstraction does not capture structured NISQ noise, such as readout errors, depolarizing noise, relaxation, drift, or cross-talk. Moreover, our approximationerror analysis assumes exact kernel values; ﬁnite-shot kernel estimation and device noise would introduce additional errors that may interact with the kernel approximation error. • Quantum Measurement Overhead. The computational speedups discussed in Appendix F concern classical posterior updates and linear-algebra costs. If kernel values are estimated on quantum hardware, the total measurement cost can still be signiﬁcant. Full GP-UCB requires at least O(T 2 ) pairwise kernel evaluations over T selected points, while a ﬁxed D-dimensional approximation requires O(T D) feature or basis evaluations after the surrogate is ﬁxed. These counts must be multiplied by the number of shots required per kernel or observable estimate. For LPQK, a direct tomography Pb n w 3 based implementation over all subsystems |s| ≤ b may additionally require local Pauli measurements over w=0 w settings. A full measurement-aware regret and runtime analysis is left for future work. • Generality Beyond Quantum Kernels. The misspeciﬁed-bandit framework applies to general classical kernels as well as quantum kernels.

Record · ID 329086 · SHA-256 25006eacda0ee67f
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.