Smoothed Score Queries and the Complexity of Sampling

We study the query and communication complexity of sampling from high-dimensional Gaussian distributions using gradient information. In the standard oracle model, exact gradients expose only matrix-vector products with the precision matrix, leading to polynomial approximation barriers and a characteristic $\sqrt{\kappa}$ dependence on the condition number. We show that this barrier disappears when the sampler is allowed to query \emph{smoothed gradients}, namely scores of Gaussian-convolved distributions. For a Gaussian target with precision $\Lambda$, a smoothed-score query at noise level $\tau$ gives access to the resolvent $(\Lambda+\tau^{-1}I)^{-1}$. Combining geometrically spaced noise levels with sinc-quadrature rational approximation, we obtain a sampler with $$ q = O\left( \left(\log\kappa+\log(\sqrt d/\varepsilon)\right) \log(\sqrt d/\varepsilon) \right) $$ smoothed-gradient queries for total variation error $\varepsilon$, improving the condition-number dependence from $\sqrt{\kappa}$ to logarithmic. We also study finite-bit gradient oracles. Using coordinatewise quantization of the transformed smoothed-gradient answers and a final dithering step, we obtain a sampling scheme whose total communicated gradient information is polylogarithmic in $\kappa$; in particular, for fixed dimension and accuracy, the bit complexity is $O(\log^2\kappa)$. To complement these upper bounds, we introduce a channel-synthesis, or reverse-Shannon, converse technique for sampling lower bounds. This converts total-variation simulation guarantees into communication requirements and yields an $\Omega(\log\kappa)$ lower bound on the required gradient information. Together, these results identify smoothed gradients as a strictly more powerful oracle for sampling and give nearly matching upper and lower bounds for its finite-bit complexity.