IQIM Postdoctoral and Graduate Student Seminar

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. New mathematics of QHD is yet to be understood, including a surprising connection between QHD and Wasserstein geometry. 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.

Lunch will be provided, following the talk, on the lawn north of the Bridge Building.