Simple Algorithm
Quantum Computing · Rydberg State · 32 min

Channel Capacities & Coding Theorems

Classical, quantum and entanglement-assisted capacities.

Shannon gave every classical channel one number, its capacity, computed by a single-letter formula. A quantum channel has several capacities, depending on whether you send bits or qubits and whether you may use entanglement, and most of them come with a twist: entangled inputs across channel uses can help, so the formulas must be regularized over infinitely many uses. One capacity, remarkably, keeps Shannon's simplicity. This lesson proves the coding theorems and maps what is still unknown.

What you’ll learn

  • State the Holevo–Schumacher–Westmoreland theorem and sketch its achievability (random coding, square-root measurement) and converse (Fano plus Holevo).
  • Explain additivity, Hastings' counterexample, and why the classical capacity requires regularization.
  • Define coherent information, state the Lloyd–Shor–Devetak theorem, and outline its decoupling proof; compute QQ for degradable and antidegradable channels.
  • Prove that the entanglement-assisted capacity max⁡ρI(R:B)\max_\rho I(R{:}B) is additive, and compare the capacities of standard channels.

Classical capacity: the HSW theorem

An (n,R,ε)(n,R,\varepsilon) code for a channel N:A→B\mathcal N:A\to B consists of 2nR2^{nR} input states on A⊗nA^{\otimes n} and a decoding POVM on B⊗nB^{\otimes n} that identifies each message with error at most ε\varepsilon. A rate RR is achievable if such codes exist with ε→0\varepsilon\to0 as n→∞n\to\infty, and the classical capacity C(N)C(\mathcal N) is the supremum of achievable rates. The natural single-use quantity is the Holevo information of the channel

χ(N)=max⁡{px,ρx}[S(N(∑xpxρx))−∑xpxS(N(ρx))],\chi(\mathcal N)=\max_{\{p_x,\rho_x\}}\Big[S\Big(\mathcal N\Big(\sum_xp_x\rho_x\Big)\Big)-\sum_xp_xS\big(\mathcal N(\rho_x)\big)\Big],

where pure input states and at most dA2d_A^2 of them suffice.

DerivationProof sketch
  1. Random coding. Fix an optimal ensemble {px,ρx}\{p_x,\rho_x\} and draw 2nR2^{nR} codewords xn(m)x^n(m) i.i.d. from p⊗np^{\otimes n}. Codeword mm is sent as the product state ρxn(m)=⨂iρxi(m)\rho_{x^n(m)}=\bigotimes_i\rho_{x_i(m)}, and Bob receives σm=N⊗n(ρxn(m))\sigma_m=\mathcal N^{\otimes n}(\rho_{x^n(m)}).

  2. Λm=(∑m′Πm′)−1/2Πm(∑m′Πm′)−1/2,Πm=Π Πxn(m) Π\Lambda_m=\Big(\sum_{m'}\Pi_{m'}\Big)^{-1/2}\Pi_m\Big(\sum_{m'}\Pi_{m'}\Big)^{-1/2},\qquad \Pi_m=\Pi\,\Pi_{x^n(m)}\,\Pi

    Square-root measurement, built from the typical projector Π\Pi of the average output σˉ⊗n\bar\sigma^{\otimes n} and the conditionally typical projector Πxn\Pi_{x^n} of each codeword.

  3. I−(S+T)−1/2S(S+T)−1/2 ≤ 2(I−S)+4T(0≤S≤I, T≥0)\id-(S+T)^{-1/2}S(S+T)^{-1/2}\ \le\ 2(\id-S)+4T\qquad(0\le S\le\id,\ T\ge0)

    The Hayashi–Nagaoka inequality, with S=ΠmS=\Pi_m and T=∑m′≠mΠm′T=\sum_{m'\neq m}\Pi_{m'}, splits the error into "the right codeword is atypical" and "a wrong codeword looks right".

  4. E perr(m) ≤ 2ϵtyp+4⋅2nR 2 n(∑xpxS(N(ρx))+δ) 2−n(S(σˉ)−δ)\mathbb E\,p_{\rm err}(m)\ \le\ 2\epsilon_{\rm typ}+4\cdot2^{nR}\,2^{\,n\left(\sum_xp_xS(\mathcal N(\rho_x))+\delta\right)}\,2^{-n\left(S(\bar\sigma)-\delta\right)}

    Averaging over the codebook, each wrong codeword's output is distributed as σˉ⊗n\bar\sigma^{\otimes n}, and a conditionally typical projector has rank at most 2n(∑xpxS+δ)2^{n(\sum_xp_xS+\delta)}. The bound tends to 0 whenever R<χ−2δR<\chi-2\delta; expurgating the worst half of the codewords makes the maximum error small too.

  5. nR ≤ I(M:M^)+1+εnR ≤ χ(N⊗n)+1+εnRnR\ \le\ I(M{:}\hat M)+1+\varepsilon nR\ \le\ \chi\big(\mathcal N^{\otimes n}\big)+1+\varepsilon nR

    Converse. Fano's inequality, then the Holevo bound for the ensemble of codeword outputs, whose inputs may be entangled across the nn uses. Divide by nn and let ε→0\varepsilon\to0. ■\blacksquare

For many channels the regularization is unnecessary because χ\chi is additive, χ(N⊗M)=χ(N)+χ(M)\chi(\mathcal N\otimes\mathcal M)=\chi(\mathcal N)+\chi(\mathcal M). King (2003) proved it for the qubit depolarizing channel ρ↦(1−p)ρ+p I/2\rho\mapsto(1-p)\rho+p\,\id/2, whose pure-state outputs have eigenvalues 1−p21-\tfrac p2 and p2\tfrac p2, so C=1−h(p2)C=1-h(\tfrac p2). Additivity also holds for entanglement-breaking and unital qubit channels.

Superadditivity: why regularize

Hastings' channels are random-unitary channels in large dimension, mixing a few Haar-random unitaries, paired with their complex conjugates: feeding a maximally entangled state into N⊗Nˉ\mathcal N\otimes\bar{\mathcal N} yields an output with one large eigenvalue, purer than any product input achieves. The violation is small and the construction probabilistic; no explicit low-dimensional counterexample is known. Earlier, Werner & Holevo (2002) had refuted the related multiplicativity of maximal output pp-norms for large pp.

Check your understanding

What does Hastings' result imply for the classical capacity?

  1. Quantum channels cannot carry classical information at the Holevo rate
  2. The classical capacity is uncomputable
  3. Entanglement shared between sender and receiver increases the classical capacity
  4. For some channels, codewords entangled across channel uses beat every product-input code, so CC must be defined by the regularized formula
Show the answer

D. For some channels, codewords entangled across channel uses beat every product-input code, so CC must be defined by the regularized formula

Non-additivity of Smin⁡S_{\min} gives non-additivity of χ\chi, so χ(N⊗n)/n\chi(\mathcal N^{\otimes n})/n can exceed χ(N)\chi(\mathcal N). The extra rate comes from entangled inputs, not from pre-shared entanglement.

Quantum capacity: coherent information and LSD

DerivationAchievability by decoupling
  1. Choose a random code subspace of dimension 2nR2^{nR} inside the typical subspace of ρ⊗n\rho^{\otimes n}, and let a reference R′R' be maximally entangled with it. Sending it through V⊗nV^{\otimes n} gives a pure state on R′BnEnR'B^nE^n.

  2. ∥ωR′En−τR′⊗ωEn∥1 ≲ 2−n2(Ic(ρ,N)−R−δ)(on average over codes)\norm{\omega_{R'E^n}-\tau_{R'}\otimes\omega_{E^n}}_1\ \lesssim\ 2^{-\frac n2\left(I_c(\rho,\mathcal N)-R-\delta\right)}\quad\text{(on average over codes)}

    The decoupling theorem: a random subspace leaves the environment almost uncorrelated with the reference whenever R<S(B)−S(E)R<S(B)-S(E) (Hayden, Horodecki, Winter & Yard, 2008).

  3. Uhlmann's theorem. If R′EnR'E^n is nearly a product with R′R' maximally mixed, the global pure state is close to one in which BnB^n holds a purification of R′R'; Uhlmann provides an isometry on BnB^n alone that maps between them. That isometry is Bob's decoder: he recovers the entanglement with R′R', hence any state in the code space.

  4. Converse. For any code achieving fidelity 1−ε1-\varepsilon, data processing for coherent information, Ic(ρ,N2∘N1)≤Ic(ρ,N1)I_c(\rho,\mathcal N_2\circ\mathcal N_1)\le I_c(\rho,\mathcal N_1) (Schumacher & Nielsen, 1996), plus continuity of entropy give nR≤Q(1)(N⊗n)+o(n)nR\le Q^{(1)}(\mathcal N^{\otimes n})+o(n). ■\blacksquare

Channel classQuantum capacityExample
Degradable: Nc=D∘N\mathcal N^c=\mathcal D\circ\mathcal NQ=Q(1)Q=Q^{(1)}, additive (Devetak & Shor, 2005)Amplitude damping, γ≤12\gamma\le\tfrac12: Q=max⁡0≤p≤1[h((1−γ)p)−h(γp)]Q=\max_{0\le p\le1}\big[h((1-\gamma)p)-h(\gamma p)\big]; for γ=14\gamma=\tfrac14, Q≈0.41Q\approx0.41, attained near p≈0.45p\approx0.45, not at p=12p=\tfrac12
Antidegradable: N=A∘Nc\mathcal N=\mathcal A\circ\mathcal N^cQ=0Q=0Amplitude damping with γ≥12\gamma\ge\tfrac12; erasure with ε≥12\varepsilon\ge\tfrac12; every entanglement-breaking channel
Erasure, probability ε\varepsilonmax⁡(0,1−2ε)\max(0,1-2\varepsilon) (Bennett, DiVincenzo & Smolin, 1997)degradable for ε≤12\varepsilon\le\tfrac12
Qubit depolarizingUnknown; hashing bound 1−H(1−3p4,p4,p4,p4)1-H\big(1-\tfrac{3p}4,\tfrac p4,\tfrac p4,\tfrac p4\big) is not optimalsuperadditive coherent information (DiVincenzo, Shor & Smolin, 1998)
Why antidegradable implies Q=0Q=0: if Eve can simulate Bob's output, any decoder that recovered the state for Bob would also recover it for Eve, producing two copies of an unknown state, which no-cloning forbids.

Entanglement assistance, and the landscape

DerivationWhy C_E needs no regularization
  1. I(R:B)=S(R)+S(B)−S(RB)=S(BE)+S(B)−S(E)=S(B)+S(B∣E)I(R{:}B)=S(R)+S(B)-S(RB)=S(BE)+S(B)-S(E)=S(B)+S(B|E)

    ωRBE\omega_{RBE} is pure, so S(R)=S(BE)S(R)=S(BE) and S(RB)=S(E)S(RB)=S(E).

  2. S(B1B2)≤S(B1)+S(B2),S(B1B2∣E1E2)≤S(B1∣E1)+S(B2∣E2)S(B_1B_2)\le S(B_1)+S(B_2),\qquad S(B_1B_2|E_1E_2)\le S(B_1|E_1)+S(B_2|E_2)

    For N1⊗N2\mathcal N_1\otimes\mathcal N_2 with any input ρA1A2\rho_{A_1A_2}: subadditivity, and the chain rule followed by "conditioning reduces entropy" (strong subadditivity).

  3. I(R:B1B2) ≤ I(R1:B1)+I(R2:B2) ≤ CE(N1)+CE(N2)I(R{:}B_1B_2)\ \le\ I(R_1{:}B_1)+I(R_2{:}B_2)\ \le\ C_E(\mathcal N_1)+C_E(\mathcal N_2)

    Each term depends only on the marginal input ρAi\rho_{A_i}. Product inputs achieve equality, so CEC_E is additive. ■\blacksquare Achievability: share purifications of ρ⊗n\rho^{\otimes n}, let Alice apply random generalized Pauli operators to her half (superdense-coding style), and decode with HSW; the resulting ensemble has Holevo information nI(R:B)nI(R{:}B).

Predict before you look

For the qubit depolarizing channel with p=12p=\tfrac12, the optimal input is I/2\id/2 and the Choi state (1−p)∣Φ+⟩ ⁣⟨Φ+∣+p I/4(1-p)\dyad{\Phi^+}+p\,\id/4 has eigenvalues 58,18,18,18\tfrac58,\tfrac18,\tfrac18,\tfrac18. Compute CE=2−S(Choi state)C_E=2-S(\text{Choi state}).

Show the answer

0.45 bits

S=58log⁡285+38log⁡28≈0.424+1.125=1.549S=\tfrac58\log_2\tfrac85+\tfrac38\log_28\approx0.424+1.125=1.549, so CE≈0.45C_E\approx0.45, compared with C=1−h(14)≈0.19C=1-h(\tfrac14)\approx0.19. Entanglement more than doubles the rate here; as p→1p\to1 the ratio CE/CC_E/C tends to 3 for qubits.

CapacityFormulaSingle-letter in general?
Classical CClim⁡1nχ(N⊗n)\lim\frac1n\chi(\mathcal N^{\otimes n})No (Hastings, 2009)
Quantum QQlim⁡1nQ(1)(N⊗n)\lim\frac1nQ^{(1)}(\mathcal N^{\otimes n})No: coherent information is superadditive, and QQ can be superactivated
Private PPlim⁡1nmax⁡[I(X:Bn)−I(X:En)]\lim\frac1n\max\big[I(X{:}B^n)-I(X{:}E^n)\big] (Devetak; Cai, Winter & Yeung)No (Li, Winter, Zou & Guo, 2009)
Entanglement-assisted CEC_Emax⁡ρI(R:B)\max_\rho I(R{:}B)Yes
Superactivation (Smith & Yard, 2008): a 50% erasure channel and a PPT "Horodecki" channel each have Q=0Q=0, yet together they have Q>0Q>0. Capacities are not even functions you can add.

Key takeaways

  • HSW: product-input codes achieve exactly χ(N)\chi(\mathcal N); with entangled inputs C=lim⁡1nχ(N⊗n)C=\lim\frac1n\chi(\mathcal N^{\otimes n}). The proof uses random coding, the square-root measurement and the Hayashi–Nagaoka inequality; the converse is Fano plus Holevo.
  • Hastings (2009): minimum output entropy, hence χ\chi, is not additive, so regularization is genuinely needed.
  • LSD: Q=lim⁡1nQ(1)(N⊗n)Q=\lim\frac1nQ^{(1)}(\mathcal N^{\otimes n}) with Ic=S(B)−S(E)I_c=S(B)-S(E), proved by decoupling plus Uhlmann. Degradable channels: Q=Q(1)Q=Q^{(1)}; antidegradable: Q=0Q=0 (no-cloning).
  • BSST: CE=max⁡ρI(R:B)C_E=\max_\rho I(R{:}B) is single-letter and additive by strong subadditivity, and QE=CE/2Q_E=C_E/2.
  • The quantum capacity of the qubit depolarizing channel is still unknown, and superactivation shows capacities are not even additive functions of channels.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Which capacity of a general quantum channel is given by a single-letter formula, with no regularization?

  1. The classical capacity CC
  2. The entanglement-assisted capacity CEC_E
  3. The quantum capacity QQ
  4. The private capacity PP
Show the answer

B. The entanglement-assisted capacity CEC_E

CE=max⁡ρI(R:B)C_E=\max_\rho I(R{:}B) is additive by strong subadditivity, so one channel use tells the whole story. CC, QQ and PP are all superadditive for some channels.

Question 2

What is the quantum capacity of the amplitude-damping channel with γ=0.7\gamma=0.7?

  1. 1−h(0.7)≈0.121-h(0.7)\approx0.12
  2. About 0.30.3, the probability that the excitation survives
  3. It is unknown
  4. 00
Show the answer

D. 00

For γ≥12\gamma\ge\tfrac12 the complementary channel (amplitude damping with 1−γ≤121-\gamma\le\tfrac12) can simulate Bob's output: the channel is antidegradable, so Q=0Q=0 by the no-cloning argument.

Question 3

What does superactivation (Smith & Yard, 2008) demonstrate?

  1. Two channels, each with zero quantum capacity, can have positive quantum capacity when used together
  2. Entanglement assistance doubles every capacity
  3. The classical capacity can exceed the Holevo information
  4. Quantum capacity can be increased by free classical feedback for every channel
Show the answer

A. Two channels, each with zero quantum capacity, can have positive quantum capacity when used together

A PPT channel (zero QQ, but positive private capacity) and a 50% erasure channel (zero QQ by symmetry) combine to give Q(N1⊗N2)>0Q(\mathcal N_1\otimes\mathcal N_2)>0. Quantum capacity is not a function of the channels separately.

Question 4

Why is the quantum capacity of a degradable channel equal to its single-letter coherent information?

  1. Because degradable channels are entanglement-breaking
  2. Because degradable channels have zero private capacity
  3. Because for degradable channels the coherent information is additive, so Q(1)(N⊗n)=nQ(1)(N)Q^{(1)}(\mathcal N^{\otimes n})=nQ^{(1)}(\mathcal N)
  4. Because Bob can always simulate Alice's input
Show the answer

C. Because for degradable channels the coherent information is additive, so Q(1)(N⊗n)=nQ(1)(N)Q^{(1)}(\mathcal N^{\otimes n})=nQ^{(1)}(\mathcal N)

If Bob can simulate Eve, Ic=S(B)−S(E)I_c=S(B)-S(E) becomes a conditional entropy of a degraded system, which is subadditive across uses (Devetak & Shor, 2005). The regularized limit then equals the one-shot value.

Further reading

  • A. S. Holevo, "The capacity of the quantum channel with general signal states", IEEE Transactions on Information Theory 44, 269 (1998); B. Schumacher & M. D. Westmoreland, "Sending classical information via noisy quantum channels", Physical Review A 56, 131 (1997).
  • S. Lloyd, "Capacity of the noisy quantum channel", Physical Review A 55, 1613 (1997); I. Devetak, "The private classical capacity and quantum capacity of a quantum channel", IEEE Transactions on Information Theory 51, 44 (2005).
  • C. H. Bennett, P. W. Shor, J. A. Smolin & A. V. Thapliyal, "Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem", IEEE Transactions on Information Theory 48, 2637 (2002).
  • M. B. Hastings, "Superadditivity of communication capacity using entangled inputs", Nature Physics 5, 255 (2009).
  • G. Smith & J. Yard, "Quantum communication with zero-capacity channels", Science 321, 1812 (2008).