报告题目：Quantum algorithms for escaping from saddle points
时间地点：2021-12-16 14:00，物理系理科楼C109
摘要：Optimization theory answers foundational questions in computer science, mathematics, operations research, etc. In this talk, I will introduce a quantum algorithm that we recently developed for nonconvex optimization, in particular for the task of escaping from saddle points. Our quantum algorithm achieves polynomial quantum speedup in dimension compared to the best-known classical algorithms. Technically, our quantum speedup is achieved by replacing the classical perturbations in gradient descent methods by simulating quantum wave equations. We also perform numerical experiments that support our quantum speedup. Finally, I will introduce directions for potential collaborations with quantum physics experts. The full version of the paper is available at https://arxiv.org/abs/2007.10253. It 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.
Bio: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 Mathematical Sciences, Tsinghua University, both in 2015. Dr. Tongyang Li’s research focuses on designing quantum algorithms for machine learning and optimization. In general, he is interested in better understanding about the power of quantum algorithms, including topics such as quantum query complexity, quantum simulation, and quantum walks. He was a recipient of the IBM Ph.D. Fellowship, the NSF QISE-NET Triplet Award, and the Lanczos Fellowship.
