Quantum Algorithms for Escaping from Saddle Points
Quantum Algorithms for Escaping from Saddle Points
复制标题
DOI：
10.22331/q-2021-08-20-529
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Chenyi Zhang;Jiaqi Leng;Tongyang Li
中科院分区：
文献类型：
--
作者：
Chenyi Zhang;Jiaqi Leng;Tongyang Li
我们启动了具有可证明保证的逃离鞍点的量子算法的研究。给定函数 f:Rn→R，我们的量子算法使用对量子评估预言机（即零阶预言机）的 O~(log2(n)/ϵ1.75) 查询输出一个 ϵ 近似二阶驻点。与 Jin 等人的经典最先进算法相比。通过 O~(log6(n)/ϵ1.75) 查询梯度预言机（即一阶预言机），我们的量子算法在 logn 方面多项式更好，并在 1/ϵ 方面匹配其复杂性。从技术上讲，我们的主要贡献是通过模拟量子波动方程来取代梯度下降方法中的经典扰动，从而通过 logn 因子来改进量子查询复杂性，以逃离鞍点。我们还展示了如何使用 Jordan 提出的量子梯度计算算法，用具有相同复杂度的量子评估查询来代替经典梯度查询。最后，我们还进行了数值实验来支持我们的理论发现。
We initiate the study of quantum algorithms for escaping from saddle points with provable guarantee. Given a function f:Rn→R, our quantum algorithm outputs an ϵ-approximate second-order stationary point using O~(log2(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 O~(log6(n)/ϵ1.75) queries to the gradient oracle (i.e., the first-order oracle), our quantum algorithm is polynomially better in terms of logn 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 logn 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.