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

JUCS - Journal of Universal Computer Science

State transition diagrams for a universal quantum gate set

Anuradha Mahasinghe, Ayodhya Liyanage

Published Mar 23, 2026• 0 citations
Publisher

Abstract

A quantum Turing machine (QTM) is an abstract model of computing that serves as the quantum counterpart of a classical Turing machine. Closely related to the probabilistic Turing machine, a QTM utilises quantum effects such as superposition, entanglement and unitary evolution. Despite its historical role as a framework for devising quantum algorithms and the significance of its classical counterpart in theoretical computing, very little attention has been paid in literature to the state transition of QTM’s for basic quantum gates. In this paper, we construct the state transition diagrams for a set of elementary quantum gates that consists of the Hadamard, CNOT, and T gates, providing a universal basis for fault tolerant quantum computation. We verify the necessary conditions to ensure that the designed state transition diagrams comply with the postulates of quantum mechanics, verifying their well formedness.

DOI
10.3897/jucs.156960

Related papers

On Quantum Turing Machine Halting Deterministically

Min Liang, Li Yang

We define a subclass of quantum Turing machine (QTM) named SR-QTM, which halts deterministically and has deterministic tape head position. A quantum state transition diagram (QSTD) is proposed to describe SR-QTM. With the help of QSTD, we construct a SR-QTM which is universal for all near-trivial transformations. This means there exists a QTM which is universal for the above subclass. Finally we prove that SR-QTM is computational equivalent with ordinary QTM in the bounded error setting. It can be seen that, because SR-QTM has the same time steps for different branches of computation, the halting scheme problem will not exist when considering SR-QTM as a model of quantum computing.

arXiv:1202.6530•Feb 29, 2012•0 citations

Partial Observation of Quantum Turing Machines and a Weaker Well-Formedness Condition

Simon Perdrix

The quantum Turing machine (QTM) has been introduced by Deutsch as an abstract model of quantum computation. The transition function of a QTM is linear, and has to be unitary to be a well-formed QTM. This well-formedness condition ensures that the evolution of the machine does not violate the postulates of quantum mechanics. However, we claim in this paper that the well-formedness condition is too strong and we introduce a weaker condition, leading to a larger class of Turing machines called Observable Quantum Turing Machines (OQTMs). We prove that the evolution of such OQTM does not violate the postulates of quantum mechanics while offering a more general abstract model for quantum computing. This novel abstract model unifies classical and quantum computations, since every well-formed QTM and every deterministic TM are OQTMs, whereas a deterministic TM has to be reversible to be a well-formed QTM. In this paper we introduce the fundamentals of OQTM like a well-observed lemma and a completion lemma. The introduction of such an abstract machine allowing classical and quantum computations is motivated by the emergence of models of quantum computation like the one-way model. More generally, the OQTM aims to be an abstract framework for the pragmatic paradigm of quantum computing: quantum data, classical control'. Furthermore, this model allows a formal and rigorous treatment of problems requiring classical interactions, like the halting of QTM. Finally, it opens new perspectives for the construction of a universal QTM.

Electronic Notes in Theoretical Computer Science•Feb 1, 2011•5 citations

On Universal and Fault-Tolerant Quantum Computing

P. Oscar Boykin, Tal Mor, Matthew Pulver +2 more

A novel universal and fault-tolerant basis (set of gates) for quantum computation is described. Such a set is necessary to perform quantum computation in a realistic noisy environment. The new basis consists of two single-qubit gates (Hadamard and ${σ_z}^{1/4}$), and one double-qubit gate (Controlled-NOT). Since the set consisting of Controlled-NOT and Hadamard gates is not universal, the new basis achieves universality by including only one additional elementary (in the sense that it does not include angles that are irrational multiples of $π$) single-qubit gate, and hence, is potentially the simplest universal basis that one can construct. We also provide an alternative proof of universality for the only other known class of universal and fault-tolerant basis proposed by Shor and by Kitaev.

arXiv:quant-ph/9906054•Jun 16, 1999•81 citations

Construction of a universal quantum computer

Antonio A. Lagana, Max A. Lohe, Lorenz von Smekal

We construct a universal quantum computer following Deutsch's original proposal of a universal quantum Turing machine (UQTM). Like Deutsch's UQTM, our machine can emulate any classical Turing machine and can execute any algorithm that can be implemented in the quantum gate array framework but under the control of a quantum program, and hence is universal. We present the architecture of the machine, which consists of a memory tape and a processor and describe the observables that comprise the registers of the processor and the instruction set, which includes a set of operations that can approximate any unitary operation to any desired accuracy and hence is quantum computationally universal. We present the unitary evolution operators that act on the machine to achieve universal computation and discuss each of them in detail and specify and discuss explicit program halting and concatenation schemes. We define and describe a set of primitive programs in order to demonstrate the universal nature of the machine. These primitive programs facilitate the implementation of more complex algorithms and we demonstrate their use by presenting a program that computes the NAND function, thereby also showing that the machine can compute any classically computable function.

Physical Review A•May 18, 2009•9 citations

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•9 citations

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
A quantum Turing machine (QTM) is an abstract model of computing that serves as the quantum counterpart of a classical Turing machine. Closely related to the probabilistic Turing machine, a QTM utilises quantum effects such as superposition, entanglement and unitary evolution. Despite its historical role as a framework for devising quantum algorithms and the significance of its classical counterpart in theoretical computing, very little attention has been paid in literature to the state transition of QTM’s for basic quantum gates. In this paper, we construct the state transition diagrams for a set of elementary quantum gates that consists of the Hadamard, CNOT, and T gates, providing a universal basis for fault tolerant quantum computation. We verify the necessary conditions to ensure that the designed state transition diagrams comply with the postulates of quantum mechanics, verifying their well formedness.
We define a subclass of quantum Turing machine (QTM) named SR-QTM, which halts deterministically and has deterministic tape head position. A quantum state transition diagram (QSTD) is proposed to describe SR-QTM. With the help of QSTD, we construct a SR-QTM which is universal for all near-trivial transformations. This means there exists a QTM which is universal for the above subclass. Finally we prove that SR-QTM is computational equivalent with ordinary QTM in the bounded error setting. It can be seen that, because SR-QTM has the same time steps for different branches of computation, the halting scheme problem will not exist when considering SR-QTM as a model of quantum computing.
The quantum Turing machine (QTM) has been introduced by Deutsch as an abstract model of quantum computation. The transition function of a QTM is linear, and has to be unitary to be a well-formed QTM. This well-formedness condition ensures that the evolution of the machine does not violate the postulates of quantum mechanics. However, we claim in this paper that the well-formedness condition is too strong and we introduce a weaker condition, leading to a larger class of Turing machines called Observable Quantum Turing Machines (OQTMs). We prove that the evolution of such OQTM does not violate the postulates of quantum mechanics while offering a more general abstract model for quantum computing. This novel abstract model unifies classical and quantum computations, since every well-formed QTM and every deterministic TM are OQTMs, whereas a deterministic TM has to be reversible to be a well-formed QTM. In this paper we introduce the fundamentals of OQTM like a well-observed lemma and a completion lemma. The introduction of such an abstract machine allowing classical and quantum computations is motivated by the emergence of models of quantum computation like the one-way model. More generally, the OQTM aims to be an abstract framework for the pragmatic paradigm of quantum computing: quantum data, classical control'. Furthermore, this model allows a formal and rigorous treatment of problems requiring classical interactions, like the halting of QTM. Finally, it opens new perspectives for the construction of a universal QTM.
A novel universal and fault-tolerant basis (set of gates) for quantum computation is described. Such a set is necessary to perform quantum computation in a realistic noisy environment. The new basis consists of two single-qubit gates (Hadamard and σz1/4{σ_z}^{1/4}σz​1/4), and one double-qubit gate (Controlled-NOT). Since the set consisting of Controlled-NOT and Hadamard gates is not universal, the new basis achieves universality by including only one additional elementary (in the sense that it does not include angles that are irrational multiples of πππ) single-qubit gate, and hence, is potentially the simplest universal basis that one can construct. We also provide an alternative proof of universality for the only other known class of universal and fault-tolerant basis proposed by Shor and by Kitaev.
We construct a universal quantum computer following Deutsch's original proposal of a universal quantum Turing machine (UQTM). Like Deutsch's UQTM, our machine can emulate any classical Turing machine and can execute any algorithm that can be implemented in the quantum gate array framework but under the control of a quantum program, and hence is universal. We present the architecture of the machine, which consists of a memory tape and a processor and describe the observables that comprise the registers of the processor and the instruction set, which includes a set of operations that can approximate any unitary operation to any desired accuracy and hence is quantum computationally universal. We present the unitary evolution operators that act on the machine to achieve universal computation and discuss each of them in detail and specify and discuss explicit program halting and concatenation schemes. We define and describe a set of primitive programs in order to demonstrate the universal nature of the machine. These primitive programs facilitate the implementation of more complex algorithms and we demonstrate their use by presenting a program that computes the NAND function, thereby also showing that the machine can compute any classically computable function.
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.