Title：Quantum algorithms for convex and nonconvex optimization
Speaker： Tongyang Li （Peking University）
Time&Venue： 2021.11.15 15:00-16:00，N420
Abstract：The theories of optimization answer foundational questions in machine learning and lead to new algorithms for practical applications. In this talk, I will introduce two quantum algorithms that we recently developed for convex optimization and nonconvex optimization, respectively. Both achieve polynomial quantum speedup compared to the best-known classical algorithms. Our quantum algorithms are 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'>nn 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.

The full version of the papers are available at https://arxiv.org/abs/1809.01731 (convex optimization) and https://arxiv.org/abs/2007.10253 (nonconvex optimization). The convex optimization paper was accepted as a contributed talk at QIP 2019, journal version Quantum, 4:221, 2020. The nonconvex optimization paper was accepted as a contributed talk at QIP 2021 (see our presentation at https://www.youtube.com/watch?v=xbHqktWa354), journal version Quantum, 5:529, 2021.