Abstract:
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”.
