Quantum Turing machine

From Wikipedia, the free encyclopedia

A Quantum Turing machine (QTM) 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; thus, quantum Turing machines have the same relation to quantum computation that normal Turing machines have to classical computation.

Quantum Turing machines are not always used for analyzing quantum computation; the quantum circuit is a more common model. Both of these models are computationally equivalent.^[1]

Quantum Turing machines can be related to classical and probablistic Turing machines in a framework based on transition matrices, shown by Lance Fortnow.^[2]

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.^[3]

The 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^[4].

[edit] References

1. ^ Andrew Yao (1993). "Quantum circuit complexity". Proceedings of the 34th Annual Symposium on Foundations of Computer Science: 352–361. 
2. ^ 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. 
3. ^ Simon Perdrix and Philippe Jorrand. "Classically-Controlled Quantum Computation" arxiv:quant-ph/0407008. also Simon Perdrix and Philippe Jorrand (2006). "Classically-Controlled Quantum Computation" (PDF). Math. Struct. in Comp. Science 16: 601–620. 
4. ^ 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]

[edit] Further reading

• Satoshi Iriyama and Masanori Ohya (2007). "On generalized quantum Turing machine and its language classes" (PDF). Kleanthis Psarris and Andrew D. Jones Proceedings of the 11 WSEAS International Conference on APPLIED MATHEMATICS, Dallas, Texas, U.S.A., March 22–24 2007, WSEAS. ISBN 978-960-8457-60-7. 
• S. Iriyama, M. Ohya, I. Volovich. "Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm" arxiv:quant-ph/0405191.