Grover's algorithm finds the marked item with probability $\ge 1 - 1/N$ within $\lceil\frac{\pi}{4}\sqrt N\rceil$ iterations

Let $N \ge 1$ and let $f\colon\{0,1,\dots,N-1\}\to\{0,1\}$ have exactly one index $\omega$ with $f(\omega) = 1$. Let $U_\omega|x\rangle = (-1)^{f(x)}|x\rangle$ be the oracle, $|s\rangle = \frac{1}{\sqrt N}\sum_x |x\rangle$ the uniform superposition and $U_s = 2|s\rangle\langle s| - I$ the Grover diffusion operator. Then there is a number of iterations $r$ with

That is, Grover's algorithm — prepare $|s\rangle$, apply the Grover iteration $U_sU_\omega$ $r$ times, measure in the computational basis — outputs $\omega$ with probability at least $1 - 1/N$ (in particular at least $1/2$ for $N \ge 2$, and approaching $1$ for $N \gg 1$) using $r = O(\sqrt N)$ applications of $U_\omega$, compared with the $\Theta(N)$ evaluations needed classically.