{"id":"arxiv/2609.20253","url":"https://arxiv.org/abs/2609.20253","tags":["quant-ph","cs.DS"],"score":0,"title":"Quantum Speedups for Log-Concave Sampling from Local Structure","domain":"quant-ph","source":"arxiv","authors":["Chenghua Liu","Qisheng Wang","Zhengfeng Ji"],"reviews":0,"subject":"quant-ph","summary":"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 ψ_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(\\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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-08-14","reactions":{}}