Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2101.02203 · Journal of quantum computing

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

Giuseppe Corrente

Published Jan 1, 2020• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.32604/jqc.2020.014586

Related papers

Quantum Turing Machines: Computations and Measurements

Stefano Guerrini, Simone Martini, Andrea Masini

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.

arXiv:1703.07748•Applied Sciences•Aug 11, 2020•11 citations

Quantum Algorithms, Paraconsistent Computation and Deutsch's Problem.

Juan C. Agudelo, Walter Alexandre Carnielli

We present the new model of paraconsistent Turing machines and revise the models of quantum Turing machines and quantum circuits, stressing the concepts of entangled states and quantum parallelism which are important features for efficient quantum algorithms. We revise a quantum circuit that solves the so-called Deutsch’s problem, and then provide another solution to Deutsch’s problem by means of paraconsistent Turing machines. This raises some stimulating questions, and we close the paper by discussing some relationships between paraconsistent Turing machines and quantum Turing machines.

Indian International Conference on Artificial Intelligence•Jan 1, 2005•5 citations

Quantum Algorithms, Paraconsistent Computation and Deutsch's Problem

We present the new model of paraconsistent Turing machines and revise the models of quantum Turing machines and quantum circuits, stressing the concepts of entangled states and quantum parallelism which are important features for efficient quantum algorithms. We revise a quantum circuit that solves the so-called Deutsch's problem, and then provide another solution to Deutsch's problem by means of paraconsistent Turing machines. This raises some stimulating questions, and we close the paper by discussing some relationships between paraconsistent Turing machines and quantum Turing machines.

CLE e-Prints•Dec 10, 2005•0 citations

Comparison of state assignment methods for “quantum circuit” model of permutative quantum state machines

Manjith Kumar, Samy Boshra-riad, Yasodha Nachimuthu +1 more

The design of state machines for quantum algorithms remains a largely unexplored topic. The abstract models for quantum computation proposed by Feynman [1], Deutsch [2] etc have been related to the theory of Quantum Turing Machines (QTM) and the work was later expanded by Bernstein and Vazirani [3] to lay the foundations of quantum complexity theory. However, no papers deal with the following problem: “how to realize the quantum state machine in hardware as an operational quantum circuit that the internal states of which can be measured and used as inputs in a system of such machines”. This is an equivalent to the fundamental problem of “structural synthesis of FSM”. This paper creates models of quantum state machines that are useful from an engineering perspective. The objective of the paper is to propose models that can be used for circuit-level implementation. We restrict our study to binary logic realized in quantum, the so-called binary permutative quantum circuits; the “permutative machines”. The presented synthesis procedure is analogous to classical logic circuits synthesis and is a necessary step in the entire design procedure of quantum automata. Thus state minimization, state assignment and excitation function realization aspects are also of interest and some preliminary experimental results are presented.

IEEE Congress on Evolutionary Computation (CEC)•Jul 1, 2010•6 citations

An Introduction to Quantum Complexity Theory

Tetsuro Nishino

In 1985, D. Deutsch introduced quantum Turing machines (QTMs for short) as Turing machines which can perform so called quantum parallel computations. Then, in 1994, P. Shor showed that QTM can factor integers with arbitrary small error probability in polynomial time. The quantum complexity theory is the computational complexity theory based on QTMs. In this paper, we first review the definitions of the QTM and major quantum complexity classes EQP, BQP, ZQP, etc. Then, we present the known results and major open questions in this field.

物性研究•Jun 20, 1999•4 citations

Quantum computing and quantum complexity theory

Umesh V. Vazirani

There is strong evidence that computers based upon the principles of quantum physics represent an inherently new and more powerful model of computation. Such computers violate the modern form of the Church-Turing thesis (which lies at the foundations of computer science). This thesis can be informally summarized as follows: all physical implementations of computing devices can be described by the same abstract model of computation-the probabilistic Turing Machine or the equivalent random access machine. In this paper, we will describe two formal models for quantum computers: quantum circuits and quantum Turing Machines, introduced by Deutsch [1985].

IEEE International Symposium on Circuits and Systems proceedings•Jan 1, 2000•0 citations
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.
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 present the new model of paraconsistent Turing machines and revise the models of quantum Turing machines and quantum circuits, stressing the concepts of entangled states and quantum parallelism which are important features for efficient quantum algorithms. We revise a quantum circuit that solves the so-called Deutsch’s problem, and then provide another solution to Deutsch’s problem by means of paraconsistent Turing machines. This raises some stimulating questions, and we close the paper by discussing some relationships between paraconsistent Turing machines and quantum Turing machines.
We present the new model of paraconsistent Turing machines and revise the models of quantum Turing machines and quantum circuits, stressing the concepts of entangled states and quantum parallelism which are important features for efficient quantum algorithms. We revise a quantum circuit that solves the so-called Deutsch's problem, and then provide another solution to Deutsch's problem by means of paraconsistent Turing machines. This raises some stimulating questions, and we close the paper by discussing some relationships between paraconsistent Turing machines and quantum Turing machines.
The design of state machines for quantum algorithms remains a largely unexplored topic. The abstract models for quantum computation proposed by Feynman [1], Deutsch [2] etc have been related to the theory of Quantum Turing Machines (QTM) and the work was later expanded by Bernstein and Vazirani [3] to lay the foundations of quantum complexity theory. However, no papers deal with the following problem: “how to realize the quantum state machine in hardware as an operational quantum circuit that the internal states of which can be measured and used as inputs in a system of such machines”. This is an equivalent to the fundamental problem of “structural synthesis of FSM”. This paper creates models of quantum state machines that are useful from an engineering perspective. The objective of the paper is to propose models that can be used for circuit-level implementation. We restrict our study to binary logic realized in quantum, the so-called binary permutative quantum circuits; the “permutative machines”. The presented synthesis procedure is analogous to classical logic circuits synthesis and is a necessary step in the entire design procedure of quantum automata. Thus state minimization, state assignment and excitation function realization aspects are also of interest and some preliminary experimental results are presented.
In 1985, D. Deutsch introduced quantum Turing machines (QTMs for short) as Turing machines which can perform so called quantum parallel computations. Then, in 1994, P. Shor showed that QTM can factor integers with arbitrary small error probability in polynomial time. The quantum complexity theory is the computational complexity theory based on QTMs. In this paper, we first review the definitions of the QTM and major quantum complexity classes EQP, BQP, ZQP, etc. Then, we present the known results and major open questions in this field.
There is strong evidence that computers based upon the principles of quantum physics represent an inherently new and more powerful model of computation. Such computers violate the modern form of the Church-Turing thesis (which lies at the foundations of computer science). This thesis can be informally summarized as follows: all physical implementations of computing devices can be described by the same abstract model of computation-the probabilistic Turing Machine or the equivalent random access machine. In this paper, we will describe two formal models for quantum computers: quantum circuits and quantum Turing Machines, introduced by Deutsch [1985].