Quantum to Classical Randomness Extractors

Abstract

The goal of randomness extraction is to distill (almost) perfect randomness from a weak source of randomness. When the source yields a classical string X, many extractor constructions are known. Yet, when considering a physical randomness source, X is itself ultimately the result of a measurement on an underlying quantum system. When characterizing the power of a source to supply randomness it is hence a natural question to ask, how much classical randomness we can extract from a quantum system. To tackle this question we here take on the study of quantum-to-classical randomness extractors (QC-extractors). We provide constructions of QC-extractors based on measurements in a full set of mutually unbiased bases (MUBs), and certain single qubit measurements. As the first application, we show that any QC-extractor gives rise to entropic uncertainty relations with respect to quantum side information. Such relations were previously only known for two measurements. As the second application, we resolve the central open question in the noisy-storage model [Wehner et al., PRL 100, 220502 (2008)] by linking security to the quantum capacity of the adversary's storage device.

6+31 pages, 2 tables, 1 figure, v2: improved converse parameters, typos corrected, new discussion, v3: new references

References in corpus (18)

• Black holes as mirrors: quantum information in random subsystems
• The uncertainty principle determines the non-locality of quantum mechanics
• Evenly distributed unitaries: on the structure of unitary designs
• Private Randomness Expansion With Untrusted Devices
• Leftover Hashing Against Quantum Side Information
• The mother of all protocols: Restructuring quantum information's family tree
• Uncertainty relations from simple entropic properties
• Security of practical private randomness generation
• Cryptography from Noisy Storage
• Entropic uncertainty relations and locking: tight bounds for mutually unbiased bases
• Security and Composability of Randomness Expansion from Bell Inequalities
• Entanglement Cost of Quantum Channels
• The Bounded Storage Model in The Presence of a Quantum Adversary
• Decoupling with unitary approximate two-designs
• Higher entropic uncertainty relations for anti-commuting observables
• The Link between Entropic Uncertainty and Nonlocality
• Security of quantum bit string commitment depends on the information measure
• Achieving the physical limits of the bounded-storage model

Cited by in corpus (23)

• Quantum Random Number Generators
• Entropic Uncertainty Relations and their Applications
• Quantum Cryptography Beyond Quantum Key Distribution
• Entanglement sampling and applications
• An equality between entanglement and uncertainty
• Catalytic Decoupling of Quantum Information
• Device-independent two-party cryptography secure against sequential attacks
• Convex-split and hypothesis testing approach to one-shot quantum measurement compression and randomness extraction
• Distributed Private Randomness Distillation
• Conditional Decoupling of Quantum Information
• Secure uniform random number extraction via incoherent strategies
• Quantum-proof randomness extractors via operator space theory
• Efficient methods for one-shot quantum communication
• Conditional entropic uncertainty relations for Tsallis entropies
• Variations on Classical and Quantum Extractors
• Quantum preparation uncertainty and lack of information
• Decoupling by local random unitaries without simultaneous smoothing, and applications to multi-user quantum information tasks
• Reliability Function of Quantum Information Decoupling via the Sandwiched Rényi Divergence
• Fault tolerant quantum data locking
• Loss of Information in Quantum Guessing Game
• "Nonlocality-of-a-single-photon" based Quantum Key Distribution and Random Number Generation schemes and their device-independent security analysis
• Limitations for private randomness repeaters
• Device-independent Shannon entropy certification