A Caltech Library Service

Quantum-proof randomness extractors via operator space theory

Berta, Mario and Fawzi, Omar and Scholz, Volkher B. (2017) Quantum-proof randomness extractors via operator space theory. IEEE Transactions on Information Theory, 63 (4). pp. 2480-2503. ISSN 0018-9448.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Quantum-proof randomness extractors are an important building block for classical and quantum cryptography as well as device independent randomness amplification and expansion. Furthermore, they are also a useful tool in quantum Shannon theory. It is known that some extractor constructions are quantum-proof whereas others are provably not [Gavinsky et al., STOC’07]. We argue that the theory of operator spaces offers a natural framework for studying to what extent extractors are secure against quantum adversaries: we first phrase the definition of extractors as a bounded norm condition between normed spaces, and then show that the presence of quantum adversaries corresponds to a completely bounded norm condition between operator spaces. From this, we show that very high min-entropy extractors as well as extractors with small output are always (approximately) quantum-proof. We also study a generalization of extractors called randomness condensers. We phrase the definition of condensers as a bounded norm condition and the definition of quantum-proof condensers as a completely bounded norm condition. Seeing condensers as bipartite graphs, we then find that the bounded norm condition corresponds to an instance of a well-studied combinatorial problem, called bipartite densest subgraph. Furthermore, using the characterization in terms of operator spaces, we can associate to any condenser a Bell inequality (two-player game), such that classical and quantum strategies are in one-to-one correspondence with classical and quantum attacks on the condenser. Hence, we get for every quantum-proof condenser (which includes in particular quantum-proof extractors) a Bell inequality that cannot be violated by quantum mechanics.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Berta, Mario0000-0002-0428-3429
Additional Information:© 2016 IEEE. Manuscript received March 29, 2015; revised June 23, 2016; accepted September 24, 2016. Date of publication November 11, 2016; date of current version March 15, 2017. Berta was supported in part by the SNSF through a fellowship, in part by the Institute for Quantum Information and Matter, in part by an NSF Physics Frontiers Center under Grant PHY-1125565, in part by the Gordon and Betty Moore Foundation under Grant GBMF-12500028, and in part by the Army Research Office grant for Research on Quantum Algorithms at IQIM under Grant W911NF-12-1-0521. V.B. Scholz and O. Fawzi were supported in part by the European Research Council grant No. 258932 and in part by the EU under the Project Randomness and Quantum Entanglement (RAQUEL). V.B. Scholz was in addition supported by an ETH Fellowship. The authors acknowledge discussions with Matthias Christandl, Fabian Furrer, Patrick Hayden, Christopher Portmann, Renato Renner, Oleg Szehr, Marco Tomamichel, Thomas Vidick, Stephanie Wehner, Reinhard Werner, and Andreas Winter. Part of this work was done while OF and VBS were visiting the Institute for Quantum Information and Matter at Caltech and they would like to thank John Preskill and Thomas Vidick for their hospitality.
Group:Institute for Quantum Information and Matter, IQIM
Funding AgencyGrant Number
Swiss National Science Foundation (SNSF)UNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
Army Research Office (ARO)W911NF-12-1-0521
European Research Council (ERC)258932
European UnionRAQUEL
Subject Keywords:Quantum Mechanics, Quantum Entanglement, Cryptography, Pseudorandomness
Record Number:CaltechAUTHORS:20160622-165817214
Persistent URL:
Official Citation:M. Berta, O. Fawzi and V. B. Scholz, "Quantum-Proof Randomness Extractors via Operator Space Theory," in IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 2480-2503, April 2017. doi: 10.1109/TIT.2016.2627531 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:68615
Deposited By: Jacquelyn O'Sullivan
Deposited On:27 Jun 2016 17:03
Last Modified:16 Aug 2017 23:52

Repository Staff Only: item control page