Imagine you have a massive spreadsheet — millions of rows — and you need to estimate the average of every column simultaneously. Classical sampling theory says: pick a few rows at random, compute the column averages, and you'll be close. But what if the columns aren't independent numbers — they're entries in a giant matrix, and you need to estimate a matrix-valued average? That's the matrix sampler problem, and it's exponentially harder because matrices don't commute. Now imagine an adversary who holds a quantum computer entangled with your randomness source. Can your extractor still distill clean random bits? That's the quantum-proof extractor problem. This paper proves these two problems are, at a deep structural level, the same thing. The core claim: Zuckerman's 1997 equivalence between classical samplers and randomness extractors generalizes to the matrix/quantum setting. Matrix samplers — which estimate matrix-valued averages from a few random samples — are equivalent to quantum-proof extractors — which produce clean randomness even against quantum side information. The authors prove this correspondence formally, then exploit it to construct explicit objects on both sides that are near-optimal in their parameters. The concrete improvements are surgical. The prior state-of-the-art matrix sampler, by Xun and Zuckerman (CCC 2025), had a poly(D) dependence in the number of samples and a log-log(D) overhead in random seed length. This paper replaces poly(D) with O(log^{1−γ} D) in sample count — an exponential improvement — and strips out the log-log(D) factor from the seed. The underlying quantum-proof extractor achieves output length n − O(a + log(1/η)) with seed length (1+α)log a + (2+α)log(1/η) + O(1), for any constant α > 0. For constant entropy rate sources, they get optimal O(log(n/η)) seed length and Ω(n) output — the first construction to hit these parameters simultaneously against quantum adversaries. Architecturally, this lives in the explicit construction tradition of pseudorandomness theory. The tools are seeded extractors built from algebraic or combinatorial objects (expander graphs, polynomial hashing, condensers), composed via the sampler-extractor bridge. The key structural insight is that the operator norm estimates required for matrix sampling translate directly into the quantum-proof condition on extractors — the non-commutativity of matrices maps onto the entanglement structure of quantum side information. No new computational model is introduced; the advance is in tightening the parameters of known constructions by exploiting the equivalence more aggressively. Integrity is solid for theory work: results are proven mathematically, not simulated. The baseline comparison is explicit and honest — Xun and Zuckerman (CCC 2025) is the named prior art, and the improvements are stated in precise asymptotic terms. The paper does not claim computational experiments or benchmarks because none are needed; the claims are existential and constructive, provable from definitions. The main limitation is the Oα notation, which hides constants depending on the arbitrary parameter α > 0 — the practical constants matter for applications but are not evaluated. The milestone question for this line of work is whether these extractors become practical building blocks for quantum cryptography and quantum complexity theory. The theoretical parameters are now nearly tight — the gap between construction and information-theoretic lower bound is a small polynomial in the error parameter. The next real unlock is either closing that polynomial gap entirely (achieving truly optimal constructions) or demonstrating that these extractors plug into concrete quantum key distribution or device-independent randomness protocols with measurable performance gains. The experiment the authors did not run — and likely are saving for follow-up — is computing explicit constants hidden by the Oα notation and evaluating whether the constructions are practical at real-world parameters (e.g., D = 2^{128} for cryptographic applications). This is the gap between asymptotic optimality and deployable code, and it's the obvious next paper.
