Holevo–Schumacher–Westmoreland capacity theorem for finite cq channels

Write ${\chi }_{\ast }={\sup }_{p\in \mathrm{\Delta }(\mathcal{X})}{\chi }_p$. The simplex is nonempty, closed, and bounded. For each state ${\rho }_x$, [F12] diagonalizes it with nonnegative eigenvalues summing to one by [F16], so its action on a unit vector has norm at most one and [F15] gives $\mathrm{\parallel }{\rho }_x\mathrm{\parallel }\le 1$. Therefore $\mathrm{\parallel }{\bar{\rho }}_p-{\bar{\rho }}_q\mathrm{\parallel }\le {\sum }_x\mathrm{\mid }{p}_x-q_x\mathrm{\mid }$. Fix an orthonormal basis identifying $H_B$ unitarily with ${\mathbb{C}}^{\dim H_B}$; this preserves spectra and operator norm, so [F7] applies. Thus the first entropy term in ${\chi }_p$ is continuous in $p$; the second is a finite linear sum. Thus [F14] shows the supremum is attained, so ${\chi }_{\ast }={\max }_p{\chi }_p$. A point-mass input law gives ${\chi }_p=0$ by [F2], hence ${\chi }_{\ast }\ge 0$.

Fix $p$ and $0<R<{\chi }_p$. Choose $\delta >0$ with $R<{\chi }_p-2\delta$. Let $T_n$ be the input typical set from [F4], with excluded probability ${\eta }_n\to 0$. Since ${\eta }_n\to 0$, $p^{\otimes n}(T_n)=1-{\eta }_n>0$ for all sufficiently large $n$; for each earlier blocklength choose a fixed $x_0\in \mathcal{X}$ and use the one-message code with word $x_0^n$ and decoding POVM $\{I\}$. Draw each large-$n$ codeword independently from $p^{\otimes n}$ conditioned on $T_n$. Its mean output state is ${\bar{\sigma }}_n^{\mathrm{\prime }}=\mathbb{E}[{\rho }_{X^n}\mid X^n\in T_n]⪯(1-{\eta }_n{)}^{-1}{\bar{\rho }}_p^{\otimes n},{\bar{\rho }}_p={\sum }_x{p}_x{\rho }_x\mathrm{.}$ The global typical projector from [F4] therefore obeys ${\mathrm{\Pi }}_n{\bar{\sigma }}_n^{\mathrm{\prime }}{\mathrm{\Pi }}_n⪯(1-{\eta }_n{)}^{-1}{e}^{-n(S({\bar{\rho }}_p)-\delta )}{\mathrm{\Pi }}_n$. Each conditional projector has acceptance at least $1-u_n$, rank at most $e^{n(H(B\mathrm{\mid }X)+\delta )}$, and the global projector accepts every conditioned codeword with at least $1-u_n$, where $u_n\to 0$ and $H(B\mathrm{\mid }X)={\sum }_x{p}_{x}S({\rho }_x)$.

Consider any $(n,M)$ code with $M\ge 2$, uniform message $J$, output states ${\omega }_m={⨂}_i{\rho }_{x_i(m)}$, decoding outcome $\widehat{J}$, and average error $e$. The Holevo measurement bound [F3] gives $I(J;\widehat{J})\le \chi (\{1\mathrm{/}M,{\omega }_m\})$. Applying Fano [F8] and the finite mutual-information identity [F9], with $H(J)=\ln M$, yields $(1-e)\ln M\le \chi (\{1\mathrm{/}M,{\omega }_m\})+\ln 2$. For $M=1$, [F2] gives $\chi (\{1,{\omega }_1\})=S({\omega }_1)-S({\omega }_1)=0$, so the inequality is $0\le \ln 2$.

Since ${\eta }_n\to 0$, choose $N$ large enough that $p^{\otimes n}(T_n)=1-{\eta }_n>0$ and ${\eta }_n\le 1\mathrm{/}2$ for every $n\ge N$. For the finite prefix $n<N$, set $M_n=1$ and use the one-message code from step 1.2. For $n\ge N$, set $M_n=\lfloor e^{nR}\rfloor$ and apply the packing lemma [F5] to the conditional input law on $T_n$, with $d=e^{n(H(B\mathrm{\mid }X)+\delta )}$ and $D^{-1}=(1-{\eta }_n{)}^{-1}{e}^{-n(S({\bar{\rho }}_p)-\delta )}$. It gives expected average error at most $2(u_n+2\sqrt{u_n})+4(M_n-1)(1-{\eta }_n{)}^{-1}{e}^{-n({\chi }_p-2\delta )}\mathrm{.}$ Since $(1-{\eta }_n{)}^{-1}\le 2$ for $n\ge N$ and $R<{\chi }_p-2\delta$, this tends to zero. Merge the packing POVM's failure effect ${\mathrm{\Lambda }}_0$ into message 1: put ${\mathrm{\Lambda }}_1^{\mathrm{\prime }}={\mathrm{\Lambda }}_1+{\mathrm{\Lambda }}_0$ and ${\mathrm{\Lambda }}_m^{\mathrm{\prime }}={\mathrm{\Lambda }}_m$ for $2\le m\le M_n$. These $M_n$ effects are positive and sum to $I$; message 1's success increases by $\mathrm{tr}({\mathrm{\Lambda }}_0{\rho }_{x^n(1)})\ge 0$, while every other success is unchanged. Thus their average error obeys the same expectation bound, including $M_n=1$. The codebook space is finite; order $\mathcal{X}$ once and choose its lexicographically first codebook whose average error is at most this expectation. This defines a deterministic code for each $n\ge N$ without any choice axiom, and the finite one-message prefix does not affect $n^{-1}\ln M_n\to R$.

Let $p_i(x)=M^{-1}\mathrm{\mid }\{m:x_i(m)=x\}\mathrm{\mid }$ and $\bar{\omega }=M^{-1}{\sum }_m{\omega }_m$. By [F17], its $i$th marginal is ${\bar{\rho }}_i={\sum }_x{p}_i(x){\rho }_x$, which is a state by [F16]. For any bipartite state ${\tau }_{AC}$, tensor it with the unique state on a one-dimensional middle register $B=\mathbb{C}$: the four entropies in [F6] become $S({\tau }_A),S({\tau }_C),0,S({\tau }_{AC})$, because tensoring with this factor leaves the spectrum unchanged. Thus [F6] implies $S({\tau }_{AC})\le S({\tau }_A)+S({\tau }_C)$; iterating gives $S(\bar{\omega })\le {\sum }_{i}S({\bar{\rho }}_i)$. Product entropy is additive: diagonalize each ${\rho }_{x_i(m)}$ by [F12], so every positive product eigenvalue has logarithm equal to the sum of its coordinate logarithms by [F13]; zero eigenvalues contribute zero by [F2]. Summing these finite terms gives $S({\omega }_m)={\sum }_{i}S({\rho }_{x_i(m)})$. Therefore $\chi (\{1\mathrm{/}M,{\omega }_m\})=S(\bar{\omega })-\frac{1}{M}{\sum }_{m}S({\omega }_m)\le {\sum }_{i=1}^n[S({\bar{\rho }}_i)-{\sum }_x{p}_i(x)S({\rho }_x)]={\sum }_i{\chi }_{p_i}\le n{\chi }_{\ast }\mathrm{.}$

The selected codes have average error tending to zero and $n^{-1}\ln M_n\to R$. If $R=0$, the single-message code has zero error. When ${\chi }_{\ast }>0$, taking a maximizing $p$ from step 1.1 proves achievability of every $0\le R<{\chi }_{\ast }$. When ${\chi }_{\ast }=0$, the single-message code shows that rate zero is reliable.

Combining steps 1.3 and 2.2 gives $(1-e)\ln M\le n{\chi }_{\ast }+\ln 2$. For any reliable sequence, divide by $n$ and let $n\to \mathrm{\infty }$; since $e_n\to 0$, its limiting upper rate is at most ${\chi }_{\ast }$. Together with step 3.1 and the capacity definition [F1], this proves the theorem.