Duality of privacy amplification against quantum adversaries and data compression with quantum side information

Abstract

We show that the tasks of privacy amplification against quantum adversaries and data compression with quantum side information are dual in the sense that the ability to perform one implies the ability to perform the other. These are two of the most important primitives in classical information theory, and are shown to be connected by complementarity and the uncertainty principle in the quantum setting. Applications include a new uncertainty principle formulated in terms of smooth min- and max-entropies, as well as new conditions for approximate quantum error correction.

v2: Includes a derivation of an entropic uncertainty principle for smooth min- and max-entropies. Discussion of the Holevo-Schumacher-Westmoreland theorem removed

References in corpus (14)

• Unconditional Security Of Quantum Key Distribution Over Arbitrarily Long Distances
• Distillation of secret key and entanglement from quantum states
• The Uncertainty Principle in the Presence of Quantum Memory
• The operational meaning of min- and max-entropy
• A Fully Quantum Asymptotic Equipartition Property
• Conjectured Strong Complementary Information Tradeoff
• The mother of all protocols: Restructuring quantum information's family tree
• Duality Between Smooth Min- and Max-Entropies
• Classical data compression with quantum side information
• Coding Theorems of Quantum Information Theory
• One-Shot Classical Data Compression with Quantum Side Information and the Distillation of Common Randomness or Secret Keys
• Physical Underpinnings of Privacy
• On the Power of Quantum Memory
• Privacy Amplification, Private States, and the Uncertainty Principle

Cited by in corpus (23)

• Quantum Information Processing with Finite Resources -- Mathematical Foundations
• Noisy channel coding via privacy amplification and information reconciliation
• More Efficient Privacy Amplification with Less Random Seeds via Dual Universal Hash Function
• The information-theoretic costs of simulating quantum measurements
• One-Shot Classical Data Compression with Quantum Side Information and the Distillation of Common Randomness or Secret Keys
• Security analysis of the decoy method with the Bennett-Brassard 1984 protocol for finite key lengths
• Unification of different views of decoherence and discord
• Polar codes for private and quantum communication over arbitrary channels
• Dual universality of hash functions and its applications to quantum cryptography
• The Smooth Entropy Formalism for von Neumann Algebras
• Strong converse theorems using Rényi entropies
• Quantum polar codes for arbitrary channels
• Maximum nonlocality and minimum uncertainty using magic states
• Leftover hashing from quantum error correction: Unifying the two approaches to the security proof of quantum key distribution
• Duality of channels and codes
• Uncertainty relations: An operational approach to the error-disturbance tradeoff
• The Physics of Quantum Information: Complementarity, Uncertainty, and Entanglement
• Duality between source coding with quantum side information and c-q channel coding
• On privacy amplification, lossy compression, and their duality to channel coding
• Performance of polar codes for quantum and private classical communication
• Quantum Capacity of Partially Corrupted Quantum Network
• Single-Shot Secure Quantum Network Coding for General Multiple Unicast Network with Free One-Way Public Communication
• Equivalence of three classical algorithms with quantum side information: Privacy amplification, error correction, and data compression