Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 57 / 2

Put $L=2^N$ and define $\theta =\arcsin \sqrt{M/L}$. The normalized good and bad vectors have disjoint computational basis supports, so they are orthogonal. Counting the terms in the uniform quantum superposition givesSince $V_0=I-2|0^N⟩⟨0^N|$, the Hadamard transform gives $-H^{\otimes N}{V}_0{H}^{\otimes N}=2|\varphi ⟩⟨\varphi |-I$, the Grover diffusion operator. On the ordered orthonormal basis $(|{\Psi }_g⟩,|{\Psi }_b⟩)$, the two reflection operators have matricesTheir product isThis is a plane rotation through angle $-2\theta$ in the displayed coordinate convention, with the invariant good-bad plane preserved by both operators. In particular its action sends $(\sin a,\cos a)$ to $(\sin (a+2\theta ),\cos (a+2\theta ))$. Induction therefore gives the Grover rotation angle formula

Measuring the state from part (a) in the computational basis succeeds with probability $p_n={\sin }^2((2n+1)\theta )$. In the sparse-solution regime $0<M\le 2^{N-1}$, one has $0<\theta \le \pi /4$. The first success interval with $p_n\ge 1/2$ is $\pi /4\le (2n+1)\theta \le 3\pi /4$. Entering it requires $n\ge \pi /(8\theta )-1/2$, so the first half-probability Grover iterate isFor this integer, the angle is at least $\pi /4$ and less than $\pi /4+2\theta \le 3\pi /4$, so the rounding cannot skip the required interval. Every smaller nonnegative integer has angle below $\pi /4$ and hence success below $1/2$, proving minimality. For $M\ll 2^N$, the leading size is $n_{\min }\sim (\pi /8)\sqrt{2^N/M}$. If $M\ge 2^{N-1}$, the initial measurement already succeeds with probability at least one half and the smallest count is zero; if $M=0$ no search can succeed.

For the known bit string $y$, define the Pauli gate product $T_y={⨂}_{j=0}^{N-1}{Z}_j^{y_j}$. Its diagonal action is $T_y|x⟩=(-1{)}^{x\cdot y}|x⟩$, where the binary inner product is taken modulo two. The Hadamard transform produces $|{\varphi }_y⟩=H^{\otimes N}|y⟩=T_y|\varphi ⟩$. Thus the required vectors for Grover search with a nonzero reflection label areThey remain orthonormal and $|{\varphi }_y⟩=\sin \theta |{\tilde{\Psi }}_g⟩+\cos \theta |{\tilde{\Psi }}_b⟩$. The new iterate is $G_y=(2|{\varphi }_y⟩⟨{\varphi }_y|-I)U_f$. Since $T_y$ commutes with the diagonal marked-state phase oracle and $T_y^2=I$,Consequently its matrix on the signed basis is exactly the rotation matrix in part (a), proving the claimed equivalence of the two evolutions.

Initialize the register inThis can be prepared by Pauli X gates on the one-bits of $y$, starting from $|0^N⟩$, followed by Hadamard gates on all qubits. Alternatively, prepare the original uniform state and apply Pauli Z gates at those same bit positions. The conjugation calculation givesThe final diagonal sign operator changes no computational basis outcome probabilities. Thus the success probability and the iteration count in part (b) are unchanged. No final correction is needed when the objective is to measure a marked string.