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 ε and failure probability δ≤ε, our matrix sampler uses m+Oα(log(D/δ)) random bits and Oα(ε−2−αlog1+α(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 poly D dependence in the number of samples by O(log1−γ D). Under the same scale of sample size, we can remove their loglog 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.
Related
- Hypercontractivity and entropy decay for infinite-dimensional quantum Gibbs samplers
- Dephasing-Enhanced Response and Phase Transitions in Quantum Boltzmann Samplers
- Size-independent Logarithmic Sobolev Inequalities for Quantum Gibbs Samplers
- Phantom Codes: Hardness, Rate Optimal qLDPC Constructions, and Distance Limits
- Ordering controlled by the measurement-feedback interval in quantum Boltzmann samplers
BibTeX
@misc{cheng2026matrix,
title = {{Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions}},
author = {Kuan Cheng and Ruiyang Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37122},
eprint = {2610.37122},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37122},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions
AU - Kuan Cheng
AU - Ruiyang Wu
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.37122
UR - https://arxiv.org/abs/2610.37122
AB - 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 ε and failure probability δ≤ε, our matrix sampler uses m+O_α(log(D/δ)) random bits and O_α(ε^−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 poly D dependence in the number of samples by O(log^1−γ D). Under the same scale of sample size, we can remove their loglog 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.
ER -