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:
- 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?