Robustness of Quantum Algorithms for Nonconvex Optimization

In this paper, we systematically study quantum algorithms for finding an ϵapproximate second-order stationary point (ϵ-SOSP) of a d-dimensional nonconvex function, a fundamental problem in nonconvex optimization, with noisy zeroth-or first-order oracles as inputs. We first prove that, up to noise of O(ϵ 10 /d 5 ), perturbed accelerated gradient descent equipped with quantum gradient estimation takes O(log d/ϵ 1.75 ) quantum queries to find an ϵ-SOSP. We then prove that standard perturbed gradient descent is robust to the noise of O(ϵ 6 /d 4 ) and O(ϵ/d 0.5+ζ ) for any ζ > 0 on the zeroth-and first-order oracles, respectively, which provides a quantum algorithm with poly-logarithmic query complexity. Furthermore, we propose a stochastic gradient descent algorithm using quantum mean estimation on the Gaussian smoothing of noisy oracles, which is robust to O(ϵ 1.5 /d) and O(ϵ/ √ d) noise on the zeroth-and first-order oracles, respectively. The quantum algorithm takes O(d 2.5 /ϵ 3.5 ) and O(d 2 /ϵ 3 ) queries to the two oracles, giving a polynomial speedup over the classical counterparts. As a complement, we characterize the domains where quantum algorithms can find an ϵ-SOSP with poly-logarithmic, polynomial, or exponential number of queries in d, or the problem is information-theoretically unsolvable even with an infinite number of queries. In addition, we prove an Ω(ϵ -12/7 ) lower bound on ϵ for any randomized classical and quantum algorithm to find an ϵ-SOSP using either noisy zeroth-or first-order oracles.