Quantum Hamiltonian Descent (QHD)
Proposal for a truly quantum counterpart of classical gradient methods
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:
-
22 two-dimensional test functions from the optimization literature
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.
-
160 randomly generated quadratic programming instances up to 75 dimensions
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.
- More details on our methodology and performance metrics:
- The full technical paper can be found on the arXiv at https://arxiv.org/abs/2303.01471.
- Find the project's source code at the QHD Github for an in-depth look at our experiments and data-wrangling.
- Find the project's raw data for download at the QHD Box.
- Watch a talk given by Prof. Xiaodi Wu at the Fields Institute at http://www.fields.utoronto.ca/talks/Quantum-Hamiltonian-descent
Thank you to our sponsors!
