Technical Summary: Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization

1. Problem Statement

This work addresses the challenge of Gaussian Process (GP) bandit optimization where the unknown mean reward function $f^*$ lies in the Reproducing Kernel Hilbert Space (RKHS) induced by a quantum kernel $\kappa_Q$. This setting is motivated by Noisy Intermediate-Scale Quantum (NISQ) era tasks such as quantum control, state preparation, and the optimization of variational quantum algorithms (VQAs).

In this framework, a learner sequentially selects actions $x_t$ and observes noisy rewards $y_t = f^*(x_t) + \eta_t$. The goal is to minimize cumulative regret $R_T$. While quantum kernels offer domain-specific inductive biases that can theoretically outperform classical kernels (e.g., RBF), the authors identify two fundamental barriers to their practical application in bandit settings:

1. Exponential Information Gain: For an $n$-qubit system, the maximum information gain $\gamma_T$ scales as $O(4^n \log T)$. This exponential scaling leads to prohibitively high cumulative regret and hinders the learnability of the model.
2. Kernel Concentration: As $n$ increases, kernel values for different data pairs concentrate exponentially around a fixed value, requiring an exponential number of quantum measurements for accurate estimation.

The paper argues that naively using full, high-dimensional quantum kernels results in poor sample efficiency and computational intractability, necessitating a trade-off between model expressivity and learnability.

2. Methodology

To address these challenges, the authors propose a framework of approximate GP bandit algorithms that utilize lower-dimensional surrogate models. These models approximate the full quantum RKHS using either reduced quantum subspaces or classical approximations, thereby reducing the information gain at the cost of introducing kernel misspecification.

The core methodology involves three specific approximation techniques:

A. Linear Projected Quantum Kernels (LPQKs)

This approach projects the global $n$-qubit quantum state onto reduced subsystems of size $b < n$.

• Mechanism: The global fidelity kernel is approximated by summing local fidelity kernels over subsystems $s$ where $|s| \leq b$. The resulting kernel $\kappa_{S_b}$ operates on a Hilbert space of dimension $2^{|s|} \times 2^{|s|}$, significantly smaller than the full $4^n$ dimension.
• Algorithm: The authors employ the EC-GP-UCB algorithm (Enlarged Confidence GP-UCB) designed for misspecified bandits. The regret bound explicitly balances the reduced information gain $\gamma_T$ (scaling with the number of Pauli-weight components up to $b$) against the misspecification error $\epsilon_b$.

B. Random Fourier Features (RFF)

This is a fully classical approximation method leveraging the Fourier representation of shift-invariant quantum kernels.

• Mechanism: Using Bochner's theorem, the quantum kernel is approximated by a finite-dimensional feature map $\phi_{RFF}$ of dimension $D$. The problem is reformulated as a misspecified linear bandit.
• Algorithm: The SquareCB algorithm is used, which achieves regret bounds dependent on the feature dimension $D$ and the misspecification error $\epsilon_D$. The authors derive a theoretical prescription for selecting $D \approx \sqrt{T}$ to minimize the regret bound.

C. P-Greedy Kernel Approximation

This method constructs a low-dimensional subspace via data-dependent subset selection.

• Mechanism: The algorithm iteratively selects points that maximize the "power function," identifying where the current subspace approximates the RKHS worst. This generates a Newton basis for a low-rank approximation of the kernel.
• Algorithm: Similar to RFF, this reduces the problem to a linear bandit setting where the misspecification error is governed by the spectral decay (Kolmogorov width) of the target kernel.

3. Key Contributions

Theoretical Contributions

• Quantum-Specific Learnability Barrier: The paper identifies the exponential scaling of maximum information gain with qubit count $n$ as a fundamental statistical barrier for GP bandits with fidelity quantum kernels.
• Regret Bounds for Misspecified Quantum Bandits: The authors derive regret bounds that characterize the trade-off between approximation error (misspecification) and information gain. They demonstrate that in regimes where the full kernel is excessively high-dimensional, a suitably chosen approximate kernel achieves strictly lower regret than the full model.
• Structural Analysis: The analysis connects circuit structure (e.g., Pauli-weight projections, generator eigenvalue gaps) directly to the information-gain/misspecification trade-off. For instance, LPQKs correspond to Pauli-weight projections, and the error bounds depend on the decay of high-weight Pauli components in the target observable.

Algorithmic and Practical Contributions

• Computational Efficiency: The proposed methods reduce time complexity from $O(T^3)$ (required for full GP inference) to $O(TD^2 + D^3)$ or $O(TD^2 + TD|A|)$, where $D \ll T$ is the approximation dimension. This enables scalable optimization for quantum-native applications.
• Dimension Selection Guidelines: The theoretical bounds provide principled guidance for selecting optimal model complexity (e.g., the number of qubits to trace out in LPQKs or the number of random features $D$ in RFF).

4. Experimental Results

The authors validate their approach on synthetic and real quantum tasks:

1. Synthetic Quantum Functions: Using a 3-qubit (and extended to 6-qubit) quantum kernel, the experiments demonstrate a characteristic "U-shaped" regret curve as a function of model complexity.

   • Low complexity leads to underfitting (high misspecification error).
   • High complexity leads to overfitting (high information gain penalty).
   • The proposed approximate kernels (LPQK, RFF, P-greedy) consistently outperform the full quantum kernel in sample efficiency when the dimension is tuned according to theoretical predictions.

2. Quantum Phase Classification: In a task to identify parameters corresponding to a ferromagnetic phase in a generalized cluster Hamiltonian, the approximate kernels significantly outperformed the full kernel, suggesting that lower-dimensional kernels suffice to distinguish phases without the penalty of full-kernel information gain.

3. Variational Quantum Eigensolver (VQE): In a Bayesian optimization task for finding the ground state of an XYZ Heisenberg Hamiltonian, simpler approximations achieved faster convergence to the minimum energy compared to the full kernel, which was deemed excessively complex for the task.

5. Significance and Claims

The paper claims that its primary significance lies in bridging the gap between the theoretical potential of quantum kernels and their practical limitations in NISQ-era optimization. By formalizing the trade-off between expressivity (captured by the full quantum RKHS) and learnability (constrained by information gain and computational cost), the authors provide a framework for scalable GP optimization.

The work asserts that:

• Full quantum kernels are often suboptimal for bandit tasks due to the "curse of dimensionality" in information gain.
• Approximate quantum kernels, when properly tuned, can achieve near-optimal performance with substantially reduced computational overhead and sample complexity.
• The theoretical insights into approximation error can guide the selection of model dimensions in practice, yielding performance that often surpasses the "ground truth" full-kernel approach in terms of cumulative regret.

The authors remain modest, noting that their regret bounds may be conservative and that the analysis assumes idealized noise models (i.i.d. Gaussian), whereas real NISQ devices exhibit structured noise. Furthermore, the RFF approach relies on the existence of a tractable Fourier expansion, which may not hold for all quantum circuits.