01482nas a2200145 4500008004100000245005500041210005500096260001400151490000600165520107700171100001801248700001601266700001701282856003701299 2021 eng d00aQuantum Algorithms for Escaping from Saddle Points0 aQuantum Algorithms for Escaping from Saddle Points c8/19/20210 v53 a
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~(log2n/ϵ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~(log6n/ϵ1.75) queries to the gradient oracle (i.e., the first-order oracle), our quantum algorithm is polynomially better in terms of n and matches its complexity in terms of 1/ϵ. Our quantum algorithm is built upon two techniques: First, we replace the classical perturbations in gradient descent methods by simulating quantum wave equations, which constitutes the polynomial speedup in n for escaping from saddle points. Second, we 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 quantum speedup.
1 aZhang, Chenyi1 aLeng, Jiaqi1 aLi, Tongyang uhttps://arxiv.org/abs/2007.10253