Quantum algorithms for escaping from saddle points
  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 $\epsilon$-approximate second-order stationary
point using $\tilde{O}(\log^{2} (n)/\epsilon^{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)/\epsilon^{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/\epsilon$. 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.
