Lossless quantum data compression and variable-length coding

Abstract

In order to compress quantum messages without loss of information it is necessary to allow the length of the encoded messages to vary. We develop a general framework for variable-length quantum messages in close analogy to the classical case and show that lossless compression is only possible if the message to be compressed is known to the sender. The lossless compression of an ensemble of messages is bounded from below by its von-Neumann entropy. We show that it is possible to reduce the number of qbits passing through a quantum channel even below the von-Neumann entropy by adding a classical side-channel. We give an explicit communication protocol that realizes lossless and instantaneous quantum data compression and apply it to a simple example. This protocol can be used for both online quantum communication and storage of quantum data.

16 pages, 5 figures

Cited by in corpus (12)

• Occam's Quantum Razor: How Quantum Mechanics can reduce the complexity of classical models
• Quantum rate distortion, reverse Shannon theorems, and source-channel separation
• Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
• Universal approximation of multi-copy states and universal quantum lossless data compression
• Quantum Kolmogorov Complexity and the Quantum Turing Machine
• Quantum information is incompressible without errors
• Lossless Quantum Prefix Compression for Communication Channels that are Always Open
• Energy Requirements for Quantum Data Compression and 1-1 Coding
• Optimality in Quantum Data Compression using Dynamical Entropy
• Quantum spectral analysis: frequency in time, with applications to signal and image processing
• On the Quantum Kolmogorov Complexity of Classical Strings
• Second Quantized Kolmogorov Complexity