# Minimum probability of measuring marked state in Grover's algorithm is 1/8

I recently came across the proposition that for a database containing $$N$$ elements with $$m<\sqrt{N}$$ marked elements, applying Grover's algorithm with any $$T$$ $$(0 iterations (that is, $$T$$ is uniformly chosen from $$0$$ to $$\sqrt N-1$$) would give you a marked state with probability of at least $$\frac{1}{8}$$.

However I don't quite understand how to prove this. I know that, given $$m$$ marked elements in $$N$$ total elements, the probability that you would measure a marked state at the $$T^{th}$$ iteration is $$\sin ^2\bigg((T+1/2)\sqrt\frac{m}{N}\bigg)$$

Suppose you have $$T=1$$. Then you get the probability as $$\sin^2\bigg(1.5\sqrt\frac{m}{N}\bigg)$$, and since you have $$\min(m)=1$$, as $$N$$ increases indefinitely, you can make the value of this function as close to 0 as you want.

Is there something I'm missing?

I suspect you're misinterpreting the statement a little. The claim will not be that for every possible value of $$T$$ the probability is at least 1/8. Instead, the success probability, averaged across all possible values of $$T$$, is at least 1/8. This means that you're trying to assess something like $$\frac{1}{\sqrt{N}-2}\sum_{T=1}^{\sqrt{N}-2}\sin^2((2T+1)\theta)$$ where $$\sin\theta=\sqrt{\frac{M}{N}}$$. So, sure, there are some small terms in that sum, but there are also some large terms, and they balance out.
• I actually got to a stage where I have an expression of the form $\frac{1}{2}-\frac{sin(4\sqrt{N} \theta)}{4\sqrt{N} sin(2\theta)}$ so having the second term there be $\frac{3}{8}$ would get me a solution (using Lemma 2, section 4 of Boyer's paper: arxiv.org/abs/quant-ph/9605034) so would you mind giving me some pointers? Commented Oct 25, 2023 at 12:01
• That looks like where I got to. I said that $\sin(4\sqrt{N}\theta)\leq 1$, and you can substitute $\sin(2\theta)=2\sqrt{M(N-M)}/N$. This is smallest for $M=1$, which leaves the second term being 1/8, I think, so the overall conclusion seems to be a bound of 3/8. Commented Oct 25, 2023 at 12:43