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:quant-ph/9704028 · Physical Review Letters

Quantum Nondemolition Monitoring of Universal Quantum Computers

Masanao Ozawa

Published Jan 19, 1998• 45 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.80.631

Related papers

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

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

Toward a Universal Quantum Computer

Yu Shi

Given the existence of a universal quantum Turing machine, there is no conflict in the definition of a universal quantum computer between being universal and the need for a halt qubit, as previously claimed. It is also pointed out that there exists a universal, i.e. programmable, quantum circuit which can perform an arbitrary quantum computation, by repeating the operation of a fixed gate array.

•Aug 24, 1999•0 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
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.
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.
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.