Quantum Turing machine
|Unsolved problem in physics:
A quantum Turing machine (QTM), also a universal quantum computer, is an abstract machine used to model the effect of a quantum computer. It provides a very simple model which captures all of the power of quantum computation. Any quantum algorithm can be expressed formally as a particular quantum Turing machine. Such Turing machines were first described in papers in 1980 and 1982 by Paul Benioff at Argonne National Laboratory. Oxford University physicist David Deutsch extended the description by showing that networks of quantum gates could function as quantum computers. These networks operated in a fashion similar to that of traditional digital computing binary logic gates.
|url=http://www.ceid.upatras.gr/tech_news/papers/quantum_theory.pdf |doi=10.1098/rspa.1985.0070 |bibcode=1985RSPSA.400...97D}}</ref>
Iriyama, Ohya, and Volovich have developed a model of a Linear Quantum Turing Machine (LQTM). This is a generalization of a classical QTM that has mixed states and that allows irreversible transition functions. These allow the representation of quantum measurements without classical outcomes.
An easy way of understanding the quantum Turing machine (QTM) is that it generalizes the classical Turing machine (TM) in the same way that the quantum finite automaton (QFA) generalizes the deterministic finite automaton (DFA). In essence, the internal states of a classical TM are replaced by pure or mixed states in a Hilbert space; the transition function is replaced by a collection of unitary matrices that map the Hilbert space to itself.
That is, a classical Turing machine is described by a 7-tuple . For a three-tape quantum Turing machine (one tape holding the input, a second tape holding intermediate calculation results, and a third tape holding output),
- The set of states is replaced by a Hilbert space.
- The tape alphabet symbols are likewise replaced by a Hilbert space (usually a different Hilbert space than the set of states).
- The blank symbol corresponds to the zero-vector.
- The input and output symbols are usually taken as a discrete set, as in the classical system; thus, neither the input nor output to a quantum machine need be a quantum system itself.
- The transition function is a generalization of a transition monoid, and is understood to be a collection of unitary matricies that are automorphisms of the Hilbert space .
- The initial state may be either a mixed state or a pure state.
- The set of final or accepting states is a subspace of the Hilbert space .
The above is merely a sketch of a quantum Turing machine, rather than its formal definition, as it leaves vague several important details: for example, how often a measurement is performed; see for example, the difference between a measure-once and a measure-many QFA. This question of measurement affects the way in which writes to the output tape are defined.
- Benioff, Paul (1980). "The computer as a physical system: A microscopic Quantum mechanical Hamiltonian model of computers as represented by Turing machines". Journal of Statistical physics 22 (5): 563–591.
- Benioff, Paul (1982). "Quantum mechanical Hamiltonian models of Turing machines". Journal of statistical physics 29 (3): 515–546.
- Deutsch, David (July 1985). "Quantum theory, the Church-Turing principle and the universal quantum computer". Proceedings of the Royal Society A 400 (1818): 97–117.
- Andrew Yao (1993). Quantum circuit complexity. 34th Annual Symposium on Foundations of Computer Science. pp. 352–361.
- Lance Fortnow (2003). "One Complexity Theorist's View of Quantum Computing". Theoretical Computer Science 292 (3): 597–610. doi:10.1016/S0304-3975(01)00377-2.
- Simon Perdrix; Philippe Jorrand (2007-04-04). "Classically-Controlled Quantum Computation". Math. Struct. In Comp. Science 16 (4): 601–620. arXiv:quant-ph/0407008. doi:10.1017/S096012950600538X. also Simon Perdrix and Philippe Jorrand (2006). "Classically-Controlled Quantum Computation" (PDF). Math. Struct. In Comp. Science 16 (4): 601–620. doi:10.1017/S096012950600538X.
- Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". Proceedings of the Royal Society A 461 (2063): 3473–3482. Bibcode:2005RSPSA.461.3473A. doi:10.1098/rspa.2005.1546. Preprint available at 
- Satoshi Iriyama; Masanori Ohya; Igor Volovich (2004). "Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm". arXiv:quant-ph/0405191 [quant-ph].
- Abstract of Deutsch's paper
- The quantum computer – history