Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization

Abstract

We investigate Gaussian Process (GP) bandit optimization utilizing quantum kernels. While quantum kernels enable embedding data into high-dimensional Hilbert spaces—potentially offering enhanced expressivity or a "quantum advantage"—this property can pose challenges in bandit learning. Specifically, employing full quantum kernels naïvely may lead to increased model complexity and, consequently, higher cumulative regret impacting the learnability. To address this, we explore the use of projected quantum kernels and classical kernel approximation techniques, which effectively reduce feature dimensionality while preserving essential quantum properties. We demonstrate that these approaches can yield improved regret bounds by strategically balancing approximation error and information gain. Empirical results show that they significantly outperform models based on full quantum kernels in bandit optimization tasks. Additionally, we analyze how to select the optimal model complexity to achieve a favorable trade-off between expressivity and learnability. Our methods also substantially reduce computational costs by simplifying kernel-based inference to linear models, since only a finite set of reduced features is required.