Robustness of Quantum Algorithms for Nonconvex Optimization

Understand

Recent results suggest that quantum computers possess the potential to speed up nonconvex optimization problems.

• However, a crucial factor for the implementation of quantum optimization algorithms is their robustness against experimental and statistical noises.
• In this paper, we systematically study quantum algorithms for finding an $\epsilon$-approximate second-order stationary point ($\epsilon$-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(\epsilon^{10}/d^5)$, accelerated perturbed gradient descent with quantum gradient estimation takes $O(\log d/\epsilon^{1.75})$ quantum queries to find an $\epsilon$-SOSP.