Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.37122

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

Kuan Cheng, Ruiyang Wu

cs.CCquant-phSubmitted Oct 27, 2026• Announced Oct 28, 2026• 0 citations
arXivHTMLPDF

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.

AI Summary

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.

Little sign of AI-generated textAI use disclosed
Then we discussed with AI and used it substantially to develop the solutions and proofs as well as to do proof checking.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Quantum-Proof Extractors: Optimal up to Constant Factors

Kai-Min Chung, Cohen, Gil, Thomas Vidick +1 more

We give the first construction of a family of quantum-proof extractors that has optimal seed length dependence $O(\log(n/\varepsilon))$ on the input length $n$ and error $\varepsilon$. Our extractors support any min-entropy $k=Ω(\log{n} + \log^{1+α}(1/\varepsilon))$ and extract $m=(1-α)k$ bits that are $\varepsilon$-close to uniform, for any desired constant $α> 0$. Previous constructions had a quadratically worse seed length or were restricted to very large input min-entropy or very few output bits. Our result is based on a generic reduction showing that any strong classical condenser is automatically quantum-proof, with comparable parameters. The existence of such a reduction for extractors is a long-standing open question, here we give an affirmative answer for condensers. Once this reduction is established, to obtain our quantum-proof extractors one only needs to consider high entropy sources. We construct quantum-proof extractors with the desired parameters for such sources by extending a classical approach to extractor construction, based on the use of block-sources and sampling, to the quantum setting. Our extractors can be used to obtain improved protocols for device-independent randomness expansion and for privacy amplification.

arXiv:1605.04194•May 13, 2016•1 citation

Quantum secure non-malleable-extractors

Naresh Goud Boddu, Rahul Jain, Upendra Kapshikar

We construct several explicit quantum secure non-malleable-extractors. All the quantum secure non-malleable-extractors we construct are based on the constructions by Chattopadhyay, Goyal and Li [2015] and Cohen [2015]. 1) We construct the first explicit quantum secure non-malleable-extractor for (source) min-entropy $k \geq \textsf{poly}\left(\log \left( \frac{n}ε \right)\right)$ ($n$ is the length of the source and $ε$ is the error parameter). Previously Aggarwal, Chung, Lin, and Vidick [2019] have shown that the inner-product based non-malleable-extractor proposed by Li [2012] is quantum secure, however it required linear (in $n$) min-entropy and seed length. Using the connection between non-malleable-extractors and privacy amplification (established first in the quantum setting by Cohen and Vidick [2017]), we get a $2$-round privacy amplification protocol that is secure against active quantum adversaries with communication $\textsf{poly}\left(\log \left( \frac{n}ε \right)\right)$, exponentially improving upon the linear communication required by the protocol due to [2019]. 2) We construct an explicit quantum secure $2$-source non-malleable-extractor for min-entropy $k \geq n- n^{Ω(1)}$, with an output of size $n^{Ω(1)}$ and error $2^{- n^{Ω(1)}}$. 3) We also study their natural extensions when the tampering of the inputs is performed $t$-times. We construct explicit quantum secure $t$-non-malleable-extractors for both seeded ($t=d^{Ω(1)}$) as well as $2$-source case ($t=n^{Ω(1)}$).

arXiv:2109.03097•Sep 7, 2021•7 citations

Near-optimal extractors against quantum storage

Anindya De, Thomas Vidick

We show that Trevisan's extractor and its variants \cite{T99,RRV99} are secure against bounded quantum storage adversaries. One instantiation gives the first such extractor to achieve an output length $Θ(K-b)$, where $K$ is the source's entropy and $b$ the adversary's storage, together with a poly-logarithmic seed length. Another instantiation achieves a logarithmic key length, with a slightly smaller output length $Θ((K-b)/K^γ)$ for any $γ>0$. In contrast, the previous best construction \cite{TS09} could only extract $(K/b)^{1/15}$ bits. Some of our constructions have the additional advantage that every bit of the output is a function of only a polylogarithmic number of bits from the source, which is crucial for some cryptographic applications. Our argument is based on bounds for a generalization of quantum random access codes, which we call \emph{quantum functional access codes}. This is crucial as it lets us avoid the local list-decoding algorithm central to the approach in \cite{TS09}, which was the source of the multiplicative overhead.

arXiv:0911.4680•Nov 24, 2009•3 citations

Variations on classical and quantum extractors

Mario Berta, Omar Fawzi, Volkher B. Scholz +1 more

Many constructions of randomness extractors are known to work in the presence of quantum side information, but there also exist extractors which do not [Gavinsky et al., STOC'07]. Here we find that spectral extractors with a bound on the second largest eigenvalue - considered as an operator on the Hilbert-Schmidt class - are quantum-proof. We then discuss fully quantum extractors and call constructions that also work in the presence of quantum correlations decoupling. As in the classical case we show that spectral extractors are decoupling. The drawback of classical and quantum spectral extractors is that they always have a long seed, whereas there exist classical extractors with exponentially smaller seed size. For the quantum case, we show that there exists an extractor with extremely short seed size d = O(log(1/ε)), where ε > 0 denotes the quality of the randomness. In contrast to the classical case this is independent of the input size and min-entropy and matches the simple lower bound d ≥ log(1/ε).

arXiv:1402.3279•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•9 citations

Variations on classical and quantum extractors

Mario Berta, Omar Fawzi, Volkher B. Scholz +1 more

Many constructions of randomness extractors are known to work in the presence of quantum side information, but there also exist extractors which do not [Gavinsky et al., STOC'07]. Here we find that spectral extractors with a bound on the second largest eigenvalue - considered as an operator on the Hilbert-Schmidt class - are quantum-proof. We then discuss fully quantum extractors and call constructions that also work in the presence of quantum correlations decoupling. As in the classical case we show that spectral extractors are decoupling. The drawback of classical and quantum spectral extractors is that they always have a long seed, whereas there exist classical extractors with exponentially smaller seed size. For the quantum case, we show that there exists an extractor with extremely short seed size d = O(log(1/ε)), where ε > 0 denotes the quality of the randomness. In contrast to the classical case this is independent of the input size and min-entropy and matches the simple lower bound d ≥ log(1/ε).

•Jul 1, 2014•4 citations

Quantum-Proof Multi-Source Randomness Extractors in the Markov Model

Rotem Arnon-Friedman, Christopher Portmann, Volkher B. Scholz

Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered or the security of only some types of extractors was shown.

Leibniz international proceedings in informatics•Jan 1, 2016•17 citations
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 DDD, accuracy ε\varepsilonε and failure probability δ≤εδ\leq\varepsilonδ≤ε, our matrix sampler uses m+Oα(log⁡(D/δ))m+O_α(\log(D/δ))m+Oα​(log(D/δ)) random bits and Oα(ε−2−αlog⁡1+α(D/δ))O_α(\varepsilon^{-2-α}\log^{1+α}(D/δ))Oα​(ε−2−αlog1+α(D/δ)) samples, for any constant α>0α>0α>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\operatorname{poly} DpolyD dependence in the number of samples by O(log⁡1−γD)O(\log^{1-γ} D)O(log1−γD). Under the same scale of sample size, we can remove their log⁡log⁡D\log\log DloglogD factor in the length of the random seed. Our underlying strong quantum-proof extractor has output length n−Oα(a+log⁡(1/η))n-O_α(a+\log(1/η))n−Oα​(a+log(1/η)) and seed length at most (1+α)log⁡a+(2+α)log⁡(1/η)+Oα(1)(1+α)\log a+(2+α)\log(1/η)+O_α(1)(1+α)loga+(2+α)log(1/η)+Oα​(1) for nnn-bit sources with conditional min-entropy n−an-an−a and error ηηη.
We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as 2−Ω(n)2^{-Ω(n)}2−Ω(n), having optimal seed length O(log⁡(n/η))O(\log(n/η))O(log(n/η)) and output length Ω(n)Ω(n)Ω(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 DDD-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<δ≤ε≤1/20<\delta\leq\varepsilon\leq1/20<δ≤ε≤1/2, writing Λ=log⁡2(2D/δ)\Lambda=\log_2(2D/\delta)Λ=log2​(2D/δ), the construction gives explicit strong matrix samplers using r=m+Oα(Λ)r=m+O_\alpha(\Lambda)r=m+Oα​(Λ) random bits and t=Oα(ε−2−αΛ1+α/log⁡(Λ/ε))t=O_\alpha(\varepsilon^{-2-\alpha}\Lambda^{1+\alpha}/\log(\Lambda/\varepsilon))t=Oα​(ε−2−αΛ1+α/log(Λ/ε)) samples, for every fixed α>0\alpha>0α>0. Relative to the cited sampler constructions, this removes either a log⁡log⁡D\log\log DloglogD randomness factor or polynomial dimension dependence in sample complexity.
The underlying strong quantum-proof extractor for entropy k=n−ak=n-ak=n−a has seed length d≤(1+α)log⁡a+(2+α)log⁡(1/η)+Oα(1)d\leq(1+\alpha)\log a+(2+\alpha)\log(1/\eta)+O_\alpha(1)d≤(1+α)loga+(2+α)log(1/η)+Oα​(1) and output length n−Oα(a+log⁡(1/η))n-O_\alpha(a+\log(1/\eta))n−Oα​(a+log(1/η)). A separate construction handles every fixed entropy rate μ>0\mu>0μ>0, with seed Oμ(log⁡(n/η))O_\mu(\log(n/\eta))Oμ​(log(n/η)) and linear output, allowing error down to 2−cμn2^{-c_\mu n}2−cμ​n. Repeated extraction increases output to (1−θ)k(1-\theta)k(1−θ)k for fixed θ>0\theta>0θ>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.
We give the first construction of a family of quantum-proof extractors that has optimal seed length dependence O(log⁡(n/ε))O(\log(n/\varepsilon))O(log(n/ε)) on the input length nnn and error ε\varepsilonε. Our extractors support any min-entropy k=Ω(log⁡n+log⁡1+α(1/ε))k=Ω(\log{n} + \log^{1+α}(1/\varepsilon))k=Ω(logn+log1+α(1/ε)) and extract m=(1−α)km=(1-α)km=(1−α)k bits that are ε\varepsilonε-close to uniform, for any desired constant α>0α> 0α>0. Previous constructions had a quadratically worse seed length or were restricted to very large input min-entropy or very few output bits. Our result is based on a generic reduction showing that any strong classical condenser is automatically quantum-proof, with comparable parameters. The existence of such a reduction for extractors is a long-standing open question, here we give an affirmative answer for condensers. Once this reduction is established, to obtain our quantum-proof extractors one only needs to consider high entropy sources. We construct quantum-proof extractors with the desired parameters for such sources by extending a classical approach to extractor construction, based on the use of block-sources and sampling, to the quantum setting. Our extractors can be used to obtain improved protocols for device-independent randomness expansion and for privacy amplification.
We construct several explicit quantum secure non-malleable-extractors. All the quantum secure non-malleable-extractors we construct are based on the constructions by Chattopadhyay, Goyal and Li [2015] and Cohen [2015]. 1) We construct the first explicit quantum secure non-malleable-extractor for (source) min-entropy k≥poly(log⁡(nε))k \geq \textsf{poly}\left(\log \left( \frac{n}ε \right)\right)k≥poly(log(εn​)) (nnn is the length of the source and εεε is the error parameter). Previously Aggarwal, Chung, Lin, and Vidick [2019] have shown that the inner-product based non-malleable-extractor proposed by Li [2012] is quantum secure, however it required linear (in nnn) min-entropy and seed length. Using the connection between non-malleable-extractors and privacy amplification (established first in the quantum setting by Cohen and Vidick [2017]), we get a 222-round privacy amplification protocol that is secure against active quantum adversaries with communication poly(log⁡(nε))\textsf{poly}\left(\log \left( \frac{n}ε \right)\right)poly(log(εn​)), exponentially improving upon the linear communication required by the protocol due to [2019]. 2) We construct an explicit quantum secure 222-source non-malleable-extractor for min-entropy k≥n−nΩ(1)k \geq n- n^{Ω(1)}k≥n−nΩ(1), with an output of size nΩ(1)n^{Ω(1)}nΩ(1) and error 2−nΩ(1)2^{- n^{Ω(1)}}2−nΩ(1). 3) We also study their natural extensions when the tampering of the inputs is performed ttt-times. We construct explicit quantum secure ttt-non-malleable-extractors for both seeded (t=dΩ(1)t=d^{Ω(1)}t=dΩ(1)) as well as 222-source case (t=nΩ(1)t=n^{Ω(1)}t=nΩ(1)).
We show that Trevisan's extractor and its variants \cite{T99,RRV99} are secure against bounded quantum storage adversaries. One instantiation gives the first such extractor to achieve an output length Θ(K−b)Θ(K-b)Θ(K−b), where KKK is the source's entropy and bbb the adversary's storage, together with a poly-logarithmic seed length. Another instantiation achieves a logarithmic key length, with a slightly smaller output length Θ((K−b)/Kγ)Θ((K-b)/K^γ)Θ((K−b)/Kγ) for any γ>0γ>0γ>0. In contrast, the previous best construction \cite{TS09} could only extract (K/b)1/15(K/b)^{1/15}(K/b)1/15 bits. Some of our constructions have the additional advantage that every bit of the output is a function of only a polylogarithmic number of bits from the source, which is crucial for some cryptographic applications. Our argument is based on bounds for a generalization of quantum random access codes, which we call \emph{quantum functional access codes}. This is crucial as it lets us avoid the local list-decoding algorithm central to the approach in \cite{TS09}, which was the source of the multiplicative overhead.
Many constructions of randomness extractors are known to work in the presence of quantum side information, but there also exist extractors which do not [Gavinsky et al., STOC'07]. Here we find that spectral extractors with a bound on the second largest eigenvalue - considered as an operator on the Hilbert-Schmidt class - are quantum-proof. We then discuss fully quantum extractors and call constructions that also work in the presence of quantum correlations decoupling. As in the classical case we show that spectral extractors are decoupling. The drawback of classical and quantum spectral extractors is that they always have a long seed, whereas there exist classical extractors with exponentially smaller seed size. For the quantum case, we show that there exists an extractor with extremely short seed size d = O(log(1/ε)), where ε > 0 denotes the quality of the randomness. In contrast to the classical case this is independent of the input size and min-entropy and matches the simple lower bound d ≥ log(1/ε).
Many constructions of randomness extractors are known to work in the presence of quantum side information, but there also exist extractors which do not [Gavinsky et al., STOC'07]. Here we find that spectral extractors with a bound on the second largest eigenvalue - considered as an operator on the Hilbert-Schmidt class - are quantum-proof. We then discuss fully quantum extractors and call constructions that also work in the presence of quantum correlations decoupling. As in the classical case we show that spectral extractors are decoupling. The drawback of classical and quantum spectral extractors is that they always have a long seed, whereas there exist classical extractors with exponentially smaller seed size. For the quantum case, we show that there exists an extractor with extremely short seed size d = O(log(1/ε)), where ε > 0 denotes the quality of the randomness. In contrast to the classical case this is independent of the input size and min-entropy and matches the simple lower bound d ≥ log(1/ε).
Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered or the security of only some types of extractors was shown.