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

Abstract

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 $δ\leq\varepsilon$, our matrix sampler uses $m+O_α(\log(D/δ))$ random bits and $O_α(\varepsilon^{-2-α}\log^{1+α}(D/δ))$ samples, for any constant $α>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-γ} 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_α(a+\log(1/η))$ and seed length at most $(1+α)\log a+(2+α)\log(1/η)+O_α(1)$ for $n$-bit sources with conditional min-entropy $n-a$ and error $η$. We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as $2^{-Ω(n)}$, having optimal seed length $O(\log(n/η))$ and output length $Ω(n)$, improving previous constructions.

The paper asks which sampling notion corresponds to extraction secure against quantum side information, and uses that connection to improve explicit constructions. It establishes a two-way correspondence, with parameter losses, between $D$-dimensional matrix averaging samplers and extractors secure against bounded quantum storage. Strong sampling corresponds to strong extraction; conditional-min-entropy extractors imply matrix samplers through a dimension-dependent entropy loss. For $0<\delta\leq\varepsilon\leq1/2$, writing $\Lambda=\log_2(2D/\delta)$, the construction gives explicit strong matrix samplers using $r=m+O_\alpha(\Lambda)$ random bits and $t=O_\alpha(\varepsilon^{-2-\alpha}\Lambda^{1+\alpha}/\log(\Lambda/\varepsilon))$ samples, for every fixed $\alpha>0$. Relative to the cited sampler constructions, this removes either a $\log\log D$ randomness factor or polynomial dimension dependence in sample complexity. The underlying strong quantum-proof extractor for entropy $k=n-a$ has seed length $d\leq(1+\alpha)\log a+(2+\alpha)\log(1/\eta)+O_\alpha(1)$ and output length $n-O_\alpha(a+\log(1/\eta))$. A separate construction handles every fixed entropy rate $\mu>0$, with seed $O_\mu(\log(n/\eta))$ and linear output, allowing error down to $2^{-c_\mu n}$. Repeated extraction increases output to $(1-\theta)k$ for fixed $\theta>0$. The correspondence encodes operator-norm witnesses as quantum states and converts distinguishing measurements into matrix tests. Constructions combine multilinear polynomial evaluation, weak designs, quantum entropy sampling, reverse-order seed expansion, high-entropy extraction, and limited-independence moment bounds. The small-deficiency output guarantee is meaningful only sufficiently near full entropy. Constant-rate results require sufficiently large inputs and sufficiently small error exponents; hidden constants depend on fixed parameters. The main sampler retains a fixed-exponent slack in sample complexity.