Faculty of Physics, Adam Mickiewicz University in Pozńan, Poland, pawel.kurzynski@amu.edu.pl
(joint work with Dagomir Kaszlikowski)
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.