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 proposed in a 1985 paper written by Oxford University physicist David Deutsch suggesting quantum gates could function in a similar fashion as traditional digital computing binary logic gates.[1] Quantum Turing machines are not always used for analyzing quantum computation; the quantum circuit is a more common model; these models are computationally equivalent.[2] Quantum Turing machines can be related to classical and probabilistic Turing machines in a framework based on transition matrices, shown by Lance Fortnow.[3] 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.[4] A quantum Turing machine with postselection was defined by Scott Aaronson, who showed that the class of polynomial time on such a machine (PostBQP) is equal to the classical complexity class PP[5]. References 1. ^ Deutsch, David (July 1985). "Quantum theory, the ChurchTuring principle and the universal quantum computer". Proceedings of the Royal Society of London; Series A, Mathematical and Physical Sciences 400 (1818): pp. 97–117. doi:10.1098/rspa.1985.0070. http://www.ceid.upatras.gr/tech_news/papers/quantum_theory.pdf.
* Satoshi Iriyama; Masanori Ohya; Igor Volovich (2004). "Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm". arΧiv:quantph/0405191 [quantph].
Retrieved from "http://en.wikipedia.org/"

