Operator-Level Quantum Acceleration of Non-Logconcave Sampling

Abstract

Sampling from probability distributions of the form $\sigma \propto e^{-\beta V}$, where $V$ is a continuous potential, is a fundamental task across physics, chemistry, biology, computer science, and statistics. However, when $V$ is non-convex, the resulting distribution becomes non-logconcave, and classical methods such as Langevin dynamics often exhibit poor performance. We introduce the first quantum algorithm that provably accelerates a broad class of continuous-time sampling dynamics. For Langevin dynamics, our method encodes the target Gibbs measure into the amplitudes of a quantum state, identified as the kernel of a block matrix derived from a factorization of the Witten Laplacian operator. This connection enables Gibbs sampling via singular value thresholding and yields up to a quartic quantum speedup over best-known classical Langevin-based methods in the non-logconcave setting. Building on this framework, we further develop the first quantum algorithm that accelerates replica exchange Langevin diffusion, a widely used method for sampling from complex, rugged energy landscapes.

48 pages, 8 figures

References in corpus (10)

• Parallel Tempering: Theory, Applications, and New Perspectives
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Near-optimal ground state preparation
• Thermal State Preparation via Rounding Promises
• Rapid thermalization of spin chain commuting Hamiltonians
• Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
• Infinite swapping replica exchange molecular dynamics leads to a simple simulation patch using mixture potentials
• Rapid thermalization of dissipative many-body dynamics of commuting Hamiltonians
• Quantum Langevin Dynamics for Optimization
• Quantized Markov Chain Couplings that Prepare Qsamples