# Operator-Level Quantum Acceleration of Non-Logconcave Sampling

arXiv: https://arxiv.org/abs/2505.05301 · HTML: https://mlsanity.com/paper/2505.05301/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 119 references that are in the map.
- First posted on arXiv 8 May 2025.

## Builds on (most cited first, 30 of 36)

- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem](https://mlsanity.com/paper/1802.08089/) (2018)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019)
- [Improved analysis for a proximal algorithm for sampling](https://mlsanity.com/paper/2202.06386/) (2022)
- [Sharp convergence rates for Langevin dynamics in the nonconvex setting](https://mlsanity.com/paper/1805.01648/) (2018)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling](https://mlsanity.com/paper/2010.09597/) (2020)
- [Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo](https://mlsanity.com/paper/2002.04121/) (2020)
- [Auxiliary gradient-based sampling algorithms](https://mlsanity.com/paper/1610.09641/) (2016)
- [Accelerating Nonconvex Learning via Replica Exchange Langevin Diffusion](https://mlsanity.com/paper/2007.01990/) (2020)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants](https://mlsanity.com/paper/2210.06539/) (2022)
- [Quantum Hamiltonian Descent](https://mlsanity.com/paper/2303.01471/) (2023)
- [Quantum Langevin Dynamics for Optimization](https://mlsanity.com/paper/2311.15587/) (2023)
- [Efficient phase-factor evaluation in quantum signal processing](https://mlsanity.com/paper/2002.11649/) (2020)
- [Statistical Estimation of the Poincar'e constant and Application to Sampling Multimodal Distributions](https://mlsanity.com/paper/1910.14564/) (2019)
- [A CS guide to the quantum singular value transformation](https://mlsanity.com/paper/2302.14324/) (2023)
- [Improved Bound for Mixing Time of Parallel Tempering](https://mlsanity.com/paper/2304.01303/) (2023)
- [Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions](https://mlsanity.com/paper/2310.11445/) (2023)
- [A quantum central path algorithm for linear optimization](https://mlsanity.com/paper/2311.03977/) (2023)

## Built on by (most cited first, 1 of 1)

- [Provable Quantum-Classical Separation for Continuous Gibbs Sampling](https://mlsanity.com/paper/2608.24527/) (2026)

## Abstract (arXiv)

Sampling from probability distributions of the form σ propto e-β 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.