Quantum Speedups for Log-Concave Sampling from Local Structure

Abstract

For a convex function $f:{\mathbb{R}}^d\to \mathbb{R}$, the problem of sampling from a distribution proportional to $e^{-f(x)}$ is called log-concave sampling. In many practical scenarios, the function $f(x)$ turns out to admit a local decomposition $f(x)={\sum }_{a=1}^R{\psi }_a(x_{S_a})$. In this paper, we consider log-concave sampling using local queries, i.e., evaluation and gradient queries to each clause ${\psi }_a(\cdot )$, which can be computationally much cheaper than the queries to $f(x)$ itself. We show that if each coordinate appears in only a small number of clauses, there is a quantum algorithm for strongly log-concave sampling using $\tilde{O}(\sqrt{\kappa }d)$ local queries, where $\kappa$ is the condition number. This improves the prior best classical result $\tilde{O}(\kappa d)$ due to Ascolani, Lavenant, and Zanella (Ann. Probab. 2026) and the quantum result $\tilde{O}(\sqrt{\kappa }{d}^2)$ implied by Childs et al. (NeurIPS 2022). Our quantum sampler applies to a broad class of locally structured models from statistical computing and machine learning, with representative examples including Gaussian Markov random fields, finite-element latent Gaussian models, and sparse generalized linear models. These results demonstrate that local structure is not merely an implementation detail, but a quantum algorithmic resource for high-dimensional sampling.