We propose Quantum Hamiltonian Descent (QHD), which is derived from the path integral of dynamical systems referring to the continuous-time limit of classical gradient descent algorithms, as a truly quantum counterpart of classical gradient methods where the contribution from classically-prohibited trajectories can significantly boost QHD’s performance for non-convex optimization. Moreover, QHD is described as a Hamiltonian evolution efficiently simulatable on both digital and analog quantum computers. By embedding the dynamics of QHD 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.