Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2008/iii/paper-57/2/a/solution

Put and define . The normalized good and bad vectors have disjoint computational basis supports, so they are orthogonal. Counting the terms in the uniform quantum superposition gives
Since , the Hadamard transform gives , the Grover diffusion operator. On the ordered orthonormal basis , the two reflection operators have matrices
Their product is
This is a plane rotation through angle in the displayed coordinate convention, with the invariant good-bad plane preserved by both operators. In particular its action sends to . Induction therefore gives the Grover rotation angle formula

New to topics? Read the docs here!