Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0011014 · Physical Review A

Indeterminate-length quantum coding

Benjamin W. Schumacher, Michael D. Westmoreland

Published Sep 10, 2001• 37 citations
arXivHTMLPDF

Abstract

The quantum analogues of classical variable-length codes are indeterminate-length quantum codes, in which code words may exist in superpositions of different lengths. This paper explores some of their properties. The length observable for such codes is governed by a quantum version of the Kraft--McMillan inequality. Indeterminate-length quantum codes also provide an alternate approach to quantum data compression.

DOI
10.1103/physreva.64.042304

Related papers

On Lossless Quantum Data Compression and Quantum Variable‐Length Codes

Rudolf Ahlswede, Ning Cai

This chapter contains sections titled: Introduction Codes, Lengths, Kraft Inequality and von Neumann Entropy Bound The Codes Length Observable and Average Length of Codewords Kraft Inequality and von Neumann Entropy Bound Base Length Construct Long Codes from Variable-length Codes Lossless Quantum Data Compression, if the Decoder is Informed about the Base Lengths Code Analysis Based on the Base Length Lossless Quantum Data Compression with a Classical Helper Lossless Quantum Data Compression for Mixed State Sources A Result on Tradeoff between Quantum and Classical Resources in Lossy Quantum Data Compression References

Quantum Information Processing•Feb 17, 2005•0 citations

On Lossless Quantum Data Compression and Quantum Variable–Length Codes

Rudolf Ahlswede, Ning Cai

This chapter contains sections titled: Introduction Codes, Lengths, Kraft Inequality and von Neumann Entropy Bound The Codes Length Observable and Average Length of Codewords Kraft Inequality and von Neumann Entropy Bound Base Length Construct Long Codes from Variable-length Codes Lossless Quantum Data Compression, if the Decoder is Informed about the Base Lengths Code Analysis Based on the Base Length Lossless Quantum Data Compression with a Classical Helper Lossless Quantum Data Compression for Mixed State Sources A Result on Tradeoff between Quantum and Classical Resources in Lossy Quantum Data Compression References

Quantum Information Processing•Feb 21, 2003•2 citations

Quantum Bit Strings and Prefix-Free Hilbert Spaces

Markus P. Müller, Caroline Rogers

We give a mathematical framework for manipulating indeterminate-length quantum bit strings. In particular, we define prefixes, fragments, tensor products and concatenation of such strings of qubits, and study their properties and relationships. The results are then used to define prefix-free Hilbert spaces in a more general way than in previous work, without assuming the existence of a basis of length eigenstates. We prove a quantum analogue of the Kraft inequality, illustrate the results with some examples and discuss the relevance of prefix-free Hilbert spaces for lossless compression.

arXiv:0804.0022•Mar 31, 2008•6 citations

Lossless quantum data compression and variable-length coding

Kim Joris Boström, Timo Felbinger

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.

arXiv:quant-ph/0105026•Physical Review A•Feb 20, 2002•37 citations

Lossless quantum prefix compression for communication channels that are always open

Markus P. Müller, Caroline Rogers, Rajagopal Nagarajan

We describe a method for lossless quantum compression if the output of the information source is not known. We compute the best possible compression rate, minimizing the expected base length of the output quantum bit string (the base length of a quantum string is the maximal length in the superposition). This complements work by Schumacher and Westmoreland who calculated the corresponding rate for minimizing the output's average length. Our compressed code words are prefix-free indeterminate-length quantum bit strings which can be concatenated in the case of multiple sources. Therefore, we generalize the known theory of prefix-free quantum codes to the case where strings have indeterminate length. Moreover, we describe a communication model which allows the lossless transmission of the compressed code words. The benefit of compression is then the reduction of transmission errors in the presence of noise.

arXiv:0808.2003•Physical Review A•Jan 6, 2009•7 citations

Lossless quantum data compression with exponential penalization: an operational interpretation of the quantum Rényi entropy

Guido Bellomo, G. M. Bosyk, Federico Holik +1 more

Based on the problem of quantum data compression in a lossless way, we present here an operational interpretation for the family of quantum Rényi entropies. In order to do this, we appeal to a very general quantum encoding scheme that satisfies a quantum version of the Kraft-McMillan inequality. Then, in the standard situation, where one is intended to minimize the usual average length of the quantum codewords, we recover the known results, namely that the von Neumann entropy of the source bounds the average length of the optimal codes. Otherwise, we show that by invoking an exponential average length, related to an exponential penalization over large codewords, the quantum Rényi entropies arise as the natural quantities relating the optimal encoding schemes with the source description, playing an analogous role to that of von Neumann entropy.

arXiv:1710.01513•Scientific Reports•Nov 1, 2017•6 citations
The quantum analogues of classical variable-length codes are indeterminate-length quantum codes, in which code words may exist in superpositions of different lengths. This paper explores some of their properties. The length observable for such codes is governed by a quantum version of the Kraft--McMillan inequality. Indeterminate-length quantum codes also provide an alternate approach to quantum data compression.
This chapter contains sections titled: Introduction Codes, Lengths, Kraft Inequality and von Neumann Entropy Bound The Codes Length Observable and Average Length of Codewords Kraft Inequality and von Neumann Entropy Bound Base Length Construct Long Codes from Variable-length Codes Lossless Quantum Data Compression, if the Decoder is Informed about the Base Lengths Code Analysis Based on the Base Length Lossless Quantum Data Compression with a Classical Helper Lossless Quantum Data Compression for Mixed State Sources A Result on Tradeoff between Quantum and Classical Resources in Lossy Quantum Data Compression References
This chapter contains sections titled: Introduction Codes, Lengths, Kraft Inequality and von Neumann Entropy Bound The Codes Length Observable and Average Length of Codewords Kraft Inequality and von Neumann Entropy Bound Base Length Construct Long Codes from Variable-length Codes Lossless Quantum Data Compression, if the Decoder is Informed about the Base Lengths Code Analysis Based on the Base Length Lossless Quantum Data Compression with a Classical Helper Lossless Quantum Data Compression for Mixed State Sources A Result on Tradeoff between Quantum and Classical Resources in Lossy Quantum Data Compression References
We give a mathematical framework for manipulating indeterminate-length quantum bit strings. In particular, we define prefixes, fragments, tensor products and concatenation of such strings of qubits, and study their properties and relationships. The results are then used to define prefix-free Hilbert spaces in a more general way than in previous work, without assuming the existence of a basis of length eigenstates. We prove a quantum analogue of the Kraft inequality, illustrate the results with some examples and discuss the relevance of prefix-free Hilbert spaces for lossless compression.
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.
We describe a method for lossless quantum compression if the output of the information source is not known. We compute the best possible compression rate, minimizing the expected base length of the output quantum bit string (the base length of a quantum string is the maximal length in the superposition). This complements work by Schumacher and Westmoreland who calculated the corresponding rate for minimizing the output's average length. Our compressed code words are prefix-free indeterminate-length quantum bit strings which can be concatenated in the case of multiple sources. Therefore, we generalize the known theory of prefix-free quantum codes to the case where strings have indeterminate length. Moreover, we describe a communication model which allows the lossless transmission of the compressed code words. The benefit of compression is then the reduction of transmission errors in the presence of noise.
Based on the problem of quantum data compression in a lossless way, we present here an operational interpretation for the family of quantum Rényi entropies. In order to do this, we appeal to a very general quantum encoding scheme that satisfies a quantum version of the Kraft-McMillan inequality. Then, in the standard situation, where one is intended to minimize the usual average length of the quantum codewords, we recover the known results, namely that the von Neumann entropy of the source bounds the average length of the optimal codes. Otherwise, we show that by invoking an exponential average length, related to an exponential penalization over large codewords, the quantum Rényi entropies arise as the natural quantities relating the optimal encoding schemes with the source description, playing an analogous role to that of von Neumann entropy.