Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 51 / 2

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.