RECORD
Quantum Speedups for Log-Concave Sampling from Local Structure
Quantum Physics · Submitted 14 Aug 2026
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | background 1.00 | 0.06 | 0.02 | asserted 1.00 |
| s1 | 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})$. | background 0.99 | 0.09 | 0.02 | asserted 0.64 |
| s2 | 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. | method 0.46 | 0.22 | 0.04 | asserted 0.86 |
| s3 | 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. | result 0.91 | 0.95 | 0.77 | asserted 1.00 |
| s4 | This improves the prior best classical result $\widetilde{O}(\kappa d)$ due to Ascolani, Lavenant, and Zanella (Ann. | result 0.67 | 0.64 | 0.24 | asserted 1.00 |
| s5 | Probab. 2026) and the quantum result $\widetilde{O}(\sqrt{\kappa} d^2)$ implied by Childs et al. (NeurIPS 2022). | result 0.42 | 0.12 | 0.15 | asserted 0.95 |
| s6 | 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. | contribution 0.70 | 0.74 | 0.10 | asserted 1.00 |
| s7 | These results demonstrate that local structure is not merely an implementation detail, but a quantum algorithmic resource for high-dimensional sampling. | interpretation 1.00 | 0.69 | 0.73 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
References
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.