Proof of the optimality of Grover's algorithm

Question

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:

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

Answer 1

The point is that, for a search algorithm to be fulfilling its purpose, you want $\lvert\langle\psi_k^x\rvert x\rangle\rvert^2>1/2$. Note that here $\lvert \psi_k^x\rangle$ is the output of the algorithm after $k$ steps if we are using the oracle to mark the $\lvert x\rangle$ state. If this condition is not verified, then by definition the algorithm is not giving as output the state we asked it to find.

What one can do then is to show that, if $\lvert\langle\psi_k^x\rvert x\rangle\rvert^2>1/2$ holds for all $x$, then $D_k=\Omega(N)$, meaning that there is some positive $c$ such that, for large enough $N$, $D_k\ge cN$. Intuitively, this is saying that a high probability of success means that the algorithm must be moving $\lvert\psi\rangle$ towards different states, and therefore $D_k$, which quantifies how much $\lvert\psi\rangle$ is moved by the algorithm, must be lower bounded.

On the other hand, one can also prove that $D_k=O(k^2)$, and more specifically that $D_k\le4k^2$, simply using the definitions of $\lvert\psi_k\rangle$ and $\lvert\psi_k^x\rangle$.

We then conclude that, if the algorithm is successfully retrieving the requested states, we must have $cN\le D_k\le 4k^2$, and thus $$k\ge\sqrt{cN/4}.$$ This means that the sole assumption that the algorithm is working leads to the conclusion that the oracle must be used $\Omega(\sqrt N)$ times.