Quantum Speedups for Log-Concave Sampling from Local Structure

arXiv:2609.20253v1 Announce Type: new Abstract: For a convex function $f \colon \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 $\widetilde{O}(\sqrt{\kappa}d)$ local queries, where $\kappa$ is the condition number. This improves the prior best classical result $\widetilde{O}(\kappa d)$ due to Ascolani, Lavenant, and Zanella (Ann. Probab. 2026) and the quantum result $\widetilde{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.

Abstract:For a convex function $f \colon \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 $\widetilde{O}(\sqrt{\kappa}d)$ local queries, where $\kappa$ is the condition number. This improves the prior best classical result $\widetilde{O}(\kappa d)$ due to Ascolani, Lavenant, and Zanella (Ann. Probab. 2026) and the quantum result $\widetilde{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.

Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS)

arXiv:2609.20253 [quant-ph]

(or arXiv:2609.20253v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.20253 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

Quantum Speedups for Log-Concave Sampling from Local Structure

Subiecte conexe