If each coordinate appears in only a small number of clauses, there is a quantum algorithm for strongly log-concave sampling using local queries using $\widetilde{O}(\sqrt{\kappa}d)$ local queries, where $\kappa$ is the condition number.
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.
We prove the first quantum-classical separation for a sampling problem over a continuous domain. For a class of Gibbs states $p\propto e^{-\beta E}$ on the torus $\mathbb{T}^d$ with smooth ($s$-Gevrey) potential and barrier amplitude $\alpha=e^{\beta\Delta}$, where $\Delta = \max E-\min E$, every classical algorithm qu...
Enrico Olivucci, Mariia Sobchuk, Sehmimul Hoque et al.· 1 citation
Consider a constraint satisfaction problem $\mathbf{C}$ on finitely many independent random variables with dependency graph $G$. Let $p_a$ be the violation probability of a constraint $a\in \mathbf{C}$ and $N_G^2 (a)$ the set of constraints at distance one or two from $a$ in $G$. Suppose that, there exists $x\in (0,1)^...
Vishesh Jain, Clayton Mizgerd, H. Pham· arXiv.org· 0 citations
We prove that for every isotropic log-concave distribution $P$ on $\mathbb{R}^d$ and every even $m\ge2$, the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a sum of squares, where $C>0$ is a universal constant. This improves on the Poincar\'e-dependent bounds (Kothari and Steinhardt, 2017),...
A total Boolean function is constructed whose randomized query complexity with one-sided error satisfies ${R}_1(f) = \Theta(\sqrt{{C}(f)})$, which is optimal even when two-sided error is allowed.
A. Ambainis, Janis Iraids, M. Kokainis· 0 citations
By exploiting a point-counting formula derived from character sums over finite fields, this work develops an alternative approach that efficiently approximates the number of points without assuming the existence of an oracle.
For a Boolean communication matrix $M$, let $D(M)$ denote its deterministic communication complexity and let $r(M):={\mathrm{rank}}_{\mathbb{R}}(M)$. The log-rank conjecture asks whether $D(M)$ is polynomial in $\log r(M)$. The best known general upper bound, due to Sudakov and Tomon'25, is $D(M)=O(\sqrt{r(M)})$. On th...
Zhao Song· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.