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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.