Quantum speedups of some general-purpose numerical optimisation algorithms
Quantum speedups of some general-purpose numerical optimisation algorithms
复制标题
DOI：
10.1088/2058-9565/abb003
复制
发表时间：
2020-10-01
影响因子：
6.7
通讯作者：
Morris, Hannah
中科院分区：
文献类型：
--
作者：
Alexandru, Cezar-Mihail;Bridgett-Tomkinson, Ella;Morris, Hannah
我们给出了几种用于最小化函数\(f:\mathbb{R}^n\rightarrow\mathbb{R}\)的通用数值优化方法的量子加速。首先，我们表明在利普希茨（Lipschitz）约束下的许多全局优化技术可以近二次加速。其次，我们表明回溯直线搜索（准牛顿优化算法中的一个要素）可以二次加速。第三，我们表明 Nelder - Mead算法的一个组件可以加速到\(O(\sqrt{n})\)的乘法因子。第四，我们表明Gilyen等人的量子梯度计算算法可用于在随机梯度下降框架中近似计算梯度。在每种情况下，我们的结果都是基于应用现有的量子算法来加速经典算法的特定组件，而不是开发新的量子技术。
We give quantum speedups of several general-purpose numerical optimisation methods for minimising a function f : R-n -> 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(root n). Fourth, we show that a quantum gradient computation algorithm of Gilyen 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.