 Solution

Use base-two logarithms throughout, so classical rates are measured in bits and quantum compression rates in qubits. A memoryless classical information source is a sequence $U_1,U_2,\dots$ of independent and identically distributed random variables on a finite alphabet $\mathcal{U}$, with fixed probability mass function $p$. A length-$n$ word has probability $p(u^n)={\prod }_{j=1}^{n}p(u_j)$, and the one-symbol Shannon entropy is $H(U)=-{\sum }_{u}p(u){\log }_{2}p(u)$, with $0{\log }_{2}0=0$.

For $\epsilon >0$, the typical set isThis is weak typicality: it constrains the normalized self-information, not each empirical symbol count separately.

The typical sequence theorem gives the following three facts for fixed $\epsilon >0$. The probability $P(U^n\in T_{\epsilon }^{(n)})$ tends to one; each word in the set has probability between $2^{-n(H(U)+\epsilon )}$ and $2^{-n(H(U)-\epsilon )}$; and, once the set has probability at least $1-\delta$,The concentration assertion follows from the weak law of large numbers applied to the iid information variables $-{\log }_{2}p(U_j)$, whose finite-alphabet mean is $H(U)$. The probability bounds are the definition of typicality exponentiated. Summing the lower bound over the typical words and using total probability at most one proves the cardinality upper bound; summing the upper bound and using total typical probability at least $1-\delta$ proves the lower bound.

Fix $R>H(U)$ and choose $0<\epsilon <R-H(U)$. Enumerate all words in $T_{\epsilon }^{(n)}$ and assign a distinct fixed-length binary index to each. Reserve one more index as a failure symbol for every atypical input. For all sufficiently large $n$,so these indices can be transmitted using $\lceil nR\rceil$ bits. The decoder inverts the typical-word enumeration; on the failure index it returns any fixed word. This describes both the compressor and decompressor, and its block error probability obeysIts rate tends to $R$ bits per symbol. Thus every $R>H(U)$ permits reliable fixed-rate compression, with no claim that atypical words are reconstructed correctly.

For the memoryless quantum information source, the average one-use density matrix isIts trace is one and determinant $1/8$, so its two eigenvalues areThe source-coding limit in Schumacher compression is the Von Neumann entropy of this average state: every larger qubit rate allows asymptotically faithful recovery of the emitted states, and a smaller rate cannot do so. Applying that limit giveswhere $h_2(t)=-t{\log }_{2}t-(1-t){\log }_2(1-t)$ is the binary entropy. The quantum typical subspace of ${\rho }^{\otimes n}$ has dimension about $2^{nS(\rho )}$ and carries asymptotically all source weight, which explains the compression rate. The entropy of the classical emission label is one bit; it is not the quantum rate because the two emitted pure states are nonorthogonal.