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

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

Joseph M. Renes

Published Nov 20, 2024• 10 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tit.2024.3500578

Related papers

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•9 citations

Sphere-packing bound for classical-quantum channels

Hao–Chung Cheng, Min-Hsiu Hsieh, Marco Tomamichel

We study lower bounds on the optimal error probability in channel coding at rates below capacity, commonly termed sphere-packing bounds. In this work, we establish a sphere-packing bound for classical-quantum channels, which significantly improves previous prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of o(log n/n), indicating our sphere-packing bound is almost exact in the high rate regime. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions.

IEEE Information Theory Workshop (ITW)•Nov 1, 2017•1 citation

Quantum Sphere-Packing Bounds With Polynomial Prefactors

Hao-Chung Cheng, Min-Hsiu Hsieh, Marco Tomamichel

We study lower bounds on the optimal error probability in classical coding over classical-quantum channels at rates below the capacity, commonly termed quantum sphere-packing bounds. Winter and Dalai have derived such bounds for classical-quantum channels; however, the exponents in their bounds only coincide when the channel is classical. In this paper, we show that these two exponents admit a variational representation and are related by the Golden-Thompson inequality, reaffirming that Dalai's expression is stronger in general classical-quantum channels. Second, we establish a finite blocklength sphere-packing bound for classical-quantum channels, which significantly improves Dalai's prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of o(logn/n), indicating our sphere-packing bound is almost exact in the high rate regime. Finally, for a special class of symmetric classical-quantum channels, we can completely characterize its optimal error probability without the constant composition code assumption. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions.

arXiv:1704.05703•IEEE Transactions on Information Theory•Jan 8, 2019•53 citations

Reliability Function of Classical-Quantum Channels

Ke Li, Dong Yang

We study the reliability function of general classical-quantum channels, which describes the optimal exponent of the decay of decoding error when the communication rate is below the capacity. As the main result, we prove a lower bound, in terms of the quantum Rényi information in Petz's form, for the reliability function. This resolves Holevo's conjecture proposed in 2000, a long-standing open problem in quantum information theory. It turns out that the obtained lower bound matches the upper bound derived by Dalai in 2013, when the communication rate is above a critical value. Thus, we have determined the reliability function in this high-rate case. Our approach relies on Renes' breakthrough made in 2022, which relates classical-quantum channel coding to that of privacy amplification, as well as our new characterization of the channel Rényi information.

arXiv:2407.12403•Physical Review Letters•Jan 8, 2025•15 citations

Sphere-packing bound for symmetric classical-quantum channels

Hao–Chung Cheng, Min-Hsiu Hsieh, Marco Tomamichel

“To be considered for the 2017 IEEE Jack Keil Wolf ISIT Student Paper Award.” We provide a sphere-packing lower bound for the optimal error probability in finite blocklengths when coding over a symmetric classical-quantum channel. Our result shows that the pre-factor can be significantly improved from the order of the subexponential to the polynomial, This established pre-factor is arguably optimal because it matches the best known random coding upper bound in the classical case. Our approaches rely on a sharp concentration inequality in strong large deviation theory and crucial properties of the error-exponent function.

arXiv:1701.02957•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•7 citations

Reliable Simulation of Quantum Channels: The Error Exponent

Ke Li, Yongsheng Yao

The Quantum Reverse Shannon Theorem has been a milestone in quantum information theory. It states that asymptotically reliable simulation of a quantum channel, assisted by unlimited shared entanglement, requires a rate of classical communication equal to the channel’s entanglement-assisted classical capacity. In this paper, we study the error exponent of quantum channel simulation, which characterizes the optimal speed of exponential convergence of the performance towards the perfect, as the blocklength increases. Based on channel purified distance, we derive lower and upper bounds for the error exponent. Then we show that the two bounds coincide when the classical communication rate is below a critical value, and hence, we have determined the exact formula of the error exponent in the low-rate case. This enables us to obtain an operational interpretation to the channel’s sandwiched Rényi information of order from 1 to 2, since our formula is expressed as a transform of this quantity. In the derivation, we have also obtained an achievability bound for quantum channel simulation in the finite-blocklength setting, which is of realistic significance.

arXiv:2112.04475•IEEE Transactions on Information Theory•Oct 28, 2024•21 citations
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.
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.
We study lower bounds on the optimal error probability in channel coding at rates below capacity, commonly termed sphere-packing bounds. In this work, we establish a sphere-packing bound for classical-quantum channels, which significantly improves previous prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of o(log n/n), indicating our sphere-packing bound is almost exact in the high rate regime. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions.
We study lower bounds on the optimal error probability in classical coding over classical-quantum channels at rates below the capacity, commonly termed quantum sphere-packing bounds. Winter and Dalai have derived such bounds for classical-quantum channels; however, the exponents in their bounds only coincide when the channel is classical. In this paper, we show that these two exponents admit a variational representation and are related by the Golden-Thompson inequality, reaffirming that Dalai's expression is stronger in general classical-quantum channels. Second, we establish a finite blocklength sphere-packing bound for classical-quantum channels, which significantly improves Dalai's prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of o(logn/n), indicating our sphere-packing bound is almost exact in the high rate regime. Finally, for a special class of symmetric classical-quantum channels, we can completely characterize its optimal error probability without the constant composition code assumption. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions.
We study the reliability function of general classical-quantum channels, which describes the optimal exponent of the decay of decoding error when the communication rate is below the capacity. As the main result, we prove a lower bound, in terms of the quantum Rényi information in Petz's form, for the reliability function. This resolves Holevo's conjecture proposed in 2000, a long-standing open problem in quantum information theory. It turns out that the obtained lower bound matches the upper bound derived by Dalai in 2013, when the communication rate is above a critical value. Thus, we have determined the reliability function in this high-rate case. Our approach relies on Renes' breakthrough made in 2022, which relates classical-quantum channel coding to that of privacy amplification, as well as our new characterization of the channel Rényi information.
“To be considered for the 2017 IEEE Jack Keil Wolf ISIT Student Paper Award.” We provide a sphere-packing lower bound for the optimal error probability in finite blocklengths when coding over a symmetric classical-quantum channel. Our result shows that the pre-factor can be significantly improved from the order of the subexponential to the polynomial, This established pre-factor is arguably optimal because it matches the best known random coding upper bound in the classical case. Our approaches rely on a sharp concentration inequality in strong large deviation theory and crucial properties of the error-exponent function.
The Quantum Reverse Shannon Theorem has been a milestone in quantum information theory. It states that asymptotically reliable simulation of a quantum channel, assisted by unlimited shared entanglement, requires a rate of classical communication equal to the channel’s entanglement-assisted classical capacity. In this paper, we study the error exponent of quantum channel simulation, which characterizes the optimal speed of exponential convergence of the performance towards the perfect, as the blocklength increases. Based on channel purified distance, we derive lower and upper bounds for the error exponent. Then we show that the two bounds coincide when the classical communication rate is below a critical value, and hence, we have determined the exact formula of the error exponent in the low-rate case. This enables us to obtain an operational interpretation to the channel’s sandwiched Rényi information of order from 1 to 2, since our formula is expressed as a transform of this quantity. In the derivation, we have also obtained an achievability bound for quantum channel simulation in the finite-blocklength setting, which is of realistic significance.