Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 323 / 2

Use base-two logarithms. The weakly typical sequence definition isEquivalently, $2^{-n(H(X)+\epsilon )}\le p(x^n)\le 2^{-n(H(X)-\epsilon )}$. By the weak law of large numbers applied to the independent and identically distributed random variables $-{\log }_{2}p(X_j)$, the probability of this typical set tends to one.

This captures the usual probability scale of a long sample, but it need not make every symbol frequency representative. For a fair binary source, every word has probability $2^{-n}$ and $H(X)=1$, so even the all-zero word is weakly typical. The strongly typical sequence definition additionally controls empirical symbol frequencies and excludes this word for small tolerance. Thus weak typicality agrees with the high-probability-set intuition, while allowing individually unrepresentative members.

Every member of the typical set has probability at least $2^{-n(H(X)+\epsilon )}$. Summing these probabilities givessoThe upper bound itself holds at every block length. For sufficiently large $n$, the high-probability property also gives the companion lower boundhence $|T_{\epsilon }^{(n)}|\ge (1-\delta )2^{n(H(X)-\epsilon )}$. Together these are the typical-set cardinality bounds underlying Shannon source coding theorem.

Memorylessness means that the ensemble's average density operator is ${\rho }^{(n)}={\pi }^{\otimes n}$. Its spectral decomposition isThe product eigenvalues giveZero eigenvalues contribute zero to the Von Neumann entropy and are excluded from logarithmic typicality tests.

The quantum typical subspace is the span of eigenvectors whose eigenvalues satisfyIts orthogonal projection $P_{\epsilon }^{(n)}$ selects precisely the classical typical set for the eigenvalue distribution $q$. The typical-set cardinality bounds and the weak law of large numbers therefore givefor any fixed $\delta >0$ and all sufficiently large $n$.

A compression-decompression scheme consists of quantum channels ${\mathcal{E}}_n:\mathcal{D}({\mathcal{H}}^{\otimes n})\to \mathcal{D}({\mathcal{K}}_n)$ and ${\mathcal{D}}_n:\mathcal{D}({\mathcal{K}}_n)\to \mathcal{D}({\mathcal{H}}^{\otimes n})$, where ${\mathrm{limsup}}_n{n}^{-1}{\log }_2\dim {\mathcal{K}}_n\le R$. For the emitted pure-state ensemble, reliability means that the mean squared quantum fidelity tends to one:The average is taken over the actual source distribution, rather than the worst possible input vector.

A standard stronger formulation of reliable quantum source compression requireswhere entanglement fidelity tests preservation of a purification and its reference-system correlations. It implies the mean-fidelity condition for every pure-state ensemble of ${\pi }^{\otimes n}$. Schumacher compression achieves this at any rate $R>S(\pi )$: choose $0<\epsilon <R-S(\pi )$, encode the quantum typical subspace, and map atypical outcomes to a fallback state. The composed channel has a Kraus term $P_{\epsilon }^{(n)}$, so its entanglement fidelity is at least $[\mathrm{Tr}({\pi }^{\otimes n}{P}_{\epsilon }^{(n)}){]}^2\to 1$.

Let $Z$ indicate whether the outcome differs from $x_1$. Then $\mathbb{P}(Z=1)=q$. The chain rule for information entropy givessince $X=x_1$ is determined when $Z=0$. The remaining conditional distribution has at most $m-1$ outcomes, so the maximum entropy on a finite alphabet is ${\log }_2(m-1)$. Therefore the Shannon source coding theorem limit obeysHere $h_2$ is the binary entropy function; equality holds when the rare outcomes are equiprobable. A convenient explicit small-$q$ bound isbecause $-(1-q){\log }_2(1-q)\le q{\log }_{2}e$. For a fixed alphabet, this upper bound tends to zero as $q\to 0$.