Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 58 (Introduction to Quantum Computation)

Let $\{|u_j⟩{\}}_{j=1}^N$ be another complete orthonormal basis, and write $|u_j⟩={\sum }_n{U}_{nj}|n⟩$. Orthonormality makes $U$ a unitary matrix, so $U{U}^{†}=I$. ThereforeThus the resolution of the identity is independent of the orthonormal basis. Equivalently, expanding any vector in the new complete basis shows that the sum of its orthogonal projections returns that vector.

Normalize the vector defining the first effect and write $E_1=\alpha |\psi ⟩⟨\psi |$. Since the two effects sum to $I$, the eigenvalues of $E_2=I-E_1$ are $1-\alpha$ along $\psi$ and $1$ on its orthogonal complement. For $E_2$ to have rank one, $\alpha =1$. Hence this binary rank-one qubit POVM is a projective measurement:The two Bloch vectors are antipodal on the Bloch sphere; the corresponding state vectors are orthogonal. The plot below chooses one representative unit vector. Rotating both directions gives every other case. The sphere represents the effect projectors' Bloch directions, rather than plotting their matrix entries.

A centre $c$ turns position into a displacement $x-c$. If $v_1,\dots ,v_N$ are a basis of the $N$-dimensional vector space, every position has unique coordinatesThus $N$ linearly independent vectors are necessary and sufficient. Fewer vectors span a proper subspace and cannot represent arbitrary displacements. The coordinates use the field defining the space. For qubit tomography, the relevant parameter space is the real three-dimensional space of Bloch vectors, rather than the complex two-dimensional space of state amplitudes.

For one fixed POVM repeated on independently prepared copies, the Born rule gives $m$ outcome probabilities with one normalization constraint. An arbitrary mixed qubit density operator has three independent real parameters,The probability map is affine in $\mathbf{r}$. It can be injective on the full Bloch ball only if $m-1\ge 3$. If its rank is smaller, a nonzero undetected direction gives two nearby physical Bloch vectors with the same probabilities. Hence $m\ge 4$ for an informationally complete POVM.

To attain this bound, take the four directionsThey are the vertices of a regular tetrahedron. The tetrahedral qubit POVM has effects $E_i=(I+{\mathbf{n}}_i\cdot \mathbf{\sigma })/4$, each positive and rank one, and ${\sum }_i{E}_i=I$. The observed probabilities areSince ${\sum }_i{\mathbf{n}}_i=0$ and ${\sum }_i{\mathbf{n}}_i{\mathbf{n}}_i^T=4I_3/3$, they recover the state byThis is the minimum for a single fixed measurement family. If the wording permits changing measurement settings between groups of copies, three binary projective measurements of the three Pauli observables also suffice, each with $m=2$. That procedure is informationally complete three-observable qubit tomography, and it does not contradict the four-outcome bound for one fixed POVM. Tomography estimates probabilities statistically from many copies; a finite sample does not determine an arbitrary continuous state exactly.

Consider any POVM, not necessarily rank one, with two distinct reported outcomes intended to identify the two states. Its effects satisfy $E_1,E_2\ge 0$ and $E_1+E_2\le I$; equality holds for a two-outcome measurement. If $⟨{\psi }_1|E_1|{\psi }_1⟩=1$, then positivity and completeness force $⟨{\psi }_1|E_2|{\psi }_1⟩=0$. Taking a positive square root gives $E_2|{\psi }_1⟩=0$. Likewise, $⟨{\psi }_2|E_2|{\psi }_2⟩=1$ and $0\le E_2\le I$ imply $(I-E_2)|{\psi }_2⟩=0$, or $E_2|{\psi }_2⟩=|{\psi }_2⟩$.

Using Hermiticity,Thus perfect discrimination of pure states requires orthogonality, contradicting the proposed nonzero overlap. This proves perfect discrimination of pure states requires orthogonality for arbitrary generalized measurements. Measurements with an inconclusive outcome can sometimes identify nonorthogonal inputs unambiguously, but unambiguous quantum state discrimination has a nonzero failure probability and is not perfect deterministic discrimination.

The Hamiltonian operator annihilates every vector orthogonal to both of its defining states:Every positive power also annihilates that vector. The exponential series therefore givesIt is a stationary zero-energy state under this unitary time evolution. The displayed evolution uses $\hslash =1$, as in the question. For $N=1$ the two independent defining vectors already span the whole qubit space, so no nonzero vector satisfies both orthogonality conditions; for larger $N$ their orthogonal complement has dimension $2^N-2$.

Write $a=⟨\psi |w⟩=2^{-N/2}$, which is real and satisfies $0<a<1$ for $N\ge 1$. The invariant two-dimensional span has orthonormal eigenvectorswith eigenvalues $\Delta (1+a)$ and $\Delta (1-a)$. In this basis,Transfer therefore requires the two evolved eigenphases to differ by an odd multiple of $\pi$:The first positive time isEquivalently, exponentiating on the invariant span gives the full evolutionAt $t_0$ this is $-i{e}^{-i\Delta t_0}|w⟩$, so the requested global phase can be chosen as $\alpha =-\Delta t_0-\pi /2$ modulo $2\pi$. Since the two vectors are linearly independent, their relative coefficient cannot produce exact transfer at an earlier positive time. This is continuous-time quantum search, with time proportional to the square root of the search-space dimension for fixed $\Delta$. Restoring units multiplies the stated time by $\hslash$. The degenerate zero-qubit case would already have $\psi =w$, so there would be no smallest positive transfer time; the formula concerns the nontrivial $N\ge 1$ search.

For the normalized vector defining the orthogonal projection $P=|\varphi ⟩⟨\varphi |$, $P^k=P$ for every $k\ge 1$. Thuswhich proves the projector phase rotation identity in this case:It changes the sign of the component along $\varphi$ and fixes the orthogonal complement, so it is a reflection operator.

For a marked computational basis vector $w$, $U_{P_w}=I-2|w⟩⟨w|$ is the marked-state phase oracle. With $|\psi ⟩=H^{\otimes N}|0^N⟩$, the other reflection isThe Hadamard gates thus implement its change of basis from the known all-zero state. The usual Grover diffusion operator is $D=2|\psi ⟩⟨\psi |-I=-U_{P_{\psi }}$. Consequently a Grover search algorithm iteration isThe minus sign is an irrelevant global phase. These two reflections rotate the search state in the span of the marked vector and the unmarked uniform vector, with the Grover rotation angle controlled by the initial marked amplitude. Iterating them approximately $\pi \sqrt{2^N}/4$ times gives high-probability search. The same pair of projectors appears additively in the continuous-time Hamiltonian, but the product of full reflections and evolution under their sum are distinct dynamics.

An oracle can recognize a solution without disclosing it in advance. If an efficiently evaluable or black-box predicate has the promised unique marked input, write $f(x)=1$ exactly for that input. A Boolean quantum oracle computes this predicate reversibly asIts diagonal projector on the search register is ${\sum }_{x}f(x)|x⟩⟨x|=|w⟩⟨w|$. To implement a selectable phase, compute $f(x)$ into a zero quantum ancilla, apply a known phase to its $1$ component, and uncompute. The search register then undergoesThis requires evaluation access to the predicate, not classical knowledge of which input passes it. The $P_{\psi }$ term is known from the Hadamard transform. With Hamiltonian-oracle access, or by controlled short-time simulations of the two terms, their sum can realize continuous-time quantum search.

The unknown projector is supplied through an oracle or a physically encoded recognition rule. It cannot be manufactured for an arbitrary hidden $w$ with no such input-dependent resource. The oracle assumption and the fixed energy scale $\Delta$ are essential when interpreting the square-root search time as a computational advantage.

The first two CNOT gates encode $u|0⟩+v|1⟩$ asthe three-qubit bit-flip repetition code. In the printed detection circuit the first quantum ancilla records $q_3\oplus q_2$ and the second records $q_2\oplus q_1$. Both start in $|0⟩$. For an incoming bit-error pattern $e=(e_1,e_2,e_3)$, the two logical basis branches give the same error syndromeAdding $111$ to a computational string leaves both parities unchanged, so the ancillas acquire no information about $u$ or $v$. The joint state after extraction isThe syndrome measurement therefore preserves the unknown logical amplitudes. For zero or one bit flip the corrections areEach indicated correction squares to the identity and restores the encoded state. The order of the two ancilla labels matters: the printed first ancilla is the $q_2,q_3$ parity, not the $q_1,q_2$ parity. This is coherent syndrome extraction for the three-qubit repetition code with the circuit's specific parity choices.

For later use, an error pattern and its complement have the same syndrome. Minimum-weight recovery corrects patterns of weight zero or one. Patterns of weight two or three instead leave $X_1{X}_2{X}_3$, the logical bit flip that exchanges the two codewords. The code protects against the stated bit-flip channel, not arbitrary single-qubit phase errors.

The PDF places the extra $X$ on $q_2$ after that qubit has interacted with $a_1$ but before it interacts with $a_2$. Its timing is essential. With no incoming error, the first extracted parity is zero. The fault then changes the data toThe remaining parity measurement gives $a_2=1$ on both branches. Thus the measured error syndrome is $01$, which the rule in the preceding part interprets as an error on $q_1$. Applying $X_1$ leavesThis is outside the original encoded subspace: neither of its supporting basis strings is $000$ or $111$. The incorrect syndrome causes a second data error rather than restoring the input. This timed bit flip during repetition-code syndrome extraction demonstrates why a simple parity circuit need not tolerate its own faults.

The same failure can be checked for every incoming channel error. Let $f\in \{0,1\}$ indicate the internal fault and let $c(s)$ be the correction bit pattern from the table. The observed syndrome and the final pre-correction data pattern areBecause $s$ is linear over binary addition and $s(c(s_{\mathrm{obs}}))=s_{\mathrm{obs}}$, the residual pattern $r=d\oplus c(s_{\mathrm{obs}})$ satisfiesWhenever the fault occurs, the residual syndrome is $10$, so recovery never returns the state to the encoded subspace, even if a channel error also occurred. The diagram therefore must not be treated as an extra independent pre-extraction data flip that would always be diagnosed normally.

Use the probability of failing to restore an arbitrary unknown input in the original encoded subspace as the error criterion. With no extraction fault, the bit-flip repetition code succeeds exactly on channel-error patterns of weight zero or one. Independent physical flips giveThe probability $B$ is the logical bit-flip probability for the ideal recovery. The preceding calculation shows that every occurrence of the specified internal fault leaves the code space. Independence of that fault therefore gives exact encoded-state failure with a faulty parity check:A single unencoded qubit has bit-flip error probability $p$. Thus the encoded scheme improves this error criterion precisely whenFor $0<p<1/2$, $p-B=p(1-p)(1-2p)>0$ and $A=(1-p{)}^2(1+2p)>0$. Rearranging givesEquality gives no improvement. At $p=0$ the unencoded channel is already perfect; at $p=1/2$ ideal recovery only ties it. For $1/2<p\le 1$, the stipulated majority correction is no better even without the internal fault, and this fault cannot improve it. Hence there is no nonnegative $q$ giving a strict improvement in those ranges.

The criterion concerns restoration of every possible logical state: a logical bit flip can accidentally preserve a particular logical $X$ eigenstate, but that is not protection of an unknown input. The threshold assumes the displayed single fault location and ideal encoding, measurement and conditional correction. Adding another recovery circuit or comparing a different average-fidelity metric would define a different noise model or performance criterion.

Use the PDF's Bell state labels throughout this question: its ${\Phi }_{-}$ is the antisymmetric spin singlet state, whereas ${\Psi }_{\pm }$ are the even-parity states. WriteExpanding the antisymmetric combination cancels its $00$ and $11$ components and givesThe two normalized orthogonal vectors are the columns of a unitary matrix $U$. Its determinant $a_0{b}_1-a_1{b}_0$ has modulus one because $\det (U^{†}U)=|\det U{|}^2=1$. ThereforeThis proves collective-unitary covariance of the two-qubit singlet: a common basis change alters only its global phase, and leaves its density projector unchanged.

The Pauli matrices act by $X|0⟩=|1⟩$, $X|1⟩=|0⟩$, $Z|0⟩=|0⟩$, and $Z|1⟩=-|1⟩$. Consequently $X\otimes X$ swaps $00$ with $11$ and $01$ with $10$. The plus combinations are its $+1$ eigenvectors, and the minus combinations its $-1$ eigenvectors. Meanwhile $Z\otimes Z$ is $+1$ on the even-parity basis vectors and $-1$ on the odd-parity ones. Thus, with the paper's labels,This verifies all four Bell states directly. The two observables commute: $XZ=-ZX$ on each factor, so the two minus signs cancel in their tensor products. Their joint eigenvalues distinguish the four states, as used in a Bell-basis measurement.

Choose the phase gateIt is unitary. Acting on both qubits leaves $|00⟩$ unchanged and multiplies $|11⟩$ by $i^2=-1$, so $S\otimes S$ sends ${\Psi }_{+}$ to ${\Psi }_{-}$ with exactly the requested phase.

Using the Hadamard gate $H$, chooseIt is unitary and symmetric, andFor any matrix $U$, applying $U\otimes U$ to $(|00⟩+|11⟩)/\sqrt{2}$ gives the coefficient matrix $U{U}^T/\sqrt{2}$. Here $U_2{U}_2^T=U_2^2=X$, henceBoth displayed transformations are exact, not merely equal up to global phase. These common local unitaries permute the triplet Bell projectors while preserving the singlet projector by the preceding determinant identity.

First explain the stated local conversion. The four equally weighted correlated local Pauli operations $I\otimes I$, $X\otimes X$, $Z\otimes Z$, and $Y\otimes Y$ remove coherences in the Bell states basis, since those states have distinct joint parity eigenvalues. This leaves four Bell probabilities. One-party Pauli operations permute the Bell projectors, so the largest probability can be placed on the singlet ${\Phi }_{-}$. Call it $p$; necessarily $p\ge 1/4$.

The two common unitaries found above generate permutations of the three triplet projectors: $S\otimes S$ exchanges ${\Psi }_{+}$ and ${\Psi }_{-}$, and $HSH\otimes HSH$ exchanges ${\Psi }_{+}$ and ${\Phi }_{+}$. Averaging the six triplet permutations replaces their weights by their common mean, while collective-unitary covariance of the two-qubit singlet fixes the singlet projector. This is Bell twirling followed by triplet symmetrization, producing the specified two-qubit Werner state. Shared randomness coordinates the local choices, so the procedure is allowed by local operations and classical communication. Common unitaries alone would preserve the original singlet weight, which need not initially be at least $1/4$; the preceding one-party permutation is what ensures that range.

For the eigenvalue calculation, put $P_s=|{\Phi }_{-}⟩⟨{\Phi }_{-}|$, $a=(1-p)/3$, and $b=p-a=(4p-1)/3$. Then $\rho =aI+b{P}_s$. In the ordered computational basis $00,01,10,11$, transposing the second subsystem givesThe $00,11$ block has eigenvalues $a-b/2$ and $a+b/2$, while the other two basis vectors also have eigenvalue $a+b/2$. Thus the partial transpose spectrum isThe last three are positive throughout the given range, so the partial transpose is not positive exactly when $p>1/2$. A separable quantum state is a convex sum of product density operators, each still positive after transposing one factor. The negative eigenvalue therefore proves entanglement.

For completeness, separability on the other side can be proved explicitly rather than inferred solely from a theorem name. Let $P_{j,\pm }=(I\pm {\sigma }_j)/2$ be the one-qubit Pauli eigenprojectors. At $p=1/2$, the mixture of six antiparallel product states isusing $P_s=(I-{\sum }_j{\sigma }_j\otimes {\sigma }_j)/4$. It is manifestly separable. For $1/4\le p\le 1/2$,with nonnegative coefficients summing to one; $I/4$ is also separable. ConsequentlyAt the boundary $p=1/2$ the partial transpose has a zero eigenvalue and the explicit decomposition shows separability.