Grover's Search Number of iterations for M > 1

Question

In Grover's Search algorithm, how to determine the number of iterations for any $M$ such that $1 < M < N/2$?

The calculations given in the Nielsen and Chuang book say that $R \leq \frac{\pi}{4} \sqrt{\left(\frac{N}{M}\right)}$. But suppose that $M = \frac{N}{2} - 1$, then we'll have $R = 1$, but clearly we will need a lot more iterations since after 1st iteration, we will still be very far away from the solution state.

Is there any reference where the number of iterations is calculated for large $M$?

Answer 1

I think Nielsen & Chuang has enough details so that you can work it out by yourself for large $M$.

One thing to mention is that, when $M$ is large, in general it might be hard to amplify the success probability: the reason is that the angle of rotation is too large so that it will always miss the 'north pole'. For example, if $M$ is exactly $N/2$, then you start with the angle $\pi/4$, and each Grover iteration will rotate the state by $\pi/2$. The result is that no matter how many iterations you go through, the probability that you will find a solution by a measurement will be always $1/2$, because your state will be at angles $\pi/4$, $3\pi/4$, $5\pi/4$, $7\pi/4$, and then it will repeat forever.

Another way to look at it: when the half of the basis vectors are solutions, then the relative phase shift will turn half of the phases by $\pi$. Then, the average amplitude would be zero. So when you invert by average, the effect is a global phase shift by $\pi$, which is meaningless. In the next iteration, again half of the states get the relative phase shift of $\pi$, which makes all amplitudes the same, then the inversion by average would do nothing.

So, no progress, no matter how many iterations you go through. Then, the best would be just measure the state to get a solution with probability $1/2$, without doing any Grover iteration, which is exactly the same thing as picking a random element, hoping that it is a solution.

So, in this case, if you want to boost the success probability, you will just have to repeat the process a few more times: when the success probability is $1/2$, when you run the experiment twice, then the success probability becomes $3/4$, and on.

In general, if what you want is to boost the success probability closer to 1, using only Grover iterations, the general answer would be complicated: it depends on whether the angle of rotation is a rational multiple of $\pi$ or not. If it is a rational multiple of $\pi$, then there is an inherent limit how far you can boost the probability using this method, but you can achieve the optimal success probability (which might be as low as $1/2$, according to the previous example). On the other hand, if the angle is an a irrational multiple of $\pi$, then you can achieve success probability arbitrarily close to 1, but the number of iterations to achieve that ... well it must be complicated. :)