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

*
*