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

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 \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 \epsilon .