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).