An observer-based de-quantisation of Deutsch's algorithm

Deutsch’s problem is the simplest and most frequently examined example of computational problem used to demonstrate the superiority of quantum computing over classical computing. Deutsch’s quantum algorithm has been claimed to be faster than any classical ones solving the same problem, only to be discovered later that this was not the case. Various de-quantised solutions for Deutsch’s quantum algorithm—classical solutions which are as efficient as the quantum one—have been proposed in the literature. These solutions are based on the possibility of classically simulating “superpositions”, a key ingredient of quantum algorithms, in particular, Deutsch’s algorithm. The de-quantisation proposed in this note is based on a classical simulation of the quantum measurement achieved with a model of observed system. As in some previous de-quantisations of Deutsch’s quantum algorithm, the resulting de-quantised algorithm is deterministic. Finally, we classify observers (as finite state automata) that can solve the problem in terms of their “observational power”.