Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 60 (Mathematical Aspects of Quantum Information Theory)

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.

The physical space of $n$ qubits is ${\mathcal{H}}_n=({\mathbb{C}}^2{)}^{\otimes n}$. An error operator is a linear operator on this space, for example one Kraus operator of a noise quantum channel. The usual channel description assumes initially uncorrelated system and environment, with the environment subsequently ignored; more general initial correlations need not define a channel on arbitrary system inputs. Finite dimension and the tensor decomposition into identifiable qubits allow an exact Pauli expansion of a quantum error. No independence between errors on different qubits is assumed by this expansion.

The $4^n$ tensor products of $I,X,Y,Z$ form an orthogonal basis of the operator space under the Hilbert-Schmidt inner product. Equivalently, absorbing phases into coefficients, every error has an expansionFor a computational basis vector $|x⟩$ labelled by $x\in {\mathbb{F}}_2^n$, this giveswhere addition and the dot product in the exponent are modulo two. Thus $X$ changes a bit, $Z$ changes its phase, and $Y$ performs both up to a scalar phase. A general error is a coherent linear combination of such actions; it need not be a classical random choice of Pauli operators. A restriction to at most $t$ faulty qubits is an additional locality assumption, expressed by the span of Pauli operators of weight at most $t$.

The weight of a Pauli operator is the number of tensor factors different from $I$, ignoring global phase. Let $P$ be the orthogonal projector onto a $2^k$-dimensional code $\mathcal{X}$. Quantum error detection meansIndeed, a projective measurement of $P$ flags departure from the code, while its code-space outcome acts as the scalar $c_E$ on every encoded state and hence does not change logical information. Harmless scalar actions are included in this criterion. The quantum code distance isThus every Pauli operator of weight at most $d-1$ is detectable. The condition is linear in $E$, so it holds for any error in their span. This proves detection of arbitrary errors affecting at most $d-1$ qubits, including coherent errors.

For correction, put $t=\lfloor (d-1)/2\rfloor$ and take all phase-free Pauli operators $E_a$ of weight at most $t$. Their pairwise products satisfyThese are the Knill--Laflamme conditions. Here is their recovery construction, rather than merely using the criterion's name. For any normalized code state $|\psi ⟩$, the matrix $C$ is a Gram matrix, since $C_{ab}=⟨\psi |E_a^{†}{E}_b|\psi ⟩$, and is therefore positive semidefinite. Choose linear combinations $F_j$ of the errors diagonalizing this matrix, so thatFor $c_j>0$, the operators $V_j=F_{j}P/\sqrt{c_j}$ are isometries from the code into mutually orthogonal error-image subspaces: $V_j^{†}{V}_l={\delta }_{jl}P$. Measure the projectors $Q_j=V_j{V}_j^{†}$ and, on outcome $j$, apply $V_j^{†}$. Complete this recovery arbitrarily on the remaining orthogonal subspace to make a trace-preserving quantum channel.

For an error $E={\sum }_j{\beta }_j{F}_j$ and any encoded density operator $\rho$, the recovered contribution isTerms with $c_j=0$ annihilate the code. For a physical noise channel whose Kraus operators belong to this span, summing the displayed scalar over those operators gives one by trace preservation. The resulting recovered state is exactly $\rho$. This proves the constructive recovery from the Knill-Laflamme condition and the requested guaranteeThis argument allows degenerate codes; distinct physical errors may have identical actions on the code.

For the Shor code, define $|G_{\pm }⟩=(|000⟩\pm |111⟩)/\sqrt{2}$. Its two normalized basis codewords areSix stabilizer generators are $Z_1{Z}_2,Z_2{Z}_3,Z_4{Z}_5,Z_5{Z}_6,Z_7{Z}_8,Z_8{Z}_9$; the two phase checks areAll eight have eigenvalue $+1$ on both basis codewords. A phase error $Z_4$ commutes with the six $Z$ checks and anticommutes with both $g_7$ and $g_8$. Their projective measurements therefore returnThe two negative phase checks identify the middle three-qubit block. Apply the Pauli Z gate $Z_4$ to restore the state, since $Z_4^2=I$. This procedure acts identically on every logical superposition, and the checks reveal no logical amplitudes. The syndrome cannot distinguish $Z_4$ from $Z_5$ or $Z_6$, but all three have the same action on the code: their pairwise products lie in the stabilizer group. Correcting with any one of them is sufficient. Thus the degeneracy in the syndrome is harmless.

For probability distributions $p$ and $q$ on a finite alphabet, their classical relative entropy in bits isA zero-$p$ term contributes zero, including when $q(x)=0$; a term with $p(x)>0$ and $q(x)=0$ makes the result $+\infty$. In that infinite case nonnegativity is immediate. Otherwise $q(x)>0$ on the support $J_p$ of $p$. For every $u>0$, $\ln u\le u-1$: the function $u-1-\ln u$ has derivative $1-1/u$ and its minimum zero at $u=1$. Apply this with $u=q(x)/p(x)$ to obtainThe last inequality uses normalization of $q$. Thus $\boxed{D(p\Vert q)\ge 0}$. Equality requires $q(x)=p(x)$ wherever $p(x)>0$ and no $q$-mass outside that support, hence occurs precisely when $p=q$.

For density matrices, usewhen the support of a positive operator $\rho$ is contained in that of $\sigma$, and set it to $+\infty$ otherwise. The data-processing inequality for quantum relative entropy states that for any quantum channel $\Phi$,Thus the relative entropy of the two output states cannot exceed that of the inputs.

For the states with a classical flag, omit indices of weight zero. On a positive-weight block, the matrix logarithms obeyon the relevant supports. The logarithms of $p_i$ cancel. Taking the trace block by block therefore gives the relative entropy of classically flagged states:If support inclusion fails in a positive-weight block, both sides are infinite. A zero-weight block makes no contribution, even if its unweighted relative entropy is infinite.

Tracing out the flag is a quantum channel with operators $A_i=⟨i|\otimes I$, since ${\sum }_i{A}_i^{†}{A}_i=I$. It sends the two flagged states to ${\sum }_i{p}_i{\rho }_i$ and ${\sum }_i{p}_i{\sigma }_i$. Applying the data-processing inequality for quantum relative entropy to this partial trace proves joint convexity of quantum relative entropy:

For a bipartite state, set ${\rho }_A={\mathrm{Tr}}_B{\rho }_{AB}$ and ${\rho }_B={\mathrm{Tr}}_A{\rho }_{AB}$. Its quantum mutual information iswhere $S(\tau )=-\mathrm{Tr}\tau {\log }_2\tau$ is the Von Neumann entropy. The support of ${\rho }_{AB}$ lies in $\mathrm{supp}{\rho }_A\otimes \mathrm{supp}{\rho }_B$. To justify this when marginals are singular, let $Q_A$ project onto $\ker {\rho }_A$. Then $\mathrm{Tr}[(Q_A\otimes I){\rho }_{AB}]=\mathrm{Tr}(Q_A{\rho }_A)=0$; positivity implies $(Q_A\otimes I){\rho }_{AB}=0$. Applying the same argument on $B$ proves the claimed support inclusion.

On that support, product eigenvectors showThe definition of the partial trace therefore givesConsequently $\boxed{S(A:B)=S({\rho }_{AB}\Vert {\rho }_A\otimes {\rho }_B)}$.

For completeness, nonnegativity of quantum relative entropy also follows from the classical proof above. Diagonalize $\rho$ in a basis $|j⟩$, with eigenvalues $r_j$, and put $q_j=⟨j|\sigma |j⟩$. These are two classical probability distributions. Scalar concavity of the logarithm applied to the spectral weights of $\sigma$ gives $⟨j|{\log }_2\sigma |j⟩\le {\log }_2{q}_j$ whenever $r_j>0$ and support inclusion holds. HenceThe support-failure case is again infinite. Applying this to the product of the marginals proves $\boxed{S(A:B)\ge 0}$ without requiring an additional entropy inequality.

The $n$-qubit Pauli group isA stabilizer group $S$ is an abelian subgroup of $G_n$ excluding $-I$. Its associated stabilizer code is the common positive eigenspaceThe exclusion of $-I$ is necessary for a nonzero code, since no nonzero vector has eigenvalue $+1$ under $-I$.

Every $s\in S$ is a signed Hermitian tensor product of Pauli matrices. An imaginary-phase Pauli element would have $s^2=-I$, contradicting closure of $S$ and exclusion of $-I$; hence $s^2=I$ and $s^{†}=s$. If $s\ne I$, it cannot be a nontrivial scalar Pauli element, and at least one of its local factors is $X,Y$ or $Z$. Each of these has trace zero. Using $\mathrm{Tr}(A\otimes B)=\mathrm{Tr}(A)\mathrm{Tr}(B)$ gives $\mathrm{Tr}s=0$.

The spectral theorem for Hermitian operators and $s^2=I$ show that all eigenvalues are $+1$ or $-1$. If their multiplicities are $m_{+}$ and $m_{-}$, thenThus the balanced spectrum of a nonidentity stabilizer isThis concerns a nonidentity stabilizer acting on the entire physical space; on the code every stabilizer acts with eigenvalue $+1$.

Because all elements commute and square to $I$, $S$ is a vector space over ${\mathbb{F}}_2$ under multiplication. Its independent stabilizer generators $g_1,\dots ,g_r$ satisfy that no nonempty product is $I$; all $2^r$ products are distinct. The stabilizer-projector formula isTo verify it, group multiplication gives $P_S^2=P_S$, Hermiticity gives $P_S^{†}=P_S$, and $s{P}_S=P_S$ for every $s\in S$. Conversely every code vector is fixed by this average, so its range is exactly ${\mathcal{X}}_S$. All nonidentity stabilizers have trace zero by the preceding proof. ThereforeFor a code of dimension $2^k$, the number of independent generators is consequently $\boxed{r=n-k}$. One can list additional redundant generators, but an independent generating set has exactly this size.

For a correctable Pauli error $E_{\alpha }$, define the syndrome bit $s_j(\alpha )$ to be zero when $E_{\alpha }$ commutes with $g_j$ and one when it anticommutes. On an encoded state,Measure the commuting stabilizer generators; their eigenvalues reveal the error syndrome without revealing logical amplitudes. In a nondegenerate quantum code, the distinct specified correctable errors have orthogonal images of the code and distinct syndromes. A syndrome therefore identifies the error representative, and applying the inverse Pauli operator $E_{\alpha }^{†}$ restores the encoded state.

If an actual error operator is a coherent linear combination of the specified errors, its state is a sum of these orthogonal syndrome components. Syndrome measurement selects one component, followed by the same inverse operation. The linearity of coherent quantum error correction ensures the logical state is recovered in every outcome. The same procedure handles noise Kraus operators in that error span; it does not require a probabilistic Pauli-noise assumption.

A Pauli error commuting with every stabilizer has the all-zero syndrome and preserves the code space. If it is a stabilizer up to global phase, this silent action is harmless. If it lies in the centralizer of a stabilizer group but is not a stabilizer up to phase, it acts as a nontrivial logical operator, and syndrome measurements cannot detect it. More generally, a non-scalar component $P_{S}E{P}_S$ of an error is an undetectable logical action. This distinguishes harmful undetected errors from scalar actions that satisfy quantum error detection algebraically.

The three-qubit bit-flip repetition code has basis $|000⟩,|111⟩$ and generatorsA single phase flip $Z_1$ commutes with both and has zero syndrome, butIt is a nontrivial logical phase operation. In particular, $P_S{Z}_1{P}_S$ is not scalar, so the error set $\{I,Z_1\}$ violates the Knill--Laflamme condition and cannot be corrected. Thus the code corrects single bit flips but not single phase flips; its distance against arbitrary quantum errors is one.

The printed normalization has its factors reversed. For the displayed map $\Phi (X)={\sum }_k{A}_{k}X{A}_k^{†}$, the condition ${\sum }_k{A}_k{A}_k^{†}=I$ says $\Phi (I)=I$, which is unitality. Trace preservation instead requiresThese are distinct trace-preserving and unital Kraus conditions. To disprove the printed equivalence, take $0<\gamma <1$ andThey obey ${\sum }_j{B}_j{B}_j^{†}=I$, butThus their completely positive map is not trace preserving. They are the adjoints of the operators of an amplitude damping channel. That channel is trace preserving but sends $I$ to $\mathrm{diag}(1+\gamma ,1-\gamma )$, so it cannot satisfy the printed normalization in any Kraus representation either. The corrected characterization is proved next.

Work in finite-dimensional input and output Hilbert spaces, with a linear map $\Phi$ on operators. Suppose first that $\Phi (X)={\sum }_k{A}_{k}X{A}_k^{†}$ and ${\sum }_k{A}_k^{†}{A}_k=I$. For every auxiliary dimension $m$ and every positive operator $W$ on the extended space,Each summand is positive because conjugation preserves positivity. This is exactly the definition of a completely positive map. Cyclicity of the trace givesso the map is also trace preserving.

Conversely, suppose $\Phi$ is completely positive and trace preserving, and let $|i⟩$ be an orthonormal input basis. Use the unnormalized entangled vector $|\Omega ⟩={\sum }_i|i⟩\otimes |i⟩$, with the reference factor first. Complete positivity makes the corresponding unnormalized Choi matrix positive:Its spectral decomposition can be written $J_{\Phi }={\sum }_k|v_k⟩⟨v_k|$, absorbing the nonnegative eigenvalues into the vectors. Define linear operators $A_k$ uniquely byExpanding the outer products and comparing their $(i,j)$ reference blocks yieldsThe matrix units span all operators, so linearity proves the Kraus representation $\Phi (X)={\sum }_k{A}_{k}X{A}_k^{†}$ for every $X$. Finally, trace preservation givesfor all $X$. Taking matrix units as test operators shows that the matrix in parentheses is zero. This proves both directions of the corrected CPT characterization, including the normalization rather than assuming it.

For an input quantum state ensemble $\{p_x,{\rho }_x\}$, write ${\sigma }_x=\Phi ({\rho }_x)$ and $\bar{\sigma }={\sum }_x{p}_x{\sigma }_x$. Its output Holevo quantity isThe Holevo capacity is the optimized one-use quantitywhere the supremum ranges over finite input ensembles and $S$ is the Von Neumann entropy in bits.

For $n$ uses of a memoryless quantum channel, the map is ${\Phi }^{\otimes n}$. An $n$-use code consists of a finite message set ${\mathcal{M}}_n$ of size $M_n$, an encoding state ${\rho }_m^{(n)}$ on the $n$ inputs for each message, and a decoding POVM $\{D_m^{(n)}:m\in {\mathcal{M}}_n\}$ on the output space, with $D_m^{(n)}\ge 0$ and ${\sum }_m{D}_m^{(n)}=I$. The encoding states may be entangled across uses. The measurement outcome is the receiver's decoded message, with conditional probabilityFor uniformly distributed messages the average error and rate areA rate $R$ is achievable if there is a sequence of such codes with $P_e^{(n)}\to 0$ and ${\mathrm{liminf}}_n{R}_n\ge R$. The unassisted classical capacity of a quantum channel is the supremum of achievable rates; the sender and receiver do not share prior entanglement.

The operational content of the Holevo-Schumacher-Westmoreland theorem is that ${\chi }^{\ast }(\Phi )$ is the capacity for product-state input encodings with collective output measurements. Allowing arbitrary entangled block inputs gives the regularized formulaThe limit equals the supremum because superadditivity of Holevo capacity follows by taking product ensembles for two blocks and using additivity of the Von Neumann entropy on product states. The coding theorem makes every rate below the one-block Holevo quantity achievable through many independently encoded blocks, with collective decoding.

The converse can be seen explicitly from the Holevo bound and Fano's inequality. For a uniform transmitted message $M$ and decoded message $\hat{M}$,The first inequality is obtained by subtracting the Fano bound on $H(M\mid \hat{M})$ from $H(M)={\log }_2{M}_n$. Dividing by $n$ and letting the average error vanish bounds every achievable rate by the regularized expression. The block-coding achievability just described supplies the reverse bound.

Under the assumed additivity of Holevo capacity across tensor powers, ${\chi }^{\ast }({\Phi }^{\otimes n})=n{\chi }^{\ast }(\Phi )$ for every $n$. ThusThe stated conditional assertion is true: under this additivity assumption, entangled input states cannot increase the asymptotic unassisted classical rate beyond the rate already achievable with product inputs. The decoder may still use collective measurements across channel outputs.