4
$\begingroup$

The Grover algorithm allows you to search for multiple elements. Assuming my search space contains four elements, if I only search for one element, I get the one I'm looking for with a probability of 100%. So far so good.

Assuming I search for two elements within the four elements, then the probability is only found at 50% of the searched element. It gets even more interesting. Suppose I search exactly three within the four elements, then the probability increases to measure a state that does not correspond to the solution state.

So my question is, how does one behave in such a situation? and is it possible to recognize these situations in advance? Are there any other problems that can occur when searching for multiple items?


Calculations (success probabilities):

$M$ is the number of searched elements, $N$ is the size of the search space. $$M=1, N =4$$ $$\sin^2\left((2\cdot 1 + 1)\cdot\sin^{-1}\left(\sqrt{\frac{1}{4}}\right)\right)=1$$

$$M=2, N =4$$ $$\sin^2\left((2\cdot 1 + 1)\cdot\sin^{-1}\left(\sqrt{\frac{2}{4}}\right)\right)=\frac{1}{2}$$

$$M=3, N =4$$ $$\sin^2\left((2\cdot 1 + 1)\cdot\sin^{-1}\left(\sqrt{\frac{3}{4}}\right)=\frac{1}{2}\right)=0$$

$\endgroup$
  • $\begingroup$ what formula are you using for the success probabilities here? $\endgroup$ – glS May 27 at 1:50
  • $\begingroup$ I took advantage of the fact that one can interpret the Grover algorithm geometrically, so that one comes to this formula for $k$ iteration steps: $|\psi\rangle=\frac{1}{\sqrt{N}}\sum|x\rangle=\cos((2k+1)\theta)|\alpha\rangle+\sin((2k+1)\theta)|\beta\rangle$ $\endgroup$ – P_Gate May 27 at 7:53
  • $\begingroup$ well ok but you should also take into account the optimal number of steps to know when to stop. Using that, for $M\ge N/2$ I suspect you would just get that the optimal number of steps is $k=0$, meaning that Grover iteration actually bring you further away from the target. Note that the same thing happen if there is a single target but the initial overlap with it is large enough. $\endgroup$ – glS May 27 at 9:21
  • $\begingroup$ That's right, that's a legitimate objection. Before that, one would actually have to determine the number of iterations to prevent these cases. $\endgroup$ – P_Gate May 27 at 12:26
3
$\begingroup$

Indeed, applying Grover in the case $ M \ge N / 2 $ will show this issue. Yet you can use a simple trick to overcome this. You just have to increase the search space by adding N new elements which you won't consider solutions. You end up doing more iterations but you will still get a quadratic speedup.

One way to recognize these situatons in advance is either you just are not getting better during your search or you just use quantum counting to get the number of solutions $M$ before doing the search.

Last question : no other problems.

$\endgroup$
  • 1
    $\begingroup$ also, if $M\ge N/2$, classical random searching will work just as well so there is no need for Grover's $\endgroup$ – glS May 27 at 9:17
  • $\begingroup$ Yes @glS thanks for adding this in comment. $\endgroup$ – cnada May 27 at 11:11

Your Answer

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

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