Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 4 / 10D (Quantum Information and Computation)

Let $P=|\psi ⟩⟨\psi |$. Since $|\psi ⟩$ is normalized, $P^2=P=P^{†}$. Hence the Householder reflectionis Hermitian andTherefore $A$ is unitary.

The marked-state phase oracle changes only the amplitude of $|x_0⟩$. Since that amplitude in $|\psi ⟩$ is $1/2$,Also,It follows that $A|\psi ⟩=-|\psi ⟩$ and $A|x_0⟩=|x_0⟩-|\psi ⟩$, soThe global minus sign has no observable effect. Prepare $|\psi ⟩=H^{\otimes 2}|00⟩$, query $I_{x_0}$ once, apply the fixed operator $A$, and perform a quantum measurement in the computational basis. The outcome is $x_0$ with probability one. This is exact Grover search on four entries.

No classical one-query algorithm can determine $x_0$ with certainty. If it queries a string $x$ and receives $1$, then it knows $x_0=x$. But if it receives $0$, each of the other three strings remains compatible with the response. Randomization cannot remove this ambiguity when certainty is required. ThusIndeed, three adaptive classical queries are necessary and sufficient in the worst case: after three negative answers, the unqueried fourth string must be $x_0$.