Grover's Algorithm: Why is the amplitude of $\left|a_{0}\right>$ after the second iteration $\frac{1}{\sqrt{N}}(5-\frac{20}{N}+\frac{16}{N^{2}})$?

Question

Grover's Algorithm: Why is the amplitude of $\left|a\right>$ after the second iteration $\frac{1}{\sqrt{N}}(5-\frac{20}{N}+\frac{16}{N^{2}})$?

If I apply the Grover operator twice to the initial state of the system \begin{equation*}G^{2}\left(\begin{matrix}\operatorname{sin}(\frac{\theta}{2})\\ \operatorname{cos}(\frac{\theta}{2})\end{matrix}\right)\end{equation*} I get \begin{equation*}\left(\begin{matrix}\operatorname{cos}(2\theta) & \operatorname{sin}{2\theta}\\ -\operatorname{sin}(2\theta) & \operatorname{cos}(2\theta)\end{matrix}\right)\left(\begin{matrix}\operatorname{sin}(\frac{\theta}{2})\\ \operatorname{cos}(\frac{\theta}{2})\end{matrix}\right)=\left(\begin{matrix}\operatorname{sin}(\frac{3\theta}{2})\\ \operatorname{cos}(\frac{3\theta}{2})\end{matrix}\right)\end{equation*} Can you please explain to me how applying the oracle operator to this yields a phase of $\frac{1}{\sqrt{N}}(5-\frac{20}{N}+\frac{16}{N^{2}})$?

Answer 1

If you multiply out the top row of your matrix, you get $$ \cos(2\theta)\sin\frac{\theta}{2}+\sin2\theta\cos\frac{\theta}{2}=\sin\frac{5\theta}{2}, $$ which is different to the answer you wrote down.

Now you just have to substitute $\sin\frac{\theta}{2}=\frac{1}{\sqrt{N}}$ and use a lot of double angle/trig addition formulae to figure out that $$ \sin\theta=\frac{2\sqrt{N-1}}{N},\qquad\sin(2\theta)=\frac{4(N-2)\sqrt{N-1}}{N^2} $$ and so on until you get $$ \sin\frac{5\theta}{2}=\frac{1}{N^2\sqrt{N}}(5N^2-20N+16). $$