# Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 47 references that are in the map.
- First posted on arXiv 26 Sep 2022.

## Builds on (most cited first, 14 of 14)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation](https://mlsanity.com/paper/2006.00475/) (2020)
- [Quantum SDP-Solvers: Better upper and lower bounds](https://mlsanity.com/paper/1705.01843/) (2017)
- [An optimal algorithm for bandit convex optimization](https://mlsanity.com/paper/1603.04350/) (2016)
- [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)
- [Quantum algorithms and lower bounds for convex optimization](https://mlsanity.com/paper/1809.01731/) (2018)
- [Quantum Sub-Gaussian Mean Estimator](https://mlsanity.com/paper/2108.12172/) (2021)
- [Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions](https://mlsanity.com/paper/1501.07242/) (2015)
- [Quantum algorithms for escaping from saddle points](https://mlsanity.com/paper/2007.10253/) (2020)
- [Quantum algorithm for estimating volumes of convex bodies](https://mlsanity.com/paper/1908.03903/) (2019)
- [Quantum Speed-ups for Semidefinite Programming](https://mlsanity.com/paper/1609.05537/) (2016)
- [Hit-and-Run for Sampling and Planning in Non-Convex Spaces](https://mlsanity.com/paper/1610.08865/) (2016)

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

- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [Quantum Bayesian Optimization](https://mlsanity.com/paper/2310.05373/) (2023)
- [Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret](https://mlsanity.com/paper/2302.10796/) (2023)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [Quantum Lipschitz Bandits](https://mlsanity.com/paper/2504.02251/) (2025)
- [Quantum Non-Linear Bandit Optimization](https://mlsanity.com/paper/2503.03023/) (2025)
- [Quantum Speedups for Sampling and Non-convex Optimization with Stochastic Oracles](https://mlsanity.com/paper/2504.03626/) (2025)
- [Quantum Speedup for Spectral Approximation of Kronecker Products](https://mlsanity.com/paper/2402.07027/) (2024)
- [Sublinear Time Quantum Algorithm for Attention Approximation](https://mlsanity.com/paper/2602.00874/) (2026)
- [On Quantum Perceptron Learning via Quantum Search](https://mlsanity.com/paper/2503.17308/) (2025)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (2025)

## Abstract (arXiv)

We initiate the study of quantum algorithms for optimizing approximately convex functions. Given a convex set cal Ksubseteqℝn and a function Fcolonℝn→ℝ such that there exists a convex function fcolonK→ℝ satisfying sup_x∈cal K|F(x)-f(x)|≤ ε/n, our quantum algorithm finds an x*∈cal K such that F(x*)-min_x∈cal K F(x)≤ε using tildeO(n3) quantum evaluation queries to F. This achieves a polynomial quantum speedup compared to the best-known classical algorithms. As an application, we give a quantum algorithm for zeroth-order stochastic convex bandits with tildeO(n5log2 T) regret, an exponential speedup in T compared to the classical Omega(√T) lower bound. Technically, we achieve quantum speedup in n by exploiting a quantum framework of simulated annealing and adopting a quantum version of the hit-and-run walk. Our speedup in T for zeroth-order stochastic convex bandits is due to a quadratic quantum speedup in multiplicative error of mean estimation.