Quantum Information Seminar

JIAQI (JIMMY) LENG

University of Maryland, College Park

Quantum Approach to Classical Optimization: Why Bother and What To Do?

Abstract: Continuous optimization problems arise in virtually all disciplines of quantitative research, including applied mathematics, computer science, and operations research. While convex optimization has been well studied in the past decades, nonconvex optimization generally remains intractable in theory and practice. Quantum computers, an emerging technology that exploits quantum physics for information processing, could pave an unprecedented path toward nonconvex optimization.

This talk focuses on Quantum Hamiltonian Descent (QHD), a recently proposed quantum algorithm for continuous optimization. QHD is derived as the path integral of standard gradient descent (GD). It inherits the algorithmic simplicity of GD and meanwhile exhibits a drastically different behavior from GD due to the quantum interference of classical paths, especially for nonconvex optimization. Specifically, we prove that QHD can efficiently solve a family of nonconvex continuous optimization instances, each characterized by exponentially many local minima. The new mathematics of QHD, including a surprising connection between QHD and Wasserstein geometry, is yet to be understood. Beyond the standard circuit-based implementation, we also propose an analog implementation of QHD through the Hamiltonian embedding technique for sparse Hamiltonian simulation. Based on this approach, we develop an open-source software named QHDOPT, which is used in an empirical study to confirm the practical advantage of QHD for large-scale nonconvex problems.

Bio: Jiaqi Leng is a fifth-year doctoral student at the University of Maryland, advised by Dr. Xiaodi Wu. His research focuses on quantum algorithms and scientific computing. In particular, he tries to bridge the gap between the theoretical foundations of quantum computing and the limitation of realistic quantum hardware in the near term. He will join UC Berkeley as a Simons Quantum Postdoctoral Fellow in the fall of 2024.

Join us in Library 121, or on Zoom, for this livestreamed talk.
Join as an attendee from PC, Mac, Linux, iOS or Android: https://mines.zoom.us/j/98804513801?pwd=TlRqWUVwVTAxdk9DUDVRZEswanZ4QT09; Password: 504387