Reflections on probabilistic compared to quantum computational devices

ABSTRACT

In this article, we underline and compare different quantum and deterministic models of computation by means of a probabilistic point of view. The main models used for this are deterministic, probabilistic and quantum Turing machines (DTM, PTM and QTM, respectively). Then we suggest that extending PTM with only part of quantum features is not useful to implement real quantum supremacy if we don’t incorporate them fully. This is done reviewing some notorious quantum physical experiments and quantum algorithms, showing that generally PTM does not fit for them, also if in some particular cases it fits.

Here we compare probabilistic and quantum models of computation to underline some common features and differences.

GRAPHICAL ABSTRACT

KEYWORDS:

• Quantum computing
• Deutsch–Jozsa algorithm
• probabilistic Turing machine
• quantum Turing machine
• quantum simulation

Acknowledgements

We are grateful to Luca Paolini of Università di Torino for his support and encouragement.

Disclosure statement

No potential conflict of interest was reported by the author(s).