论文标题
从鞍点逃脱的量子算法
Quantum algorithms for escaping from saddle points
论文作者
论文摘要
我们启动了量子算法的研究，以逃离可证明保证的鞍点。给定一个函数$ f \ colon \ mathbb {r}^{n} \ to \ mathbb {r {r} $，我们的量子算法输出a $ε$ - 二阶固定点，使用$ \ tilde {O} （即，零级甲骨文）。与Jin等人的经典最新算法相比。带有$ \ tilde {o}（\ log^{6}（n）/ε^{1.75}）$ QUERIES $ QUERIES $ QUERIES（即一阶Oracle），我们的Quantum Algorithm在$ \ log n $上是多种算法更好的，并且与$ \ n $相匹配，并且在其复杂性上与$ 1/ε$ 1/ε$相匹配。从技术上讲，我们的主要贡献是通过模拟量子波方程来代替梯度下降方法中的经典扰动的想法，量子波方程构成了量子查询复杂性的改善，并使用$ \ log n $因子逃脱了鞍点。我们还展示了如何使用Jordan引起的量子梯度计算算法来替换具有相同复杂性的量子评估查询的经典梯度查询。最后，我们还执行支持我们理论发现的数值实验。
We initiate the study of quantum algorithms for escaping from saddle points with provable guarantee. Given a function $f\colon\mathbb{R}^{n}\to\mathbb{R}$, our quantum algorithm outputs an $ε$-approximate second-order stationary point using $\tilde{O}(\log^{2} (n)/ε^{1.75})$ queries to the quantum evaluation oracle (i.e., the zeroth-order oracle). Compared to the classical state-of-the-art algorithm by Jin et al. with $\tilde{O}(\log^{6} (n)/ε^{1.75})$ queries to the gradient oracle (i.e., the first-order oracle), our quantum algorithm is polynomially better in terms of $\log n$ and matches its complexity in terms of $1/ε$. Technically, our main contribution is the idea of replacing the classical perturbations in gradient descent methods by simulating quantum wave equations, which constitutes the improvement in the quantum query complexity with $\log n$ factors for escaping from saddle points. We also show how to use a quantum gradient computation algorithm due to Jordan to replace the classical gradient queries by quantum evaluation queries with the same complexity. Finally, we also perform numerical experiments that support our theoretical findings.
