4
$\begingroup$

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<T<\sqrt{N}-1)$ 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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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 tried to quickly (i.e. not particularly carefully, hence I won't reproduce what I did here) to bound this, and came up with 3/8 rather than the claimed 1/8.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – requiemman
    Oct 25, 2023 at 12:01
  • $\begingroup$ 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. $\endgroup$
    – DaftWullie
    Oct 25, 2023 at 12:43

Your Answer

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

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