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?

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

  • $\begingroup$ Thanks for your Answer! One questiom comes up if I read this, so why is $D_k \leq 4k^2$, where does the factor 4 comes from. I could not explain that. I have seen this factor in Nielsens book too, but there is for me missing why the factor 4 appears there. $\endgroup$
    – P_Gate
    May 27, 2019 at 17:00
  • 1
    $\begingroup$ @P_Gate well it comes from a proof by induction, so I'm not sure how to understand it intuitively. One might try to rederive it without using induction, which would more likely give a direct understanding of the $4$ factor. Anyway, you might try to ask that as a separate question $\endgroup$
    – glS
    May 27, 2019 at 17:07
  • $\begingroup$ Yes, I have seen the proof, in the end there is actually also this 4, the problem is, if I know the end of the proof that is fine and good. But without the end of the proof I would not have personally come to this factor 4 now. $\endgroup$
    – P_Gate
    May 27, 2019 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.