Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization
Pith reviewed 2026-07-02 15:51 UTC · model grok-4.3
The pith
Projected quantum kernels and classical approximations reduce dimensionality in GP bandit optimization while preserving key quantum properties, yielding misspecified algorithms with regret bounds that guide model complexity.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Projected quantum kernels and classical kernel approximation techniques reduce feature dimensionality while preserving key quantum properties; using these approximate kernels yields misspecified GP bandit algorithms whose regret bounds characterize the trade-off between approximation error and information gain, thereby guiding selection of optimal model complexity and empirically outperforming full quantum kernels in sample efficiency while cutting computational overhead.
What carries the argument
Projected quantum kernels and classical kernel approximation techniques that reduce feature dimensionality while preserving key quantum properties.
If this is right
- Regret bounds quantify the trade-off between approximation error and information gain.
- The bounds give explicit guidance for selecting optimal model complexity.
- Misspecified GP algorithms achieve improved sample efficiency over full quantum kernels.
- Computational overhead is substantially reduced, enabling scalable optimization.
- The approach supports GP optimization for quantum-native applications on NISQ hardware.
Where Pith is reading between the lines
- The same projection and approximation strategy could be tested on other kernel-based quantum algorithms beyond bandits.
- The regret analysis framework may extend to settings where the mean function only approximately lies in the RKHS.
- Empirical validation on actual quantum hardware would test whether the preserved quantum properties translate to practical advantage.
- The dimensionality-reduction idea might inform kernel design choices in classical high-dimensional bandit problems.
Load-bearing premise
The mean reward function lies in the RKHS induced by the quantum kernel, and the proposed projections and approximations preserve the key quantum properties without introducing uncontrolled error that would invalidate the regret analysis.
What would settle it
A controlled experiment on a quantum control task in which the cumulative regret achieved by the projected or approximated kernels exceeds the regret of the full quantum kernel, or in which observed performance deviates from the predicted error-information-gain trade-off in the regret bounds.
Figures
read the original 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\"{i}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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper investigates GP bandit optimization with quantum kernels under the assumption that the mean reward lies in the induced RKHS. It proposes projected quantum kernels and classical approximations to reduce feature dimensionality while preserving key quantum properties, develops misspecified GP bandit algorithms, and derives regret bounds characterizing the expressivity-learnability trade-off to guide model complexity selection. Empirical results claim improved sample efficiency and reduced overhead versus full quantum kernels for NISQ tasks such as quantum control.
Significance. If the regret bounds hold with controlled approximation error, the work provides a principled framework for deploying quantum kernels in bandit settings without excessive model complexity, which is relevant for NISQ-era applications. The explicit trade-off characterization via regret analysis and the reported empirical gains in sample efficiency represent a concrete step toward scalable quantum kernel methods.
minor comments (3)
- The abstract states that regret bounds are derived but the provided text supplies no equation numbers or proof outlines; if the full manuscript contains them in §3–4, cross-reference them explicitly in the abstract for clarity.
- Notation for the projected kernel (likely defined in §2) should include an explicit equation showing how the projection operator acts on the feature map to make the dimensionality reduction precise.
- In the empirical section, the overhead reduction is claimed but no table or figure quantifies wall-clock time or memory versus the full kernel; adding such a comparison would strengthen the practical claim.
Simulated Author's Rebuttal
We thank the referee for their positive assessment of our work on projected quantum kernels and misspecified GP bandit algorithms, and for recommending minor revision. The provided referee summary accurately reflects the manuscript's focus on the expressivity-learnability trade-off in quantum kernel bandit optimization for NISQ tasks.
Circularity Check
No significant circularity
full rationale
The derivation begins from the standard assumption that the mean reward lies in the RKHS of the quantum kernel, then introduces projected kernels and approximations whose error is controlled in the regret analysis. Regret bounds are derived to quantify the resulting expressivity-learnability trade-off, and empirical comparisons are presented separately. No load-bearing step reduces by construction to a fitted parameter, self-citation, or renamed input; the central claims rest on external GP bandit theory and explicit approximation-error terms rather than self-referential definitions.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
arXiv preprint arXiv:1506.02785 , year=
On the error of random Fourier features , author=. arXiv preprint arXiv:1506.02785 , year=
-
[2]
arXiv preprint arXiv:2502.04021 , year=
Variational Quantum Optimization with Continuous Bandits , author=. arXiv preprint arXiv:2502.04021 , year=
-
[3]
Advances in neural information processing systems , volume=
Reinforcement learning for optimization of variational quantum circuit architectures , author=. Advances in neural information processing systems , volume=
-
[4]
Zur Elektrodynamik bewegter Körper
Albert Einstein. Zur Elektrodynamik bewegter Körper. Annalen der Physik. 1905
1905
-
[5]
The \ Companion
Michel Goossens and Frank Mittelbach and Alexander Samarin. The \ Companion. 1993
1993
-
[6]
Neural contextual bandits with deep representation and shallow exploration , author=. arXiv preprint arXiv:2012.01780 , year=
-
[7]
Quantum Machine Intelligence , volume=
On fundamental aspects of quantum extreme learning machines , author=. Quantum Machine Intelligence , volume=. 2025 , publisher=
2025
-
[8]
Quantum Science and Technology , volume=
Quantum-classical hybrid neural networks in the neural tangent kernel regime , author=. Quantum Science and Technology , volume=. 2023 , publisher=
2023
-
[9]
Quantum , volume=
Quantum lazy training , author=. Quantum , volume=. 2023 , publisher=
2023
-
[10]
International Conference on Machine Learning , pages=
Neural contextual bandits with ucb-based exploration , author=. International Conference on Machine Learning , pages=. 2020 , organization=
2020
-
[11]
Trained quantum neural networks are Gaussian processes
Trained quantum neural networks are Gaussian processes , author=. arXiv preprint arXiv:2402.08726 , year=
work page internal anchor Pith review Pith/arXiv arXiv
-
[12]
New Journal of Physics , volume=
Improving the dynamics of quantum sensors with reinforcement learning , author=. New Journal of Physics , volume=. 2020 , publisher=
2020
-
[13]
Physical Review X , volume=
Reinforcement learning in different phases of quantum control , author=. Physical Review X , volume=. 2018 , publisher=
2018
-
[14]
Physical review letters , volume=
Quantum support vector machine for big data classification , author=. Physical review letters , volume=. 2014 , publisher=
2014
-
[15]
npj Quantum Information , volume=
Quantum classifier with tailored quantum kernel , author=. npj Quantum Information , volume=. 2020 , publisher=
2020
-
[16]
Quantum Machine Intelligence , volume=
Quantum Gaussian process regression for Bayesian optimization , author=. Quantum Machine Intelligence , volume=. 2024 , publisher=
2024
-
[17]
Machine Learning: Science and Technology , volume=
Benchmarking of quantum fidelity kernels for Gaussian process regression , author=. Machine Learning: Science and Technology , volume=. 2024 , publisher=
2024
-
[18]
International Conference on Machine Learning , pages=
Learning near optimal policies with low inherent bellman error , author=. International Conference on Machine Learning , pages=. 2020 , organization=
2020
-
[19]
Conference on Learning Theory , pages=
Efficient and robust algorithms for adversarial linear contextual bandits , author=. Conference on Learning Theory , pages=. 2020 , organization=
2020
-
[20]
International Conference on Machine Learning , pages=
High-dimensional experimental design and kernel bandits , author=. International Conference on Machine Learning , pages=. 2021 , organization=
2021
-
[21]
Proceedings of the AAAI Conference on Artificial Intelligence , volume=
Misspecified linear bandits , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=
-
[22]
arXiv preprint arXiv:2301.09680 , year=
Quantum heavy-tailed bandits , author=. arXiv preprint arXiv:2301.09680 , year=
-
[23]
Advances in Neural Information Processing Systems , volume=
Quantum bayesian optimization , author=. Advances in Neural Information Processing Systems , volume=
-
[24]
2017 , publisher=
Fourier analysis on groups , author=. 2017 , publisher=
2017
-
[25]
The 40th Conference on Uncertainty in Artificial Intelligence , year=
Quantum kernelized bandits , author=. The 40th Conference on Uncertainty in Artificial Intelligence , year=
-
[26]
arXiv preprint arXiv:2311.13552 , year=
A unified framework for trace-induced quantum kernels , author=. arXiv preprint arXiv:2311.13552 , year=
-
[27]
Wan, Zongqi and Zhang, Zhijie and Li, Tongyang and Zhang, Jialin and Sun, Xiaoming , title =. 2023 , isbn =. doi:10.1609/aaai.v37i8.26202 , booktitle =
-
[28]
Quantum , volume=
Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states , author=. Quantum , volume=. 2022 , publisher=
2022
-
[29]
Advances in Neural Information Processing Systems , volume=
The inductive bias of quantum kernels , author=. Advances in Neural Information Processing Systems , volume=
-
[30]
In International Conference on Machine Learning (ICML), pages 1015--1022 , year=
Gaussian process optimization in the bandit setting: No regret and experimental design , author=. In International Conference on Machine Learning (ICML), pages 1015--1022 , year=
-
[31]
Nature Communications , volume=
Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines , author=. Nature Communications , volume=. 2023 , publisher=
2023
-
[32]
Quantum Science and Technology , volume=
Filtering variational quantum algorithms for combinatorial optimization , author=. Quantum Science and Technology , volume=. 2022 , publisher=
2022
-
[33]
International Conference on Machine Learning , pages=
Approximation theory based methods for rkhs bandits , author=. International Conference on Machine Learning , pages=. 2021 , organization=
2021
-
[34]
Finite-Time Analysis of Kernelised Contextual Bandits
Finite-time analysis of kernelised contextual bandits , author=. arXiv preprint arXiv:1309.6869 , year=
work page internal anchor Pith review Pith/arXiv arXiv
-
[35]
arXiv preprint arXiv:2112.00426 , year=
Noisy Bayesian optimization for variational quantum eigensolvers , author=. arXiv preprint arXiv:2112.00426 , year=
-
[36]
npj Quantum Information , volume=
Variational quantum algorithm with information sharing , author=. npj Quantum Information , volume=. 2021 , publisher=
2021
-
[37]
Science advances , volume=
Training of quantum circuits on a hybrid quantum computer , author=. Science advances , volume=. 2019 , publisher=
2019
-
[38]
Advances in neural information processing systems , volume=
Misspecified gaussian process bandit optimization , author=. Advances in neural information processing systems , volume=
-
[39]
Advances in Neural Information Processing Systems , volume=
Physics-informed bayesian optimization of variational quantum circuits , author=. Advances in Neural Information Processing Systems , volume=
-
[40]
Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences
Gaussian processes and kernel methods: A review on connections and equivalences , author=. arXiv preprint arXiv:1807.02582 , year=
work page internal anchor Pith review Pith/arXiv arXiv
-
[41]
Schuld, Maria and Sweke, Ryan and Meyer, Johannes Jakob , year=. Effect of data encoding on the expressive power of variational quantum-machine-learning models , volume=. Physical Review A , publisher=. doi:10.1103/physreva.103.032430 , number=
-
[42]
Machine Learning: Science and Technology , volume=
On the expressivity of embedding quantum kernels , author=. Machine Learning: Science and Technology , volume=. 2024 , publisher=
2024
-
[43]
arXiv preprint arXiv:2409.04406 , year=
Quantum Kernel Methods under Scrutiny: A Benchmarking Study , author=. arXiv preprint arXiv:2409.04406 , year=
-
[44]
Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design
Gaussian process optimization in the bandit setting: No regret and experimental design , author=. arXiv preprint arXiv:0912.3995 , year=
work page internal anchor Pith review Pith/arXiv arXiv
-
[45]
Nature communications , volume=
Power of data in quantum machine learning , author=. Nature communications , volume=. 2021 , publisher=
2021
-
[46]
Quantum Science and Technology , volume=
Faster variational quantum algorithms with quantum kernel-based surrogate models , author=. Quantum Science and Technology , volume=. 2023 , publisher=
2023
-
[47]
Machine Learning with Quantum Computers , pages=
Quantum models as kernel methods , author=. Machine Learning with Quantum Computers , pages=. 2021 , publisher=
2021
-
[48]
Nature communications , volume=
Noise-induced barren plateaus in variational quantum algorithms , author=. Nature communications , volume=. 2021 , publisher=
2021
-
[49]
Nature communications , volume=
Barren plateaus in quantum neural network training landscapes , author=. Nature communications , volume=. 2018 , publisher=
2018
-
[50]
Nature Reviews Physics , volume=
Variational quantum algorithms , author=. Nature Reviews Physics , volume=. 2021 , publisher=
2021
-
[51]
Nature communications , volume=
Exponential concentration in quantum kernel methods , author=. Nature communications , volume=. 2024 , publisher=
2024
-
[52]
Quantum Machine Intelligence , volume=
Quantum bandits , author=. Quantum Machine Intelligence , volume=. 2020 , publisher=
2020
-
[53]
Proceedings of the AAAI Conference on Artificial Intelligence , volume=
Quantum exploration algorithms for multi-armed bandits , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=
-
[54]
, title =
Li, Lihong and Chu, Wei and Langford, John and Schapire, Robert E. , title =. 2010 , booktitle =
2010
-
[55]
2017 , booktitle =
Ghosh, Avishek and Chowdhury, Sayak Ray and Gopalan, Aditya , title =. 2017 , booktitle =
2017
-
[56]
Learning with good feature representations in bandits and in RL with a generative model , year =
Lattimore, Tor and Szepesv\'. Learning with good feature representations in bandits and in RL with a generative model , year =. Proceedings of the 37th International Conference on Machine Learning , articleno =
-
[57]
and Rakhlin, Alexander , title =
Foster, Dylan J. and Rakhlin, Alexander , title =. Proceedings of the 37th International Conference on Machine Learning , articleno =. 2020 , publisher =
2020
-
[58]
and Xu, Yuesheng and Zhang, Haizhang , title =
Micchelli, Charles A. and Xu, Yuesheng and Zhang, Haizhang , title =. J. Mach. Learn. Res. , month = dec, pages =. 2006 , issue_date =
2006
-
[59]
Proceedings of the 21st International Conference on Neural Information Processing Systems , pages =
Rahimi, Ali and Recht, Benjamin , title =. Proceedings of the 21st International Conference on Neural Information Processing Systems , pages =. 2007 , publisher =
2007
-
[60]
2022 , eprint=
Classically Approximating Variational Quantum Machine Learning with Random Fourier Features , author=. 2022 , eprint=
2022
-
[61]
2021 , eprint=
Supervised quantum machine learning models are kernel methods , author=. 2021 , eprint=
2021
-
[62]
2015 , eprint=
On the Error of Random Fourier Features , author=. 2015 , eprint=
2015
-
[63]
Advances in Computational Mathematics , volume=
Near-optimal data-independent point locations for radial basis function interpolation , author=. Advances in Computational Mathematics , volume=. 2005 , publisher=
2005
-
[64]
Constructive Approximation , pages=
Greedy Algorithms for Reduced Bases in Banach Spaces , author=. Constructive Approximation , pages=. 2013 , publisher=
2013
-
[65]
and Huang, Hsin-Yuan and Cerezo, M
Caro, Matthias C. and Huang, Hsin-Yuan and Cerezo, M. and Sharma, Kunal and Sornborger, Andrew and Cincio, Lukasz and Coles, Patrick J. , year=. Generalization in quantum machine learning from few training data , volume=. Nature Communications , publisher=. doi:10.1038/s41467-022-32550-3 , number=
-
[66]
Kolmogorov widths on the sphere via eigenvalue estimates for H\"{o}lderian integral operators
Jordão, T. and Menegatto, V.A. , year=. Kolmogorov widths on the sphere via eigenvalue estimates for H\". 1805.08476 , archivePrefix=
work page internal anchor Pith review Pith/arXiv arXiv
-
[67]
A Course in Functional Analysis , author =
-
[68]
Quantum Machine Learning in Feature Hilbert Spaces , volume=
Schuld, Maria and Killoran, Nathan , year=. Quantum Machine Learning in Feature Hilbert Spaces , volume=. Physical Review Letters , publisher=. doi:10.1103/physrevlett.122.040504 , number=
-
[69]
Supervised learning with quantum-enhanced feature spaces,
Havlicek, Vojtech and Corcoles, Antonio D. and Temme, Kristan and Harrow, Aram W. and Kandala, Abhinav and Chow, Jerry M. and Gambetta, Jay M. , year=. Supervised learning with quantum-enhanced feature spaces , volume=. Nature , publisher=. doi:10.1038/s41586-019-0980-2 , number=
-
[70]
On the sub-Gaussianity of the Beta and Dirichlet distributions , volume=
Marchal, Olivier and Arbel, Julyan , year=. On the sub-Gaussianity of the Beta and Dirichlet distributions , volume=. Electronic Communications in Probability , publisher=. doi:10.1214/17-ecp92 , number=
-
[71]
Uniform approximation of functions with random bases , year=
Rahimi, Ali and Recht, Benjamin , booktitle=. Uniform approximation of functions with random bases , year=
-
[72]
doi:10.22331/q-2024-11-14-1523 , url =
Gradients and frequency profiles of quantum re-uploading models , author =. doi:10.22331/q-2024-11-14-1523 , url =
-
[73]
2018 , eprint=
What Doubling Tricks Can and Can't Do for Multi-Armed Bandits , author=. 2018 , eprint=
2018
-
[74]
Wang, Xuchuang and Chen, Yu-Zhen Janice and de Andrade, Matheus Guedes and Allcock, Jonathan and Hajiesmaili, Mohammad and Lui, John C.S. and Towsley, Don , title =. 2025 , isbn =. doi:10.1609/aaai.v39i20.35432 , booktitle =
-
[75]
Buchholz, Simon and K. Multi-. doi:10.22331/q-2025-03-25-1672 , url =
-
[76]
Wang, Daochen and You, Xuchen and Li, Tongyang and Childs, Andrew M. , year=. Quantum Exploration Algorithms for Multi-Armed Bandits , volume=. Proceedings of the AAAI Conference on Artificial Intelligence , publisher=. doi:10.1609/aaai.v35i11.17212 , number=
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.