mlsanityData to 14 Oct 2026

Quantum Bayesian Optimization

arXiv 2310.05373 ↗First posted 9 Oct 2023cs.LG cs.AIcited by 12

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 28 of its 44 references that are in the map. First posted on arXiv 9 Oct 2023.

Builds on

28 of 44 references.

References · 28

  1. 2018A Tutorial on Bayesian Optimizationcited by 744
  2. 2020The power of quantum neural networkscited by 379
  3. 2017On Kernelized Multi-armed Banditscited by 352
  4. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  5. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  6. 2020Neural Thompson Samplingcited by 128
  7. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
  8. 2020Federated Bayesian Optimization via Thompson Samplingcited by 77
  9. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  10. 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
  11. 2022A Survey on Quantum Reinforcement Learningcited by 53
  12. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 39
16 more
  1. 2020Bayesian Optimization of Risk Measurescited by 36
  2. 2021Differentially Private Federated Bayesian Optimization with Distributed Explorationcited by 32
  3. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  4. 2022Sample-Then-Optimize Batch Neural Thompson Samplingcited by 25
  5. 2021Quantum Algorithms for Reinforcement Learning with a Generative Modelcited by 24
  6. 2020Quantum exploration algorithms for multi-armed banditscited by 22
  7. 2020Advances in Quantum Deep Learning: An Overviewcited by 21
  8. 2022Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regretscited by 19
  9. 2020Quantum Banditscited by 18
  10. 2022Federated Neural Banditscited by 17
  11. 2022Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Timescited by 13
  12. 2022Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Banditscited by 11
  13. 2022Bayesian Optimization under Stochastic Delayed Feedbackcited by 10
  14. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  15. 2023Quantum Heavy-tailed Banditscited by 8
  16. 2023Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learningcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 5; 2026: 4.

12 papers.

  1. 2024PINNACLE: PINN Adaptive ColLocation and Experimental points selectioncited by 32
  2. 2023Batch Bayesian Optimization for Replicable Experimental Designcited by 8
  3. 2025Quantum Lipschitz Banditscited by 4
  4. 2024A Bandit Approach with Evolutionary Operators for Model Selectioncited by 2
  5. 2025Quantum Non-Linear Bandit Optimizationcited by 2
  6. 2025PIED: Physics-Informed Experimental Design for Inverse Problemscited by 2
  7. 2025Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexitiescited by 2
  8. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  9. 2026Quantum-Enhanced Neural Contextual Bandit Algorithmscited by 1
  10. 2026Spectral Anatomy of Quantum Gaussian Process Kernelscited by 0
  11. 2026Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimizationcited by 0
  12. 2026Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithmscited by 0