Quantum-Proof Extractors: Optimal up to Constant Factors

Abstract

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.

The paper has been withdrawn due to an error in the proof of Lemma 3.4 (step going from second-last to last centered equations), which invalidates the main result