Stochastic Quantum Hamiltonian Descent

Sirui Peng, Sean Chen, Xiaoming Sun, Hongyi ZhouarXiv 2025 · arXiv

TL;DR

Stochastic Quantum Hamiltonian Descent (SQHD) is a new optimization framework that combines the computational efficiency of Stochastic Gradient Descent (SGD) with the global search power of quantum tunneling. By modeling stochastic sampling as an open quantum system, the authors provide a provably convergent, gate-based algorithm that can escape local minima more effectively than classical methods while remaining scalable for large datasets.

What Problem Does This Paper Address?

In the world of machine learning, Stochastic Gradient Descent (SGD) is king because it is efficient; it updates models using small "mini-batches" of data rather than the entire dataset. However, SGD is a local searcher—it can easily get trapped in the "valleys" of local minima in complex, non-convex landscapes.

On the quantum side, Quantum Hamiltonian Descent (QHD) has emerged as a powerful alternative. It uses quantum tunneling to "teleport" through energy barriers, allowing it to find global minima that classical gradients might miss. The catch? Standard QHD is "full-batch," meaning it requires queries to the entire dataset at every step. For modern large-scale machine learning, this is a computational dealbreaker.

The authors of this paper bridge this gap, creating a "stochastic" version of quantum optimization that is both computationally cheap and globally exploratory.

Methods

The core innovation of this paper is treating the "noise" generated by stochastic sampling as a physical process within an open quantum system.

  1. Lindbladian Dynamics: The authors propose a continuous-time model called Stochastic Quantum Hybrid Dynamics. They use the Lindblad master equation to describe the system's evolution. In this model, the "ideal" gradient descent is the Hamiltonian part, while the randomness of choosing different data points (the stochasticity) is modeled as dissipation/noise terms.
  2. The Generator: The evolution is driven by a generator ($L_{LS}$) composed of two parts:
  3. $L_{GD}$ (Gradient Descent Term): Drives the system along the optimization path using a Hamiltonian that includes kinetic energy (Laplace operator) and potential energy (the objective function).
  4. $L_{NOISE}$ (Stochastic Noise Term): Explicitly models the diffusive effects of using random mini-batches.
  5. Discrete-Time Algorithm (SQHD): To make this practical for near-term quantum computers, the authors developed a gate-based algorithm. Instead of trying to simulate complex Lindbladian dynamics directly (which is hardware-intensive), they use a second-order Trotter-Suzuki decomposition. This allows them to approximate the continuous dynamics using standard unitary gates and stochastic queries to individual function components.

Datasets

The algorithm was evaluated on several classic non-convex optimization "landscapes" rather than traditional image or text datasets. These benchmarks are designed to test an algorithm's ability to escape local minima:

  • Styblinski-Tang function (dw): A multi-modal landscape used to test global search.
  • Michalewicz function (mich): Characterized by steep ridges and narrow valleys.
  • Cube-Wave function (cubewave): A highly oscillatory landscape.
  • Nonlinear Least Squares (sino and sino-alt): Problems derived from fitting models to data, representing more "real-world" optimization challenges.

Key Insights and Ideas

  • Stochasticity as Dissipation: The "aha moment" is the realization that the iterative randomness of SGD can be mathematically mapped to an open quantum system interacting with an environment. This allows the researchers to use the tools of quantum thermodynamics to prove optimization convergence.
  • Quantum Weak Approximation: The authors prove that their discrete, gate-based algorithm is an "order-2 quantum weak approximation" of the continuous-time dynamics. This bridges the gap between high-level physics theory and actual quantum circuit implementation.
  • Tunneling for Free: By maintaining the Hamiltonian structure of QHD, SQHD retains the ability to tunnel through barriers. The stochastic noise actually helps the system explore, while the quantum effects prevent it from getting stuck in the shallow local minima that often plague classical SGD.

Key Results

  • Theoretical Convergence: The authors provide rigorous proofs (Theorems 1 and 2) showing that SQHD converges for convex and smooth objective functions.
  • Superior Exploration: In numerical experiments on non-convex functions, SQHD demonstrated a higher probability of finding the global minimum compared to classical Stochastic Gradient Descent with Momentum (SGDM).
  • Efficiency Gain: SQHD achieves solution quality comparable to (or better than) full-batch QHD but with a significantly lower per-iteration cost (querying only $1/m$ of the data).
  • Resolution Independence: Interestingly, while classical discretization resolution often affects QHD's performance, SQHD's solution quality remained robust across different spatial resolutions, though higher resolution led to slower convergence.

Limitations and Future Work

  • Convergence Speed: While SQHD is cheaper per iteration than QHD, the authors note that its overall convergence rate (in terms of total iterations) is generally slower. Finding the "sweet spot" where the reduced cost outweighs the slower convergence is an open question.
  • Hyperparameter Sensitivity: Like many quantum algorithms, SQHD is sensitive to the choice of learning rate and Hamiltonian coefficients. The authors suggest that a more quantitative analysis of these hyperparameters is needed.
  • Hardware Implementation: The current results are based on numerical simulations. The next logical step is to run SQHD on actual noisy intermediate-scale quantum (NISQ) devices to see how physical hardware noise interacts with the algorithmic stochastic noise.
  • Adaptive Variants: The authors briefly touch upon adaptive learning rates (similar to Adam in classical ML) and suggest this as a promising avenue for future "Adaptive SQHD" research.

Summary updated

Abstract

Stochastic Gradient Descent (SGD) and its variants underpin modern machine learning by enabling efficient optimization of large-scale models. However, their local search nature limits exploration in complex landscapes. In this paper, we introduce Stochastic Quantum Hamiltonian Descent (SQHD), a quantum optimization algorithm that integrates the computational efficiency of stochastic gradient methods with the global exploration power of quantum dynamics. We propose a Lindbladian dynamics as the quantum analogue of continuous-time SGD. We further propose a discrete-time gate-based algorithm that approximates these dynamics while avoiding direct Lindbladian simulation, enabling practical implementation on near-term quantum devices. We rigorously prove the convergence of SQHD for convex and smooth objectives. Numerical experiments demonstrate that SQHD also exhibits advantages in non-convex optimization. All these results highlight its potential for quantum-enhanced machine learning.
BibTeX
@misc{peng2025stochastic,
  author = {Sirui Peng and Sean Chen and Xiaoming Sun and Hongyi Zhou},
  title = {{Stochastic Quantum Hamiltonian Descent}},
  year = {2025},
  eprint = {2507.15424},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.15424},
  howpublished = {arXiv},
}
Figure