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:1511.06071 · IEEE Transactions on Information Theory

Channel Simulation and Coded Source Compression

Min-Hsiu Hsieh, Shun Watanabe

Published Aug 3, 2016• 29 citations
arXivHTMLPDF

Abstract

Coded source compression, also known as source compression with helpers, has been a major variant of distributed source compression, but has hitherto received little attention in the quantum regime. This letter treats and solves the corresponding quantum coded source compression through an observation that connects coded source compression with channel simulation. First, we consider classical source coding with quantum side information, where the quantum side information is observed by a helper and sent to the decoder via a classical channel. We derive a single-letter characterization of the achievable rate region for this problem. The direct coding theorem of our result is proved via the measurement compression theory of Winter, a quantum-to-classical channel simulation. Our result reveals that a helper's scheme which separately conducts a measurement and a compression is suboptimal, and measurement compression seems necessary to achieve the optimal rate region. We then study coded source compression in the fully quantum regime, where two different scenarios are considered depending on the types of communication channels between the legitimate source and the receiver. We further allow entanglement assistance from the quantum helper in both scenarios. We characterize the involved quantum resources and derive single-letter expressions of the achievable rate region. The direct coding proofs are based on well-known quantum protocols, the quantum state merging protocol, and the fully quantum Slepian-Wolf protocol, together with the quantum reverse Shannon theorem.

DOI
10.1109/tit.2016.2597853

Related papers

Source compression with a quantum helper

Min-Hsiu Hsieh, Shun Watanabe

We study classical source coding with quantum side-information where the quantum side-information is observed by a helper and sent to the decoder via a classical channel. We derive a single-letter characterization of the achievable rate region for this problem. The direct part of our result is proved via the measurement compression theory by Winter. Our result reveals that a helper's scheme that separately conducts a measurement and a compression is suboptimal, and the measurement compression is fundamentally needed to achieve the optimal rate region.

arXiv:1501.04366•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•3 citations

Fully quantum source compression with a quantum helper

Min-Hsiu Hsieh, Shun Watanabe

We study source compression with a helper in the fully quantum regime, extending our earlier result on classical source compression with a quantum helper [arXiv:1501.04366, 2015]. We characterise the quantum resources involved in this problem, and derive a single-letter expression of the achievable rate region when entanglement assistance is available. The direct coding proof is based on a combination of two fundamental protocols, namely the quantum state merging protocol and the quantum reverse Shannon theorem (QRST). This result connects distributed source compression with the QRST protocol, a quantum protocol that consumes noiseless resources to simulate a noisy quantum channel.

arXiv:1504.05227•IEEE Information Theory Workshop (ITW)•Oct 1, 2015•2 citations

Distributed Compression of Correlated Classical-Quantum Sources

Zahra Baghali Khanian, Andreas Winter

We resume the investigation of the problem of independent local compression of correlated quantum sources, the classical case of which is covered by the celebrated Slepian-Wolf theorem. We focus specifically on classical-quantum (cq) sources, for which one edge of the rate region, corresponding to the compression of the classical part, using the quantum part as side information at the decoder, was previously determined by Devetak and Winter [Phys. Rev. A 68, 042301 (2003)]. Whereas the Devetak-Winter protocol attains a rate-sum equal to the von Neumann entropy of the joint source, here we show that the full rate region is much more complex, due to the partially quantum nature of the source. In particular, in the opposite case of compressing the quantum part of the source, using the classical part as side information at the decoder, typically the rate sum is strictly larger than the von Neumann entropy of the total source.We determine the full rate region in the generic case, showing that, apart from the Devetak-Winter point, all other points in the achievable region have a rate sum strictly larger than the joint entropy. We can interpret the difference as the price paid for the quantum encoder being ignorant of the classical side information. In the general case, we give an achievable rate region, via protocols that are built on the decoupling principle, and the principles of quantum state merging and quantum state redistribution. Our achievable region is matched almost by a single-letter converse, which however still involves asymptotic errors and an unbounded auxiliary system.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•6 citations

Distributed Compression of Correlated Classical-Quantum Sources or: The Price of Ignorance

Zahra Baghali Khanian, Andreas Winter

We resume the investigation of the problem of independent local compression of correlated quantum sources, the classical case of which is covered by the celebrated Slepian-Wolf theorem. We focus specifically on classical-quantum (cq) sources, for which one edge of the rate region, corresponding to the compression of the classical part, using the quantum part as side information at the decoder, was previously determined by Devetak and Winter [Phys. Rev. A 68, 042301 (2003)]. Whereas the Devetak-Winter protocol attains a rate-sum equal to the von Neumann entropy of the joint source, here we show that the full rate region is much more complex, due to the partially quantum nature of the source. In particular, in the opposite case of compressing the quantum part of the source, using the classical part as side information at the decoder, typically the rate sum is strictly larger than the von Neumann entropy of the total source. We determine the full rate region in the generic case, showing that, apart from the Devetak-Winter point, all other points in the achievable region have a rate sum strictly larger than the joint entropy. We can interpret the difference as the price paid for the quantum encoder being ignorant of the classical side information. In the general case, we give an achievable rate region, via protocols that are built on the decoupling principle, and the protocols of quantum state merging and quantum state redistribution. Our achievable region is matched almost by a single-letter converse, which however still involves asymptotic errors and an unbounded auxiliary system.

arXiv:1811.09177•IEEE Transactions on Information Theory•Mar 17, 2020•25 citations

The information-theoretic costs of simulating quantum measurements

Mark M. Wilde, Patrick M. Hayden, Francesco Buscemi +1 more

Winter's measurement compression theorem stands as one of the most penetrating insights of quantum information theory. In addition to making an original and profound statement about measurement in quantum theory, it also underlies several other general protocols used for entanglement distillation and local purity distillation. The theorem provides for an asymptotic decomposition of any quantum measurement into noise and information . This decomposition leads to an optimal protocol for having a sender simulate many independent instances of a quantum measurement and send the measurement outcomes to a receiver, using as little communication as possible. The protocol assumes that the parties have access to some amount of common randomness, which is a strictly weaker resource than classical communication. In this review, we provide a second look at Winter's measurement compression theorem, detailing the information processing task, giving examples for understanding it, reviewing Winter's achievability proof, and detailing a new approach to its single-letter converse theorem. We prove an extension of the theorem to the case in which the sender is not required to receive the outcomes of the simulated measurement. The total cost of common randomness and classical communication can be lower for such a 'non-feedback' simulation, and we prove a single-letter converse theorem demonstrating optimality. We then review the Devetak–Winter theorem on classical data compression with quantum side information, providing new proofs of its achievability and converse parts. From there, we outline a new protocol that we call 'measurement compression with quantum side information,' announced previously by two of us in our work on triple trade-offs in quantum Shannon theory. This protocol has several applications, including its part in the 'classically-assisted state redistribution' protocol, which is the most general protocol on the static side of the quantum information theory tree, and its role in reducing the classical communication cost in a task known as local purity distillation. We also outline a connection between measurement compression with quantum side information and recent work on entropic uncertainty relations in the presence of quantum memory. Finally, we prove a single-letter theorem characterizing measurement compression with quantum side information when the sender is not required to obtain the measurement outcome.

arXiv:1206.4121•Journal of Physics A Mathematical and Theoretical•Oct 18, 2012•90 citations

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•54 citations
Coded source compression, also known as source compression with helpers, has been a major variant of distributed source compression, but has hitherto received little attention in the quantum regime. This letter treats and solves the corresponding quantum coded source compression through an observation that connects coded source compression with channel simulation. First, we consider classical source coding with quantum side information, where the quantum side information is observed by a helper and sent to the decoder via a classical channel. We derive a single-letter characterization of the achievable rate region for this problem. The direct coding theorem of our result is proved via the measurement compression theory of Winter, a quantum-to-classical channel simulation. Our result reveals that a helper's scheme which separately conducts a measurement and a compression is suboptimal, and measurement compression seems necessary to achieve the optimal rate region. We then study coded source compression in the fully quantum regime, where two different scenarios are considered depending on the types of communication channels between the legitimate source and the receiver. We further allow entanglement assistance from the quantum helper in both scenarios. We characterize the involved quantum resources and derive single-letter expressions of the achievable rate region. The direct coding proofs are based on well-known quantum protocols, the quantum state merging protocol, and the fully quantum Slepian-Wolf protocol, together with the quantum reverse Shannon theorem.
We study classical source coding with quantum side-information where the quantum side-information is observed by a helper and sent to the decoder via a classical channel. We derive a single-letter characterization of the achievable rate region for this problem. The direct part of our result is proved via the measurement compression theory by Winter. Our result reveals that a helper's scheme that separately conducts a measurement and a compression is suboptimal, and the measurement compression is fundamentally needed to achieve the optimal rate region.
We study source compression with a helper in the fully quantum regime, extending our earlier result on classical source compression with a quantum helper [arXiv:1501.04366, 2015]. We characterise the quantum resources involved in this problem, and derive a single-letter expression of the achievable rate region when entanglement assistance is available. The direct coding proof is based on a combination of two fundamental protocols, namely the quantum state merging protocol and the quantum reverse Shannon theorem (QRST). This result connects distributed source compression with the QRST protocol, a quantum protocol that consumes noiseless resources to simulate a noisy quantum channel.
We resume the investigation of the problem of independent local compression of correlated quantum sources, the classical case of which is covered by the celebrated Slepian-Wolf theorem. We focus specifically on classical-quantum (cq) sources, for which one edge of the rate region, corresponding to the compression of the classical part, using the quantum part as side information at the decoder, was previously determined by Devetak and Winter [Phys. Rev. A 68, 042301 (2003)]. Whereas the Devetak-Winter protocol attains a rate-sum equal to the von Neumann entropy of the joint source, here we show that the full rate region is much more complex, due to the partially quantum nature of the source. In particular, in the opposite case of compressing the quantum part of the source, using the classical part as side information at the decoder, typically the rate sum is strictly larger than the von Neumann entropy of the total source.We determine the full rate region in the generic case, showing that, apart from the Devetak-Winter point, all other points in the achievable region have a rate sum strictly larger than the joint entropy. We can interpret the difference as the price paid for the quantum encoder being ignorant of the classical side information. In the general case, we give an achievable rate region, via protocols that are built on the decoupling principle, and the principles of quantum state merging and quantum state redistribution. Our achievable region is matched almost by a single-letter converse, which however still involves asymptotic errors and an unbounded auxiliary system.
We resume the investigation of the problem of independent local compression of correlated quantum sources, the classical case of which is covered by the celebrated Slepian-Wolf theorem. We focus specifically on classical-quantum (cq) sources, for which one edge of the rate region, corresponding to the compression of the classical part, using the quantum part as side information at the decoder, was previously determined by Devetak and Winter [Phys. Rev. A 68, 042301 (2003)]. Whereas the Devetak-Winter protocol attains a rate-sum equal to the von Neumann entropy of the joint source, here we show that the full rate region is much more complex, due to the partially quantum nature of the source. In particular, in the opposite case of compressing the quantum part of the source, using the classical part as side information at the decoder, typically the rate sum is strictly larger than the von Neumann entropy of the total source. We determine the full rate region in the generic case, showing that, apart from the Devetak-Winter point, all other points in the achievable region have a rate sum strictly larger than the joint entropy. We can interpret the difference as the price paid for the quantum encoder being ignorant of the classical side information. In the general case, we give an achievable rate region, via protocols that are built on the decoupling principle, and the protocols of quantum state merging and quantum state redistribution. Our achievable region is matched almost by a single-letter converse, which however still involves asymptotic errors and an unbounded auxiliary system.
Winter's measurement compression theorem stands as one of the most penetrating insights of quantum information theory. In addition to making an original and profound statement about measurement in quantum theory, it also underlies several other general protocols used for entanglement distillation and local purity distillation. The theorem provides for an asymptotic decomposition of any quantum measurement into noise and information . This decomposition leads to an optimal protocol for having a sender simulate many independent instances of a quantum measurement and send the measurement outcomes to a receiver, using as little communication as possible. The protocol assumes that the parties have access to some amount of common randomness, which is a strictly weaker resource than classical communication. In this review, we provide a second look at Winter's measurement compression theorem, detailing the information processing task, giving examples for understanding it, reviewing Winter's achievability proof, and detailing a new approach to its single-letter converse theorem. We prove an extension of the theorem to the case in which the sender is not required to receive the outcomes of the simulated measurement. The total cost of common randomness and classical communication can be lower for such a 'non-feedback' simulation, and we prove a single-letter converse theorem demonstrating optimality. We then review the Devetak–Winter theorem on classical data compression with quantum side information, providing new proofs of its achievability and converse parts. From there, we outline a new protocol that we call 'measurement compression with quantum side information,' announced previously by two of us in our work on triple trade-offs in quantum Shannon theory. This protocol has several applications, including its part in the 'classically-assisted state redistribution' protocol, which is the most general protocol on the static side of the quantum information theory tree, and its role in reducing the classical communication cost in a task known as local purity distillation. We also outline a connection between measurement compression with quantum side information and recent work on entropic uncertainty relations in the presence of quantum memory. Finally, we prove a single-letter theorem characterizing measurement compression with quantum side information when the sender is not required to obtain the measurement outcome.
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.