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

Concavity of the Auxiliary Function for Classical-Quantum Channels

Cheng, HC, Min-Hsiu Hsieh

Published Oct 1, 2016• 10 citations
OpenAlex

Abstract

© 2016 IEEE. The auxiliary function of a classical channel appears in two fundamental quantities, the random coding exponent and the sphere-packing exponent, which yield upper and lower bounds on the error probability of decoding, respectively. A crucial property of the auxiliary function is its concavity, and this property consequently leads to several important results in finite blocklength analysis. In this paper, we prove that the auxiliary function of a classical-quantum channel also enjoys the same concavity property, extending an earlier partial result to its full generality. We also prove that the auxiliary function satisfies the data-processing inequality, among various other important properties. Furthermore, we show that the concavity property of the auxiliary function enables a geometric interpretation of the random coding exponent and the sphere-packing exponent of a classical-quantum channel. The key component in our proof is an important result from the theory of matrix geometric means.

Related papers

Concavity of the Auxiliary Function for Classical-Quantum Channels

Hao-Chung Cheng, Min-Hsiu Hsieh

The auxiliary function of a classical channel appears in two fundamental quantities, the random coding exponent and the sphere-packing exponent, which yield upper and lower bounds on the error probability of decoding, respectively. A crucial property of the auxiliary function is its concavity, and this property consequently leads to several important results in finite blocklength analysis. In this paper, we prove that the auxiliary function of a classical-quantum channel also enjoys the same concavity property, extending an earlier partial result to its full generality. We also prove that the auxiliary function satisfies the data-processing inequality, among various other important properties. Furthermore, we show that the concavity property of the auxiliary function enables a geometric interpretation of the random coding exponent and the sphere-packing exponent of a classical-quantum channel. The key component in our proof is an important result from the theory of matrix geometric means.

arXiv:1602.03297•IEEE Transactions on Information Theory•Aug 9, 2016•11 citations

Remarks on concavity of the auxiliary function appearing in quantum reliability function in classical-quantum channels

J.I. Fujii, R. Nakamoto, K. Yanagi

This is an extension of results represented in ISIT2003. Concavity of the auxiliary function which appears in the random coding exponent as the lower bound of the quantum reliability function for general quantum states is proven for 0 /spl les/ s /spl les/ 1.

arXiv:cs/0501057•IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•1 citation

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

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

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

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•51 citations
© 2016 IEEE. The auxiliary function of a classical channel appears in two fundamental quantities, the random coding exponent and the sphere-packing exponent, which yield upper and lower bounds on the error probability of decoding, respectively. A crucial property of the auxiliary function is its concavity, and this property consequently leads to several important results in finite blocklength analysis. In this paper, we prove that the auxiliary function of a classical-quantum channel also enjoys the same concavity property, extending an earlier partial result to its full generality. We also prove that the auxiliary function satisfies the data-processing inequality, among various other important properties. Furthermore, we show that the concavity property of the auxiliary function enables a geometric interpretation of the random coding exponent and the sphere-packing exponent of a classical-quantum channel. The key component in our proof is an important result from the theory of matrix geometric means.
The auxiliary function of a classical channel appears in two fundamental quantities, the random coding exponent and the sphere-packing exponent, which yield upper and lower bounds on the error probability of decoding, respectively. A crucial property of the auxiliary function is its concavity, and this property consequently leads to several important results in finite blocklength analysis. In this paper, we prove that the auxiliary function of a classical-quantum channel also enjoys the same concavity property, extending an earlier partial result to its full generality. We also prove that the auxiliary function satisfies the data-processing inequality, among various other important properties. Furthermore, we show that the concavity property of the auxiliary function enables a geometric interpretation of the random coding exponent and the sphere-packing exponent of a classical-quantum channel. The key component in our proof is an important result from the theory of matrix geometric means.
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.
“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.
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.
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.