Sub-optimal number of iterations in Grover's algorithm tutorial

[jhwatrous]

In the tutorial Grover's algorithm using the Sampler primitive the number of iterations claimed to be optimal for Grover's algorithm is this number:

$$ \left\lfloor \frac{\pi}{4} \sqrt{\frac{N}{s}} \right\rfloor $$

where $N = 2^n$ and $s$ is the number of marked items.

This number is usually optimal but not always — the number should be this:

$$ \left\lfloor \frac{\pi}{4 \sin^{-1}\left(\sqrt{s/N}\right)} \right\rfloor $$

For example, if there are $n=7$ bits (so $N=2^7 = 128$) and there are $s = 19$ marked items, then the two expressions give a number of iterations that differ by one, and the second number of iterations (which is optimal) succeeds with a probability slightly larger than the first: about 85.9% versus 84.3%.

Suggested solutions

Use the second formula.