Description
The theories of optimization answer foundational questions in statistics, operations research, machine learning, etc., and lead to new algorithms for practical applications. In this talk, I will introduce quantum algorithms for nonconvex optimization, which are very much motivated by intuitions from quantum physics. In particular, given a function
f: R^n → R, our quantum algorithm outputs an ε-approximate second-order stationary point using O(log n / ε^1.75) queries to the quantum evaluation oracle (i.e., the zeroth-order oracle). Compared to the classical algorithm by Jin et al. using O((log n)^6 / ε^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/ε. Technically, our main contribution is the idea of replacing the classical perturbations in gradient descent methods by simulating the evolution of the Schrodinger equation. In the end, we will also briefly introduce our recent development in quantum algorithms for general nonconvex optimization problems.
