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:2507.06232

Error Exponents for Quantum Packing Problems via An Operator Layer Cake Theorem

Hao–Chung Cheng, Po-Chieh Liu

Published Jul 8, 2025• 24 citations
arXivHTMLPDF

Abstract

In this work, we prove a one-shot random coding bound for classical-quantum channel coding, a problem conjectured by Burnashev and Holevo in 1998. By choosing the optimal input distribution, the bound implies the optimal error exponent (i.e., the reliability function) of classical-quantum channels for rates above the critical rate, even in infinite-dimensional Hilbert spaces. Our result extends to various quantum packing-type problems, including classical communication over any fully quantum channel with or without entanglement-assistance, constant composition codes, and classical data compression with quantum side information via fixed-length or variable-length coding. Our technical ingredient is to establish an operator layer cake theorem - the directional derivative of an operator logarithm admits an integral representation of certain projections. This shows that a kind of pretty-good measurement is equivalent to a randomized Holevo-Helstrom measurement, which provides an operational explanation of why the pretty-good measurement is pretty good.

DOI
10.48550/arxiv.2507.06232

Related papers

Gallager’s Random Coding Bound for Classical-Quantum Channels and Beyond

Po-Chieh Liu, Hao–Chung Cheng

We establish Gallager’s random coding bound for classical-quantum channels, thereby resolving a long-standing conjecture proposed by Burnashev and Holevo in 1998. By optimizing the input distribution, this bound achieves the optimal error exponent—known as the reliability function—for rates above the critical rate, even in infinite-dimensional Hilbert spaces. Furthermore, the established bound is immediately applicable to general quantum channels and a variety of broader quantum information-theoretic tasks.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 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•10 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•9 citations

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

Optimal Trace Inequalities for Single-Shot Quantum Information

Gilad Gour

Single-shot quantum information theory is governed not only by entropy exponents, but also by the finite-resource constants that multiply them. These constants directly affect the quantitative performance of decoupling, covering, convex-splitting, position-based decoding, and one-shot communication protocols, yet they are often inherited from nonoptimal scalar estimates or from classical-to-quantum lifting arguments that introduce additional losses. In this work we show that the operator layer-cake representation provides a mechanism for lifting sharp scalar inequalities to the noncommutative setting without loss. Using an iterative Riemann--Stieltjes integration-by-parts method, we derive sharp quantum trace inequalities that tighten several standard single-shot bounds. For a logarithmic trace inequality recently introduced by Cheng \emph{et al.}\ and subsequently used in quantum covering and decoupling problems, we determine the exact optimal prefactor, replacing the previously known constant by a smaller Lambert-$W$ constant and proving universal optimality for positive operators. We also completely characterize the threshold behavior that appears under normalization to quantum states. In addition, we establish optimal two-sided collision-divergence inequalities, which lead to improved position-based decoding and single-shot classical communication bounds. These results show that several finite-resource bounds in single-shot quantum information can be tightened, and that within the layer-cake Rényi-divergence framework the resulting constants are genuine optimality barriers rather than artifacts of the proof.

quant-pharXiv:2604.14617•Apr 17, 2026•1 citation

Lower Bounds on Error Exponents via a New Quantum Decoder

Salman Beigi, Marco Tomamichel

We introduce a new quantum decoder based on a variant of the pretty good measurement, but defined via an alternative matrix quotient. We then use this novel decoder to derive new lower bounds on the error exponent both in the one-shot and asymptotic regimes for the classical-quantum and the entanglement-assisted channel coding problems. Our bounds are expressed in terms of measured (for the one-shot bounds) and sandwiched (for the asymptotic bounds) channel Rényi mutual information of order between 1/2 and 1. The bounds are not comparable with some previously established bounds for general channels, yet they are tight (for rates close to capacity) when the channel is classical. Finally, we also use our new decoder to rederive Cheng’s recent tight bound on the decoding error probability, which implies that most existing asymptotic results also hold for the new decoder.

arXiv:2310.09014•IEEE Transactions on Information Theory•Aug 20, 2024•10 citations
In this work, we prove a one-shot random coding bound for classical-quantum channel coding, a problem conjectured by Burnashev and Holevo in 1998. By choosing the optimal input distribution, the bound implies the optimal error exponent (i.e., the reliability function) of classical-quantum channels for rates above the critical rate, even in infinite-dimensional Hilbert spaces. Our result extends to various quantum packing-type problems, including classical communication over any fully quantum channel with or without entanglement-assistance, constant composition codes, and classical data compression with quantum side information via fixed-length or variable-length coding. Our technical ingredient is to establish an operator layer cake theorem - the directional derivative of an operator logarithm admits an integral representation of certain projections. This shows that a kind of pretty-good measurement is equivalent to a randomized Holevo-Helstrom measurement, which provides an operational explanation of why the pretty-good measurement is pretty good.
We establish Gallager’s random coding bound for classical-quantum channels, thereby resolving a long-standing conjecture proposed by Burnashev and Holevo in 1998. By optimizing the input distribution, this bound achieves the optimal error exponent—known as the reliability function—for rates above the critical rate, even in infinite-dimensional Hilbert spaces. Furthermore, the established bound is immediately applicable to general quantum channels and a variety of broader quantum information-theoretic tasks.
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 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.
Single-shot quantum information theory is governed not only by entropy exponents, but also by the finite-resource constants that multiply them. These constants directly affect the quantitative performance of decoupling, covering, convex-splitting, position-based decoding, and one-shot communication protocols, yet they are often inherited from nonoptimal scalar estimates or from classical-to-quantum lifting arguments that introduce additional losses. In this work we show that the operator layer-cake representation provides a mechanism for lifting sharp scalar inequalities to the noncommutative setting without loss. Using an iterative Riemann--Stieltjes integration-by-parts method, we derive sharp quantum trace inequalities that tighten several standard single-shot bounds. For a logarithmic trace inequality recently introduced by Cheng \emph{et al.}\ and subsequently used in quantum covering and decoupling problems, we determine the exact optimal prefactor, replacing the previously known constant by a smaller Lambert-WWW constant and proving universal optimality for positive operators. We also completely characterize the threshold behavior that appears under normalization to quantum states. In addition, we establish optimal two-sided collision-divergence inequalities, which lead to improved position-based decoding and single-shot classical communication bounds. These results show that several finite-resource bounds in single-shot quantum information can be tightened, and that within the layer-cake Rényi-divergence framework the resulting constants are genuine optimality barriers rather than artifacts of the proof.
We introduce a new quantum decoder based on a variant of the pretty good measurement, but defined via an alternative matrix quotient. We then use this novel decoder to derive new lower bounds on the error exponent both in the one-shot and asymptotic regimes for the classical-quantum and the entanglement-assisted channel coding problems. Our bounds are expressed in terms of measured (for the one-shot bounds) and sandwiched (for the asymptotic bounds) channel Rényi mutual information of order between 1/2 and 1. The bounds are not comparable with some previously established bounds for general channels, yet they are tight (for rates close to capacity) when the channel is classical. Finally, we also use our new decoder to rederive Cheng’s recent tight bound on the decoding error probability, which implies that most existing asymptotic results also hold for the new decoder.