= Solution
For the known bit string $y$, define the <Pauli gate> product $T_y=\bigotimes_{j=0}^{N-1}Z_j^{y_j}$. Its diagonal action is $T_y|x\rangle=(-1)^{x\cdot y}|x\rangle$, where the <binary inner product> is taken modulo two. The <Hadamard transform> produces $|\phi_y\rangle=H^{\otimes N}|y\rangle=T_y|\phi\rangle$. Thus the required <vectors> for <Grover search with a nonzero reflection label> are
$$
\boxed{|\widetilde\Psi_g\rangle=\frac1{\sqrt M}\sum_{f(x)=1}(-1)^{x\cdot y}|x\rangle,\qquad |\widetilde\Psi_b\rangle=\frac1{\sqrt{2^N-M}}\sum_{f(x)=0}(-1)^{x\cdot y}|x\rangle.}
$$
They remain <orthonormal> and $|\phi_y\rangle=\sin\theta|\widetilde\Psi_g\rangle+\cos\theta|\widetilde\Psi_b\rangle$. The new iterate is $G_y=(2|\phi_y\rangle\langle\phi_y|-I)U_f$. Since $T_y$ commutes with the diagonal <marked-state phase oracle> and $T_y^2=I$,
$$
G_y=T_yGT_y.
$$
Consequently its <matrix> on the signed <basis> is exactly the <rotation matrix> in part (a), proving the claimed equivalence of the two evolutions.
Back to article page
