An Observer-Based De-Quantisation of Deutsch’s Algorithm

Cristian S. Calude, Matteo Cavaliere, Radu Mardare

Research output: Contribution to journalArticlepeer-review


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”.
Original languageEnglish
Pages (from-to)191-201
Number of pages11
JournalInternational Journal of Foundations of Computer Science
Issue number01
Publication statusPublished - 2011


Dive into the research topics of 'An Observer-Based De-Quantisation of Deutsch’s Algorithm'. Together they form a unique fingerprint.

Cite this