3
$\begingroup$

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}})$?

$\endgroup$
2
  • $\begingroup$ Did you apply both oracle and diffusion operator? Based on matrix you posted it does not seem so. $\endgroup$ Feb 5, 2023 at 13:30
  • $\begingroup$ The angles you're getting should be $\frac{5\theta}{2}$ not $\frac{3\theta}{2}$. $\endgroup$
    – DaftWullie
    Feb 6, 2023 at 9:42

1 Answer 1

1
$\begingroup$

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). $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.