# Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 63 references that are in the map.
- First posted on arXiv 12 Oct 2022.

## Builds on (most cited first, 19 of 19)

- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient](https://mlsanity.com/paper/1710.00095/) (2017)
- [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019)
- [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)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo](https://mlsanity.com/paper/2002.04121/) (2020)
- [Quantum Inference on Bayesian Networks](https://mlsanity.com/paper/1402.7359/) (2014)
- [Convex optimization using quantum oracles](https://mlsanity.com/paper/1809.00643/) (2018)
- [Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions](https://mlsanity.com/paper/2106.05480/) (2021)
- [Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds](https://mlsanity.com/paper/1911.03043/) (2019)
- [Quantum algorithms and lower bounds for convex optimization](https://mlsanity.com/paper/1809.01731/) (2018)
- [Quantum Chebyshev's Inequality and Applications](https://mlsanity.com/paper/1807.06456/) (2018)
- [Quantum algorithms for escaping from saddle points](https://mlsanity.com/paper/2007.10253/) (2020)
- [Quantum algorithm for estimating volumes of convex bodies](https://mlsanity.com/paper/1908.03903/) (2019)

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

- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [Quantum Langevin Dynamics for Optimization](https://mlsanity.com/paper/2311.15587/) (2023)
- [Learning Quantum Processes with Quantum Statistical Queries](https://mlsanity.com/paper/2310.02075/) (2023)
- [Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions](https://mlsanity.com/paper/2310.11445/) (2023)
- [Quantum Speedups for Sampling and Non-convex Optimization with Stochastic Oracles](https://mlsanity.com/paper/2504.03626/) (2025)
- [Quantum Speedup for Spectral Approximation of Kronecker Products](https://mlsanity.com/paper/2402.07027/) (2024)
- [Operator-Level Quantum Acceleration of Non-Logconcave Sampling](https://mlsanity.com/paper/2505.05301/) (2025)
- [Provable Quantum-Classical Separation for Continuous Gibbs Sampling](https://mlsanity.com/paper/2608.24527/) (2026)

## Abstract (arXiv)

Given a convex function fcolonℝd→ℝ, the problem of sampling from a distribution propto e-f(x) is called log-concave sampling. This task has wide applications in machine learning, physics, statistics, etc. In this work, we develop quantum algorithms for sampling log-concave distributions and for estimating their normalizing constants intℝde-f(x)d x. First, we use underdamped Langevin diffusion to develop quantum algorithms that match the query complexity (in terms of the condition number kappa and dimension d) of analogous classical algorithms that use gradient (first-order) queries, even though the quantum algorithms use only evaluation (zeroth-order) queries. For estimating normalizing constants, these algorithms also achieve quadratic speedup in the multiplicative error ε. Second, we develop quantum Metropolis-adjusted Langevin algorithms with query complexity widetildeO(kappa1/2d) and widetildeO(kappa1/2d3/2/ε) for log-concave sampling and normalizing constant estimation, respectively, achieving polynomial speedups in kappa,d,ε over the best known classical algorithms by exploiting quantum analogs of the Monte Carlo method and quantum walks. We also prove a 1/ε1-o(1) quantum lower bound for estimating normalizing constants, implying near-optimality of our quantum algorithms in ε.