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.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 AMay 1, 19952 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.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 PhysicsMar 1, 198120 citations

A formulation of Quantum Turing Machine

Ryuichi Sawae, Hiroshi Takeuchi, Tadahito Harima

Dec 1, 19950 citations

On the simulation of quantum turing machines

Marco Carpentieri

Theoretical Computer ScienceMar 26, 20037 citations

{\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.