A Caltech Library Service

Quantum-Proof Extractors: Optimal up to Constant Factors

Chung, Kai-Min and Cohen, Gil and Vidick, Thomas and Wu, Xiaodi (2016) Quantum-Proof Extractors: Optimal up to Constant Factors. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We give the first construction of a family of quantum-proof extractors that has optimal seed length dependence O(log(n/ǫ)) on the input length n and error ǫ. Our extractors support any min-entropy k = Ω(log n + log1+α (1/ǫ)) and extract m = (1 − α)k bits that are ǫ-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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:We thank Yanlin Chen, Yi-Hsiu Chen, Anindya De, Andrew Drucker, Robert K¨onig, Ashwin Nayak, Salil Vadhan, and Nengkun Yu for helpful discussions. Part of the research was conducted when KC and XW were visiting the Institute for Quantum Computing, University of Waterloo and we thank IQC for its hospitality. Part of the research was conducted while XW was affiliated with the Simons Institute for the Theory of Computing, University of California, Berkeley and with the Center for Theoretical Physics, Massachusetts Institute of Technology. TV was partially supported by NSF CAREER Grant CCF-1553477, an AFOSR YIP award, and the IQIM, an NSF Physics Frontiers Center (NFS Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028).
Group:UNSPECIFIED, Institute for Quantum Information and Matter
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)UNSPECIFIED
Gordon and Betty Moore Foundation12500028
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Record Number:CaltechAUTHORS:20160517-182619760
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:67161
Deposited By: Joy Painter
Deposited On:18 May 2016 16:28
Last Modified:04 Jun 2020 10:14

Repository Staff Only: item control page