Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization
For researchers in quantum machine learning and NISQ-era applications, this work provides a practical method to make quantum kernel bandit optimization scalable and efficient, addressing a key bottleneck in quantum-native optimization tasks.
The paper addresses the challenge of balancing expressivity and learnability in Gaussian process bandit optimization with quantum kernels, where full high-dimensional kernels lead to high regret and poor learnability. They propose projected quantum kernels and classical approximations, achieving better sample efficiency and lower computational overhead while providing regret bounds that guide model complexity selection.
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 NISQ-era tasks such as quantum control, state preparation and variational quantum algorithms. While quantum kernels can offer a `quantum advantage' via domain-specific 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 misspecified 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 efficiency, while substantially reducing computational overhead, enabling scalable GP optimization for quantum-native applications.