5
$\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$$

Improve this question
$\endgroup$
4
  • $\begingroup$ what formula are you using for the success probabilities here? $\endgroup$
    – glS ♦
    May 27, 2019 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, 2019 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, 2019 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, 2019 at 12:26

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 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, 2019 at 9:17
  • $\begingroup$ Yes @glS thanks for adding this in comment. $\endgroup$
    – cnada
    May 27, 2019 at 11:11

Your Answer

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

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