  Gradient descent is a fundamental algorithm in both theory and practice for
continuous optimization. Identifying its quantum counterpart would be appealing
to both theoretical and practical quantum applications. A conventional approach
to quantum speedups in optimization relies on the quantum acceleration of
intermediate steps of classical algorithms, while keeping the overall
algorithmic trajectory and solution quality unchanged. 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.
