Quantum Turing machine

Quantum Turing machine

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.cite conference|author=Andrew Yao|title=Quantum circuit complexity|booktitle=Proceedings of the 34th Annual Symposium on Foundations of Computer Science|pages=352–361|year=1993]

Quantum Turing machines can be related to classical and probablistic Turing machines in a framework based on transition matrices, shown by Lance Fortnow.cite journal|author=Lance Fortnow|title = One Complexity Theorist's View of Quantum Computing|journal=Theoretical Computer Science|volume=292|year=2003|pages=597--610|doi = 10.1016/S0304-3975(01)00377-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. [cite arxiv|eprint=quant-ph/0407008|title=Classically-Controlled Quantum Computation|author=Simon Perdrix and Philippe Jorrand|date=2007-04-04|pages=87 also cite journal|title=Classically-Controlled Quantum Computation|author=Simon Perdrix and Philippe Jorrand|format=PDF|url=http://dcm-workshop.org.uk./2005/dcm-draft-proceedings.pdf|date=2006|pages=601–620|journal=Math. Struct. in Comp. Science|volume=16]

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 [cite journal|last=Aaronson|first=Scott|date=2005|title=Quantum computing, postselection, and probabilistic polynomial-time|journal=Proceedings of the Royal Society A|volume=461|issue=2063|pages=3473–3482|doi=10.1098/rspa.2005.1546 Preprint available at [http://arxiv.org/abs/quant-ph/0412187] ] .

References

Further reading

*
*


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Turing machine equivalents — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

  • Probabilistic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Non-deterministic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Multi-track Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Read-only Turing machine — A read only Turing machine or Two way deterministic finite state automaton (2DFA) is class of models of computability that behave like a standard Turing machine and can move in both directions across input, except cannot write to its input tape.… …   Wikipedia

  • Quantum programming — is a set of computer programming languages that allow the expression of quantum algorithms using high level constructs. The point of quantum languages is not so much to provide a tool for programmers, but to provide tools for researchers to… …   Wikipedia

  • Quantum finite automata — In quantum computing, quantum finite automata or QFA are a quantum analog of probabilistic automata. They are related to quantum computers in a similar fashion as finite automata are related to Turing machines. Several types of automata may be… …   Wikipedia

  • Quantum information — For the journal with this title, see Historical Social Research. In quantum mechanics, quantum information is physical information that is held in the state of a quantum system. The most popular unit of quantum information is the qubit, a two… …   Wikipedia

  • Quantum channel — In quantum information theory, a quantum channel is a communication channel which can transmit quantum information, as well as classical information. An example of quantum information is the state of a qubit. An example of classical information… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”