Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions

We establish an equivalence between matrix samplers and quantum-proof randomness extractors. The classical sampler--extractor equivalence is established by a seminal work of Zuckerman (Random Structures & Algorithms, 1997). Using this equivalence, we construct explicit strong matrix samplers with optimal randomness overhead and near-optimal sample complexity via constructing quantum-proof extractors. Specifically for matrix dimension $D$, accuracy $\varepsilon$ and failure probability $\delta\leq\varepsilon$, our matrix sampler uses $m+O_\alpha(\log(D/\delta))$ random bits and $O_\alpha(\varepsilon^{-2-\alpha}\log^{1+\alpha}(D/\delta))$ samples, for any constant $\alpha>0$. Compared with the matrix sampler of Xun and Zuckerman (CCC 2025), our construction has improvements in two aspects. Under the same optimal random seed length, we can replace the $\operatorname{poly} D$ dependence in the number of samples by $O(\log^{1-\gamma} D)$. Under the same scale of sample size, we can remove their $\log\log D$ factor in the length of the random seed. Our underlying strong quantum-proof extractor has output length $n-O_\alpha(a+\log(1/\eta))$ and seed length at most $(1+\alpha)\log a+(2+\alpha)\log(1/\eta)+O_\alpha(1)$ for $n$-bit sources with conditional min-entropy $n-a$ and error $\eta$. We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as $2^{-\Omega(n)}$, having optimal seed length $O(\log(n/\eta))$ and output length $\Omega(n)$, improving previous constructions.