Exact success probability after an integer number of Grover iterates

For $k=0$, the address coordinate column is $(\cos \theta ,\sin \theta {)}^{\mathsf{T}}$ by [F1], which is $(\cos ((2k+1)\theta ),\sin ((2k+1)\theta ){)}^{\mathsf{T}}$.

If after $k$ iterations the column is $(\cos ((2k+1)\theta ),\sin ((2k+1)\theta ){)}^{\mathsf{T}}$, multiplication by the matrix in [F2] and the addition formulas [F5] gives $(\cos ((2k+3)\theta ),\sin ((2k+3)\theta ){)}^{\mathsf{T}}$. Induction therefore gives the marked amplitude $\sin ((2k+1)\theta )$ for every integer $k\ge 0$.

The address vector at step 2.1 is unit by [F1] and [F7]. The response starts in the unit basis vector $\mathrm{\mid }0⟩$ and the gates $X,H$ in [F15] are unitary, so the response state $\mathrm{\mid }-⟩$ supplied by [F14] is unit. Their tensor product $u$ is unit by the product pairing [F12]–[F13], and [F8] makes $\rho =\mathrm{\mid }u⟩⟨u\mathrm{\mid }$ a density operator.

For each product-basis vector $e_{x,b}$, [F9] and [F11] give the diagonal weight $⟨\rho e_{x,b},e_{x,b}⟩=\mathrm{\mid }⟨e_{x,b},u⟩{\mathrm{\mid }}^2$. By step 2.1, the address coordinate along $\mathrm{\mid }G⟩$ is $\sin ((2k+1)\theta )$; the definition $\mathrm{\mid }G⟩=t^{-1\mathrm{/}2}{\sum }_{x\in M}\mathrm{\mid }x⟩$ in [F1] therefore gives coefficient $\sin ((2k+1)\theta )\mathrm{/}\sqrt{t}$ at each marked $x$. The squared response coordinates sum to $1$ because $\mathrm{\mid }-⟩$ is unit and the qubit computational basis is orthonormal by [F10], [F14]–[F15]. Summing over the $t$ marked addresses and both response values gives $t({\sin }^2((2k+1)\theta )\mathrm{/}t)\cdot 1={\sin }^2((2k+1)\theta )$. The terminal output law [F6] sums precisely over the unmeasured response register, so this is the measured marked probability.

If $t=0$, $O_M=I$ and $R_s\mathrm{\mid }s⟩=\mathrm{\mid }s⟩$, so all iterates remain in the unmarked subspace and the marked probability is $0$. If $t=N$, $O_M=-I$ and each iterate maps $\mathrm{\mid }s⟩$ to $-\mathrm{\mid }s⟩$; every address is marked, so the probability is $1$.