© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

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

Simon Perdrix

Published Jan 1, 2011• 0 citations

Abstract

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.

Related papers

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

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

Halting in quantum Turing computation

Willem L. Fouché, Johannes Heidema, Jones, G. +1 more

The paper considers the halting scheme for quantum Turing machines. The scheme originally proposed by Deutsch appears to be correct, but not exactly as originally intended. We discuss the result of Ozawa as well as the objections raised by Myers, Kieu and Danos and others. Finally, the relationship of the halting scheme to the quest for a universal quantum Turing machine is considered.

arXiv:0705.3077•May 22, 2007•4 citations

On the Halting Problem for Quantum Turing Machines

Masanao Ozawa

Foundations of the theory of quantum Turing machines are investigated.The local transition functions are characterized for fully general quantum Tur- ing machines.Foundational problems on the preparation and the measurement of quantum Turing machines are discussed.The halt scheme, originally proposed by Deutsch, is formulated precisely and is shown to work without spoiling computation.

•Oct 1, 1998•2 citations

Undecidable, Unrecognizable, and Quantum Computing

Michael Siomau

Quantum computing allows us to solve some problems much faster than existing classical algorithms. Yet, the quantum computer has been believed to be no more powerful than the most general computing model—the Turing machine. Undecidable problems, such as the halting problem, and unrecognizable inputs, such as the real numbers, are beyond the theoretical limit of the Turing machine. I suggest a model for a quantum computer, which is less general than the Turing machine, but may solve the halting problem for any task programmable on it. Moreover, inputs unrecognizable by the Turing machine can be recognized by the model, thus breaking the theoretical limit for a computational task. A quantum computer is not just a successful design of the Turing machine as it is widely perceived now, but is a different, less general but more powerful model for computing, the practical realization of which may need different strategies than those in use now.

Quantum Reports•Jul 1, 2020•3 citations

Quantum Nondemolition Monitoring of Universal Quantum Computers

Masanao Ozawa

The halt scheme for quantum Turing machines, originally proposed by Deutsch, is reformulated precisely and is proven to work without spoiling the computation. The ``conflict'' pointed out recently by Myers in the definition of a universal quantum computer is shown to be only apparent. In the context of quantum nondemolition (QND) measurement, it is also shown that the output observable, an observable representing the output of the computation, is a QND observable and that the halt scheme is equivalent to the QND monitoring of the output observable.

arXiv:quant-ph/9704028•Physical Review Letters•Jan 19, 1998•45 citations

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.

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.

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.

Quantum computing allows us to solve some problems much faster than existing classical algorithms. Yet, the quantum computer has been believed to be no more powerful than the most general computing model—the Turing machine. Undecidable problems, such as the halting problem, and unrecognizable inputs, such as the real numbers, are beyond the theoretical limit of the Turing machine. I suggest a model for a quantum computer, which is less general than the Turing machine, but may solve the halting problem for any task programmable on it. Moreover, inputs unrecognizable by the Turing machine can be recognized by the model, thus breaking the theoretical limit for a computational task. A quantum computer is not just a successful design of the Turing machine as it is widely perceived now, but is a different, less general but more powerful model for computing, the practical realization of which may need different strategies than those in use now.

The halt scheme for quantum Turing machines, originally proposed by Deutsch, is reformulated precisely and is proven to work without spoiling the computation. The ``conflict'' pointed out recently by Myers in the definition of a universal quantum computer is shown to be only apparent. In the context of quantum nondemolition (QND) measurement, it is also shown that the output observable, an observable representing the output of the computation, is a QND observable and that the halt scheme is equivalent to the QND monitoring of the output observable.