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

Physical Review Letters

Quantum Mechanical Models of Turing Machines That Dissipate No Energy

Paul A. Benioff

Published Jun 7, 1982• 296 citations
Publisher

Abstract

Quantum mechanical Hamiltonian models of Turing machines are constructed here on a finite lattice of spin-\textonehalf{} systems. The models do not dissipate any energy and they operate at the quantum limit in that the system (energy uncertainty)/(computation speed) is close to the limit given by the time-energy uncertainty principle.
DOI
10.1103/physrevlett.48.1581

Related papers

Models of Quantum Computers and Decoherence Problem

I. V. Volovich

Mathematical models of quantum computers such as a multidimensional quantum Turing machine and quantum circuits are described and its relations with lattice spin models are discussed. One of the main open problems one has to solve if one wants to build a quantum computer is the decoherence due to the coupling with the environment. We propose a possible solution of this problem by using a control of parameters of the system. This proposal is based on the analysis of the spin-boson Hamiltonian performed in the stochastic limit approximation.

arXiv:quant-ph/9902055•Feb 15, 1999•6 citations

Unitary dilation models of Turing machines in quantum mechanics

Paul A. Benioff

A goal of quantum-mechanical models of the computation process is the description of operators that model changes in the information-bearing degrees of freedom. Iteration of the operators should correspond to steps in the computation, and the final state of halting computations should be stable under iteration. The problem is that operators constructed directly from the process description do not have these properties. In general these operators annihilate the halted state. If information-erasing steps are present, there are additional problems. These problems are illustrated in this paper by consideration of operators for two simple one-step processes and two simple Turing machines. In general the operators are not unitary and, if erasing steps are present, they are not even contraction operators. Various methods of extension or dilation to unitary operators are discussed. Here unitary power dilations are considered as a solution to these problems. It is seen that these dilations automatically provide a good solution to the initial- and final-state problems. For processes with erasing steps, recording steps must be included prior to the dilation, but only for the steps that erase information. Hamiltonians for these processes are also discussed. It is noted that H, described by exp(-iH\ensuremath{\Delta})=${\mathit{U}}^{\mathit{T}}$, where ${\mathit{U}}^{\mathit{T}}$ is a unitary step operator for the process and \ensuremath{\Delta} a time interval, has complexity problems. These problems and those noted above are avoided here by the use of the Feynman approach to constructing Hamiltonians directly from the unitary power dilations of the model operators. It is seen that the Hamiltonians so constructed have some interesting properties.

Physical Review A•May 1, 1995•2 citations

Quantum mechanical computation

James D. Brasher

The physics and the mathematics of computation are examined to provide a foundation and perspective for the investigation of the quantum mechanics of computation. Our purpose is to explore the fundamental limits and constraints imposed on computation by Nature through the laws of physics and the mathematics of computational complexity. Inasmuch as information storage and transmission are an integral part of computation, their physical bounds are considered. The computer is viewed both physically and mathematically as a dynamical system, and is depicted in terms of the basic Turing machine paradigm. Three fundamental classes of the Turing machine are defined; the deterministic, stochastic and quantum Turing machines. Hamiltonian models and physical realizations of quantum computing are described. Quantum computers can perform some tasks which have no classical analogue, but they cannot compute functions that are non-computable by classical means. Some classically intractable problems can be solved with quantum computers.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Mar 1, 1994•0 citations

Models of Quantum Turing Machines

Paul A. Benioff

Quantum Turing machines are discussed and reviewed in this paper. Most of the paper is concerned with processes defined by a step operator T that is used to construct a Hamiltonian H according to Feynman's prescription. Differences between these models and the models of Deutsch are discussed and reviewed. It is emphasized that the models with H constructed from T include fully quantum mechanical processes that take computation basis states into linear superpositions of these states. The requirement that T be distinct path generating is reviewed. The advantage of this requirement is that Schrödinger evolution under H is one dimensional along distinct finite or infinite paths of nonoverlapping states in some basis BT. It is emphasized that BT can be arbitrarily complex with extreme entanglements between states of component systems. The new aspect of quantum Turing machines introduced here is the emphasis on the structure of graphs obtained when the states in the BT paths are expanded as linear superpositions of states in a reference basis such as the computation basis BC. Examples are discussed that illustrate the main points of the paper. For one example the graph structures of the paths in BT expanded as states in BC include finite stage binary trees and concatenated finite stage binary trees with or without terminal infinite binary trees. Other examples are discussed in which the graph structures correspond to interferometers and iterations of interferometers. 03.65.Bz,89.70.+c

arXiv:quant-ph/9708054•Fortschritte der Physik•Jun 1, 1998•18 citations

Quantum mechanical Hamiltonian models of discrete processes

Paul A. Benioff

Here the results of other work on quantum mechanical Hamiltonian models of Turing machines are extended to include any discrete process T on a countably infinite set A. The models are constructed here by use of scattering phase shifts from successive scatterers to turn on successive step interactions. Also a locality requirement is imposed. The construction is done by first associating with each process T a model quantum system M with associated Hilbert space ℋM and step operator UT. Since UT is not unitary in general, M, ℋM, and UT are extended into a (continuous time) Hamiltonian model on a larger space which satisfies the locality requirement. The construction is compared with the minimal unitary dilation of UT. It is seen that the model constructed here is larger than the minimal one. However, the minimal one does not satisfy the locality requirement.

Journal of Mathematical Physics•Mar 1, 1981•20 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
Mathematical models of quantum computers such as a multidimensional quantum Turing machine and quantum circuits are described and its relations with lattice spin models are discussed. One of the main open problems one has to solve if one wants to build a quantum computer is the decoherence due to the coupling with the environment. We propose a possible solution of this problem by using a control of parameters of the system. This proposal is based on the analysis of the spin-boson Hamiltonian performed in the stochastic limit approximation.
A goal of quantum-mechanical models of the computation process is the description of operators that model changes in the information-bearing degrees of freedom. Iteration of the operators should correspond to steps in the computation, and the final state of halting computations should be stable under iteration. The problem is that operators constructed directly from the process description do not have these properties. In general these operators annihilate the halted state. If information-erasing steps are present, there are additional problems. These problems are illustrated in this paper by consideration of operators for two simple one-step processes and two simple Turing machines. In general the operators are not unitary and, if erasing steps are present, they are not even contraction operators. Various methods of extension or dilation to unitary operators are discussed. Here unitary power dilations are considered as a solution to these problems. It is seen that these dilations automatically provide a good solution to the initial- and final-state problems. For processes with erasing steps, recording steps must be included prior to the dilation, but only for the steps that erase information. Hamiltonians for these processes are also discussed. It is noted that H, described by exp(-iH\ensuremath{\Delta})=UT{\mathit{U}}^{\mathit{T}}UT, where UT{\mathit{U}}^{\mathit{T}}UT is a unitary step operator for the process and \ensuremath{\Delta} a time interval, has complexity problems. These problems and those noted above are avoided here by the use of the Feynman approach to constructing Hamiltonians directly from the unitary power dilations of the model operators. It is seen that the Hamiltonians so constructed have some interesting properties.
The physics and the mathematics of computation are examined to provide a foundation and perspective for the investigation of the quantum mechanics of computation. Our purpose is to explore the fundamental limits and constraints imposed on computation by Nature through the laws of physics and the mathematics of computational complexity. Inasmuch as information storage and transmission are an integral part of computation, their physical bounds are considered. The computer is viewed both physically and mathematically as a dynamical system, and is depicted in terms of the basic Turing machine paradigm. Three fundamental classes of the Turing machine are defined; the deterministic, stochastic and quantum Turing machines. Hamiltonian models and physical realizations of quantum computing are described. Quantum computers can perform some tasks which have no classical analogue, but they cannot compute functions that are non-computable by classical means. Some classically intractable problems can be solved with quantum computers.
Quantum Turing machines are discussed and reviewed in this paper. Most of the paper is concerned with processes defined by a step operator T that is used to construct a Hamiltonian H according to Feynman's prescription. Differences between these models and the models of Deutsch are discussed and reviewed. It is emphasized that the models with H constructed from T include fully quantum mechanical processes that take computation basis states into linear superpositions of these states. The requirement that T be distinct path generating is reviewed. The advantage of this requirement is that Schrödinger evolution under H is one dimensional along distinct finite or infinite paths of nonoverlapping states in some basis BT. It is emphasized that BT can be arbitrarily complex with extreme entanglements between states of component systems. The new aspect of quantum Turing machines introduced here is the emphasis on the structure of graphs obtained when the states in the BT paths are expanded as linear superpositions of states in a reference basis such as the computation basis BC. Examples are discussed that illustrate the main points of the paper. For one example the graph structures of the paths in BT expanded as states in BC include finite stage binary trees and concatenated finite stage binary trees with or without terminal infinite binary trees. Other examples are discussed in which the graph structures correspond to interferometers and iterations of interferometers. 03.65.Bz,89.70.+c
Here the results of other work on quantum mechanical Hamiltonian models of Turing machines are extended to include any discrete process T on a countably infinite set A. The models are constructed here by use of scattering phase shifts from successive scatterers to turn on successive step interactions. Also a locality requirement is imposed. The construction is done by first associating with each process T a model quantum system M with associated Hilbert space ℋM and step operator UT. Since UT is not unitary in general, M, ℋM, and UT are extended into a (continuous time) Hamiltonian model on a larger space which satisfies the locality requirement. The construction is compared with the minimal unitary dilation of UT. It is seen that the model constructed here is larger than the minimal one. However, the minimal one does not satisfy the locality requirement.
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.