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/0701108

Deutsch's Universal Quantum Turing Machine (Revisited)

Willem L. Fouché, Johannes Heidema, Jones, Glyn, Petrus H. Potgieter

Published Jan 16, 2007• 4 citations
arXivHTMLPDF

Abstract

Deutsch, Feynman, and Manin viewed quantum computing as a kind of universal physical simulation procedure. Much of the writing about quantum Turing machines has shown how these machines can simulate an arbitrary unitary transformation on a finite number of qubits. This interesting problem has been addressed most famously in a paper by Deutsch, and later by Bernstein and Vazirani. Quantum Turing machines form a class closely related to deterministic and probabilistic Turing machines and one might hope to find a universal machine in this class. A universal machine is the basis of a notion of programmability. The extent to which universality has in fact been established by the pioneers in the field is examined and a key notion in theoretical computer science (universality) is scrutinised. In a forthcoming paper, the authors will also consider universality in the quantum gate model.

DOI
10.48550/arxiv.quant-ph/0701108

Related papers

Quantum computation

Sanjeev Arora, Boaz Barak

Turning to quantum mechanics … secret, secret, close the doors! we always have had a great deal of difficulty in understanding the world view that quantum mechanics represents. … It has not yet become obvious to me that there's no real problem. I cannot define the real problem, therefore I suspect there's no real problem, but I'm not sure there's no real problem. So that's why I like to investigate things. – Richard Feynman, 1964 The only difference between a probabilistic classical world and the equations of the quantum world is that somehow or other it appears as if the probabilities would have to go negative. – Richard Feynman, in “Simulating Physics with Computers,” 1982 Our first result is the existence of an efficient universal quantum Turning machine in Deutsch's model. … We give the first formal evidence that quantum Turning machines violate the modern complexity theoretic formulation of the Church Turning thesis. We show the existence of a problem relative to an oracle that can be solved in polynomial time on a quantum Turning machine but require super polynomial time on a bounded error probabilistic Turning machine. – E. Bernstein and U. Vazirani, “Quantum Complexity Theory,” 1997 Quantum computing is a new computational model that may be physically realizable and may provide an exponential advantage over “classical” computational models such as probabilistic and deterministic Turing machines.

Cambridge University Press eBooks•Apr 20, 2009•0 citations

Universality of quantum Turing machines with deterministic control

Paulo Mateus, Amı́lcar Sernadas, André Souto

A simple notion of quantum Turing machine with deterministic, classical control is proposed and shown to be powerful enough to compute any unitary transformation that is computable by a finitely generated quantum circuit. An efficient universal machine with the s-m-n property is presented. The BQP class is recovered. A robust notion of plain Kolmogorov complexity of quantum states is proposed and compared with those previously reported in the literature.

Journal of Logic and Computation•Feb 26, 2015•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

Quantum computers that can be simulated classically in polynomial time

Leslie Gabriel Valiant

A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 \times 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations, and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. In other words it is possible that quantum phenomena can be used in a scalable fashion to make computers but that they do not have superpolynomial speedups compared to Turing machines for any problem. The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent will one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.

ACM Symposium on Theory of Computing (STOC)•Jul 6, 2001•78 citations

An Introduction to Quantum Computing

David K. Ferry

The idea of using quantum mechanics to provide more power than classical computers seem to have begun around 1981 to 1982, but Deutsch put the concept on a sounder footing a short time later. Deutsch reformulated the Turing thesis with the assertion that every finite realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means. However, he asserted that the output of a quantum machine, although fully determined by the input state, is not an observable itself. Progress beyond mathematical approaches came later when Lloyd suggested that arrays of weakly coupled quantum systems might be able to serve as the quantum computer if they were subjected to a sequence of controlled electromagnetic pulses, which could place the quantum bits into the desired super-positions. It was John von Neumann, working with the computer pioneers at the University of Pennsylvania, who suggested that the binary system should be used for simplicity in building computers.

CRC Press eBooks•Nov 6, 2020•15 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
Deutsch, Feynman, and Manin viewed quantum computing as a kind of universal physical simulation procedure. Much of the writing about quantum Turing machines has shown how these machines can simulate an arbitrary unitary transformation on a finite number of qubits. This interesting problem has been addressed most famously in a paper by Deutsch, and later by Bernstein and Vazirani. Quantum Turing machines form a class closely related to deterministic and probabilistic Turing machines and one might hope to find a universal machine in this class. A universal machine is the basis of a notion of programmability. The extent to which universality has in fact been established by the pioneers in the field is examined and a key notion in theoretical computer science (universality) is scrutinised. In a forthcoming paper, the authors will also consider universality in the quantum gate model.
Turning to quantum mechanics … secret, secret, close the doors! we always have had a great deal of difficulty in understanding the world view that quantum mechanics represents. … It has not yet become obvious to me that there's no real problem. I cannot define the real problem, therefore I suspect there's no real problem, but I'm not sure there's no real problem. So that's why I like to investigate things. – Richard Feynman, 1964 The only difference between a probabilistic classical world and the equations of the quantum world is that somehow or other it appears as if the probabilities would have to go negative. – Richard Feynman, in “Simulating Physics with Computers,” 1982 Our first result is the existence of an efficient universal quantum Turning machine in Deutsch's model. … We give the first formal evidence that quantum Turning machines violate the modern complexity theoretic formulation of the Church Turning thesis. We show the existence of a problem relative to an oracle that can be solved in polynomial time on a quantum Turning machine but require super polynomial time on a bounded error probabilistic Turning machine. – E. Bernstein and U. Vazirani, “Quantum Complexity Theory,” 1997 Quantum computing is a new computational model that may be physically realizable and may provide an exponential advantage over “classical” computational models such as probabilistic and deterministic Turing machines.
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.
A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 \times 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations, and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. In other words it is possible that quantum phenomena can be used in a scalable fashion to make computers but that they do not have superpolynomial speedups compared to Turing machines for any problem. The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent will one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.
The idea of using quantum mechanics to provide more power than classical computers seem to have begun around 1981 to 1982, but Deutsch put the concept on a sounder footing a short time later. Deutsch reformulated the Turing thesis with the assertion that every finite realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means. However, he asserted that the output of a quantum machine, although fully determined by the input state, is not an observable itself. Progress beyond mathematical approaches came later when Lloyd suggested that arrays of weakly coupled quantum systems might be able to serve as the quantum computer if they were subjected to a sequence of controlled electromagnetic pulses, which could place the quantum bits into the desired super-positions. It was John von Neumann, working with the computer pioneers at the University of Pennsylvania, who suggested that the binary system should be used for simplicity in building computers.
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.