{"id":"arxiv/2610.37122","url":"https://arxiv.org/abs/2610.37122","tags":["cs.CC","quant-ph"],"score":0,"title":"Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions","domain":"cs.CC","source":"arxiv","authors":["Kuan Cheng","Ruiyang Wu"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-27","reactions":{}}