Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.01080

Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization

Y Huang, Vincent Y. F. Tan, Sharu Theresa Jose

Published Jul 1, 2026• 0 citations
arXivHTMLPDF

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 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.

DOI
10.48550/arxiv.2607.01080

Related papers

Quantum Bayesian Optimization

Zhongxiang Dai, Gregory Kang Ruey Lau, Arun Verma +3 more

Kernelized bandits, also known as Bayesian optimization (BO), has been a prevalent method for optimizing complicated black-box reward functions. Various BO algorithms have been theoretically shown to enjoy upper bounds on their cumulative regret which are sub-linear in the number T of iterations, and a regret lower bound of Omega(sqrt(T)) has been derived which represents the unavoidable regrets for any classical BO algorithm. Recent works on quantum bandits have shown that with the aid of quantum computing, it is possible to achieve tighter regret upper bounds better than their corresponding classical lower bounds. However, these works are restricted to either multi-armed or linear bandits, and are hence not able to solve sophisticated real-world problems with non-linear reward functions. To this end, we introduce the quantum-Gaussian process-upper confidence bound (Q-GP-UCB) algorithm. To the best of our knowledge, our Q-GP-UCB is the first BO algorithm able to achieve a regret upper bound of O(polylog T), which is significantly smaller than its regret lower bound of Omega(sqrt(T)) in the classical setting. Moreover, thanks to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear kernel achieves a smaller regret than the quantum linear UCB algorithm from the previous work. We use simulations, as well as an experiment using a real quantum computer, to verify that the theoretical quantum speedup achieved by our Q-GP-UCB is also potentially relevant in practice.

arXiv:2310.05373•neural information processing systems•Jan 1, 2023•6 citations

Benchmarking of quantum fidelity kernels for Gaussian process regression

Xuyang Guo, Jun Feng Dai, Roman V. Krems

Abstract Quantum computing algorithms have been shown to produce performant quantum kernels for machine-learning classification problems. Here, we examine the performance of quantum kernels for regression problems of practical interest. For an unbiased benchmarking of quantum kernels, it is necessary to construct the most optimal functional form of the classical kernels and the most optimal quantum kernels for each given data set. We develop an algorithm that uses an analog of the Bayesian information criterion to optimize the sequence of quantum gates used to estimate quantum kernels for Gaussian process models. The algorithm increases the complexity of the quantum circuits incrementally, while improving the performance of the resulting kernels, and is shown to yield much higher model accuracy with fewer quantum gates than a fixed quantum circuit ansatz. We demonstrate that quantum kernels thus obtained can be used to build accurate models of global potential energy surfaces (PES) for polyatomic molecules. The average interpolation error of the six-dimensional PES obtained with a random distribution of 2000 energy points is 16 cm−1 for H3O+, 15 cm−1 for H2CO and 88 cm−1 for HNO2. We show that a compositional optimization of classical kernels for Gaussian process regression converges to the same errors. This indicates that quantum kernels can achieve the same, though not better, expressivity as classical kernels for regression problems.

arXiv:2407.15961•Machine Learning Science and Technology•Sep 1, 2024•1 citation

Deep Quantum Neural Networks are Gaussian Process

Rad, Ali

The overparameterization of variational quantum circuits, as a model of Quantum Neural Networks (QNN), not only improves their trainability but also serves as a method for evaluating the property of a given ansatz by investigating their kernel behavior in this regime. In this study, we shift our perspective from the traditional viewpoint of training in parameter space into function space by employing the Bayesian inference in the Reproducing Kernel Hilbert Space (RKHS). We observe the influence of initializing parameters using random Haar distribution results in the QNN behaving similarly to a Gaussian Process (QNN-GP) at wide width or, empirically, at a deep depth. This outcome aligns with the behaviors observed in classical neural networks under similar circumstances with Gaussian initialization. Moreover, we present a framework to examine the impact of finite width in the closed-form relationship using a $ 1/d$ expansion, where $d$ represents the dimension of the circuit's Hilbert space. The deviation from Gaussian output can be monitored by introducing new quantum meta-kernels. Furthermore, we elucidate the relationship between GP and its parameter space equivalent, characterized by the Quantum Neural Tangent Kernels (QNTK). This study offers a systematic way to study QNN behavior in over- and under-parameterized scenarios, based on the perturbation method, and addresses the limitations of tracking the gradient descent methods for higher-order corrections like dQNTK and ddQNTK. Additionally, this probabilistic viewpoint lends itself naturally to accommodating noise within our model.

arXiv:2305.12664•May 22, 2023•2 citations

The Inductive Bias of Quantum Kernels

Jonas M. Kübler, Simon Buchholz, Bernhard Schölkopf

It has been hypothesized that quantum computers may lend themselves well to applications in machine learning. In the present work, we analyze function classes defined via quantum kernels. Quantum computers offer the possibility to efficiently compute inner products of exponentially large density operators that are classically hard to compute. However, having an exponentially large feature space renders the problem of generalization hard. Furthermore, being able to evaluate inner products in high dimensional spaces efficiently by itself does not guarantee a quantum advantage, as already classically tractable kernels can correspond to high- or infinite-dimensional reproducing kernel Hilbert spaces (RKHS). We analyze the spectral properties of quantum kernels and find that we can expect an advantage if their RKHS is low dimensional and contains functions that are hard to compute classically. If the target function is known to lie in this class, this implies a quantum advantage, as the quantum computer can encode this inductive bias, whereas there is no classically efficient way to constrain the function class in the same way. However, we show that finding suitable quantum kernels is not easy because the kernel evaluation might require exponentially many measurements. In conclusion, our message is a somewhat sobering one: we conjecture that quantum machine learning models can offer speed-ups only if we manage to encode knowledge about the problem at hand into quantum circuits, while encoding the same bias into a classical model would be hard. These situations may plausibly occur when learning on data generated by a quantum process, however, they appear to be harder to come by for classical datasets.

arXiv:2106.03747•Jun 7, 2021•42 citations

Introducing the kernel descent optimizer for variational quantum algorithms

Lars Simon, Holger Eble, Manuel Radons

In recent years, variational quantum algorithms have garnered significant attention as a candidate approach for near-term quantum advantage using noisy intermediate-scale quantum (NISQ) devices. In this article we introduce kernel descent, a novel algorithm for minimizing the functions underlying variational quantum algorithms. We compare kernel descent to existing methods and carry out extensive experiments to demonstrate its effectiveness. In particular, we showcase scenarios in which kernel descent outperforms gradient descent and quantum analytic descent. The algorithm follows the well-established scheme of iteratively computing classical local approximations to the objective function and subsequently executing several classical optimization steps with respect to the former. Kernel descent sets itself apart with its employment of reproducing kernel Hilbert space techniques in the construction of the local approximations, which leads to the observed advantages.

arXiv:2409.10257•Scientific Reports•Aug 2, 2025•0 citations

Variational Quantum Kernels with Task-Specific Quantum Metric Learning

Daniel T. Chang

Quantum kernel methods, i.e., kernel methods with quantum kernels, offer distinct advantages as a hybrid quantum-classical approach to quantum machine learning (QML), including applicability to Noisy Intermediate-Scale Quantum (NISQ) devices and usage for solving all types of machine learning problems. Kernel methods rely on the notion of similarity between points in a higher (possibly infinite) dimensional feature space. For machine learning, the notion of similarity assumes that points close in the feature space should be close in the machine learning task space. In this paper, we discuss the use of variational quantum kernels with task-specific quantum metric learning to generate optimal quantum embeddings (a.k.a. quantum feature encodings) that are specific to machine learning tasks. Such task-specific optimal quantum embeddings, implicitly supporting feature selection, are valuable not only to quantum kernel methods in improving the latter's performance, but they can also be valuable to non-kernel QML methods based on parameterized quantum circuits (PQCs) as pretrained embeddings and for transfer learning. This further demonstrates the quantum utility, and quantum advantage (with classically-intractable quantum embeddings), of quantum kernel methods.

arXiv:2211.05225•Nov 8, 2022•0 citations
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.
Kernelized bandits, also known as Bayesian optimization (BO), has been a prevalent method for optimizing complicated black-box reward functions. Various BO algorithms have been theoretically shown to enjoy upper bounds on their cumulative regret which are sub-linear in the number T of iterations, and a regret lower bound of Omega(sqrt(T)) has been derived which represents the unavoidable regrets for any classical BO algorithm. Recent works on quantum bandits have shown that with the aid of quantum computing, it is possible to achieve tighter regret upper bounds better than their corresponding classical lower bounds. However, these works are restricted to either multi-armed or linear bandits, and are hence not able to solve sophisticated real-world problems with non-linear reward functions. To this end, we introduce the quantum-Gaussian process-upper confidence bound (Q-GP-UCB) algorithm. To the best of our knowledge, our Q-GP-UCB is the first BO algorithm able to achieve a regret upper bound of O(polylog T), which is significantly smaller than its regret lower bound of Omega(sqrt(T)) in the classical setting. Moreover, thanks to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear kernel achieves a smaller regret than the quantum linear UCB algorithm from the previous work. We use simulations, as well as an experiment using a real quantum computer, to verify that the theoretical quantum speedup achieved by our Q-GP-UCB is also potentially relevant in practice.
Abstract Quantum computing algorithms have been shown to produce performant quantum kernels for machine-learning classification problems. Here, we examine the performance of quantum kernels for regression problems of practical interest. For an unbiased benchmarking of quantum kernels, it is necessary to construct the most optimal functional form of the classical kernels and the most optimal quantum kernels for each given data set. We develop an algorithm that uses an analog of the Bayesian information criterion to optimize the sequence of quantum gates used to estimate quantum kernels for Gaussian process models. The algorithm increases the complexity of the quantum circuits incrementally, while improving the performance of the resulting kernels, and is shown to yield much higher model accuracy with fewer quantum gates than a fixed quantum circuit ansatz. We demonstrate that quantum kernels thus obtained can be used to build accurate models of global potential energy surfaces (PES) for polyatomic molecules. The average interpolation error of the six-dimensional PES obtained with a random distribution of 2000 energy points is 16 cm−1 for H3O+, 15 cm−1 for H2CO and 88 cm−1 for HNO2. We show that a compositional optimization of classical kernels for Gaussian process regression converges to the same errors. This indicates that quantum kernels can achieve the same, though not better, expressivity as classical kernels for regression problems.
The overparameterization of variational quantum circuits, as a model of Quantum Neural Networks (QNN), not only improves their trainability but also serves as a method for evaluating the property of a given ansatz by investigating their kernel behavior in this regime. In this study, we shift our perspective from the traditional viewpoint of training in parameter space into function space by employing the Bayesian inference in the Reproducing Kernel Hilbert Space (RKHS). We observe the influence of initializing parameters using random Haar distribution results in the QNN behaving similarly to a Gaussian Process (QNN-GP) at wide width or, empirically, at a deep depth. This outcome aligns with the behaviors observed in classical neural networks under similar circumstances with Gaussian initialization. Moreover, we present a framework to examine the impact of finite width in the closed-form relationship using a $ 1/d$ expansion, where ddd represents the dimension of the circuit's Hilbert space. The deviation from Gaussian output can be monitored by introducing new quantum meta-kernels. Furthermore, we elucidate the relationship between GP and its parameter space equivalent, characterized by the Quantum Neural Tangent Kernels (QNTK). This study offers a systematic way to study QNN behavior in over- and under-parameterized scenarios, based on the perturbation method, and addresses the limitations of tracking the gradient descent methods for higher-order corrections like dQNTK and ddQNTK. Additionally, this probabilistic viewpoint lends itself naturally to accommodating noise within our model.
It has been hypothesized that quantum computers may lend themselves well to applications in machine learning. In the present work, we analyze function classes defined via quantum kernels. Quantum computers offer the possibility to efficiently compute inner products of exponentially large density operators that are classically hard to compute. However, having an exponentially large feature space renders the problem of generalization hard. Furthermore, being able to evaluate inner products in high dimensional spaces efficiently by itself does not guarantee a quantum advantage, as already classically tractable kernels can correspond to high- or infinite-dimensional reproducing kernel Hilbert spaces (RKHS). We analyze the spectral properties of quantum kernels and find that we can expect an advantage if their RKHS is low dimensional and contains functions that are hard to compute classically. If the target function is known to lie in this class, this implies a quantum advantage, as the quantum computer can encode this inductive bias, whereas there is no classically efficient way to constrain the function class in the same way. However, we show that finding suitable quantum kernels is not easy because the kernel evaluation might require exponentially many measurements. In conclusion, our message is a somewhat sobering one: we conjecture that quantum machine learning models can offer speed-ups only if we manage to encode knowledge about the problem at hand into quantum circuits, while encoding the same bias into a classical model would be hard. These situations may plausibly occur when learning on data generated by a quantum process, however, they appear to be harder to come by for classical datasets.
In recent years, variational quantum algorithms have garnered significant attention as a candidate approach for near-term quantum advantage using noisy intermediate-scale quantum (NISQ) devices. In this article we introduce kernel descent, a novel algorithm for minimizing the functions underlying variational quantum algorithms. We compare kernel descent to existing methods and carry out extensive experiments to demonstrate its effectiveness. In particular, we showcase scenarios in which kernel descent outperforms gradient descent and quantum analytic descent. The algorithm follows the well-established scheme of iteratively computing classical local approximations to the objective function and subsequently executing several classical optimization steps with respect to the former. Kernel descent sets itself apart with its employment of reproducing kernel Hilbert space techniques in the construction of the local approximations, which leads to the observed advantages.
Quantum kernel methods, i.e., kernel methods with quantum kernels, offer distinct advantages as a hybrid quantum-classical approach to quantum machine learning (QML), including applicability to Noisy Intermediate-Scale Quantum (NISQ) devices and usage for solving all types of machine learning problems. Kernel methods rely on the notion of similarity between points in a higher (possibly infinite) dimensional feature space. For machine learning, the notion of similarity assumes that points close in the feature space should be close in the machine learning task space. In this paper, we discuss the use of variational quantum kernels with task-specific quantum metric learning to generate optimal quantum embeddings (a.k.a. quantum feature encodings) that are specific to machine learning tasks. Such task-specific optimal quantum embeddings, implicitly supporting feature selection, are valuable not only to quantum kernel methods in improving the latter's performance, but they can also be valuable to non-kernel QML methods based on parameterized quantum circuits (PQCs) as pretrained embeddings and for transfer learning. This further demonstrates the quantum utility, and quantum advantage (with classically-intractable quantum embeddings), of quantum kernel methods.