  Log-concave sampling has witnessed remarkable algorithmic advances in recent
years, but the corresponding problem of proving lower bounds for this task has
remained elusive, with lower bounds previously known only in dimension one. In
this work, we establish the following query lower bounds: (1) sampling from
strongly log-concave and log-smooth distributions in dimension $d\ge 2$
requires $\Omega(\log \kappa)$ queries, which is sharp in any constant
dimension, and (2) sampling from Gaussians in dimension $d$ (hence also from
general log-concave and log-smooth distributions in dimension $d$) requires
$\widetilde \Omega(\min(\sqrt\kappa \log d, d))$ queries, which is nearly sharp
for the class of Gaussians. Here $\kappa$ denotes the condition number of the
target distribution. Our proofs rely upon (1) a multiscale construction
inspired by work on the Kakeya conjecture in geometric measure theory, and (2)
a novel reduction that demonstrates that block Krylov algorithms are optimal
for this problem, as well as connections to lower bound techniques based on
Wishart matrices developed in the matrix-vector query literature.
