Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 51 (Quantum Computation)

The answer qubit enters the Boolean quantum oracle in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$, because the Pauli X gate followed by the Hadamard gate maps $|0⟩$ to $|-⟩$. Since $X|-⟩=-|-⟩$, quantum phase kickback multiplies the $|xy⟩$ component by $(-1{)}^{f(x,y)}$ and leaves the answer qubit unchanged. The two input qubits enter in the uniform quantum superposition $|++⟩$. ThusEquivalently, using the Controlled-Z gate and the Pauli Z gate,Here the exponent in the phase may be evaluated as an ordinary integer, since its parity agrees with the exclusive or expression. In particular, $d$ contributes only a global phase.

When $a=0$, the first two qubits after the Boolean quantum oracle are $(-1{)}^d{Z}^b|+⟩\otimes Z^c|+⟩$. The Hadamard gate obeys $H{Z}^t|+⟩=|t⟩$ for $t\in \{0,1\}$. Applying the Walsh-Hadamard transform therefore givesConsequently the quantum measurement in the computational basis has the deterministic outcomesThese four distinct answers identify the four promised Boolean quantum oracles with one query and certainty. The constant term does not affect the measurement in quantum mechanics, because a global phase does not change its probabilities.

All four promised functions have $a=1$. Use quadratic Boolean phase cancellation: apply a Controlled-Z gate to remove the phase $(-1{)}^{xy}$, then apply the Walsh-Hadamard transform. With the rightmost gate acting first, chooseBecause $C_Z^2=I$ and the Controlled-Z gate commutes with the Pauli Z gates,The quantum measurement in the computational basis consequently producesEach answer occurs with probability one for its promised Boolean quantum oracle.

In the ordered computational basis $00,01,10,11$, the first two qubits of $|{\psi }_{0000}⟩$ have amplitudes $(1,1,1,1)/2$, while those of $|{\psi }_{1111}⟩$ have amplitudes $(-1,1,1,1)/2$. Both have the same normalized answer qubit $|-⟩$. Their inner product is thereforeA common unitary operator $U\otimes I$ preserves this nonzero inner product. To distinguish the alternatives with certainty using the prescribed quantum measurement in the computational basis, their first-register outcome supports would have to be disjoint: every outcome possible under one alternative must be impossible under the other. Vectors with disjoint computational basis supports have zero inner product, contradicting its preservation. Thus no such $U$ exists. This is also an instance of perfect discrimination of pure states requires orthogonality; allowing a more general measurement in quantum mechanics would not rescue this pair of states. The obstruction concerns these prepared oracle-output states, rather than every conceivable oracle-query procedure.

A classical query with known answer bit $z$ reveals exactly the one bit $f(x,y)$, since it returns $z\oplus f(x,y)$. For the four promised Boolean functions, the value table isEvery possible first query splits the four alternatives into one class of size one and another of size three. On the branch with three remaining alternatives, a second binary answer can separate at most two classes. At least two alternatives therefore still agree on that branch, regardless of how the second query was chosen adaptively. This decision tree argument proves that a procedure guaranteed to identify every alternative needs at least three queries in the worst case.

For sufficiency, query $00,01,10$. The three-bit answer strings for $1,y,x,x\oplus y$ are respectively $111,010,001,011$, which are all distinct. Hence the exact classical worst-case query requirement is three. Some individual branches can terminate sooner; the lower bound does not assert that every oracle requires three queries.

Write $N=|A|$. For $N>1$, the unmarked computational basis vectors in $A$ give the normalized vectorIts norm is one and $⟨a|\omega ⟩=0$, so these two vectors form an orthonormal basis for $\mathcal{V}$. Splitting the uniform superposition state into its marked and unmarked terms givesThe nonnegative coefficients select the specified angle in $[0,\pi /2]$.

There is one degenerate boundary case: if $N=1$, then $|{\psi }_A⟩=|a⟩$ and $\mathcal{V}$ is one-dimensional. No vector in $\mathcal{V}$ can complete $|a⟩$ to a two-element orthonormal basis. Thus the printed two-dimensional description needs $N>1$. For $N=1$ the search itself is already solved, with $\theta =\pi /2$ and no query.

For $N>1$, use the orthonormal basis $(|a⟩,|\omega ⟩)$ from the preceding part. Both reflection operators preserve $\mathcal{V}$, because their reflected vectors belong to it. With $s=\sin \theta$ and $c=\cos \theta$, their restricted matrices areMultiplying in the specified order, including the overall minus sign, givesEquivalently,In particular, $G$ sends $\sin t|a⟩+\cos t|\omega ⟩$ to $\sin (t+2\theta )|a⟩+\cos (t+2\theta )|\omega ⟩$. This proves the Grover rotation angle description with the signs appropriate to these reflection operators.

For $N\ge 2$, induction using the Grover rotation angle givesThe quantum measurement in the computational basis therefore returns $a$ with probability ${\sin }^2((2k+1)\theta )$. Since $0<\theta \le \pi /4$, the first angle interval attaining the required success isThe first successful Grover iterate is consequentlyIndeed, this is the first integer at or above the lower endpoint requirement $k\ge \pi /(4\theta )-1$. The inequality $\lceil t-1\rceil <t$ also implies $(2k_{\min }+1)\theta <\pi /2+\theta$, so this iterate cannot overshoot the first success interval. Every smaller nonnegative integer lies before that interval and fails the threshold. Finally, $\arcsin u>u$ for $0<u<1$, soFor the singleton case $N=1$, measuring the initial state already returns $a$ with certainty, and $k_{\min }=0<\pi /4$. For $N=2$, the requested threshold is only $1/2$, so zero iterations already suffice. These boundary cases agree with the search guarantee.

List the known distinct strings in $A$ as $a_0,\dots ,a_{N-1}$, where $N=2^m$, and use an $m$-qubit index quantum ancilla. Apply Hadamard gates to that register to prepareFirst, for each $j$ with $a_j\ne 0^n$, apply the available unitary operator that transposes $|0^n,j⟩$ and $|a_j,j⟩$. The pairs are disjoint because they have distinct index labels. Skip a transposition when the two vectors coincide. This producesSecond, for each $j\ne 0$, transpose $|a_j,j⟩$ and $|a_j,0^m⟩$. These pairs are disjoint because the data strings $a_j$ are distinct. No pair contains the term with $j=0$, and no later transposition moves an earlier output. The final state is exactlyThis clean subset superposition preparation uses at most $N+(N-1)=2N-1$ of the given transpositions and $m$ Hadamard gates. Since $m=O({\log }_{2}n)$, $N$ is polynomial in $n$; multiplying this count by the assumed polynomial size of each transposition gives a polynomial-size quantum circuit. The index quantum ancilla returns to zero, so the data register is a pure uniform superposition state, rather than a mixture obtained by discarding its index. The construction uses an available enumeration of the known subset; a membership oracle alone would not justify that enumeration.

Using the printed measurement-vector convention, the unitary operator isThus it is a phase gate followed by a Hadamard gate, with angle sign opposite to the parameter in the catalogued J gate. Its rows are the conjugate transposes of the orthonormal measurement vectors, so it is unitary. Right multiplication by the Pauli Z gate changes the sign of the second column, which is exactly the effect of left multiplication by the Pauli X gate, exchanging the two rows. Explicitly,Similarly, right multiplication by the Pauli X gate exchanges columns, givingTherefore the exact identities, retaining the global phase in the second one, areThese supply Pauli-frame propagation along a measurement wire.

Write the normalized input quantum state as $|\psi ⟩=a|0⟩+b|1⟩$. The fresh quantum ancilla is $|+⟩$, so the Controlled-Z gate createsApplying the measurement bra $⟨v_k(\theta )|$ to the first qubit leaves the unnormalized second-qubit vectorSince $|+⟩,|-⟩$ form an orthonormal basis,Also $U(\theta )|\psi ⟩=a|+⟩+e^{-i\theta }b|-⟩$, while the Pauli X gate fixes $|+⟩$ and changes the sign of $|-⟩$. Dividing by the branch norm therefore givesThis is one-bit teleportation with the present positive-exponent measurement vectors; the transferred logical gate is $U(\theta )=J(-\theta )$.

Label the chain cluster state from top to bottom by $1,2,3,4$, and let $k,l,m$ be the phase-measurement outcomes on the first three vertices, with raw computational basis outcome $s$ on vertex four. Repeated one-bit teleportation leaves the last qubit, up to global phase, inThis sequential description applies even though the whole graph state is prepared first: a later Controlled-Z gate acts only on unmeasured qubits and commutes with earlier single-qubit measurement operators. It can therefore be moved past those measurements for the purpose of calculating each conditional branch.

Take $\alpha =\theta$ and $\beta =0$, so $U(0)=H$. After the second measurement the logical state isFor binary $p,q$, the identities proved above imply the Pauli-frame propagation along a measurement wire rulewhere $\simeq$ means equality up to global phase. Choose the third angle adaptively as $\gamma =(-1{)}^{l\oplus 1}\varphi$. Then $(-1{)}^l\gamma =-\varphi$, andReading the target circuit in temporal order gives its premeasurement stateConsequentlyThe Pauli Z gate changes only phases in the computational basis, while the Pauli X gate exchanges its two measurement outcomes. Thus the explicit choices areIndeed, for every earlier outcome branch,Hence averaging over the earlier random outcomes leaves exactly the target probability distribution. This implements the desired measurement-based quantum computation without physically removing the final Pauli frame.

Let $\varphi =j\pi /2$ for an integer $j$, and put $q=j\mathrm{mod}2$. Use the fixed phase-measurement angles $(\theta ,0,-\varphi )$ and a fixed final computational basis measurement. Denote their outcomes by $k,l,m,s$. The adaptive construction would instead use $-\varphi$ when $l=0$ and $+\varphi$ when $l=1$.

For the printed measurement vectors,Therefore $+\varphi$ and $-\varphi$ define the same unordered pair of rank-one linear projections; the labels are exchanged if and only if $q=1$. In the branch $l=1$, the outcome that would be called $m_{\mathrm{ad}}$ in the adaptive experiment is thus $m\oplus q$. In both branches,The output correction from the preceding part becomesIf $j$ is even this reduces to $s\oplus k\oplus m$; if $j$ is odd an additional $l$ is included. This equatorial measurement relabeling at Clifford angles changes only the classical interpretation, not any physical measurement basis.

All four fixed single-qubit projective measurements act on different vertices, so their operators commute. They can be performed simultaneously, with the displayed classical correction applied afterward. The first angle $\theta$ may be arbitrary: it was never adaptive. Only the sign choice for the third angle needed to be replaced. Thus the simulation is nonadaptive for every $\varphi \in (\pi /2)\mathbb{Z}$.

For nonnegative integers $n$, assume the storage channel over successive intervals of length $\tau$ composes as $D_{ϵ}^n$. This is the memoryless interpretation of the specified storage law. In the computational basis, write the density operator asConjugation by the Pauli Z gate reverses the off-diagonal entries and leaves the diagonal entries unchanged, soAfter $n$ applications of the phase-flip channel, the multiplier is $(1-2ϵ{)}^n$. Comparing with the multiplier $1-2{ϵ}_n$ of a single phase-flip channel givesFor $n=0$ this gives the identity channel. Equivalently, composing two consecutive phase errors cancels them because $Z^2=I$, so their effective probability obeys ${ϵ}_{n+1}=ϵ+(1-2ϵ){ϵ}_n$. The same expression solves this recurrence. The iterated phase-flip channel formula presumes this composition law; specifying a channel at one time alone would not constrain a memory-bearing environment at later times.

Since $0<1-2ϵ<1$, the off-diagonal multiplier of the iterated phase-flip channel tends to zero. ThusLet $P_0=|0⟩⟨0|$ and $P_1=|1⟩⟨1|$ be the computational basis measurement projectors. The nonselective projective measurement channel iswhich is exactly the displayed limit. Its diagonal entries retain the original outcome probabilities; the measurement outcome is ignored and the coherences are erased. The limiting evolution is therefore the completely dephasing channel.

Number the three data qubits from top to bottom. It suffices initially to follow a pure input $|\psi ⟩=a|0⟩+b|1⟩$; linearity will extend the result to every density operator. The first two controlled-NOT gates create $a|000⟩+b|111⟩$. The first layer of Hadamard gates then encodes this asthe three-qubit phase-flip repetition code. Let $e_i$ indicate whether a Pauli Z gate occurred on data qubit $i$ during storage. The next layer of Hadamard gates uses $HZH=X$ and givesThe two initially zero syndrome quantum ancillas receive the adjacent parities. In the diagram's top-to-bottom order, their error syndrome isBoth terms of the logical superposition have these same parities, so the syndrome is independent of $a,b$. Measuring it reveals no logical-state information.

At the marked position of $R$ in the printed circuit, there has already been another layer of Hadamard gates on the data. There is also a layer immediately after $R$. Thus a desired correction $X_i$ in the parity-extraction frame must be implemented as $R=Z_i$ at the actual recovery location, since $H^{\otimes 3}{Z}_i{H}^{\otimes 3}=X_i$. Choose the recovery according toThe two patterns on each row share a syndrome because complementing all three bits does not change either parity. For a weight-zero or one error, the recovery removes the entire error in the parity-extraction frame. The remaining state is $a|000⟩+b|111⟩$, and the two final controlled-NOT gates give $|\psi ⟩|00⟩$.

For a weight-two or three error, minimum-weight recovery instead leaves all three bits flipped, giving $a|111⟩+b|000⟩$. The final controlled-NOT gates send this to $(a|1⟩+b|0⟩)|00⟩=X|\psi ⟩|00⟩$. Consequently, for every input density operator,The logical failure is a Pauli X gate after decoding, even though the stored physical errors were Pauli Z gates: $Z_1{Z}_2{Z}_3$ exchanges the two encoded codewords. This is the logical failure of the three-qubit phase-flip repetition code.

Independent applications of the phase-flip channel are a classical mixture of the eight physical Pauli Z gate error patterns. A specified weight-$k$ pattern has probability ${ϵ}^k(1-ϵ{)}^{3-k}$. The recovery from the preceding part succeeds on weight zero and one, and yields the logical Pauli X gate on weight two and three. There are three weight-two patterns and one weight-three pattern, so the logical failure probability isAveraging the corrected branches gives the complete decoded quantum channelIn particular, the leading logical error is $3{ϵ}^2$, rather than an error of first order in $ϵ$. For the stated range,Thus the failure probability is smaller than the physical error probability. The decoded channel is a bit-flip channel; it is not $D_{p_L}$, whose error operator would be $Z$. This distinction follows from the logical codeword exchange in the phase-flip repetition code.

Take a normalized environment quantum stateThe Controlled-Z gate is symmetric between the two qubits, so it can be written with the environment as the controlling system:Expanding the joint density operator after the interaction givesIn the partial trace, the two off-diagonal environment operators have trace zero, while each diagonal projector has trace one. HenceEquivalently, the Kraus operators are $K_0=\sqrt{1-ϵ}I$ and $K_1=\sqrt{ϵ}Z$, and $K_0^{†}{K}_0+K_1^{†}{K}_1=I$. This explicit Stinespring dilation describes the system's dephasing by discarding information in the environment. A fresh environment in this state at each storage interval also realizes the memoryless iteration used in part (a).