= Solution
Write $N=2^n$ and $|s\rangle=N^{-1/2}\sum_{x=0}^{N-1}|x\rangle$. The initial <Hadamard gates> prepare $|s\rangle$ in the search register and $|-\rangle$ in the final <quantum ancilla>. Since the <Pauli X gate> satisfies $X|-\rangle=-|-\rangle$, the <Boolean quantum oracle> acts by <quantum phase kickback>:
$$
U_f(|x\rangle|-\rangle)=(-1)^{f(x)}|x\rangle|-\rangle.
$$
For a single marked entry this is the <marked-state phase oracle> $O_a=I-2|a\rangle\langle a|$ on the search register. The ancilla stays separate and unchanged throughout.
The <Grover diffusion operator> is $V=2|s\rangle\langle s|-I$, because $H^{\otimes n}|0^n\rangle=|s\rangle$. The PDF circuit places one diffusion after each oracle call, so the state before measurement is
$$
(VO_a)^k|s\rangle\otimes|-\rangle.
$$
In the supplied <amplitude amplification theorem>, take $|\psi\rangle=|s\rangle$ and $|\phi\rangle=|a\rangle$. 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 gives
$$
\boxed{\mathbb P(\text{output }a)=\sin^2((2k+1)\theta).}
$$
The 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 $|\langle\phi|\psi\rangle|$.
Back to article page
