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

It can be proved that $D_k$ is upper bounded by $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?

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.