# Proof of the optimality of Grover's algorithm

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_1O_1|\psi\rangle$$ $$|\psi_k\rangle=U_k...U_1|\psi\rangle$$

$$D_k$$ is defined as a deviation after $$k$$ steps:

$$D_{k}=\sum_x |||\psi_k^x\rangle-|\psi_k\rangle||^2$$

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:

1. Why does it have to be shown that $$D_k$$ is limited?
2. Why must it be shown that $$D_k$$ does not grow faster than $$O(k^2)$$? What is the idea behind it?
3. In the second proof it is to be assumed that $$D_k\Omega(N)$$ holds, why is that exactly 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.