Joint IQIM/AWS Seminar Series
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: https://jiaqileng.github.io/quantum-hamiltonian-descent/
This week's seminar will be presented by zoom:
https://caltech.zoom.us/j/88407627311?pwd=RGx4MlpSUnBLbDJvdE4rS1FHbWZvUT09
Meeting ID: 884 0762 7311
Passcode: 932356