# Quantum Non-Linear Bandit Optimization

arXiv: https://arxiv.org/abs/2503.03023 · HTML: https://mlsanity.com/paper/2503.03023/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 79 references that are in the map.
- First posted on arXiv 4 Mar 2025.

## Builds on (most cited first, 30 of 49)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Scalable Bayesian Optimization Using Deep Neural Networks](https://mlsanity.com/paper/1502.05700/) (2015)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Neural Architecture Search with Bayesian Optimisation and Optimal Transport](https://mlsanity.com/paper/1802.07191/) (2018)
- [BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search](https://mlsanity.com/paper/1910.11858/) (2019)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Practical Multi-fidelity Bayesian Optimization for Hyperparameter Tuning](https://mlsanity.com/paper/1903.04703/) (2019)
- [Bayesian optimization for materials design](https://mlsanity.com/paper/1506.01349/) (2015)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations](https://mlsanity.com/paper/1908.01425/) (2019)
- [Bayesian Optimization for Materials Design with Mixed Quantitative and Qualitative Variables](https://mlsanity.com/paper/1910.01688/) (2019)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Learning search spaces for Bayesian optimization: Another view of hyperparameter transfer learning](https://mlsanity.com/paper/1909.12552/) (2019)
- [Convex and Non-convex Optimization Under Generalized Smoothness](https://mlsanity.com/paper/2306.01264/) (2023)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [Quantum SDP-Solvers: Better upper and lower bounds](https://mlsanity.com/paper/1705.01843/) (2017)
- [Sample-Then-Optimize Batch Neural Thompson Sampling](https://mlsanity.com/paper/2210.06850/) (2022)
- [Convex optimization using quantum oracles](https://mlsanity.com/paper/1809.00643/) (2018)
- [Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets](https://mlsanity.com/paper/2205.14988/) (2022)
- [A Quantum Interior Point Method for LPs and SDPs](https://mlsanity.com/paper/1808.09266/) (2018)
- [When is Realizability Sufficient for Off-Policy Reinforcement Learning?](https://mlsanity.com/paper/2211.05311/) (2022)
- [Quantum algorithms and lower bounds for convex optimization](https://mlsanity.com/paper/1809.01731/) (2018)

## Built on by (most cited first, 2 of 2)

- [Quantum-Enhanced Neural Contextual Bandit Algorithms](https://mlsanity.com/paper/2601.02870/) (2026)
- [Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities](https://mlsanity.com/paper/2601.06913/) (2026)

## Abstract (arXiv)

We study non-linear bandit optimization where the learner maximizes a black-box function with zeroth order function oracle, which has been successfully applied in many critical applications such as drug discovery and materials design. Existing works have showed that with the aid of quantum computing, it is possible to break the classical Omega(√T) regret lower bound and achieve the new O(polylog T) upper bound. However, they usually assume that the objective function sits within the reproducing kernel Hilbert space and their algorithms suffer from the curse of dimensionality. In this paper, we propose the new Q-NLB-UCB algorithm which enjoys an input dimension-free O(polylog T) upper bound, making it applicable for high-dimensional tasks. At the heart of our algorithm design are quantum Monte Carlo mean estimator, parametric function approximation technique, and a new quantum non-linear regression oracle, which can be of independent interests in more quantum machine learning problems. Our algorithm is also validated for its efficiency compared with other quantum algorithms on both high-dimensional synthetic and real-world tasks.