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

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.