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

Wiley eBooks

Models of Quantum Turing Machines

Paul A. Benioff

Published Oct 12, 1999• 5 citations
Publisher

Abstract

This chapter contains sections titled: Abstract I Introduction II The Physical Model III The Step Operator IV T as a Sum of elementary Step Operators V Distinct Path Generation A Basis Independent Description of Distinct Path Generation B Eigenfunctions, Spectrum of H C Sum Over Path Representation D Effective Determination of Distinct Path Generation VI Examples A The Erasure Operator B General Product Qubit Transformation and Add 1 C QTMS with Interferometer Graph Structures Acknowledgements References

DOI
10.1002/3527603093.ch7

Related papers

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•23 citations

Algorithms for Quantum Systems – Quantum Algorithms

T. Beth, Markus Grassl, D. Janzing +3 more

This chapter contains sections titled: Introduction Fast Quantum Signal Transforms Quantum Error-correcting Codes Efficient Decomposition of Quantum Operations into Given One-parameter Groups Simulation of Hamiltonians References

Quantum Information Processing•Feb 17, 2005•1 citation

Algorithms for Quantum Systems — Quantum Algorithms

T. Beth, Markus Grassl, Dominik Janzing +3 more

This chapter contains sections titled: Introduction Fast Quantum Signal Transforms Quantum Error-correcting Codes Efficient decomposition of quantum operations into given one-parameter groups Simulation of Hamiltonians References

Quantum Information Processing•Feb 21, 2003•2 citations

Quantum computation

Stephen Mark Barnett

In the preceding chapter we established that a suitable set of quantum gates, complemented by quantum error correction, allows us to produce a desired multiqubit unitary transformation. This transformation is one of the three steps in a quantum computation; the others, of course, are the preparation of the qubits in their initial state and the measurement of them after the transformation has been implemented. A quantum computation is designed to solve a problem or class of problems. The power of quantum computers is that they can do this, at least for some problems, very much more efficiently and quickly than any conventional computer based on classical logic operations. If we can build a quantum computer then a number of important problems which are currently intractable will become solvable. The potential for greatly enhanced computational power is, in itself, reason enough to study quantum computers, but there is another. Moore’s law is the observation that the number of transistors on a chip doubles roughly every eighteen months. A simple corollary is that computer performance also doubles on the same timescale. Associated with this exponential improvement is a dramatic reduction in the size of individual components. If the pace is to be kept up then it is inevitable that quantum effects will become increasingly important and ultimately will limit the operation of the computer. In these circumstances it is sensible to consider the possibility of harnessing quantum effects to realize quantum information processors and computers. We start with a brief introduction to the theory of computer science, the principles of which underlie the operation of what we shall refer to as classical computers. These include all existing machines and any based on the manipulation of classical bits. The development of computer science owes much to Turing, who devised a simple but powerful model of a computing device: the Turing machine. It its most elementary form, this consists of four elements. (i) A tape for data storage, which acts as a memory. This tape has a sequence of spaces, each of which has on it one of a finite set of symbols. (ii) A processor, which controls the operations of the machine.

Oxford University Press eBooks•May 28, 2009•0 citations

Quantum ballistic evolution in quantum mechanics: Application to quantum computers

Paul A. Benioff

Quantum computers are important examples of processes whose evolution can be described in terms of iterations of single-step operators or their adjoints. Based on this, Hamiltonian evolution of processes with associated step operators T is investigated here. The main limitation of this paper is to processes which evolve quantum ballistically, i.e., motion restricted to a collection of nonintersecting or distinct paths on an arbitrary basis. The main goal of this paper is proof of a theorem which gives necessary and sufficient conditions that T must satisfy so that there exists a Hamiltonian description of quantum ballistic evolution for the process, namely, that T is a partial isometry and is orthogonality preserving and stable on some basis. Simple examples of quantum ballistic evolution for quantum Turing machines with one and with more than one type of elementary step are discussed. It is seen that for nondeterministic machines the basis set can be quite complex with much entanglement present. It is also proven that, given a step operator T for an arbitrary deterministic quantum Turing machine, it is decidable if T is stable and orthogonality preserving, and if quantum ballistic evolution is possible. The proof fails if T is a step operator for a nondeterministic machine. It is an open question if such a decision procedure exists for nondeterministic machines. This problem does not occur in classical mechanics. Also the definition of quantum Turing machines used here is compared with that used by other authors. \textcopyright{} 1996 The American Physical Society.

arXiv:quant-ph/9605022•Physical Review A•Aug 1, 1996•15 citations

Quantum bits and quantum gates

E. Desurvire

This chapter represents our first step into quantum information theory (QIT). The key to operating such a transition is to become familiar with the concept of the quantum bit, or qubit , which is a probabilistic superposition of the classical 0 and 1 bits. In the quantum world, the classical 0 and 1 bits become the pure states |0〉 and |1〉, respectively. It is as if a coin can be classically in either heads or tails states, but is now allowed to exist in a superposition of both! Then I show that qubits can be physically transformed by the action of unitary matrices , which are also called operators . I show that such qubit transformations, resulting from any qubit manipulation, can be described by rotations on a 2D surface, which is referred to as the Bloch sphere . The Pauli matrices are shown to generate all such unitary transformations. These transformations are reversible , because they are characterized by unitary matrices ; this property always makes it possible to trace the input information carried by qubits. I will then describe different types of elementary quantum computations performed by elementary quantum gates, forming a veritable “zoo” of unitary operators, called I , X , Y , Z , H , CNOT, CCNOT, CROSSOVER or SWAP, controlled- U , and controlled-controlled- U . These gates can be used to form quantum circuits , involving any number of qubits, and of which several examples and tools for analysis are provided. Finally, the concept of tensor product , as progressively introduced through the above description, is eventually formalized.

Cambridge University Press eBooks•Feb 19, 2009•0 citations
This chapter contains sections titled: Abstract I Introduction II The Physical Model III The Step Operator IV T as a Sum of elementary Step Operators V Distinct Path Generation A Basis Independent Description of Distinct Path Generation B Eigenfunctions, Spectrum of H C Sum Over Path Representation D Effective Determination of Distinct Path Generation VI Examples A The Erasure Operator B General Product Qubit Transformation and Add 1 C QTMS with Interferometer Graph Structures Acknowledgements References
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
In the preceding chapter we established that a suitable set of quantum gates, complemented by quantum error correction, allows us to produce a desired multiqubit unitary transformation. This transformation is one of the three steps in a quantum computation; the others, of course, are the preparation of the qubits in their initial state and the measurement of them after the transformation has been implemented. A quantum computation is designed to solve a problem or class of problems. The power of quantum computers is that they can do this, at least for some problems, very much more efficiently and quickly than any conventional computer based on classical logic operations. If we can build a quantum computer then a number of important problems which are currently intractable will become solvable. The potential for greatly enhanced computational power is, in itself, reason enough to study quantum computers, but there is another. Moore’s law is the observation that the number of transistors on a chip doubles roughly every eighteen months. A simple corollary is that computer performance also doubles on the same timescale. Associated with this exponential improvement is a dramatic reduction in the size of individual components. If the pace is to be kept up then it is inevitable that quantum effects will become increasingly important and ultimately will limit the operation of the computer. In these circumstances it is sensible to consider the possibility of harnessing quantum effects to realize quantum information processors and computers. We start with a brief introduction to the theory of computer science, the principles of which underlie the operation of what we shall refer to as classical computers. These include all existing machines and any based on the manipulation of classical bits. The development of computer science owes much to Turing, who devised a simple but powerful model of a computing device: the Turing machine. It its most elementary form, this consists of four elements. (i) A tape for data storage, which acts as a memory. This tape has a sequence of spaces, each of which has on it one of a finite set of symbols. (ii) A processor, which controls the operations of the machine.
Quantum computers are important examples of processes whose evolution can be described in terms of iterations of single-step operators or their adjoints. Based on this, Hamiltonian evolution of processes with associated step operators T is investigated here. The main limitation of this paper is to processes which evolve quantum ballistically, i.e., motion restricted to a collection of nonintersecting or distinct paths on an arbitrary basis. The main goal of this paper is proof of a theorem which gives necessary and sufficient conditions that T must satisfy so that there exists a Hamiltonian description of quantum ballistic evolution for the process, namely, that T is a partial isometry and is orthogonality preserving and stable on some basis. Simple examples of quantum ballistic evolution for quantum Turing machines with one and with more than one type of elementary step are discussed. It is seen that for nondeterministic machines the basis set can be quite complex with much entanglement present. It is also proven that, given a step operator T for an arbitrary deterministic quantum Turing machine, it is decidable if T is stable and orthogonality preserving, and if quantum ballistic evolution is possible. The proof fails if T is a step operator for a nondeterministic machine. It is an open question if such a decision procedure exists for nondeterministic machines. This problem does not occur in classical mechanics. Also the definition of quantum Turing machines used here is compared with that used by other authors. \textcopyright{} 1996 The American Physical Society.
This chapter represents our first step into quantum information theory (QIT). The key to operating such a transition is to become familiar with the concept of the quantum bit, or qubit , which is a probabilistic superposition of the classical 0 and 1 bits. In the quantum world, the classical 0 and 1 bits become the pure states |0〉 and |1〉, respectively. It is as if a coin can be classically in either heads or tails states, but is now allowed to exist in a superposition of both! Then I show that qubits can be physically transformed by the action of unitary matrices , which are also called operators . I show that such qubit transformations, resulting from any qubit manipulation, can be described by rotations on a 2D surface, which is referred to as the Bloch sphere . The Pauli matrices are shown to generate all such unitary transformations. These transformations are reversible , because they are characterized by unitary matrices ; this property always makes it possible to trace the input information carried by qubits. I will then describe different types of elementary quantum computations performed by elementary quantum gates, forming a veritable “zoo” of unitary operators, called I , X , Y , Z , H , CNOT, CCNOT, CROSSOVER or SWAP, controlled- U , and controlled-controlled- U . These gates can be used to form quantum circuits , involving any number of qubits, and of which several examples and tools for analysis are provided. Finally, the concept of tensor product , as progressively introduced through the above description, is eventually formalized.