Grover's algorithm on probabilistic classical machines
Let $F$ be a function that maps integers from $0 \dots N-1$ to $\{0, 1\}$. We want to find $x$ (which is promised to be unique) such that:

$$F(x) = 1$$

Now let's take two random integers $a$ and $b$ from $0 \dots N-1$ and output:


$b$, if $F(a) = 0$
$a$, if $F(a) = 1$


For any fixed $x$ and $y$ we have:

$$P_{a=x} = P_{b=x} = P_{a=y} = P_{b=y} = \frac{1}{N}\\
P_{a \ne x} = P_{b \ne x} = P_{a \ne y} = P_{b \ne y} = \frac{N-1}{N}$$

Knowing that $a$ and $b$ are independent random variables, the probability that we output $x$ is

$$P_{a = x \lor a \ne x \land b = x} =
P_{a = x} + P_{a \ne x} P_{b = x} =
\frac{1}{N} + \frac{N - 1}{N^2}$$

and the probability that we output some other value $y \ne x$ is

$$P_{a \ne x \land b = y} = P_{a \ne x} P_{b = y} =
\frac{N - 1}{N^2} &lt; \frac{1}{N}$$