Quantum Dynamical Systems for Optimization: Theory and Experiments

Abstract: Classical algorithms are often not effective for solving nonconvex optimization problems where local minima are separated by high barriers. In this talk, we introduce optimization algorithms based on quantum dynamical systems. On the one hand, we leverage the global effect of quantum tunneling in the Schrodinger equation, which introduces a quantum algorithm termed the quantum tunneling walk (QTW). We apply QTW to nonconvex problems where local minima are approximately global minima, and it achieves quantum speedup over classical stochastic gradient descents (SGD) when the barriers between different local minima are high but thin and the minima are flat. On the other hand, we also consider open quantum systems coupled with a heat bath, which introduces a quantum algorithm termed Quantum Langevin Dynamics (QLD) covering the practical case with random quantum noise to the system. We prove the convergence of QLD in optimizing convex and slightly nonconvex functions, demonstrating that the average energy of the system can approach zero in the low temperature limit with an exponential decay rate correlated with the evolution time. The theories of both quantum algorithms are well supported by numerical experiments, and they outperform a series of state-of-the-art quantum and classical optimization algorithms in many non-convex landscapes.This talk is based on two papers: arXiv:2209.14501 (Quantum 7, 1030 (2023)) and arXiv:2311.15587 (in submission).Bio: Dr. Tongyang Li is currently an assistant professor at Center on Frontiers of Computing Studies, 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.