Monday, February 10, 2014

Quantum Turing machine

Quantum Turing machine

From Wikipedia, the free encyclopedia
List of unsolved problems in physics
Is a universal quantum computer sufficient to efficiently simulate an arbitrary physical system?
Turing machines
Machine
Science
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]

References

  1. Jump up ^ 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. Jump up ^ Andrew Yao (1993). "Quantum circuit complexity". Proceedings of the 34th Annual Symposium on Foundations of Computer Science. pp. 352–361.
  3. Jump up ^ 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. Jump up ^ 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. Jump up ^ 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

This page was last modified on 16 September 2013 at 14:22.
end quote from:
quantum Turing machine
Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)