Quantum Turing machine

From Wikipedia, the free encyclopedia
Jump to: navigation, search
List of unsolved problems in physics
Is a universal quantum computer sufficient to efficiently simulate an arbitrary physical system?

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 to 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]


  1. ^ Deutsch, David (July 1985). "Quantum theory, the Church-Turing principle and the universal quantum computer". Proceedings of the Royal Society A 400 (1818): pp. 97–117. Bibcode:1985RSPSA.400...97D. doi:10.1098/rspa.1985.0070. 
  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 (3): 597–610. doi:10.1016/S0304-3975(01)00377-2. 
  4. ^ 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. 
  5. ^ 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 [1]

Further reading[edit]