Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants
This work addresses a fundamental computational challenge in machine learning, physics, and statistics by providing quantum speedups, though it is incremental as it builds on existing classical algorithms like Langevin diffusion.
The paper tackles the problem of sampling from log-concave distributions and estimating their normalizing constants, developing quantum algorithms that achieve query complexities matching or surpassing classical methods, with specific speedups such as quadratic in multiplicative error and polynomial in condition number and dimension.
Given a convex function $f\colon\mathbb{R}^{d}\to\mathbb{R}$, 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_{\mathbb{R}^d}e^{-f(x)}\mathrm{d} x$. First, we use underdamped Langevin diffusion to develop quantum algorithms that match the query complexity (in terms of the condition number $κ$ 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 $\widetilde{O}(κ^{1/2}d)$ and $\widetilde{O}(κ^{1/2}d^{3/2}/ε)$ for log-concave sampling and normalizing constant estimation, respectively, achieving polynomial speedups in $κ,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 $ε$.