© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1703.07748 · Applied Sciences

Quantum Turing Machines: Computations and Measurements

Stefano Guerrini, Simone Martini, Andrea Masini

Published Aug 11, 2020• 9 citations

Abstract

Contrary to the classical case, the relation between quantum programming languages and quantum Turing Machines (QTM) has not been fully investigated. In particular, there are features of QTMs that have not been exploited, a notable example being the intrinsic infinite nature of any quantum computation. In this paper, we propose a definition of QTM, which extends and unifies the notions of Deutsch and Bernstein & Vazirani. In particular, we allow both arbitrary quantum input, and meaningful superpositions of computations, where some of them are “terminated” with an “output”, while others are not. For some infinite computations an “output” is obtained as a limit of finite portions of the computation. We propose a natural and robust observation protocol for our QTMs, which does not modify the probability of the possible outcomes of the machines. Finally, we use QTMs to define a class of quantum computable functions—any such function is a mapping from a general quantum state to a probability distribution of natural numbers. We expect that our class of functions, when restricted to classical input-output, will not be different from the set of the recursive functions.

DOI: 10.3390/app10165551

Related papers

Towards A Theory Of Quantum Computability

Stefano Guerrini, Simone Martini, Andrea Masini

We propose a definition of quantum computable functions as mappings between superpositions of natural numbers to probability distributions of natural numbers. Each function is obtained as a limit of an infinite computation of a quantum Turing machine. The class of quantum computable functions is recursively enumerable, thus opening the door to a quantum computability theory which may follow some of the classical developments.

arXiv:1504.02817•Apr 10, 2015•1 citation

Translation of Quantum Circuits into Quantum Turing Machines for Deutsch and Deutsch-Jozsa Problems

Giuseppe Corrente

We want in this article to show the usefulness of Quantum Turing Machine (QTM) in a high-level didactic context as well as in theoretical studies. We use QTM to show its equivalence with quantum circuit model for Deutsch and Deutsch-Jozsa algorithms. Further we introduce a strategy of translation from Quantum Circuit to Quantum Turing models by these examples. Moreover we illustrate some features of Quantum Computing such as superposition from a QTM point of view and starting with few simple examples very known in Quantum Circuit form.

arXiv:2101.02203•Journal of quantum computing•Jan 1, 2020•2 citations

Reflections on probabilistic compared to quantum computational devices

Giuseppe Corrente

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.

International Journal of Parallel Emergent and Distributed Systems•Aug 11, 2020•2 citations

Turing Machine Simulations: Classic and Quantum

Hafsa Yazdani, Fatemah Al Zayer, Naya Nagy +1 more

The simulation software presented in this paper visualizes abstract machines and concepts.It simulates five different Turing machine (TM) types of two categories: classical Turing machines and quantum Turing machines.The quantum Turing machines implement superposition bothfor the tape cells and for the state of the read/write head.Studentsprogramming our TMs get hands-on experience of naturally non-intuitive quantum theory concepts: superposition, quantum measurement,state collapse.Additionally, the quantum head TM described in this paper is the first TM definition that implements John Deutsch's multiverse theory.To the best of our knowledge, our program is the firstthat gives users the experience of programming their own multiverses.

International Journal of Computer and Electrical Engineering•Oct 22, 2013•0 citations

A Mathematical Model of Quantum Computer by Both Arithmetic and Set Theory

Vasil Dinev Penchev

A practical viewpoint links reality, representation, and language to calculation by the concept of Turing (1936) machine being the mathematical model of our computers. After the Gödel incompleteness theorems (1931) or the insolvability of the so-called halting problem (Turing 1936; Church 1936) as to a classical machine of Turing, one of the simplest hypotheses is completeness to be suggested for two ones. That is consistent with the provability of completeness by means of two independent Peano arithmetics discussed in Section I.Many modifications of Turing machines cum quantum ones are researched in Section II for the Halting problem and completeness, and the model of two independent Turing machines seems to generalize them.Then, that pair can be postulated as the formal definition of reality therefore being complete unlike any of them standalone, remaining incomplete without its complementary counterpart. Representation is formal defined as a one-to-one mapping between the two Turing machines, and the set of all those mappings can be considered as “language” therefore including metaphors as mappings different than representation. Section III investigates that formal relation of “reality”, “representation”, and “language” modeled by (at least two) Turing machines.The independence of (two) Turing machines is interpreted by means of game theory and especially of the Nash equilibrium in Section IV.Choice and information as the quantity of choices are involved. That approach seems to be equivalent to that based on set theory and the concept of actual infinity in mathematics and allowing of practical implementations.

•Jan 1, 2020•2 citations

The computing power of Turing machine based on quantum logic

Yun Shang, Xian Ping Lu, Ruqian Lu

Turing machines based on quantum logic can solve undecidable problems. In this paper we will give recursion-theoretical characterization of the computational power of this kind of quantum Turing machines. In detail, for the unsharp case, it is proved that Σ01 ∪Π01⊆ LTd(ε,Σ)(LTw(ε,Σ))⊆Π02 when the truth value lattice is locally finite and the operation ∧ is computable, where LTd(ε,Σ)(LTw(ε,Σ))denotes the class of quantum language accepted by these Turing machine in depth-first model (respectively, width-first model); for the sharp case, we can obtain similar results for usual orthomodular lattices.

EPiC series in computing•Jan 23, 2018•0 citations

Contrary to the classical case, the relation between quantum programming languages and quantum Turing Machines (QTM) has not been fully investigated. In particular, there are features of QTMs that have not been exploited, a notable example being the intrinsic infinite nature of any quantum computation. In this paper, we propose a definition of QTM, which extends and unifies the notions of Deutsch and Bernstein & Vazirani. In particular, we allow both arbitrary quantum input, and meaningful superpositions of computations, where some of them are “terminated” with an “output”, while others are not. For some infinite computations an “output” is obtained as a limit of finite portions of the computation. We propose a natural and robust observation protocol for our QTMs, which does not modify the probability of the possible outcomes of the machines. Finally, we use QTMs to define a class of quantum computable functions—any such function is a mapping from a general quantum state to a probability distribution of natural numbers. We expect that our class of functions, when restricted to classical input-output, will not be different from the set of the recursive functions.

We want in this article to show the usefulness of Quantum Turing Machine (QTM) in a high-level didactic context as well as in theoretical studies. We use QTM to show its equivalence with quantum circuit model for Deutsch and Deutsch-Jozsa algorithms. Further we introduce a strategy of translation from Quantum Circuit to Quantum Turing models by these examples. Moreover we illustrate some features of Quantum Computing such as superposition from a QTM point of view and starting with few simple examples very known in Quantum Circuit form.

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.

The simulation software presented in this paper visualizes abstract machines and concepts.It simulates five different Turing machine (TM) types of two categories: classical Turing machines and quantum Turing machines.The quantum Turing machines implement superposition bothfor the tape cells and for the state of the read/write head.Studentsprogramming our TMs get hands-on experience of naturally non-intuitive quantum theory concepts: superposition, quantum measurement,state collapse.Additionally, the quantum head TM described in this paper is the first TM definition that implements John Deutsch's multiverse theory.To the best of our knowledge, our program is the firstthat gives users the experience of programming their own multiverses.

A practical viewpoint links reality, representation, and language to calculation by the concept of Turing (1936) machine being the mathematical model of our computers. After the Gödel incompleteness theorems (1931) or the insolvability of the so-called halting problem (Turing 1936; Church 1936) as to a classical machine of Turing, one of the simplest hypotheses is completeness to be suggested for two ones. That is consistent with the provability of completeness by means of two independent Peano arithmetics discussed in Section I.Many modifications of Turing machines cum quantum ones are researched in Section II for the Halting problem and completeness, and the model of two independent Turing machines seems to generalize them.Then, that pair can be postulated as the formal definition of reality therefore being complete unlike any of them standalone, remaining incomplete without its complementary counterpart. Representation is formal defined as a one-to-one mapping between the two Turing machines, and the set of all those mappings can be considered as “language” therefore including metaphors as mappings different than representation. Section III investigates that formal relation of “reality”, “representation”, and “language” modeled by (at least two) Turing machines.The independence of (two) Turing machines is interpreted by means of game theory and especially of the Nash equilibrium in Section IV.Choice and information as the quantity of choices are involved. That approach seems to be equivalent to that based on set theory and the concept of actual infinity in mathematics and allowing of practical implementations.

Turing machines based on quantum logic can solve undecidable problems. In this paper we will give recursion-theoretical characterization of the computational power of this kind of quantum Turing machines. In detail, for the unsharp case, it is proved that Σ01 ∪Π01⊆ LTd(ε,Σ)(LTw(ε,Σ))⊆Π02 when the truth value lattice is locally finite and the operation ∧ is computable, where LTd(ε,Σ)(LTw(ε,Σ))denotes the class of quantum language accepted by these Turing machine in depth-first model (respectively, width-first model); for the sharp case, we can obtain similar results for usual orthomodular lattices.