International Journal of Quantum Information

LOSSLESS QUANTUM DATA COMPRESSION AND QUANTUM KOLMOGOROV COMPLEXITY

Caroline Rogers, Rajagopal Nagarajan

Published Mar 1, 2011• 2 citations

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.05937Oct 10, 20211 citation

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 MathematicsJan 1, 20220 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/0508170Aug 23, 20051 citation

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 TheoryJun 1, 200410 citations

QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS

Caterina E. Mora, Hans J. Briegel, Barbara Kraus

Kolmogorov complexity is a measure of the information contained in a binary string. We investigate here the notion of quantum Kolmogorov complexity, a measure of the information required to describe a quantum state. We show that for any definition of quantum Kolmogorov complexity measuring the number of classical bits required to describe a pure quantum state, there exists a pure n-qubit state which requires exponentially many bits of description. This is shown by relating the classical communication complexity to the quantum Kolmogorov complexity. Furthermore, we give some examples of how quantum Kolmogorov complexity can be applied to prove results in different fields, such as quantum computation and thermodynamics, and we generalize it to the case of mixed quantum states.

arXiv:quant-ph/0610109International Journal of Quantum InformationOct 1, 200743 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.01513Oct 4, 20171 citation