# Success probability in Grover's algorithm where there are multiple targets

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

• what formula are you using for the success probabilities here?
– glS
May 27 '19 at 1:50
• 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$ May 27 '19 at 7:53
• 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.
– glS
May 27 '19 at 9:21
• That's right, that's a legitimate objection. Before that, one would actually have to determine the number of iterations to prevent these cases. May 27 '19 at 12:26

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.
• also, if $M\ge N/2$, classical random searching will work just as well so there is no need for Grover's