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

IEEE Transactions on Information Theory

Duality Between Source Coding With Quantum Side Information and Classical-Quantum Channel Coding

Hao–Chung Cheng, Eric P. Hanson, Nilanjana Datta, Min-Hsiu Hsieh

Published Jun 13, 2022• 10 citations
Publisher

Abstract

In this paper, we establish an interesting duality between two different quantum information-processing tasks, namely, classical source coding with quantum side information, and channel coding over classical-quantum channels. The duality relates the optimal error exponents of these two tasks, generalizing the classical results of Ahlswede and Dueck [IEEE Trans. Inf. Theory, 28(3):430–443, 1982]. We establish duality both at the operational level and at the level of the entropic quantities characterizing these exponents. For the latter, the duality is given by an exact relation, whereas for the former, duality manifests itself in the following sense: an optimal coding strategy for one task can be used to construct an optimal coding strategy for the other task. Along the way, we derive a bound on the error exponent for classical-quantum channel coding with constant composition codes which might be of independent interest. Finally, we consider the task of variable-length classical compression with quantum side information, and a duality relation between this task and classical-quantum channel coding can also be established correspondingly. Furthermore, we study the strong converse of this task, and show that the strong converse property does not hold even in the i.i.d. scenario.

DOI
10.1109/tit.2022.3182748

Related papers

Duality between source coding with quantum side information and c-q channel coding

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

In this paper, we establish an interesting duality between two different quantum information-processing tasks, namely, classical source coding with quantum side information, and channel coding over classical-quantum channels. The duality relates the optimal error exponents of these two tasks, generalizing the classical results of Ahlswede and Dueck. We establish duality both at the operational level and at the level of the entropic quantities characterizing these exponents. For the latter, the duality is given by an exact relation, whereas for the former, duality manifests itself in the following sense: an optimal coding strategy for one task can be used to construct an optimal coding strategy for the other task. Along the way, we derive a bound on the error exponent for classical-quantum channel coding with constant composition codes which might be of independent interest.

arXiv:1809.11143•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•18 citations

Privacy Amplification, Lossy Compression, and their Duality to Channel Coding

Joseph M. Renes

We examine the task of privacy amplification from information-theoretic and coding-theoretic points of view. In the former, we give a one-shot characterization of the optimal rate of privacy amplification against classical adversaries in terms of the optimal type-II error in asymmetric hypothesis testing. This formulation can be easily computed to give finite- blocklength bounds and turns out to be equivalent to smooth min-entropy bounds by Renner and Wolf [Asiacrypt 2005] and Watanabe and Hayashi [ISIT 2013], as well as a bound in terms of the Eγdivergence by Yang, Schaefer, and Poor [arXiv:1706.03866 [cs.IT]]. In the latter, we show that protocols for privacy amplification based on linear codes can be easily repurposed for lossy compression. Our construction leads to protocols of optimal rate in the asymptotic i.i.d. limit for a variety of compression scenarios. Finally, appealing to the notion of channel duality recently detailed by us in [IEEE Trans. Inf. Theory 64,577 (2018)], we show that linear error-correcting codes for symmetric channels with quantum output can be transformed into linear lossy source coding schemes for classical variables arising from the dual channel. This explains a “curious duality” in these problems for the (self-dual) erasure channel observed by Martinian and Yedidia [Allerton 2003; arXiv:cs/0408008] and partly anticipates recent results on optimal lossy compression by polar and low-density generator matrix codes.

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

Achievable error exponents of data compression with quantum side information and communication over symmetric classical-quantum channels

Joseph M. Renes

A fundamental quantity of interest in Shannon theory, classical or quantum, is the optimal error exponent of a given channel W and rate R: the constant E(W,R) which governs the exponential decay of decoding error when using ever larger codes of fixed rate R to communicate over ever more (memoryless) instances of a given channel W. Here I show that a bound by Hayashi [CMP 333, 335 (2015)] for an analogous quantity in privacy amplification implies a lower bound on the error exponent of communication over symmetric classical-quantum channels. The resulting bound matches Dalai’s [IEEE TIT 59, 8027 (2013)] sphere-packing upper bound for rates above a critical value, and reproduces the well-known classical result for symmetric channels. The argument proceeds by first relating the error exponent of privacy amplification to that of compression of classical information with quantum side information, which gives a lower bound that matches the sphere-packing upper bound of Cheng et al. [IEEE TIT 67, 902 (2021)]. In turn, the polynomial prefactors to the sphere-packing bound found by Cheng et al. may be translated to the privacy amplification problem, sharpening a recent result by Li, Yao, and Hayashi [arXiv:2111.01075 [quant-ph]], at least for linear randomness extractors.

arXiv:2207.08899•IEEE Information Theory Workshop (ITW)•Apr 23, 2023•5 citations

Tight Lower Bound on the Error Exponent of Classical-Quantum Channels

Joseph M. Renes

A fundamental quantity of interest in Shannon theory, classical or quantum, is the error exponent of a given channel W and rate R: the constant$E(W,R)$which governs the exponential decay of decoding error when using ever larger optimal codes of fixed rate R to communicate over ever more (memoryless) instances of a given channel W. Nearly matching lower and upper bounds are well-known for classical channels. Here I show a lower bound on the error exponent of communication over arbitrary classical-quantum (CQ) channels which matches Dalai’s sphere-packing upper bound for rates above a critical value, exactly analogous to the case of classical channels. This proves a conjecture made by Holevo in his investigation of the problem. Unlike the classical case, however, the argument does not proceed via a refined analysis of a suitable decoder, but instead by leveraging a bound by Hayashi on the error exponent of the cryptographic task of privacy amplification. This bound is then related to the coding problem via tight entropic uncertainty relations and Gallager’s method of constructing capacity-achieving parity-check codes for arbitrary channels. Along the way, I find a lower bound on the error exponent of the task of compression of classical information relative to quantum side information that matches the sphere-packing upper bound of Cheng et al. In turn, the polynomial prefactors to the sphere-packing bound found by Cheng et al. may be translated to the privacy amplification problem, sharpening a recent result by Li, Yao, and Hayashi, at least for linear randomness extractors.

arXiv:2407.11118•IEEE Transactions on Information Theory•Nov 20, 2024•7 citations

Divergence Radii and the Strong Converse Exponent of Classical-Quantum Channel Coding With Constant Compositions

Milán Mosonyi, Tomohiro Ogawa

There are different inequivalent ways to define the Rényi capacity of a channel for a fixed input distribution. In [IEEE Transactions on Information Theory, 41(1):26-34, 1995], Csiszár has shown that for classical discrete memoryless channels there is a distinguished such quantity that has an operational interpretation as a generalized cutoff rate for constant composition channel coding. We show that the analogous notion of Rényi capacity, defined in terms of the sandwiched quantum Rényi divergences, has the same operational interpretation in the strong converse problem of constant composition classical-quantum channel coding.

arXiv:1811.10599•IEEE Transactions on Information Theory•Dec 2, 2020•32 citations

On Privacy Amplification, Lossy Compression, and Their Duality to Channel Coding

Joseph M. Renes

We examine the task of privacy amplification from information-theoretic and coding-theoretic points of view. In the former, we give a one-shot characterization of the optimal rate of privacy amplification against classical adversaries in terms of the optimal type-II error in asymmetric hypothesis testing. The converse significantly improves on previous bounds based on smooth min-entropy by Watanabe and Hayashi [7] and turns out to be equivalent to a recent formulation in terms of the Eγ divergence by Yang et al. [9]. In the latter, we show that the protocols for privacy amplification based on linear codes can be easily repurposed for channel simulation. Combined with the known relations between channel simulation and lossy source coding, this implies that the privacy amplification can be understood as a basic primitive for both channel simulation and lossy compression. Applied to symmetric channels or lossy compression settings, our construction leads to protocols of the optimal rate in the asymptotic i.i.d. limit. Finally, appealing to the notion of channel duality recently detailed by us in [15], we show that the linear error-correcting codes for symmetric channels with quantum output can be transformed into linear lossy source coding schemes for classical variables arising from the dual channel. This explains a “curious duality” in these problems for the (self-dual) erasure channel observed by Martinian and Yedidia [16] and partly anticipates recent results on optimal lossy compression by polar and low-density generator matrix codes.

arXiv:1708.05685•IEEE Transactions on Information Theory•Aug 13, 2018•11 citations
In this paper, we establish an interesting duality between two different quantum information-processing tasks, namely, classical source coding with quantum side information, and channel coding over classical-quantum channels. The duality relates the optimal error exponents of these two tasks, generalizing the classical results of Ahlswede and Dueck [IEEE Trans. Inf. Theory, 28(3):430–443, 1982]. We establish duality both at the operational level and at the level of the entropic quantities characterizing these exponents. For the latter, the duality is given by an exact relation, whereas for the former, duality manifests itself in the following sense: an optimal coding strategy for one task can be used to construct an optimal coding strategy for the other task. Along the way, we derive a bound on the error exponent for classical-quantum channel coding with constant composition codes which might be of independent interest. Finally, we consider the task of variable-length classical compression with quantum side information, and a duality relation between this task and classical-quantum channel coding can also be established correspondingly. Furthermore, we study the strong converse of this task, and show that the strong converse property does not hold even in the i.i.d. scenario.
In this paper, we establish an interesting duality between two different quantum information-processing tasks, namely, classical source coding with quantum side information, and channel coding over classical-quantum channels. The duality relates the optimal error exponents of these two tasks, generalizing the classical results of Ahlswede and Dueck. We establish duality both at the operational level and at the level of the entropic quantities characterizing these exponents. For the latter, the duality is given by an exact relation, whereas for the former, duality manifests itself in the following sense: an optimal coding strategy for one task can be used to construct an optimal coding strategy for the other task. Along the way, we derive a bound on the error exponent for classical-quantum channel coding with constant composition codes which might be of independent interest.
We examine the task of privacy amplification from information-theoretic and coding-theoretic points of view. In the former, we give a one-shot characterization of the optimal rate of privacy amplification against classical adversaries in terms of the optimal type-II error in asymmetric hypothesis testing. This formulation can be easily computed to give finite- blocklength bounds and turns out to be equivalent to smooth min-entropy bounds by Renner and Wolf [Asiacrypt 2005] and Watanabe and Hayashi [ISIT 2013], as well as a bound in terms of the Eγdivergence by Yang, Schaefer, and Poor [arXiv:1706.03866 [cs.IT]]. In the latter, we show that protocols for privacy amplification based on linear codes can be easily repurposed for lossy compression. Our construction leads to protocols of optimal rate in the asymptotic i.i.d. limit for a variety of compression scenarios. Finally, appealing to the notion of channel duality recently detailed by us in [IEEE Trans. Inf. Theory 64,577 (2018)], we show that linear error-correcting codes for symmetric channels with quantum output can be transformed into linear lossy source coding schemes for classical variables arising from the dual channel. This explains a “curious duality” in these problems for the (self-dual) erasure channel observed by Martinian and Yedidia [Allerton 2003; arXiv:cs/0408008] and partly anticipates recent results on optimal lossy compression by polar and low-density generator matrix codes.
A fundamental quantity of interest in Shannon theory, classical or quantum, is the optimal error exponent of a given channel W and rate R: the constant E(W,R) which governs the exponential decay of decoding error when using ever larger codes of fixed rate R to communicate over ever more (memoryless) instances of a given channel W. Here I show that a bound by Hayashi [CMP 333, 335 (2015)] for an analogous quantity in privacy amplification implies a lower bound on the error exponent of communication over symmetric classical-quantum channels. The resulting bound matches Dalai’s [IEEE TIT 59, 8027 (2013)] sphere-packing upper bound for rates above a critical value, and reproduces the well-known classical result for symmetric channels. The argument proceeds by first relating the error exponent of privacy amplification to that of compression of classical information with quantum side information, which gives a lower bound that matches the sphere-packing upper bound of Cheng et al. [IEEE TIT 67, 902 (2021)]. In turn, the polynomial prefactors to the sphere-packing bound found by Cheng et al. may be translated to the privacy amplification problem, sharpening a recent result by Li, Yao, and Hayashi [arXiv:2111.01075 [quant-ph]], at least for linear randomness extractors.
A fundamental quantity of interest in Shannon theory, classical or quantum, is the error exponent of a given channel W and rate R: the constantE(W,R)E(W,R)E(W,R)which governs the exponential decay of decoding error when using ever larger optimal codes of fixed rate R to communicate over ever more (memoryless) instances of a given channel W. Nearly matching lower and upper bounds are well-known for classical channels. Here I show a lower bound on the error exponent of communication over arbitrary classical-quantum (CQ) channels which matches Dalai’s sphere-packing upper bound for rates above a critical value, exactly analogous to the case of classical channels. This proves a conjecture made by Holevo in his investigation of the problem. Unlike the classical case, however, the argument does not proceed via a refined analysis of a suitable decoder, but instead by leveraging a bound by Hayashi on the error exponent of the cryptographic task of privacy amplification. This bound is then related to the coding problem via tight entropic uncertainty relations and Gallager’s method of constructing capacity-achieving parity-check codes for arbitrary channels. Along the way, I find a lower bound on the error exponent of the task of compression of classical information relative to quantum side information that matches the sphere-packing upper bound of Cheng et al. In turn, the polynomial prefactors to the sphere-packing bound found by Cheng et al. may be translated to the privacy amplification problem, sharpening a recent result by Li, Yao, and Hayashi, at least for linear randomness extractors.
There are different inequivalent ways to define the Rényi capacity of a channel for a fixed input distribution. In [IEEE Transactions on Information Theory, 41(1):26-34, 1995], Csiszár has shown that for classical discrete memoryless channels there is a distinguished such quantity that has an operational interpretation as a generalized cutoff rate for constant composition channel coding. We show that the analogous notion of Rényi capacity, defined in terms of the sandwiched quantum Rényi divergences, has the same operational interpretation in the strong converse problem of constant composition classical-quantum channel coding.
We examine the task of privacy amplification from information-theoretic and coding-theoretic points of view. In the former, we give a one-shot characterization of the optimal rate of privacy amplification against classical adversaries in terms of the optimal type-II error in asymmetric hypothesis testing. The converse significantly improves on previous bounds based on smooth min-entropy by Watanabe and Hayashi [7] and turns out to be equivalent to a recent formulation in terms of the Eγ divergence by Yang et al. [9]. In the latter, we show that the protocols for privacy amplification based on linear codes can be easily repurposed for channel simulation. Combined with the known relations between channel simulation and lossy source coding, this implies that the privacy amplification can be understood as a basic primitive for both channel simulation and lossy compression. Applied to symmetric channels or lossy compression settings, our construction leads to protocols of the optimal rate in the asymptotic i.i.d. limit. Finally, appealing to the notion of channel duality recently detailed by us in [15], we show that the linear error-correcting codes for symmetric channels with quantum output can be transformed into linear lossy source coding schemes for classical variables arising from the dual channel. This explains a “curious duality” in these problems for the (self-dual) erasure channel observed by Martinian and Yedidia [16] and partly anticipates recent results on optimal lossy compression by polar and low-density generator matrix codes.