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 algorithmclassical solutions which are as efficient as the quantum onehave 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". © 2011 World Scientific Publishing Company.
An observer-based de-quantisation of Deutsch's algorithm / Calude, C. S.; Cavaliere, M.; Mardare, R.. - In: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - ISSN 0129-0541. - 22:1(2011), pp. 191-201. [10.1142/S0129054111007940]
An observer-based de-quantisation of Deutsch's algorithm
Cavaliere M.;
2011
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 algorithmclassical solutions which are as efficient as the quantum onehave 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". © 2011 World Scientific Publishing Company.File | Dimensione | Formato | |
---|---|---|---|
Calude_Cavaliere_ET_AL_2011_An_Observer_Based_De_Quantisation_of_Deutschs_Algorithim.pdf
Open access
Tipologia:
Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione
1.99 MB
Formato
Adobe PDF
|
1.99 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris