skip to main content

Joint IQIM/AWS Seminar Series

Wednesday, October 4, 2023
11:00am to 12:00pm
Add to Cal
Online Event
Quantum Hamiltonian Descent
Xiaodi Wu, Associate Professor, Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park,

Abstract: Gradient descent is a fundamental algorithm for continuous optimization. Identifying its quantum counterpart would be appealing to both theoretical and practical quantum applications. In this talk, we propose Quantum Hamiltonian Descent (QHD) as a truly quantum counterpart of classical gradient algorithms, which is derived from the path integral of dynamical systems referring to the continuous-time limit of classical gradient descent algorithms, where the contribution from classically-prohibited trajectories can significantly boost QHD's performance for non-convex optimization. Indeed we identify a family of degree-4 polynomial non-convex optimization instances with $2^d$ local minima for dimension d, which can be solved in polynomial time by QHD, whereas a comprehensive empirical study suggests that representative state-of-the-art classical solvers including Gurobi would require a super-polynomial time to solve these instances. Moreover, QHD is described as a Hamiltonian evolution that allows efficient simulation on both digital and analog quantum computers. By embedding QHD into the evolution of quantum Ising Hamiltonians, we experimentally implemented QHD for non-convex constrained quadratic programming instances up to 75 dimensions by using DWave machines as an analog quantum Ising simulator. The DWave-implemented QHD, although noisy and only applicable to sparse instances due to the restriction of DWave machines, still outperforms the quantum adiabatic algorithm and most representative state-of-the-art classical solvers except Gurobi, based on the time-to-solution metric. Finally, we propose a "three-phase picture" to explain the behavior of QHD, especially its difference from the quantum adiabatic algorithm. Based on joint work (arXiv: 2303.01471 and a working manuscript) with Jiaqi Leng, Ethan Hickman, Joseph Li, and Yufan Zheng. Website for data visualization and more:

This week's seminar will be presented by zoom:

Meeting ID: 884 0762 7311
Passcode: 932356

For more information, please contact Marcia Brown by phone at 626-395-4013 or by email at [email protected].