Holevo–Schumacher–Westmoreland Classical Capacity

HSW is the reference point for a whole industry of channel-capacity calculations. For any additive channel — entanglement-breaking links, unital qubit channels, the depolarizing and dephasing channels — the classical capacity is a finite optimization that designers of quantum networks actually run, setting the rate budget for trusted-node relays and repeater segments; the depolarizing formula $C=1-H_2(p/2)$ is the workhorse benchmark for testing decoder constructions. On the fundamental side, Hastings' 2009 disproof of additivity turned HSW from a "solved" problem into an open one: because $C$ is generally not single-letter, a major research thread hunts for computable upper bounds, notably the entanglement-assisted capacity $C_E$, which is single-letter and squeezes $C$ from above. HSW also anchors the "capacity zoo": comparing $C$ (classical), $Q$ (quantum, the Lloyd–Shor–Devetak theorem), $C_E$, and the private capacity $P$ tells a network architect which resource a given link carries best. And in continuous-variable optics, the Gaussian HSW capacity governs bosonic fiber and free-space channels, where the 2014 solution of the minimum-output-entropy conjecture finally pinned down the capacity of the pure-loss channel that describes real optical communication.

Recall Shannon's noisy-channel theorem: a classical channel transmits $C=\max_{p(x)} I(X;Y)$ bits per use, achieved by random codebooks decoded by joint typicality. HSW lifts this to quantum outputs. Alice chooses signal states $\rho_x$ with probabilities $p_x$; the channel maps each to $\mathcal{N}(\rho_x)$; Bob must distinguish roughly $2^{n\chi}$ output sequences. The role $I(X;Y)$ played classically is now played by the Holevo information $\chi$, and the received string becomes a quantum state Bob can only read by measurement — a measurement that inevitably disturbs what it reads. The Holevo quantity $\chi=S(\bar\rho)-\sum_x p_x S(\mathcal{N}(\rho_x))$ measures how much the average output $\bar\rho=\sum_x p_x\mathcal{N}(\rho_x)$ spreads beyond the average spread of the individual signals. A large $S(\bar\rho)$ means many distinguishable configurations; subtracting the average noise entropy removes the part the channel already smeared out. The difference is the bits per use Bob can reliably recover — the first figure shows this pipeline.

Why regularize? Holevo information is generally superadditive: $\chi^\star(\mathcal{N}\otimes\mathcal{M})$ can exceed $\chi^\star(\mathcal{N})+\chi^\star(\mathcal{M})$. Entangled signal states spread across two uses, decoded together, sometimes carry more classical information than any product strategy applied use-by-use. So the operational capacity is the per-letter limit over $n$ uses — even though the optimal inputs within a block may need to be entangled to reach it. For many important channel families this never happens and the single-letter formula is exact; the second figure shows the cleanest such case, the qubit depolarizing channel, where King proved additivity and the capacity has a closed form.

The decoding measurement is the engine of achievability, and where the quantum story departs from Shannon's. A square-root (pretty-good) measurement built from the codeword output states, projected onto the typical subspace of $\bar\rho^{\otimes n}$, succeeds with high probability whenever the rate is below $\chi$ — the quantum analogue of jointly-typical decoding. Its analysis leans on a gentle measurement lemma: a test nearly certain to pass barely disturbs the state, so successive tests chain without back-action snowballing into error.

The central object is the Holevo information of an ensemble evaluated after the channel — the entropy of the average output minus the average of the individual output entropies. Everything downstream either optimizes this quantity or proves the optimum is operationally meaningful.

where: $\{p_x,\rho_x\}$ — input ensemble, signal states $\rho_x$ chosen with probability $p_x$; $\mathcal{N}$ — the CPTP channel applied to each signal; $S(\rho)=-\mathrm{Tr}(\rho\log_2\rho)$ — von Neumann entropy in bits; $\bar\rho=\sum_x p_x\mathcal{N}(\rho_x)$ — average output state. Reading: total output spread minus the spread the channel imposes on each point is what stays distinguishable. Optimizing over the ensemble gives the single-shot Holevo capacity, attained on pure signal states with a bounded number of them (Carathéodory).

where: $\max$ — over all input ensembles; the optimum is attained using at most $d^2$ pure signal states, with $d=\dim$ of the input. Reading: a single-use figure of merit, computable by finite optimization. The operational capacity is the regularized Holevo information — the per-use limit as block length grows, with entangled inputs allowed within each block. The regularization is not a technicality; superadditivity forces it.

where: $\mathcal{N}^{\otimes n}$ — $n$ parallel uses of the channel, with entangled inputs allowed across the block; $C(\mathcal{N})$ — classical capacity in bits per channel use. Reading: capacity is the best block Holevo information averaged over ever-longer blocks. Product-input random coding achieves the single-letter value, so $\chi^\star$ is always a lower bound on capacity, and exact when $\chi$ is additive.

where: $\ge$ — the HSW achievability half, product codes reach $\chi^\star$. Reading: tight for entanglement-breaking, unital-qubit, and depolarizing channels. The converse rests on Holevo's bound, which caps the accessible classical information extractable by any measurement Bob makes on a single output.

where: $I_{\mathrm{acc}}=\max_{\text{POVM}} I(X;Y)$ — accessible information, the best classical mutual information over Bob's measurements. Reading: no measurement reads out more than $\chi$ bits about $x$ — the seed of the converse. Achievability is powered by a specific decoder — the square-root (pretty-good) measurement built from the codeword output states, sandwiched inside the typical-subspace projector.

where: $\sigma_m=\mathcal{N}^{\otimes n}(\rho_{x^n(m)})$ — output of the codeword for message $m$; $\Pi$ — projector onto the typical subspace of $\bar\rho^{\otimes n}$; $\{\Lambda_m\}$ — a valid POVM decoding to $m$. Reading: a genuine POVM that "points at" whichever codeword the output most resembles. The gentle measurement lemma controls the back-action: a test almost certain to succeed leaves the state almost undisturbed, so the decoder's sequential tests do not accumulate damage.

where: $\Lambda$ — measurement operator nearly certain to accept $\rho$; $\|\cdot\|_1$ — trace norm measuring state disturbance. Reading: near-certain success buys near-invisibility — the quantum substitute for classical readout having no back-action. Finally, the fact that forces the regularization: Holevo information can be strictly superadditive.

where: strictness is Hastings' 2009 result. Reading: because it can be strict, $\tfrac1n\chi^\star(\mathcal{N}^{\otimes n})$ can rise with $n$, so only the limit (3) is the true capacity.

The regularized formula (3) collapses to the single-letter $\chi^\star$ for several important families, and takes a closed form in the cleanest cases.

1 · Holevo information of two non-orthogonal signals (why χ is not just log of the message count)

Alice sends the pure states $|0\rangle$ and $|{+}\rangle=(|0\rangle+|1\rangle)/\sqrt2$, each with probability $\tfrac12$, through the noiseless qubit channel. There are two messages, so a naive count says "1 bit." Find the Holevo information $\chi$ and interpret it.

Step 1. The signal states are pure and the channel is the identity, so each output entropy vanishes: $S(\omega_x)=0$. Thus $\chi=S(\bar\rho)$ with $\bar\rho=\tfrac12|0\rangle\langle0|+\tfrac12|{+}\rangle\langle{+}|$. In matrix form $\bar\rho=\tfrac12\!\begin{pmatrix}1&0\\0&0\end{pmatrix}+\tfrac12\!\cdot\!\tfrac12\!\begin{pmatrix}1&1\\1&1\end{pmatrix}=\begin{pmatrix}0.75&0.25\\0.25&0.25\end{pmatrix}$.

Step 2. Diagonalize $\bar\rho$: trace $=1$, determinant $=0.75\cdot0.25-0.25^2=0.125$, giving eigenvalues $\lambda_\pm=\tfrac12(1\pm\sqrt{1-4\cdot0.125})=\tfrac12(1\pm\sqrt{0.5})$, i.e. $\lambda_+=0.8536$ and $\lambda_-=0.1464$.

Step 3. The Holevo information is the entropy of these eigenvalues: $\chi=-0.8536\log_2 0.8536-0.1464\log_2 0.1464=\mathbf{0.601\ \text{bits}}$. Because the two states are non-orthogonal, they cannot be perfectly distinguished, and the Holevo bound guarantees that no measurement whatsoever extracts more than $0.601$ bits about which state was sent — strictly less than the $1$ bit a message count would suggest. χ ≈ 0.601 bits, well below log₂2 = 1, exactly because ⟨0|+⟩ ≠ 0.

2 · Classical capacity of the qubit depolarizing channel (fully worked)

The depolarizing channel is $\mathcal{N}_p(\rho)=(1-p)\rho+p\,\tfrac{I}{2}$ with $p=0.2$. Using King's additivity result, compute its exact classical capacity.

Step 1. King proved $\chi$ is additive for the depolarizing channel, so $C=\chi^\star$ — no regularization. By the unitary covariance of $\mathcal{N}_p$, the optimal ensemble is any uniform basis ensemble (e.g. $\{|0\rangle,|1\rangle\}$ each with probability $\tfrac12$), for which the average output is maximally mixed, $\bar\rho=I/2$, so $S(\bar\rho)=1$.

Step 2. For a pure input, say $|0\rangle$, the output is $(1-p)|0\rangle\langle0|+p\,\tfrac{I}{2}$, with eigenvalues $1-\tfrac{p}{2}$ and $\tfrac{p}{2}$. At $p=0.2$ these are $0.9$ and $0.1$, so the output (noise) entropy is $S(\mathcal{N}(\rho_x))=H_2(0.1)=-0.1\log_2 0.1-0.9\log_2 0.9=\mathbf{0.469\ \text{bits}}$, the same for every pure input.

Step 3. Therefore $C=\chi^\star=S(\bar\rho)-H_2(p/2)=1-H_2(0.1)=1-0.469=\mathbf{0.531\ \text{bits per use}}$. As a sanity check the closed form $C=1-H_2(p/2)$ gives $C=1$ at $p=0$ (noiseless) and $C=0$ at $p=1$ (the channel then outputs $I/2$ regardless of input, transmitting nothing). C(0.2) = 0.531 bits/use, monotonically decreasing from 1 to 0 as the noise grows.

The classical capacity of a quantum channel is where Shannon's 1948 information theory finally met quantum mechanics — and the letter H in HSW belongs to the mathematician who saw the connection first and carried it furthest.

References. Nielsen & Chuang, Quantum Computation and Quantum Information, §12.3–12.4 · Wilde, Quantum Information Theory (2nd ed.), Ch. 20 (Classical Communication) · Watrous, The Theory of Quantum Information, Ch. 8 · Holevo, IEEE Trans. Inf. Theory 44, 269 (1998) · Schumacher & Westmoreland, Phys. Rev. A 54, 1869 (1996) and 56, 131 (1997) · Hastings, Nature Physics 5, 255 (2009) — superadditivity counterexample · King, IEEE Trans. Inf. Theory 49, 221 (2003) — depolarizing additivity · Shor, Commun. Math. Phys. 246, 453 (2004) — entanglement-breaking additivity · Preskill, Lecture Notes on Quantum Computation, Ch. 10. The identity $I(X;B)=\chi$ follows by direct entropy computation on the classical–quantum state. The converse chains Fano's inequality, data processing, and the Holevo bound. The achievability bound rests on Hayashi–Nagaoka applied to the typical-subspace dimensions $2^{n(S(\bar\omega)\pm\delta)}$ and $2^{n(\sum p_x S(\omega_x)\pm\delta)}$. The depolarizing capacity is $C=1-H_2(p/2)$ for $\mathcal{N}_p(\rho)=(1-p)\rho+pI/2$, with endpoints $C(0)=1$, $C(1)=0$, $C(0.2)=0.531$; a formula built from the Pauli-error distribution yields negative values and must not be used here. All entropies are in bits ($\log_2$); the worked numbers $\chi=0.601$ and $C=0.531$ are computed from the eigenvalues.

Builds on: Holevo Bound · Von Neumann Entropy · Quantum Channels and Completely Positive Trace-Preserving Maps · Quantum Relative Entropy · Shannon Entropy and Classical Information Measures. Leads to: Complementary Channels and Degradability · Strong Subadditivity of Quantum Entropy · Data-Processing Inequality.

Ask the tutor: Ask me to walk through why entangled inputs can beat product codes for a specific Hastings-type channel, or to compute the Holevo capacity of any channel you name step by step.