论文标题
某些通用数值优化算法的量子加速
Quantum speedups of some general-purpose numerical optimisation algorithms
论文作者
论文摘要
我们给出了几种通用数值优化方法的量子加速，以最大程度地减少函数$ f：\ mathbb {r}^n \ to \ mathbb {r} $。首先，我们表明，在Lipschitz约束下进行的许多全球优化技术都可以近乎加速。其次，我们表明，回溯线搜索是准牛顿优化算法中的成分，可以加速到四边形。第三，我们表明，Nelder-Mead算法的一个组件可以通过$ o（\ sqrt {n}）$的乘法因子加速。第四，我们表明Gilyén等人的量子梯度计算算法。可用于在随机梯度下降的框架中大致计算梯度。在每种情况下，我们的结果都是基于应用现有的量子算法来加速经典算法的特定组件，而不是开发新的量子技术。
We give quantum speedups of several general-purpose numerical optimisation methods for minimising a function $f:\mathbb{R}^n \to \mathbb{R}$. First, we show that many techniques for global optimisation under a Lipschitz constraint can be accelerated near-quadratically. Second, we show that backtracking line search, an ingredient in quasi-Newton optimisation algorithms, can be accelerated up to quadratically. Third, we show that a component of the Nelder-Mead algorithm can be accelerated by up to a multiplicative factor of $O(\sqrt{n})$. Fourth, we show that a quantum gradient computation algorithm of Gilyén et al. can be used to approximately compute gradients in the framework of stochastic gradient descent. In each case, our results are based on applying existing quantum algorithms to accelerate specific components of the classical algorithms, rather than developing new quantum techniques.
