Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 32 (Quantum Information Theory)

Over a finite field ${\mathbb{F}}_q$, a linear code of length $N$ and dimension $k$ is a $k$-dimensional subspace $C\subseteq {\mathbb{F}}_q^N$. A full-row-rank generator matrix $G\in {\mathbb{F}}_q^{k\times N}$ gives $C=\{mG:m\in {\mathbb{F}}_q^k\}$, using row-vector messages. A full-row-rank parity-check matrix $H\in {\mathbb{F}}_q^{(N-k)\times N}$ gives $C=\{x:H{x}^T=0\}$. The dual code is $C^{\perp }=\{y:x\cdot y=0\text{ for all }x\in C\}$, of dimension $N-k$. Thus the rows of $H$ span $C^{\perp }$, andConversely the rank conditions and $H{G}^T=0$ imply that the row space of $G$ equals the kernel of $H$, by inclusion and equality of dimensions.

For a CSS code, specialize to binary linear codes $C_2\subseteq C_1\subseteq {\mathbb{F}}_2^N$, of dimensions $k_2,k_1$. Define orthonormal encoded statesDifferent cosets have disjoint computational-basis support. Their span has dimension $2^{k_1-k_2}$, so it encodes $K=k_1-k_2$ logical qubits. For binary vectors write $X(u)={⨂}_j{X}_j^{u_j}$ and $Z(v)={⨂}_j{Z}_j^{v_j}$. The stabilizer generators are $X(u)$ for a basis of $C_2$, and $Z(v)$ for a basis of $C_1^{\perp }$. They fix each encoded state: the former permute its coset terms and the latter contribute phases $(-1{)}^{v\cdot (x+y)}=1$. Their commutation relation is $X(u)Z(v)=(-1{)}^{u\cdot v}Z(v)X(u)$, so the classical dual inclusion $C_1^{\perp }\subseteq C_2^{\perp }$ makes them commute. There are $k_2+N-k_1=N-K$ independent checks, giving precisely this encoded space.

For a Pauli error $X(e)Z(f)$, the Z checks give bit-error syndrome $H_1{e}^T$, where $H_1$ checks $C_1$, and the X checks give phase-error syndrome $G_2{f}^T$, where $G_2$ generates $C_2$ and hence checks $C_2^{\perp }$. Classical decoders therefore correct up to $t_X$ bit flips and $t_Z$ phase flips if $d(C_1)>2t_X$ and $d(C_2^{\perp })>2t_Z$. A Y error has both components; it is not omitted from this correction scheme.

For the precise quantum code distance, harmless stabilizer errors must be excluded. A pure-X error preserves the code exactly when $e\in C_1$, and is a stabilizer when $e\in C_2$; a pure-Z error preserves it when $f\in C_2^{\perp }$, and is a stabilizer when $f\in C_1^{\perp }$. Consequently, for $K>0$,A mixed Pauli error has weight equal to the size of the union of its X and Z supports. If it is a nontrivial logical operator, at least one component is nontrivial, so its weight is at least $\min (d_X,d_Z)$; pure-X or pure-Z operators attain that minimum. Thus $t=\lfloor (d-1)/2\rfloor$ arbitrary-qubit errors are correctable: products of two such Pauli errors have weight below $d$ and act scalarly on the code, or take it to an orthogonal syndrome sector. This is the Knill--Laflamme condition. Expanding arbitrary errors in the Pauli basis extends correction to their coherent linear span.

An explicit example is the Steane code. Take $C_1$ to be the binary Hamming code withThe distinct nonzero columns show that $C_1$ has no weight-one or weight-two word, while three dependent columns give a weight-three word. Hence its classical distance is three. Direct multiplication gives $H{H}^T=0$, proving $C_2\subseteq C_1$. Every nonzero word of $C_2$ has weight four, so the logical X and Z distances are both three. Its six stabilizer checks are the X and Z strings given by the three rows of $H$. A logical basis is the uniform superposition over $C_2$ and over $1+C_2$, since $1=(1,\dots ,1)\in C_1\setminus C_2$. The resulting $[[7,1,3]]$ CSS code corrects every single-qubit error.

A quantum operation is a linear, completely positive, trace-nonincreasing map on operators; its output trace records the probability of a selected outcome. A deterministic process that sends every density matrix to another normalized density matrix is a quantum channel, satisfying linearity, complete positivity and trace preservation. Linearity preserves probabilistic mixtures. Complete positivity means that ${\mathrm{id}}_R\otimes \mathcal{E}$ remains positive for every finite-dimensional reference system $R$, so the process also acts consistently on entangled inputs. Trace preservation maintains total probability. Conditioning a selected branch by dividing by its output trace is generally nonlinear; it is a separate state-update step.

The Stinespring dilation of a deterministic operation on a system $A$ iswhere $U$ is unitary on system plus environment, the initial environment is fixed and independent of the input, and the environment is discarded. A mixed environment can be purified by adding an extra environment system. For different input and output dimensions, use an isometry $V:A\to B\otimes E$ instead of this same-system unitary form.

Choose an orthonormal environment basis $\{|\alpha ⟩\}$. Taking the partial trace gives the Kraus representationUnitarity and completeness of the environment basis giveConversely, suppose the Kraus operators obey this completeness condition. Define $V|\psi ⟩={\sum }_{\alpha }{K}_{\alpha }|\psi ⟩\otimes |\alpha ⟩$. Then $V^{†}V=I$, so $V$ is an isometry. For equal input/output system dimensions, extend the orthonormal images of the subspace $A\otimes |0⟩$ to an orthonormal basis of $A\otimes E$. Mapping a completed input basis to that output basis supplies a unitary $U$ with $U(|\psi ⟩|0⟩)=V|\psi ⟩$. Tracing the environment recovers the given operator sum. This proves both directions of the equivalence.

It also follows directly that every completely positive map in finite dimensions has an operator sum. Form its unnormalized Choi matrix $J=(\mathrm{id}\otimes \mathcal{E})|\Omega ⟩⟨\Omega |$, with $|\Omega ⟩={\sum }_i|i⟩|i⟩$. Complete positivity makes $J\ge 0$. Resolve $J={\sum }_{\alpha }|v_{\alpha }⟩⟨v_{\alpha }|$ and reshape each vector as $|v_{\alpha }⟩={\sum }_i|i⟩K_{\alpha }|i⟩$. Comparing the coefficients of $|i⟩⟨j|$ gives $\mathcal{E}(|i⟩⟨j|)={\sum }_{\alpha }{K}_{\alpha }|i⟩⟨j|K_{\alpha }^{†}$, hence the same formula for every operator by linearity. Trace preservation imposes the completeness condition just derived.

Finally, linearity of the operator sum is immediate from matrix multiplication. For any positive operator $B$ on reference plus system,because each summand is a positive congruence. This proves complete positivity for every reference dimension. Cyclicity of the trace givesKraus form is trace preserving exactly when ${\sum }_{\alpha }{K}_{\alpha }^{†}{K}_{\alpha }=I$. Without this normalization, the final printed assertion would be false: a single operator $K=I/2$ gives output trace one quarter on every input density matrix. Thus the completeness condition is an essential part of the physical Kraus representation.

The generalized measurement postulate specifies operators $M_i$ with ${\sum }_i{M}_i^{†}{M}_i=I$. On a density matrix $\rho$, the outcome probability and conditional state areThe probabilities are nonnegative and sum to one. More generally an outcome may contain several Kraus operators $M_{i\alpha }$, in which case one sums over $\alpha$ in both formulas. A projective measurement with the usual Lüders update is the special case $M_i=P_i$, where $P_i=P_i^{†}$, $P_i{P}_j={\delta }_{ij}{P}_i$ and ${\sum }_i{P}_i=I$. Projection-valued effects alone fix the projective outcome probabilities, but an additional outcome-dependent unitary can change the conditional state; for the standard projective update the measurement operators themselves are the projectors.

A POVM is a family of positive effects $E_i$ summing to $I$. Its probabilities are $p_i=\mathrm{Tr}(\rho E_i)$. A generalized measurement gives effects $E_i=M_i^{†}{M}_i$, or $E_i={\sum }_{\alpha }{M}_{i\alpha }^{†}{M}_{i\alpha }$. Conversely $M_i=\sqrt{E_i}$ realizes any POVM. The POVM does not determine the post-measurement state: different operators with these same effects have the same probabilities and can have different state updates.

A pure POVM has rank-one nonzero effects, $E_i=w_i|{\psi }_i⟩⟨{\psi }_i|$, with normalized pure states $|{\psi }_i⟩$ and positive $w_i$. Here pure means rank-one effects, not the different property of extremality in the convex set of POVMs.

The POVM–ensemble duality for the maximally mixed state is a bijection between POVMs in dimension $d$ and ensemble decompositions of $I/d$. Given effects $E_i$, setomitting zero effects. Each ${\sigma }_i$ is a density matrix, ${\sum }_i{p}_i=\mathrm{Tr}I/d=1$, andConversely, if an ensemble satisfies ${\sum }_i{p}_i{\sigma }_i=I/d$, then $E_i=d{p}_i{\sigma }_i$ are positive and sum to $I$, hence form a POVM. Taking traces recovers the original probabilities, so the transformations are inverse. Pure POVMs correspond exactly to pure-state ensemble decompositions of the maximally mixed state. For such a POVM, $p_i=w_i/d$ and ${\sum }_i{w}_i=d$; it need not be an orthogonal measurement.

The transpose map $T(X)=X^T$ in a fixed basis is linear, trace preserving and positive: if $X\ge 0$, then for every $v$, $v^{†}{X}^{T}v=\overline{{\bar{v}}^{†}X\bar{v}}\ge 0$. It is nevertheless not a completely positive map. Apply $\mathrm{id}\otimes T$ to the two-qubit Bell state $|{\Phi }^{+}⟩=(|00⟩+|11⟩)/\sqrt{2}$. The resulting operator iswith eigenvalues $1/2,1/2,1/2,-1/2$. The negative eigenvector is $(|01⟩-|10⟩)/\sqrt{2}$. Thus a positive input on system plus reference acquires a negative expectation value. Transposition is positive but not completely positive, so it cannot be a deterministic local quantum process on arbitrary entangled states.

For a density matrix $\rho$ on a $d$-dimensional Hilbert space, its Von Neumann entropy, in bits, iswhere the ${\lambda }_a$ are its eigenvalues and $0{\log }_{2}0=0$. Each summand is nonnegative, proving $S\ge 0$, with equality exactly when one eigenvalue is one and the rest zero, namely for a pure state.

We first prove the nonnegativity of quantum relative entropy needed below. Diagonalize $\rho$ with eigenvalues ${\lambda }_a$ and eigenvectors $u_a$, and $\sigma$ with eigenvalues ${\mu }_b$ and eigenvectors $v_b$. Put $B_{ab}=|⟨u_a,v_b⟩{|}^2$ and $q_a=⟨u_a|\sigma |u_a⟩={\sum }_b{B}_{ab}{\mu }_b$. Each row of $B$ sums to one. Concavity of the ordinary logarithm gives ${\sum }_b{B}_{ab}{\log }_2{\mu }_b\le {\log }_2{q}_a$. ConsequentlyThe final Gibbs inequality follows directly from ${\sum }_{{\lambda }_a>0}{\lambda }_a\log (q_a/{\lambda }_a)\le \log {\sum }_{{\lambda }_a>0}{q}_a\le 0$. Support failure gives $D=+\infty$; zero eigenvalues can otherwise be handled by restriction or regularization. Equality requires $q_a={\lambda }_a$ and equality in the logarithm inequality on every positive-weight row. Thus $u_a$ is a $\sigma$ eigenvector of eigenvalue ${\lambda }_a$ wherever ${\lambda }_a>0$. The remaining diagonal entries of $\sigma$ vanish and positivity makes the remaining rows and columns zero. Hence equality holds exactly when $\rho =\sigma$.

Taking $\sigma =I/d$ gives $D(\rho \Vert I/d)={\log }_{2}d-S(\rho )$, provingThe lower equality is attained exactly by pure states and the upper exactly by the maximally mixed state $I/d$.

For $\bar{\rho }={\sum }_i{p}_i{\rho }_i$, each positive-weight state has support contained in that of $\bar{\rho }$. Expanding the quantum relative entropy givesThis proves Concavity of Von Neumann entropy, with equality precisely when every positive-weight ${\rho }_i$ is the same state.

For the upper entropy bound for a quantum mixture, diagonalize each component, ${\rho }_i={\sum }_a{\lambda }_{ia}|v_{ia}⟩⟨v_{ia}|$, and set $q_{ia}=p_i{\lambda }_{ia}$. Form the rectangular matrix $B$ whose columns are $\sqrt{q_{ia}}{v}_{ia}$. Then $B{B}^{†}=\bar{\rho }$, while the Gram matrix $\Gamma =B^{†}B$ has diagonal $q_{ia}$. The two matrices have the same nonzero eigenvalues: $B$ and $B^{†}$ map corresponding positive-eigenvalue eigenspaces isomorphically. Thus $S(\Gamma )=S(\bar{\rho })$.

If there are $L$ columns, let $W=\mathrm{diag}(1,\omega ,\dots ,{\omega }^{L-1})$, with $\omega =e^{2\pi i/L}$. ThenAll the summands have the same Von Neumann entropy. The just-proved concavity therefore implies $S(\bar{\rho })=S(\Gamma )\le S(\mathrm{diag}\Gamma )=H(q)$. Finally,We have proved both requested bounds:For the upper equality, strictness in the concavity argument forces $\Gamma$ to be diagonal. Its entries between two positive-weight component eigenvectors then force those vectors to be orthogonal. Thus upper equality holds exactly when the supports of the positive-weight component states are mutually orthogonal. In that case their classical label is perfectly distinguishable, explaining the extra $H(p)$ bits.

The Schumacher compression theorem concerns a memoryless quantum information source with average density matrix $\rho$ on a finite-dimensional Hilbert space. For $n$ uses the average state is ${\rho }_n={\rho }^{\otimes n}$. Compression consists of an encoding quantum channel into a space of dimension $D_n$ and a decoding channel back to the original block space, with asymptotic rate $n^{-1}{\log }_2{D}_n$ qubits per source use. The optimal reliable rate is $S(\rho )$: every larger rate is achievable, and no smaller rate is reliable. This holds for average pure-source fidelity; the direct construction also preserves a purification reference, and the converse for that stronger entanglement fidelity criterion holds with fidelity tending to zero below the threshold. The encoding and decoding are deterministic channels; no free classical transmission of the source label is allowed.

Diagonalize $\rho ={\sum }_j{\lambda }_j|j⟩⟨j|$ and omit zero-probability eigenvalues when sampling. Define the quantum typical subspace projector $P_{n,\delta }$ by retaining product eigenvectors withThe sampled random variable $-{\log }_2{\lambda }_j$ has expectation $S=S(\rho )$. The weak law of large numbers gives $w_n=\mathrm{Tr}({\rho }_n{P}_{n,\delta })\to 1$. Every retained eigenvalue is at least $2^{-n(S+\delta )}$, and the total probability is at most one, soThis proves the two typical subspace theorem estimates used in the direct part.

Write $P=P_{n,\delta }$. Encode its range isometrically into a compressed space and reserve one orthogonal failure flag. Decode the range back isometrically and the failure flag to a fixed pure state $|\phi ⟩$. This typical-subspace compression with a failure flag is a physical channel whose composite action isIndeed its Kraus operators are $P$ and $|\phi ⟩⟨e_a|$, where the $e_a$ form an orthonormal basis of $\ker P$, and their adjoint products sum to $I$. The Kraus formula for entanglement fidelity givesFor any pure-state ensemble of ${\rho }_n$, the average squared quantum fidelity is at least this number: apply convexity of $|z{|}^2$ separately to the amplitudes $⟨{\psi }_x|K_{\alpha }|{\psi }_x⟩$ with their source probabilities. Thus average fidelity also tends to one. The compressed dimension is at most $2^{n(S+\delta )}+1$, and its rate is at most $S+\delta +o(1)$. Choose $\delta <R-S$ for any prescribed $R>S$. One may also take ${\delta }_n=n^{-1/4}$: the finite spectral information variance and Chebyshev's inequality still give $w_n\to 1$, with rate tending to $S$. A pure source, $S=0$, can simply be re-prepared exactly without sending any qubits.

For the coherent converse, we prove the finite-dimensional quantum compression converse. If the compressed space has dimension $D$, the state of reference plus compressed system has a pure-state decomposition with Schmidt rank at most $D$. Applying decoder Kraus operators locally cannot increase the Schmidt rank of those vectors, so the final reference–output state has Schmidt number at most $D$. Let $|{\Psi }_{{\rho }_n}⟩$ purify the source, with squared Schmidt coefficients equal to the decreasing eigenvalues ${\mu }_1\ge {\mu }_2\ge \cdots$ of ${\rho }_n$. For any normalized vector $|v⟩$ of Schmidt rank at most $D$, its reference support lies in a rank-at-most-$D$ projector $Q$. HenceThe last bound follows by maximizing ${\sum }_j{\mu }_j⟨j|Q|j⟩$ subject to $0\le ⟨j|Q|j⟩\le 1$ and their sum at most $D$. Average over a Schmidt-rank-bounded decomposition of the final state to obtain $F_e\le {\sum }_{j=1}^D{\mu }_j$.

At rate $R<S$, choose $0<\delta <S-R$. The total source probability outside the quantum typical subspace tends to zero, while every eigenvalue inside it is at most $2^{-n(S-\delta )}$. Therefore for $D_n\le 2^{nR}$,This argument allows arbitrary encoding and decoding channels, not only subspace projection.

For completeness, average pure-source reliability also forces the same rate, even though it is a weaker criterion than entanglement fidelity. Here is a separate converse for that formulation. Let the emitted block pure states be ${\psi }_x$, with probabilities $p_x$, and let ${\sigma }_x$ be the decoded states. If their mean squared fidelity tends to one, then their mean trace distance ${\bar{\delta }}_n$ tends to zero, since $\frac{1}{2}\Vert {\sigma }_x-{\psi }_x{\Vert }_1\le \sqrt{1-⟨{\psi }_x|{\sigma }_x|{\psi }_x⟩}$. This inequality follows by choosing a purification with that overlap and using contraction of trace distance under a partial trace.

We need only an elementary entropy continuity from Jordan decomposition bound, derivable from Question 4. If $\delta =\frac{1}{2}\Vert \sigma -\tau {\Vert }_1$, write the positive and negative parts of $\sigma -\tau$ as $\delta {\omega }_{+},\delta {\omega }_{-}$. The common density matrixand the two mixture bounds giveHere $g$ is increasing and concave, $g(0)=0$. Apply this in block dimension $d^n$, both to the average states and to individual outputs, using convexity of trace distance and concavity of $g$. Since the original ensemble is pure, its Holevo quantity is $S({\rho }_n)=nS$. The decoded ensemble hasThe Holevo quantity under a quantum channel cannot increase. To specify the entropy ingredient, Strong subadditivity of Von Neumann entropy states $S(XB)+S(BE)\ge S(B)+S(XBE)$. Attach the classical source label $X$, dilate the decoder isometrically to $BE$, and trace out $E$. The displayed inequality says $I(X:B)\le I(X:BE)$; the isometry preserves the input mutual information. Since $I(X:B)$ of a labelled ensemble is its Holevo quantity, this proves the needed decoder monotonicity. Before decoding, the system has dimension $D_n$, so its Holevo quantity is at most ${\log }_2{D}_n$. Thus ${\log }_2{D}_n\ge nS-o(n)$ and the rate cannot be below $S$. Both operational fidelity formulations therefore have the claimed noiseless coding threshold.

Fix the noise convention explicitly: $p$ is the total probability of a nonidentity Pauli error. The memoryless qubit quantum depolarizing channel iswith independent identical use on successive qubits, namely ${\mathcal{D}}_p^{\otimes n}$ on an $n$-qubit block. Its normalized Kraus operators are $\sqrt{1-p}I,\sqrt{p/3}X,\sqrt{p/3}Y,\sqrt{p/3}Z$.

Write the Bloch sphere representation of a density matrix as $\rho =(I+\mathbf{r}\cdot \mathbf{\sigma })/2$, with $|\mathbf{r}|\le 1$. Its eigenvalues are $(1\pm |\mathbf{r}|)/2$, proving exactly this positivity condition. Conjugation by one Pauli operator preserves that coordinate of the Bloch vector and reverses the other two. Summing the three conjugations givessoThe Bloch ball contracts isotropically, collapses to the maximally mixed state at $p=3/4$, and contracts with reversal for $p>3/4$. That last interval still represents a physical Pauli mixture. If instead $q$ is the probability of replacing the state by $I/2$, then $\mathcal{D}(\rho )=(1-q)\rho +qI/2$, with $p=3q/4$ and $\eta =1-q$; the usual replacement-probability range $0\le q\le 1$ stops at complete depolarization.

Let $h_2(x)=-x{\log }_{2}x-(1-x){\log }_2(1-x)$, with endpoint limits. In bits per use, the unassisted product-state classical capacity and the entanglement-assisted capacity of a qubit depolarizing channel arewhere $H_4$ is Shannon entropy of the listed four probabilities. Equivalently $C_E=2+(1-p){\log }_2(1-p)+p{\log }_2(p/3)$. The first quantity is a classical capacity with product quantum inputs and potentially collective output measurements, not the quantum capacity. These are the requested capacity formulae; a proof of their coding theorems is not needed here. The maximally entangled input gives a Bell-diagonal joint state with those four probabilities, explaining the entropy appearing in $C_E$. The original entanglement-assisted capacity calculation gives the depolarizing-channel expression.

At $p=0$ the capacities are one and two. Both vanish at $p=3/4$. On the full Pauli-error interval they increase again beyond that point, reaching $1-h_2(2/3)$ and $2-{\log }_{2}3$ at $p=1$; on the replacement-probability plot both decrease to zero at $q=1$. The two panels make this convention distinction explicit.

For the high-noise capacity ratio for qubit depolarization, put $\eta =1-4p/3\to 0$. Taylor expansion of binary entropy around one half givesThe four probabilities for $C_E$ are $1/4+3\eta /4$ and three copies of $1/4-\eta /4$. For a perturbation ${\delta }_i$ of the uniform four-outcome distribution, with ${\sum }_i{\delta }_i=0$, entropy expansion givesHere ${\sum }_i{\delta }_i^2=3{\eta }^2/4$, hence $C_E=3{\eta }^2/(2\ln 2)+O({\eta }^3)$. ThereforeThe reciprocal ratio is $1/3$, and the same enhancement factor occurs as $q\to 1$ in the replacement convention.