A Caltech Library Service

Variations on classical and quantum extractors

Berta, Mario and Fawzi, Omar and Scholz, Volkher and Szehr, Oleg (2014) Variations on classical and quantum extractors. In: 2014 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 1474-1478. ISBN 978-1-4799-5186-4.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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/ε).

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Berta, Mario0000-0002-0428-3429
Additional Information:© 2014 IEEE. We acknowledge discussions with Stephanie Wehner. MB and VBS acknowledges financial support by the German Science Foundation (grant CH 843/2-1), the Swiss National Science Foundation (grants PP00P2-128455, 20CH21-138799 (CHIST-ERA project CQC)), the Swiss National Center of Competence in Research 'Quantum Science and Technology (QSIT), and the Swiss State Secretariat for Education and Research supporting COST action MP1006. The research of OF is supported by the European Research Council grant No. 258932. VBS is supported by an ETH Postdoctoral Fellowship.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Deutsche Forschungsgemeinschaft (DFG)CH 843/2-1
Swiss National Science Foundation (SNSF)PP00P2-128455
Swiss National Science Foundation (SNSF)20CH21-138799
Swiss National Center of Competence in ResearchUNSPECIFIED
Swiss State Secretariat for Education and ResearchMP1006
European Research Council (ERC)258932
ETH Postdoctoral FellowshipUNSPECIFIED
Record Number:CaltechAUTHORS:20150227-083629007
Persistent URL:
Official Citation:Berta, M.; Fawzi, O.; Scholz, V.; Szehr, O., "Variations on classical and quantum extractors," Information Theory (ISIT), 2014 IEEE International Symposium on , vol., no., pp.1474,1478, June 29 2014-July 4 2014 doi: 10.1109/ISIT.2014.6875078 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:55319
Deposited By: Tony Diaz
Deposited On:04 Mar 2015 00:19
Last Modified:10 Nov 2021 20:44

Repository Staff Only: item control page