Holevo random-coding exponent for classical–quantum channels

Problem

Does every memoryless classical–quantum channel with a finite input alphabet and finite-dimensional output satisfy the random-coding lower bound in Eq. (5), including channels with mixed, noncommuting output states?

Let \(W:x\mapsto W_x\) map a finite alphabet \(\mathcal X\), with \(|\mathcal X|\geq2\), to density operators on a finite-dimensional Hilbert space \(\mathcal H_B\). All logarithms have base two. An \(n\)-use code consists of \(M\) distinct words \(x^n(m)\in\mathcal X^n\) and a decoding POVM \(\{\Lambda_m\}_{m=1}^M\) on \(\mathcal H_B^{\otimes n}\). For equiprobable messages, its average error is Eq. (1):

\begin{equation} p_e(\mathcal C_n,\Lambda):=1-\frac1M\sum_{m=1}^M\operatorname{Tr}\!\left[\Lambda_m\bigotimes_{i=1}^nW_{x_i(m)}\right]. \tag{1} \end{equation}

For \(0<R<\log|\mathcal X|\), optimize over codes of rate at least \(R\) and define the reliability function using Eq. (2):

\begin{equation} p_e^*(n,R):=\inf_{\mathcal C_n,\Lambda:\,|\mathcal C_n|\geq2^{nR}}p_e(\mathcal C_n,\Lambda), \qquad E(W,R):=\limsup_{n\to\infty}-\frac1n\log p_e^*(n,R). \tag{2} \end{equation}

The decoding measurement is unrestricted; the communication uses no shared entanglement or feedback. For a probability distribution \(p\) on \(\mathcal X\), define the auxiliary function and random-coding exponent by Eqs. (3) and (4):

\begin{equation} E_0(s,p,W):=-\log\operatorname{Tr}\!\left[\left(\sum_{x\in\mathcal X}p(x)W_x^{1/(1+s)}\right)^{1+s}\right], \qquad E_0(s,W):=\max_pE_0(s,p,W),\qquad s\geq0. \tag{3} \end{equation}

\begin{equation} E_r(W,R):=\max_{0\leq s\leq1}\{E_0(s,W)-sR\}. \tag{4} \end{equation}

The conjectured achievability assertion is

\begin{equation} E(W,R)\geq E_r(W,R)\qquad\text{for every such }W\text{ and }R. \tag{5} \end{equation}

Source

This is the asymptotic random-coding lower bound in Section II, Eq. (6), pp. 4–5 of Holevo’s arXiv version 2; it follows from the finite-block conjecture in his Eq. (5) [Hol00].

Progress

Renes proves Eq. (5) for arbitrary finite-alphabet classical–quantum channels with finite-dimensional output in Theorem 3.1, Eq. (22). His construction combines privacy-amplification bounds with distribution shaping and allows arbitrary mixed output states. The proof appeared in July 2024 and was published in 2025 [Ren25].
Li and Yang independently prove the same lower bound in Theorem 2, Eq. (13), with parameter \(\alpha=1/(1+s)\in[1/2,1]\). Their Theorem 3 also identifies the exact reliability function in its stated high-rate regime below capacity by combining achievability with a sphere-packing converse. The present record does not assert an unrestricted sphere-packing converse at the capacity endpoint, where zero-error codes can create exceptions. This result was published in January 2025 [LY25].
Cheng and Liu, Theorem 3.2 of arXiv version 4, establish the finite-block Burnashev–Holevo random-coding bound itself with a dimension-independent prefactor bounded by \(1.102\), resolving the finite-block conjecture underlying the source formulation. Section 3.1 extends the bound to finite input alphabets with separable infinite-dimensional output Hilbert spaces. The work has an ISIT 2026 conference publication [CL26].

Comment

The archived statement is the random-coding achievability inequality, which is fully solved. Determining the exact reliability function for all rates below capacity is a broader question: the low-rate regime where the random-coding and sphere-packing bounds differ remains outside this solved statement. No exact duplicate was found in the authored catalog, ledger proposals, or private pool. The literature audit checked primary full sources and later work through 9 September 2026; it was not an exhaustive citation-index review. The originating formulation was checked directly in Holevo’s Section II.

References

[Hol00]: A. S. Holevo, “Reliability Function of General Classical-Quantum Channel,” IEEE Transactions on Information Theory 46, 2256–2261 (2000).DOI arXiv
[Ren25]: J. M. Renes, “Tight Lower Bound on the Error Exponent of Classical-Quantum Channels,” IEEE Transactions on Information Theory 71, 530–538 (2025).DOI arXiv
[LY25]: K. Li and D. Yang, “Reliability Function of Classical-Quantum Channels,” Physical Review Letters 134, 010802 (2025).DOI arXiv
[CL26]: P.-C. Liu and H.-C. Cheng, “Gallager’s Random Coding Bound for Classical-Quantum Channels and Beyond,” in 2026 IEEE International Symposium on Information Theory (ISIT) (2026). Extended version: H.-C. Cheng and P.-C. Liu, “Error Exponents for Quantum Packing Problems via an Operator Layer Cake Theorem,” arXiv version 4, 4 June 2026.DOI arXiv

Holevo random-coding exponent for classical–quantum channels

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems