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/0209029 · Physical Review A

Classical data compression with quantum side information

Igor Devetak, Andreas Winter

Published Oct 3, 2003• 118 citations
arXivHTMLPDF

Abstract

The problem of classical data compression when the decoder has quantum side information at his disposal is considered. This is a quantum generalization of the classical Slepian-Wolf theorem. The optimal compression rate is found to be reduced from the Shannon entropy of the source by the Holevo information between the source and side information.

DOI
10.1103/physreva.68.042301

Related papers

Channel Simulation With Quantum Side Information

Zhicheng Luo, Igor Devetak

We study and solve the problem of classical channel simulation with quantum side information at the receiver. This is a generalization of both the classical reverse Shannon theorem, and the classical-quantum Slepian-Wolf problem. The optimal noiseless communication rate is found to be reduced from the mutual information between the channel input and output by the Holevo information between the channel output and the quantum side information. Our main theorem has two important corollaries. The first is a quantum generalization of the Wyner-Ziv problem: rate-distortion theory with quantum side information. The second is an alternative proof of the tradeoff between classical communication and common randomness distilled from a quantum state. The fully quantum generalization of the problem considered isquantumstateredistribution. Here the sender and receiver share a mixed quantum state and the sender wants to transfer part of her state to the receiver using entanglement and quantum communication. We present outer and inner bounds on the achievable rate pairs.

arXiv:quant-ph/0611008•IEEE Transactions on Information Theory•Feb 26, 2009•50 citations

Non-Asymptotic Classical Data Compression With Quantum Side Information

Hao–Chung Cheng, Eric P. Hanson, Nilanjana Datta +1 more

In this paper, we analyze classical data compression with quantum side information (also known as the classical-quantum Slepian–Wolf protocol) in the so-called large and moderate deviation regimes. In the non-asymptotic setting, the protocol involves compressing classical sequences of finite length$n$and decoding them with the assistance of quantum side information. In the large deviation regime, the compression rate is fixed, and we obtain bounds on the error exponent function, which characterizes the minimal probability of error as a function of the rate. Devetak and Winter showed that the asymptotic data compression limit for this protocol is given by a conditional entropy. For any protocol with a rate below this quantity, the probability of error converges to one asymptotically and its speed of convergence is given by the strong converse exponent function. We obtain finite blocklength bounds on this function, and determine exactly its asymptotic value. In the moderate deviation regime for the compression rate, the latter is no longer considered to be fixed. It is allowed to depend on the blocklength$n$, but assumed to decay slowly to the asymptotic data compression limit. Starting from a rate above this limit, we determine the speed of convergence of the error probability to zero and show that it is given in terms of the conditional information variance.

arXiv:1803.07505•IEEE Transactions on Information Theory•Nov 17, 2020•28 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•10 citations

One-Shot Classical Data Compression With Quantum Side Information and the Distillation of Common Randomness or Secret Keys

Joseph M. Renes, Renato Renner

The task of compressing classical information in the one-shot scenario is studied in the setting where the decompressor additionally has access to some given quantum side information. In this hybrid classical-quantum version of the famous Slepian-Wolf problem, the smooth max entropy is found to govern the number of bits into which classical information can be compressed so that it can be reliably recovered from the compressed version and quantum side information. Combining this result with known results on privacy amplification then yields tight bounds on the amount of common randomness and secret key that can be recovered in one shot from hybrid classical-quantum systems using one-way classical communication.

arXiv:1008.0452•IEEE Transactions on Information Theory•Feb 28, 2012•71 citations

One-Shot Classical Data Compression with Quantum Side Information and the Distillation of Common Randomness or Secret Keys

Joseph M. Renes, Renato Renner

The task of compressing classical information in the one-shot scenario is studied in the setting where the decompressor additionally has access to some given quantum side information. In this hybrid classical-quantum version of the famous Slepian-Wolf problem, the smooth max-entropy is found to govern the number of bits into which classical information can be compressed so that it can be reliably recovered from the compressed version and quantum side information. Combining this result with known results on privacy amplification then yields bounds on the amount of common randomness and secret key that can be recovered in one-shot from hybrid classical-quantum systems using one-way classical communication.

•Aug 14, 2016•50 citations

Error Exponents and Strong Converse Exponents for Classical Data Compression with Quantum Side Information

Hao–Chung Cheng, Eric P. Hanson, Nilanjana Datta +1 more

In this paper, we analyze classical data compression with quantum side information (also known as the classical-quantum Slepian- Wolf protocol) in the so-called large and moderate deviation regimes. In the non-asymptotic setting, the protocol involves compressing classical sequences of finite length n and decoding them with the assistance of quantum side information. In the large deviation regime, the compression rate is fixed, and we obtain bounds on the error exponent function, which characterizes the minimal probability of error as a function of the rate. Devetak and Winter showed that the asymptotic data compression limit for this protocol is given by a conditional entropy. For any protocol with a rate below this quantity, the probability of error converges to one asymptotically and its speed of convergence is given by the strong converse exponent function. We obtain finite blocklength bounds on this function, and determine exactly its asymptotic value, thus improving on previous results by Tomamichel. In the moderate deviation regime for the compression rate, the latter is no longer considered to be fixed. It is allowed to depend on the blocklength n, but assumed to decay slowly to the asymptotic data compression limit. Starting from a rate above this limit, we determine the speed of convergence of the error probability to zero and show that it is given in terms of the conditional information variance. Our results complement earlier results obtained by Tomamichel and Hayashi, in which they analyzed the so-called small deviation regime of this protocol.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•1 citation
The problem of classical data compression when the decoder has quantum side information at his disposal is considered. This is a quantum generalization of the classical Slepian-Wolf theorem. The optimal compression rate is found to be reduced from the Shannon entropy of the source by the Holevo information between the source and side information.
We study and solve the problem of classical channel simulation with quantum side information at the receiver. This is a generalization of both the classical reverse Shannon theorem, and the classical-quantum Slepian-Wolf problem. The optimal noiseless communication rate is found to be reduced from the mutual information between the channel input and output by the Holevo information between the channel output and the quantum side information. Our main theorem has two important corollaries. The first is a quantum generalization of the Wyner-Ziv problem: rate-distortion theory with quantum side information. The second is an alternative proof of the tradeoff between classical communication and common randomness distilled from a quantum state. The fully quantum generalization of the problem considered isquantumstateredistribution. Here the sender and receiver share a mixed quantum state and the sender wants to transfer part of her state to the receiver using entanglement and quantum communication. We present outer and inner bounds on the achievable rate pairs.
In this paper, we analyze classical data compression with quantum side information (also known as the classical-quantum Slepian–Wolf protocol) in the so-called large and moderate deviation regimes. In the non-asymptotic setting, the protocol involves compressing classical sequences of finite lengthnnnand decoding them with the assistance of quantum side information. In the large deviation regime, the compression rate is fixed, and we obtain bounds on the error exponent function, which characterizes the minimal probability of error as a function of the rate. Devetak and Winter showed that the asymptotic data compression limit for this protocol is given by a conditional entropy. For any protocol with a rate below this quantity, the probability of error converges to one asymptotically and its speed of convergence is given by the strong converse exponent function. We obtain finite blocklength bounds on this function, and determine exactly its asymptotic value. In the moderate deviation regime for the compression rate, the latter is no longer considered to be fixed. It is allowed to depend on the blocklengthnnn, but assumed to decay slowly to the asymptotic data compression limit. Starting from a rate above this limit, we determine the speed of convergence of the error probability to zero and show that it is given in terms of the conditional information variance.
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.
The task of compressing classical information in the one-shot scenario is studied in the setting where the decompressor additionally has access to some given quantum side information. In this hybrid classical-quantum version of the famous Slepian-Wolf problem, the smooth max entropy is found to govern the number of bits into which classical information can be compressed so that it can be reliably recovered from the compressed version and quantum side information. Combining this result with known results on privacy amplification then yields tight bounds on the amount of common randomness and secret key that can be recovered in one shot from hybrid classical-quantum systems using one-way classical communication.
The task of compressing classical information in the one-shot scenario is studied in the setting where the decompressor additionally has access to some given quantum side information. In this hybrid classical-quantum version of the famous Slepian-Wolf problem, the smooth max-entropy is found to govern the number of bits into which classical information can be compressed so that it can be reliably recovered from the compressed version and quantum side information. Combining this result with known results on privacy amplification then yields bounds on the amount of common randomness and secret key that can be recovered in one-shot from hybrid classical-quantum systems using one-way classical communication.
In this paper, we analyze classical data compression with quantum side information (also known as the classical-quantum Slepian- Wolf protocol) in the so-called large and moderate deviation regimes. In the non-asymptotic setting, the protocol involves compressing classical sequences of finite length n and decoding them with the assistance of quantum side information. In the large deviation regime, the compression rate is fixed, and we obtain bounds on the error exponent function, which characterizes the minimal probability of error as a function of the rate. Devetak and Winter showed that the asymptotic data compression limit for this protocol is given by a conditional entropy. For any protocol with a rate below this quantity, the probability of error converges to one asymptotically and its speed of convergence is given by the strong converse exponent function. We obtain finite blocklength bounds on this function, and determine exactly its asymptotic value, thus improving on previous results by Tomamichel. In the moderate deviation regime for the compression rate, the latter is no longer considered to be fixed. It is allowed to depend on the blocklength n, but assumed to decay slowly to the asymptotic data compression limit. Starting from a rate above this limit, we determine the speed of convergence of the error probability to zero and show that it is given in terms of the conditional information variance. Our results complement earlier results obtained by Tomamichel and Hayashi, in which they analyzed the so-called small deviation regime of this protocol.