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

Electronic Notes in Theoretical Computer Science

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

Simon Perdrix

Published Feb 1, 2011• 5 citations
Publisher

Abstract

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.

DOI
10.1016/j.entcs.2011.01.009

Related papers

Partial observation of quantum Turing machine and weaker well-formedness condition

Simon Perdrix

Abstract. 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. How-ever, we claim in this paper that the well-formedness condition is too strong and we intro-duce 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 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’. Further-more, 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 construc-tion of a universal QTM. 1

•Jan 1, 2008•0 citations

Towards Observable Quantum Turing Machines: Fundamentals, Computational Power, and Universality

Simon Perdrix

We study the observation of quantum Turing machines by allowing interactions between a quantum machine and its environment during the computation, whereas a quantum Turing machine --original model introduced by Deutsch-- remains isolated. We show that the introduction of observations leads to a weakening of the well formedness conditions of quantum Turing machines such that any (reversible or not) classical Turing machine is a special instance of a quantum machine. Moreover, observation of quantum Turing machines provides a formal solution to the halting process problem: the impossibility to know whether a given quantum Turing machine has actually reached its halting state. It also provides a more realistic abstract architecture of a quantum computer while most of the physical proposals of quantum computers are based on an hybrid classical-quantum architecture. However, we show that a natural formalisation of an observable quantum Turing machines leads to an over-powerful model solving undecidable problems. As a consequence, we introduce a restricted version of observable quantum Turing machines and we show that, under this restriction, any observable quantum Turing machine can be efficiently simulated by a quantum Turing machine. Finally, we discuss the potential application of the observable quantum Turing machine in the quest of a universal quantum Turing machine while recent papers have pointed out that a classical control is a key feature of a universal quantum machine.

•Jan 1, 2011•0 citations

Quantum complexity theory

Ethan Bernstein, Umesh V. Vazirani

Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1993•1,413 citations

State transition diagrams for a universal quantum gate set

Anuradha Mahasinghe, Ayodhya Liyanage

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.

JUCS - Journal of Universal Computer Science•Mar 23, 2026•0 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•11 citations

Quantum Complexity Theory

Ethan Bernstein, Umesh V. Vazirani

In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that $O(\log T)$ bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.

SIAM Journal on Computing•Oct 1, 1997•1,635 citations
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.
Abstract. 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. How-ever, we claim in this paper that the well-formedness condition is too strong and we intro-duce 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 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’. Further-more, 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 construc-tion of a universal QTM. 1
We study the observation of quantum Turing machines by allowing interactions between a quantum machine and its environment during the computation, whereas a quantum Turing machine --original model introduced by Deutsch-- remains isolated. We show that the introduction of observations leads to a weakening of the well formedness conditions of quantum Turing machines such that any (reversible or not) classical Turing machine is a special instance of a quantum machine. Moreover, observation of quantum Turing machines provides a formal solution to the halting process problem: the impossibility to know whether a given quantum Turing machine has actually reached its halting state. It also provides a more realistic abstract architecture of a quantum computer while most of the physical proposals of quantum computers are based on an hybrid classical-quantum architecture. However, we show that a natural formalisation of an observable quantum Turing machines leads to an over-powerful model solving undecidable problems. As a consequence, we introduce a restricted version of observable quantum Turing machines and we show that, under this restriction, any observable quantum Turing machine can be efficiently simulated by a quantum Turing machine. Finally, we discuss the potential application of the observable quantum Turing machine in the quest of a universal quantum Turing machine while recent papers have pointed out that a classical control is a key feature of a universal quantum machine.
Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
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.
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.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that O(log⁡T)O(\log T)O(logT) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.