Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 49 (Quantum Computation)

Write $N=2^n$ and $|s⟩=N^{-1/2}{\sum }_{x=0}^{N-1}|x⟩$. The initial Hadamard gates prepare $|s⟩$ in the search register and $|-⟩$ in the final quantum ancilla. Since the Pauli X gate satisfies $X|-⟩=-|-⟩$, the Boolean quantum oracle acts by quantum phase kickback:For a single marked entry this is the marked-state phase oracle $O_a=I-2|a⟩⟨a|$ on the search register. The ancilla stays separate and unchanged throughout.

The Grover diffusion operator is $V=2|s⟩⟨s|-I$, because $H^{\otimes n}|0^n⟩=|s⟩$. The PDF circuit places one diffusion after each oracle call, so the state before measurement isIn the supplied amplitude amplification theorem, take $|\psi ⟩=|s⟩$ and $|\varphi ⟩=|a⟩$. Their overlap has modulus $1/\sqrt{N}$, so the Grover rotation angle is $\theta =\arcsin (N^{-1/2})$. A quantum measurement in the computational basis therefore givesThe inverse sine here is applied to the overlap of the two different states. The converted TeX's self-overlap in the angle definition is a transcription error; the original PDF has $|⟨\varphi |\psi ⟩|$.

If there is no marked entry, the Boolean quantum oracle is the identity. The uniform superposition state is a positive eigenstate of the Grover diffusion operator:Thus every iteration leaves the full state $|s⟩\otimes |-⟩$ unchanged. The measured search bits have the uniform distributionOnly the first $n$ qubits are measured in the printed circuit. If the untouched ancilla were also measured in the computational basis, its bit would be an independent fair bit, giving probability $1/(2N)$ for each joint outcome.

Use a verified Grover promise test. Since $n>1$, $N\ge 4$. ChooseThis is a nearest integer to $\pi /(4\theta )-1/2$, so $|(2k+1)\theta -\pi /2|\le \theta$. Run the Grover search algorithm for $k$ iterations and measure the candidate $x$. Make one further oracle query with input $|x⟩|0⟩$ and measure the answer bit $f(x)$. Declare that a marked entry exists exactly when this bit is one.

In the zero case the verification always returns zero, so the decision is correct with certainty. In the single-marked-entry case, verification returns one exactly when the candidate is $a$, andFinally, $\arcsin u\ge u$ on $[0,1]$ gives $k\le \pi \sqrt{N}/4$. HenceThe verification query is necessary for this decision rule: an unverified search-register label does not itself say whether it is marked.

The Pauli Z gate exchanges the two Hadamard basis states: $Z|+⟩=|-⟩$ and $Z|-⟩=|+⟩$. Multiplying the displayed gate by the Pauli X gate givesOn the other hand,The two operators agree, provingAlso $U(\theta )=H\mathrm{diag}(1,e^{-i\theta })=J(-\theta )$ in the J gate convention. Keeping this angle sign explicit avoids confusing the two conventions for equatorial qubit measurements.

Prepare the three-vertex graph-state wire: start all three qubits in $|+⟩$ and apply Controlled-Z gates on edges $1-2$ and $2-3$. In this paper's equatorial qubit measurement convention the basis vectors can be chosen asThe given identity means that measuring an input qubit at angle $\theta$, with outcome $r$, teleports its state to the next qubit as $X^{r}U(\theta )|\psi ⟩$. Each outcome has probability $1/2$, since $X^{r}U(\theta )$ is unitary. This is one-bit teleportation with a known Pauli frame.

Measure vertex 1 at angle $\alpha$ and record $r$. Then measure vertex 2 at angle $\gamma =(-1{)}^r\beta$, taken modulo $2\pi$, and record $s$. The controlled-Z on edge $2-3$ commutes with the first measurement, so the two teleportation steps can be applied successively. The remaining normalized state isFor $r=0$ this is $X^{s}U(\beta )U(\alpha )|+⟩$. For $r=1$, the relation proved above gives $U(-\beta )X=e^{i\beta }ZU(\beta )$. Thus in every branch the remaining state isThe scalar is a global phase and has no effect on probabilities.

Finally measure vertex 3 in the computational basis, obtaining $z$, and reportThe $Z^r$ byproduct changes only computational-basis phases; $X^s$ changes the output label by $s$. Hence the corrected bit has exactly the ideal circuit's probability distribution in every branch, not merely on average. The procedure uses only single-qubit measurements after preparing the graph state, adaptive classical angle selection, and deterministic classical output processing.

First expand the result of the first gate in the computational basis:Using $1+e^{-i\alpha }=2e^{-i\alpha /2}\cos (\alpha /2)$ and $1-e^{-i\alpha }=2i{e}^{-i\alpha /2}\sin (\alpha /2)$, this becomesApply $U(\beta )|0⟩=|+⟩$ and $U(\beta )|1⟩=e^{-i\beta }|-⟩$ to obtainFor example, its quantum measurement in the computational basis has probabilities $\mathbb{P}(k=0)=(1+\sin \alpha \sin \beta )/2$ and $\mathbb{P}(k=1)=(1-\sin \alpha \sin \beta )/2$, obtained by squaring the two basis amplitudes.

Use two-bit remote state preparation on a graph-state path. Alice performs the first two measurements from the preceding measurement-based quantum computation: angle $\alpha$ on her first qubit, giving $r$, then angle $(-1{)}^r\beta$ on her second, giving $s$. She sends the pair $(r,s)$ to Bob, using exactly two classical communication bits.

The branch calculation already gives Bob's state as $e^{ir\beta }{X}^s{Z}^r|\chi ⟩$, where $|\chi ⟩=U(\beta )U(\alpha )|+⟩$. Bob applies $X^s$ first and $Z^r$ second, so his correction operator is $Z^r{X}^s$. Since $X^2=Z^2=I$,ThusThe final state is exactly the desired state up to the irrelevant global phase. No postselection is used: all four measurement branches have probability $1/4$ and are corrected. Bob does not need the angles themselves; Alice uses them in her measurement choices, while the two bits specify his Pauli correction.

Number the wires from top to bottom as $1,\dots ,5$. The first two controlled-NOT gates encode $|\psi ⟩=u|0⟩+v|1⟩$ into the bit-flip repetition codeon data wires $1,2,3$. The lower two zero ancillas store an error syndrome. Reading the PDF's four detection CNOTs givesThe syndrome and the data qubit to be flipped are thereforeThis is coherent syndrome extraction for the three-qubit repetition code. The recovery Toffoli gates implement these conditions; the intervening Pauli X gates temporarily turn zero-valued controls into one-valued controls and then restore the syndrome wires. Finally, inverse encoding returns the logical state to the top wire and resets data wires 2 and 3 to zero.

For the specified error $X_1$, the encoded data becomes $u|100⟩+v|011⟩$. Both terms have syndrome $01$, so detection factors out $|01{⟩}_{45}$ without revealing the logical amplitudes. Recovery flips data wire 1, restoring $u|000⟩+v|111⟩$, and decoding yieldsThe lower four wires need not all return to zero: their syndrome record is independent of the logical state, which is what the correction requirement needs.

Use the Hadamard gate identity $H=(X+Z)/\sqrt{2}$ on the first data wire. The $X_1$ branch is corrected as above and has syndrome $01$. The $Z_1$ branch changes the encoded state to $\alpha |000⟩-\beta |111⟩$, with syndrome $00$. No bit-flip recovery is triggered, and decoding leaves $Z|\psi ⟩$ on the top wire.

By linearity of the full quantum circuit, its output for $H_1$ is thereforewhere the four-bit strings are ordered as wires $2,3,4,5$. The two syndrome states are orthogonal. Taking their partial trace removes the cross terms, so the reduced density matrix isThe top output undergoes a completely dephasing channel in the computational basis. The bit-flip component is corrected, but the undetected phase component destroys logical coherence after the syndrome is ignored.

The point needing proof is that a corrected error's residual state cannot retain dependence on the logical input. Let $W_j$ denote the complete linear map from the logical input to all five output wires for error $E_j$. Protection gives $W_j|0⟩=|0⟩|{\eta }_{j,0}⟩$ and $W_j|1⟩=|1⟩|{\eta }_{j,1}⟩$. Applying protection to $|+⟩$ and comparing its two top-qubit components yieldsso $|{\eta }_{j,0}⟩=|{\eta }_{j,1}⟩=|{\eta }_{j,+}⟩$. Denote the common vector by $|{\eta }_j⟩$. Linearity then gives $W_j|\psi ⟩=|\psi ⟩|{\eta }_j⟩$ for every input.

The encoding and all operations surrounding the error are fixed. Replacing the error by $E=\alpha E_1+\beta E_2$ consequently replaces the overall map by $\alpha W_1+\beta W_2$, givingBecause $E$ and the surrounding circuit are unitary, the output is normalized for every normalized input; the residual vector in parentheses thus has norm one. This proves linearity of coherent quantum error correction and hence protection against $E$. Orthogonality of $|{\eta }_1⟩$ and $|{\eta }_2⟩$ is not required for this proof.

Use phase-flip protection by Hadamard conjugation. Insert a Hadamard gate on each of the three data wires immediately after the two encoding CNOTs and before the physical error. Insert another Hadamard on each data wire immediately after the error and before syndrome detection. Leave the two syndrome ancillas and every detection, recovery and decoding gate unchanged.

The first layer changes the encoded state to $\alpha |+++⟩+\beta |---⟩$, the three-qubit phase-flip repetition code. The two layers surrounding the error turn the effective error seen by the old circuit intoSince $H^2=I$ and $HZH=X$, the four physical cases become respectively $I,X_1,X_2,X_3$. The original coherent syndrome and recovery circuit corrects all four, as its syndrome table shows. Thus two Hadamard layers on the three data wires, straddling the error, give the required phase-flip protection. The final top wire is the original $|\psi ⟩$, not $H|\psi ⟩$, because the second layer returns the data to the original coding basis before recovery and decoding.

Put $N=2^n$ and label the binary digits of $x$ by $x_{n-1},\dots ,x_0$, with $x={\sum }_{j=0}^{n-1}{2}^j{x}_j$. The Walsh-Hadamard transform prepares the uniform quantum superposition $N^{-1/2}{\sum }_x|x⟩$. Applying the phase gate $R_a^{2^j}$ to the qubit for digit $x_j$ multiplies its basis amplitude by $\exp (2\pi ia{2}^j{x}_j/N)$. Taking their product givesWith the most significant qubit written first, this provesEach power is implemented by repeated uses of the supplied gate. The total is ${\sum }_{j=0}^{n-1}{2}^j=N-1$ uses. This realizes dyadic phase-gate identification without needing an unknown controlled gate or asserting a gate-call cost polynomial in $n$.

The inverse quantum Fourier transform in the original PDF has matrix elements $N^{-1/2}{e}^{-2\pi iky/N}$ multiplying $|y⟩⟨k|$. The converted TeX incorrectly repeats $y$ in the bra; using the actual PDF operator,If $y=a$, every summand of the inner sum is one, so it equals $N$. If $y\ne a$, let $q=e^{2\pi i(a-y)/N}$. Then $q\ne 1$ and $q^N=1$, and the finite geometric series gives ${\sum }_{x=0}^{N-1}{q}^x=(1-q^N)/(1-q)=0$. This is orthogonality of roots of unity. HenceA quantum measurement in the computational basis consequently returns the integer $a$ with probability one.

The eigenvalue on $|0⟩$ of every power is one, and its eigenvalue on $|1⟩$ is $e^{2\pi iak/N}$. ThusIf $a$ is odd, its greatest common divisor with $N=2^n$ is one. Divisibility can therefore be cancelled, givingIn particular, the $N$ powers with $0\le k<N$ are distinct. Each is the phase gate $R_m$ with $m\equiv ak(\mathrm{mod}N)$, and multiplication by $a$ is a permutation of these residue classes. Equivalently, for any desired $m$, choose $k\equiv a^{-1}m(\mathrm{mod}N)$, where $a^{-1}$ is the modular inverse. Then $R_a^k=R_m$, using the representative $0\le k<N$ and repeated forward applications only. Thus the powers generate the entire set. Once the preceding identification procedure has found $a$, these powers can also be labelled and selected classically.

Write the normalized qubit as $|\varphi ⟩=c_0|0⟩+c_1|1⟩$, with $|c_0{|}^2+|c_1{|}^2=1$. Only the $|1⟩$ amplitude changes between the two phase gates, soSince $|e^{i\delta }-1|=2|\sin (\delta /2)|\le |\delta |$,The phase-gate discretization error is uniform over all input states; its exact operator norm is $2|\sin (\delta /2)|$. To choose an approximating gate, round $N\theta /(2\pi )$ to the nearest integer and reduce it modulo $N$. Taking the shortest circular angle difference gives $|\delta |\le \pi /N$, and hence a uniform state-vector error at most $\pi /2^n$. The circular choice handles the identified endpoints $0$ and $2\pi$ correctly.