We introduce nebit, a classical bit with a signed probability distribution. We study its properties and basic transformations that can be applied to it. Then, we introduce a simple dynamical model – a classical random walk supplemented with nebits. We show that such a model exhibits some counterintuitive non-classical properties and that it 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. (shrink)