Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 49 / 1

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.