Quantum Hamiltonian Descent

Ubiquitous continuous optimization has been an active topic investigated for quantum speed-ups. The conventional approach relies on the quantum acceleration of intermediate steps of corresponding classical algorithms, whereas the trajectory of resultant quantum algorithms and the quality of the solutions are similar to classical ones. We propose Quantum Hamiltonian Descent (QHD) as a truly quantum counterpart of classical gradient methods for continuous optimization, which is derived by quantizing dynamical systems referring to the continuous-time limit of gradient methods through the path integral formulation of quantum mechanics. QHD's convergence to the global optimum is established in both convex and non-convex settings. More importantly, QHD is described as a time-dependent Hamiltonian evolution that can be efficiently simulated on both digital and analog quantum computers. By embedding QHD's Hamiltonian evolution into the evolution of the so-called Quantum Ising Machine (including DWave and others), we empirically observe that the DWave-implemented QHD outperforms a selection of the state-of-the-art gradient-based classical solvers and the standard quantum adiabatic algorithm, based on the time-to-solution metric, on non-convex constrained quadratic programming instances up to 75 dimensions. Finally, we propose a "three-phase picture" to explain the behavior of QHD, especially its difference from the quantum adiabatic algorithm.