  We introduce nebit, a classical bit with a signed probability distribution.
We quantify its entropy using Szekely theorem on signed probability measures
and show that classical stochastic dynamics supplemented with nebits can
achieve or even exceed the speedup of Grover's quantum search algorithm. The
proposed classical dynamics never reveals negativity of nebits and thus we do
not need any operational interpretation of negative probabilities. We argue
that nebits can be useful as a measure of non-classicality as well as a tool to
find new quantum algorithms.
