Quantum Turing machine
Wikipedia on Answers.com:
Top
Quantum Turing machine
| Is a universal quantum computer sufficient to efficiently simulate an arbitrary physical system? |  |
|
|
|
| Machina | |
|---|---|
| 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
- ^ 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. Bibcode 1985RSPSA.400...97D. doi:10.1098/rspa.1985.0070. http://www.ceid.upatras.gr/tech_news/papers/quantum_theory.pdf.
- ^ Andrew Yao (1993). "Quantum circuit complexity". Proceedings of the 34th Annual Symposium on Foundations of Computer Science. pp. 352–361.
- ^ 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.
- ^ 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. http://dcm-workshop.org.uk./2005/dcm-draft-proceedings.pdf.
- ^ 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
- Satoshi Iriyama; Masanori Ohya; Igor Volovich (2004). "Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm". arXiv:quant-ph/0405191 [quant-ph].
- Abstract of Deutsch's paper
- The quantum computer – history
|
|||||||||||||||||||||||||||||||||||||||
| P ≟ NP | This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it. |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
Post a question - any question - to the WikiAnswers community:
Copyrights:
Wikipedia on Answers.com
This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article Quantum Turing machine.
Read more