I am currently working on the proof of Grover's algorithm, which states that the runtime is optimal.
In Nielsen they say, the idea is to check whether $D_k$ is restricted and does not grow faster than $O(k^2)$. Now in Nielsen, an inductive proof is given which I do not quite understand. The algorithm starts in $|\psi\rangle$ and applies $O_x$ $k$-times, with some unitary operators. We now define: $$O_x=I-2|x\rangle\langle x|$$ $$|\psi_k^x\rangle=U_kO_x...U_1 O_x|\psi\rangle$$ $$|\psi_k\rangle=U_k...U_1|\psi\rangle$$
$D_k$ is defined as a deviation after $k$ steps:
With a proof it should now be shown that $D_k$ is restricted and can not grow fatser than $O(k^2)$. Now we come to the actual problem.
I am interested in the proof of some points:
- Why does it have to be shown that $D_k$ is limited?
- Why must it be shown that $D_k$ does not grow faster than $O(k^2)$? What is the idea behind it?
- In the second proof it is to be assumed that $D_k=\Omega(N)$ holds, why exactly is that important? Which statement is behind it?
If someone needs more information, I have a helpful PDF here. Otherwise, I can also give more information.
I hope that these are not too many questions at once, but I would be glad if someone could give me some clarity.