= Solution
Let
$$
H_n=H^{\otimes n},
\qquad
|s\rangle=H_n|0^n\rangle
=\frac1{\sqrt N}\sum_{x\in B_n}|x\rangle,
$$
where $H$ is the <Hadamard gate>. For a computational-basis string $z$, define the phase reflection
$$
I_z=I-2|z\rangle\langle z|.
$$
Thus $I_0$ changes the sign of $|0^n\rangle$, while $I_{x_0}$ changes the sign of the marked state.
Conjugating $I_0$ by $H_n$ reflects in the hyperplane perpendicular to $|s\rangle$, so
$$
-H_nI_0H_n=2|s\rangle\langle s|-I
$$
is the <Grover diffusion operator>, the reflection about $|s\rangle$. The <Grover search algorithm>[Grover iteration operator]
$$
Q=(2|s\rangle\langle s|-I)I_{x_0}
$$
is the product of two reflections. It acts as a rotation through $2\theta$ in the plane spanned by the marked state $|x_0\rangle$ and the normalized uniform superposition of unmarked states, where
$$
\sin\theta=\frac1{\sqrt N}.
$$
It is the identity up to sign on the orthogonal complement of that plane.
Back to article page
