On Complexity of Gaussian Sampling
Abstract
We study the number of exact matrix-vector queries needed to sample a centered d-dimensional Gaussian with condition number at most κ to total variation error ε. The best known algorithm uses O(min{d,√κlog(d/ε)}) queries, while the known lower bounds do not grow as ε→0 and match this bound only for κ≤ d1/5−δ at constant accuracy. We introduce a construction based on a hidden determinant sign and prove a lower bound of Ω (min{d,√κlog(1+d/(√κ ε))}) uniformly for all d≥1, κ≥4, and 0<ε≤1/16. This bound matches the known upper bound up to constant factors whenever κ≤ d2−δ for fixed δ∈(0,2), or ε≤ d−c for fixed c>0. We also extend a recent fixed-spectrum construction with a hidden eigenbasis from κ=2 to 2≤κ≤ d1−δ, for any fixed δ∈(0,1). This gives an Ωδ(√κlog d) lower bound at constant accuracy that holds even when the spectrum of the precision matrix is known to the algorithm.
Related
- Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start
- A Universal Lower Bound for the Complexity of Gaussian-Divisible Spin Glasses
- Log-depth entanglement transition in hypercube Gaussian boson sampling
- Anticoncentration and entanglement in Gaussian boson sampling
- Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction
BibTeX
@misc{zhou2026complexity,
title = {{On Complexity of Gaussian Sampling}},
author = {Huanjian Zhou and Taiji Suzuki},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20492},
eprint = {2610.20492},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20492},
}
RIS
TY - UNPB
TI - On Complexity of Gaussian Sampling
AU - Huanjian Zhou
AU - Taiji Suzuki
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20492
UR - https://arxiv.org/abs/2610.20492
AB - We study the number of exact matrix-vector queries needed to sample a centered d-dimensional Gaussian with condition number at most κ to total variation error ε. The best known algorithm uses O(min{d,√κlog(d/ε)}) queries, while the known lower bounds do not grow as ε→0 and match this bound only for κ≤ d^1/5−δ at constant accuracy. We introduce a construction based on a hidden determinant sign and prove a lower bound of Ω (min{d,√κlog(1+d/(√κ ε))}) uniformly for all d≥1, κ≥4, and 0<ε≤1/16. This bound matches the known upper bound up to constant factors whenever κ≤ d^2−δ for fixed δ∈(0,2), or ε≤ d^−c for fixed c>0. We also extend a recent fixed-spectrum construction with a hidden eigenbasis from κ=2 to 2≤κ≤ d^1−δ, for any fixed δ∈(0,1). This gives an Ω_δ(√κlog d) lower bound at constant accuracy that holds even when the spectrum of the precision matrix is known to the algorithm.
ER -