 Solution

Write $N=2^n$ and $|s⟩=N^{-1/2}{\sum }_{x=0}^{N-1}|x⟩$. The initial Hadamard gates prepare $|s⟩$ in the search register and $|-⟩$ in the final quantum ancilla. Since the Pauli X gate satisfies $X|-⟩=-|-⟩$, the Boolean quantum oracle acts by quantum phase kickback:For a single marked entry this is the marked-state phase oracle $O_a=I-2|a⟩⟨a|$ on the search register. The ancilla stays separate and unchanged throughout.

The Grover diffusion operator is $V=2|s⟩⟨s|-I$, because $H^{\otimes n}|0^n⟩=|s⟩$. The PDF circuit places one diffusion after each oracle call, so the state before measurement isIn the supplied amplitude amplification theorem, take $|\psi ⟩=|s⟩$ and $|\varphi ⟩=|a⟩$. Their overlap has modulus $1/\sqrt{N}$, so the Grover rotation angle is $\theta =\arcsin (N^{-1/2})$. A quantum measurement in the computational basis therefore givesThe inverse sine here is applied to the overlap of the two different states. The converted TeX's self-overlap in the angle definition is a transcription error; the original PDF has $|⟨\varphi |\psi ⟩|$.