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

International Journal of Quantum Information

LOSSLESS QUANTUM DATA COMPRESSION AND QUANTUM KOLMOGOROV COMPLEXITY

Caroline Rogers, Rajagopal Nagarajan

Published Mar 1, 2011• 2 citations
Publisher

Abstract

We show that the optimal rate of lossless quantum data compression is closely related to Berthiaume, van Dam and Laplante's quantum Kolmogorov complexity. We show that: • The expected quantum Kolmogorov complexity of a mixture is close to the optimal rate of lossless data compression of that mixture. • If quantum Kolmogorov complexity obeys some inequality, then so does the optimal rate of lossless quantum data compression.

DOI
10.1142/s0219749911007848

Related papers

Kolmogorov complexity of unitary transformations in quantum computing

Alexei Kaltchenko

We introduce a notion of Kolmogorov complexity of unitary transformation, which can (roughly) be understood as the least possible amount of information required to fully describe and reconstruct a given finite unitary transformation. In the context of quantum computing, it corresponds to the least possible amount of data to define and describe a quantum circuit or quantum computer program. Our Kolmogorov complexity of unitary transformation is built upon Kolmogorov "qubit complexity" of Berthiaume, W. Van Dam and S. Laplante via mapping from unitary transformations to positive operators, which are subsequently "purified". We discuss the optimality of our notion of Kolmogorov complexity in a broad sense and obtain a simple complexity bound.

arXiv:2110.05937•Oct 10, 2021•2 citations

On Kolmogorov Complexity of Unitary Transformations in Quantum Computing

Alexei Kaltchenko

We introduce a notion of Kolmogorov complexity of unitary transformation, which can (roughly) be understood as the least possible amount of information required to fully describe and reconstruct a given finite unitary transformation. In the context of quantum computing, it corresponds to the least possible amount of data to define and describe a quantum circuit or quantum computer program. Our Kolmogorov complexity of unitary transformation is built upon Kolmogorov "qubit complexity" of Berthiaume, W. Van Dam and S. Laplante via mapping from unitary transformations to unnormalized density operators, which are subsequently "purified" into unnormalized vectors in Hilbert space. We discuss the optimality of our notion of Kolmogorov complexity in a broad sense.

i-manager’s Journal on Mathematics•Jan 1, 2022•0 citations

Lossless Quantum Compression

Caroline Rogers, Rajagopal Nagarajan

We describe lossless quantum compression of unknown mixtures (of non-orthogonal states) and give an expression of the optimal rate of compression.

arXiv:quant-ph/0508170•Aug 23, 2005•2 citations

On Lossless Quantum Data Compression With a Classical Helper

Rudolf Ahlswede, N. Cai

After K. Bostro/spl uml/m and T. Felbinger observed that lossless quantum data compression does not exist unless decoders know the lengths of codewords, they introduced a classical noiseless channel to inform the decoder of a quantum source about the lengths of codewords. In this paper we analyze their codes and present: 1) a sufficient and necessary condition for the existence of such codes for given lists of lengths of codes; 2) a characterization of the optimal compression rate for their codes. However our main contribution is a more efficient way to use the classical channel. We propose a more general coding scheme. It turned out that the optimal compression can always be achieved by a code obtained by this scheme. A von Neumann entropy lower bound to rates of our codes and a necessary and sufficient condition to achieve the bound are obtained. The gap between this lower bound and the compression rates is also well analyzed. For a special family of quantum sources we provide a sharper lower bound in terms of Shannon entropy. Finally, we propose some problems for further research.

IEEE Transactions on Information Theory•Jun 1, 2004•11 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 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
We show that the optimal rate of lossless quantum data compression is closely related to Berthiaume, van Dam and Laplante's quantum Kolmogorov complexity. We show that: • The expected quantum Kolmogorov complexity of a mixture is close to the optimal rate of lossless data compression of that mixture. • If quantum Kolmogorov complexity obeys some inequality, then so does the optimal rate of lossless quantum data compression.
We introduce a notion of Kolmogorov complexity of unitary transformation, which can (roughly) be understood as the least possible amount of information required to fully describe and reconstruct a given finite unitary transformation. In the context of quantum computing, it corresponds to the least possible amount of data to define and describe a quantum circuit or quantum computer program. Our Kolmogorov complexity of unitary transformation is built upon Kolmogorov "qubit complexity" of Berthiaume, W. Van Dam and S. Laplante via mapping from unitary transformations to positive operators, which are subsequently "purified". We discuss the optimality of our notion of Kolmogorov complexity in a broad sense and obtain a simple complexity bound.
We introduce a notion of Kolmogorov complexity of unitary transformation, which can (roughly) be understood as the least possible amount of information required to fully describe and reconstruct a given finite unitary transformation. In the context of quantum computing, it corresponds to the least possible amount of data to define and describe a quantum circuit or quantum computer program. Our Kolmogorov complexity of unitary transformation is built upon Kolmogorov "qubit complexity" of Berthiaume, W. Van Dam and S. Laplante via mapping from unitary transformations to unnormalized density operators, which are subsequently "purified" into unnormalized vectors in Hilbert space. We discuss the optimality of our notion of Kolmogorov complexity in a broad sense.
After K. Bostro/spl uml/m and T. Felbinger observed that lossless quantum data compression does not exist unless decoders know the lengths of codewords, they introduced a classical noiseless channel to inform the decoder of a quantum source about the lengths of codewords. In this paper we analyze their codes and present: 1) a sufficient and necessary condition for the existence of such codes for given lists of lengths of codes; 2) a characterization of the optimal compression rate for their codes. However our main contribution is a more efficient way to use the classical channel. We propose a more general coding scheme. It turned out that the optimal compression can always be achieved by a code obtained by this scheme. A von Neumann entropy lower bound to rates of our codes and a necessary and sufficient condition to achieve the bound are obtained. The gap between this lower bound and the compression rates is also well analyzed. For a special family of quantum sources we provide a sharper lower bound in terms of Shannon entropy. Finally, we propose some problems for further research.
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