论文标题
用应用程序对数遗憾随机凸Bistits应用大约优化凸功能的量子加速
Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits
论文作者
论文摘要
我们启动量子算法的研究，以优化近似凸功能。给定一个convex集合$ {\ cal k} \ subseteq \ mathbb {r}^{n} $和一个函数$ f \ colon \ colon \ colon \ mathbb {r}^{n} \ to \ to \ mathbb {r} $满足$ \ sup_ {x \ in {\ cal k}}} | f（x）-f（x）-f（x）| \leqε/n $，我们的量子算法找到一个$ x^{*} \ in {\ cal k k} $ in {\ cal k} $ f（x）\leqε$使用$ \ tilde {o}（n^{3}）$量子评估查询到$ f $。与最著名的经典算法相比，这实现了多项式量子加速。作为一个应用程序，我们给出了$ \ tilde {o}（n^{5} \ log^{2} t）$遗憾的Zeroth-rorder随机凸Bistits的量子算法。从技术上讲，我们通过利用模拟退火的量子框架并采用量子式步行的量子版本来实现$ n $的量子加速。我们在$ t $中的加速零级随机凸匪是由于平均估计的乘法误差时的二次量子加速。
We initiate the study of quantum algorithms for optimizing approximately convex functions. Given a convex set ${\cal K}\subseteq\mathbb{R}^{n}$ and a function $F\colon\mathbb{R}^{n}\to\mathbb{R}$ such that there exists a convex function $f\colon\mathcal{K}\to\mathbb{R}$ satisfying $\sup_{x\in{\cal K}}|F(x)-f(x)|\leq ε/n$, our quantum algorithm finds an $x^{*}\in{\cal K}$ such that $F(x^{*})-\min_{x\in{\cal K}} F(x)\leqε$ 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 $Ω(\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.
