We construct a strong extractor against quantum storage that works for every min-entropy $k$ , has logarithmic seed length, and outputs $Ω(k)$ bits, provided that the quantum adversary has at most $βk$ qubits of memory, for any $β< \half$. The construction works by first condensing the source (with minimal entropy-loss) and then applying an extractor that works well against quantum adversaries when the source is close to uniform. We also obtain an improved construction of a strong quantum-proof extractor in the high min-entropy regime. Specifically, we construct an extractor that uses a logarithmic seed length and extracts $Ω(n)$ bits from any source over $\B^n$, provided that the min-entropy of the source conditioned on the quantum adversary's state is at least $(1-β) n$ , for any $β< \half$.We construct a strong extractor against quantum storage that works for every min-entropy $k$, has logarithmic seed length, and outputs $Ω(k)$ bits, provided that the quantum adversary has at most $βk$ qubits of memory, for any $β< \half$. The construction works by first condensing the source (with minimal entropy-loss) and then applying an extractor that works well against quantum adversaries when the source is close to uniform. We also obtain an improved construction of a strong quantum-proof extractor in the high min-entropy regime. Specifically, we construct an extractor that uses a logarithmic seed length and extracts $Ω(n)$ bits from any source over $\B^n$, provided that the min-entropy of the source conditioned on the quantum adversary's state is at least $(1-β) n$, for any $β< \half$.

arXiv:1004.3737Apr 21, 20101 citation

A simple quantum eraser

Wendell G. Holladay

Physics Letters ADec 1, 199314 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/ε).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/ε).

Jan 1, 20144 citations

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

Kuan Cheng, Ruiyang Wu

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.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.

cs.CCCross-listedarXiv:2610.37122Oct 28, 20260 citations

Mining quantum stuff

Physics WorldDec 1, 20130 citations

We construct a strong extractor against quantum storage that works for every min-entropy

k

, has logarithmic seed length, and outputs

Ω(k)

bits, provided that the quantum adversary has at most

βk

qubits of memory, for any $β< \half$. The construction works by first condensing the source (with minimal entropy-loss) and then applying an extractor that works well against quantum adversaries when the source is close to uniform. We also obtain an improved construction of a strong quantum-proof extractor in the high min-entropy regime. Specifically, we construct an extractor that uses a logarithmic seed length and extracts

Ω(n)

bits from any source over $\B^n$, provided that the min-entropy of the source conditioned on the quantum adversary's state is at least

(1-β) n

, for any $β< \half$.

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.