Quantum Turing machine

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 Church-Turing 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.
2. ^ Andrew Yao (1993). "Quantum circuit complexity". Proceedings of the 34th Annual Symposium on Foundations of Computer Science. pp. 352–361.
3. ^ Lance Fortnow (2003). "One Complexity Theorist's View of Quantum Computing". Theoretical Computer Science 292: 597–610. doi:10.1016/S0304-3975(01)00377-2.
4. ^ Simon Perdrix; Philippe Jorrand (2007-04-04). "Classically-Controlled Quantum Computation". pp. 87. arΧiv:quant-ph/0407008 [quant-ph]. also Simon Perdrix and Philippe Jorrand (2006). "Classically-Controlled Quantum Computation" (PDF). Math. Struct. In Comp. Science 16: 601–620. doi:10.1017/S096012950600538X. http://dcm-workshop.org.uk./2005/dcm-draft-proceedings.pdf.
5. ^ Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". Proceedings of the Royal Society A 461 (2063): 3473–3482. doi:10.1098/rspa.2005.1546. Preprint available at [1]