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

Abstract

We initiate the study of quantum algorithms for optimizing approximately convex functions. Given a convex set $\mathcal{K}\subseteq {\mathbb{R}}^n$ and a function $F:{\mathbb{R}}^n\to \mathbb{R}$ such that there exists a convex function $f:\mathcal{K}\to \mathbb{R}$ satisfying $\sup_{x\in{\cal K}}|F(x)-f(x)|\leq \epsilon/n$,ourquantumalgorithmfindsan$x^{*}\in{\cal K}$suchthat$F(x^{*})-\min_{x\in{\cal K}} F(x)\leq\epsilon$ using $\tilde{O}(n^3)$ 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 $\tilde{O}(n^5{\log }^{2}T)$ regret, an exponential speedup in $T$ compared to the classical $\Omega (\sqrt{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.