Quantum to Classical Randomness Extractors
arXiv:1111.2026 · doi:10.1109/TIT.2013.2291780
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.
arXiv comment6+31 pages, 2 tables, 1 figure, v2: improved converse parameters, typos corrected, new discussion, v3: new references
References in corpus (46)
- Random Numbers Certified by Bell's Theorem
- Black holes as mirrors: quantum information in random subsystems
- The Uncertainty Principle in the Presence of Quantum Memory
- Unconditionally secure quantum bit commitment is impossible
- Exact and Approximate Unitary 2-Designs: Constructions and Applications
- The operational meaning of min- and max-entropy
- Distance measures to compare real and ideal quantum processes
- Is Quantum Bit Commitment Really Possible?
- A new proof for the existence of mutually unbiased bases
- Min- and Max- Relative Entropies and a New Entanglement Monotone
- Insecurity of Quantum Secure Computations
- The Uncertainty Relation for Smooth Entropies
- Entropic uncertainty relations - A survey
- Evenly distributed unitaries: on the structure of unitary designs
- The uncertainty principle determines the non-locality of quantum mechanics
- Private Randomness Expansion With Untrusted Devices
- Random Quantum Circuits are Approximate 2-designs
- Randomness vs Non Locality and Entanglement
- Leftover Hashing Against Quantum Side Information
- A Fully Quantum Asymptotic Equipartition Property
- Quantum state merging and negative information
- The mother of all protocols: Restructuring quantum information's family tree
- Continuity of quantum conditional information
- Duality Between Smooth Min- and Max-Entropies
- On Quantum Fidelities and Channel Capacities
- Uncertainty relations from simple entropic properties
- A decoupling approach to the quantum capacity
- Unconditional security from noisy quantum storage
- Security of practical private randomness generation
- Trevisan's extractor in the presence of quantum side information
- Cryptography from Noisy Storage
- Distilling common randomness from bipartite quantum states
- Entropic uncertainty relations and locking: tight bounds for mutually unbiased bases
- Reexamination of Quantum Bit Commitment: the Possible and the Impossible
- Security and Composability of Randomness Expansion from Bell Inequalities
- Tema Con Variazioni: Quantum Channel Capacity
- Entanglement Cost of Quantum Channels
- The Bounded Storage Model in The Presence of a Quantum Adversary
- Decoupling with unitary approximate two-designs
- On the Power of Quantum Memory
- Implementation of two-party protocols in the noisy-storage model
- 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
- Making An Empty Promise With A Quantum Computer
- 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