Quantum Speedups for Log-Concave Sampling from Local Structure
Abstract
For a convex function f : ℝd → ℝ, 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) = ∑a=1R ψa(xSa). In this paper, we consider log-concave sampling using local queries, i.e., evaluation and gradient queries to each clause ψa(·), 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 Õ(√κd) local queries, where κ is the condition number. This improves the prior best classical result Õ(κd) due to Ascolani, Lavenant, and Zanella (Ann. Probab. 2026) and the quantum result Õ(√κ d2) 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.
Related
- Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks
- Local Anticoncentration for Gaussian Boson Sampling via Conditional Wishart Geometry
- Multi-Threshold Sampling: Local and Global Parameter Identifiability
- Wigner Momentum Estimation and Sampling with Local Modes: A Second-Moment Approximation to High-Frequency Momentum Marginals
- Multilevel Plaquette-Space Sampling for Lattice Gauge Theories with Local Constraint Solves
BibTeX
@misc{liu2026quantum,
title = {{Quantum Speedups for Log-Concave Sampling from Local Structure}},
author = {Chenghua Liu and Qisheng Wang and Zhengfeng Ji},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20253},
eprint = {2609.20253},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20253},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Speedups for Log-Concave Sampling from Local Structure
AU - Chenghua Liu
AU - Qisheng Wang
AU - Zhengfeng Ji
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.20253
UR - https://arxiv.org/abs/2609.20253
AB - For a convex function f : ℝ^d → ℝ, 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) = ∑_a=1^R ψ_a(x_S_a). In this paper, we consider log-concave sampling using local queries, i.e., evaluation and gradient queries to each clause ψ_a(·), 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 Õ(√κd) local queries, where κ is the condition number. This improves the prior best classical result Õ(κd) due to Ascolani, Lavenant, and Zanella (Ann. Probab. 2026) and the quantum result Õ(√κ 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.
ER -