Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 323 / 1

A rate-$R$ block code consists of an encoder $E_n:J^n\to \{1,\dots ,M_n\}$ and decoder $D_n$, with $M_n\le 2^{nR}$; it is reliable when $\mathrm{Pr}[D_n(E_n(U^n))\ne U^n]\to 0$. Choose $\epsilon >0$ with $H(U)+\epsilon <R$. The typical set has probability tending to one and cardinality at most $2^{n(H(U)+\epsilon )}\le 2^{nR}$. Encode its words injectively and map every atypical word to a default codeword. The error probability is at most the atypical probability, so reliable compression exists.

A quantum rate-$R$ code uses a compression channel into a space of dimension at most $2^{nR}$ followed by a decompression channel; reliability means that its entanglement fidelity, and hence its average source-state fidelity, tends to one on ${\pi }^{\otimes n}$. Diagonalize $\pi ={\sum }_{u}p(u)|u⟩⟨u|$. The projector onto eigenvectors labelled by the classical typical set has dimension at most $2^{n(S(\pi )+\epsilon )}$ and expectation in ${\pi }^{\otimes n}$ tending to one. For $R>S(\pi )$ choose $\epsilon$ so this typical subspace fits in $2^{nR}$ dimensions, encode it isometrically, and send the orthogonal complement to a fixed state. The typical-subspace probability and the gentle-measurement estimate make the fidelity tend to one. This is Schumacher compression.

Every word in $C_n(r)$ has probability at least $2^{-nr}$, so normalization gives $|C_n(r)|\le 2^{nr}$. Choose $H(U)<r<R$ and then $\epsilon <r-H(U)$. Every $\epsilon$-typical word satisfies $p(u^n)\ge 2^{-n(H(U)+\epsilon )}\ge 2^{-nr}$, hence $T_{\epsilon }^{(n)}\subseteq C_n(r)$ and $\mathrm{Pr}[C_n(r)]\to 1$. Injectively encoding $C_n(r)$ and using a default codeword outside it gives rate at most $R$ and vanishing error.