首页| English| 中国科学院

Quantum algorithms for convex and nonconvex optimization

副标题:

时间:2021-11-15  来源:

题目: Quantum algorithms for convex and nonconvex optimization

报告人:Tongyang Li (北京大学)
时间: 2021年11月15日, 周一下午 3:00-4:00
地点: 数学院南楼 420

摘要: 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$ 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.

 

个人简介: Tongyang Li (李彤阳) is currently an assistant professor at the Center on Frontiers of Computing Studies and the School of Computer Science, Peking University. Previously he was a postdoctoral associate at the Center for Theoretical Physics, Massachusetts Institute of Technology. He received Master and Ph.D. degrees from the Department of Computer Science, University of Maryland in 2018 and 2020, respectively. He received Bachelor of Engineering from Institute for Interdisciplinary Information Sciences, Tsinghua University and Bachelor of Science from Department of Mathem

相关附件
相关文档