We propose Quantum Hamiltonian Descent (QHD) as a truly quantum counterpart of classical gradient methods, which is derived from the path integral of classical dynamical systems corresponding to the continuous-time limit of classical gradient descent algorithms. We establish QHD’s convergence to the global optimum 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 D-Wave and others), we empirically observe that the D-Wave-implemented QHD outperforms a selection of 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.
For more details:
Play with interactive 3D visualizations of the QHD evolution! See the objective function definition and two surface plots of the function and the wave function probability distribution side by side on each function's dedicated page.
See how QHD performs when specially encoded to run on the publicly-available D-Wave Advantage 6.1 System. QHD compares favorably with both classical local solvers and the native quantum annealing algorithm of the D-Wave device.