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

Given a convex function f : R^d → R, the problem of sampling from a distribution (Equation presented) 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(Equation presented). 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 (Equation presented) and (Equation presented) 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 (Equation presented) quantum lower bound for estimating normalizing constants, implying near-optimality of our quantum algorithms in ∊.