4
$\begingroup$

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.

$\endgroup$

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.