View source for Quantum Turing machine

{{Short description|Model of quantum computation}}
{{Turing}}
<!-- Basic definition -->
A '''quantum Turing machine''' ('''QTM''') or '''universal quantum computer''' is an [[abstract machine]] used to [[Model of computation|model]] the effects of a [[quantum computer]].  It provides a simple model that captures all of the power of quantum computation—that is, any [[quantum algorithm]] can be expressed formally as a particular quantum Turing machine. However, the computationally equivalent [[quantum circuit]] is a more common model.<ref name=equivalence>{{cite conference|author=Andrew Yao|author-link=Andrew Yao|title=Quantum circuit complexity|conference=34th Annual Symposium on Foundations of Computer Science|pages=352–361|year=1993}}</ref><ref name="newequivalence">{{cite journal|arxiv=1808.01701|author1=Abel Molina|author2=John Watrous|author-link2=John Watrous (computer scientist)|title=Revisiting the simulation of quantum Turing machines by quantum circuits|journal=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences|date=2018|volume=475|issue=2226|doi=10.1098/rspa.2018.0767|pmid=31293355|pmc=6598068}}</ref>{{rp|2}}

<!-- Relation to classical computation -->
Quantum Turing machines can be related to classical and [[probabilistic Turing machines]] in a framework based on [[Stochastic matrix|transition matrices]]. That is, a matrix can be specified whose product with the matrix representing a classical or probabilistic machine provides the quantum [[probability matrix]] representing the quantum machine. This was shown by [[Lance Fortnow]].<ref name="transition">{{cite journal|author=Fortnow|first=Lance|author-link=Lance Fortnow|year=2003|title=One Complexity Theorist's View of Quantum Computing|journal=Theoretical Computer Science|volume=292|issue=3|pages=597–610|doi=10.1016/S0304-3975(01)00377-2|arxiv=quant-ph/0003035|s2cid=18657540}}</ref>

== Informal sketch ==
{{Unsolved|physics|Is a [[universal quantum computer]] sufficient to [[Algorithmic efficiency|efficiently]] [[Dynamical simulation|simulate]] an arbitrary physical system?}}
A way of understanding the quantum Turing machine (QTM) is that it generalizes the classical [[Turing machine]] (TM) in the same way that the [[quantum finite automaton]] (QFA) generalizes the [[deterministic finite automaton]] (DFA).  In essence, the internal states of a classical TM are replaced by [[pure state|pure]] or [[mixed quantum state|mixed states]] in a [[Hilbert space]]; the transition function is replaced by a collection of [[unitary matrix|unitary matrices]] that map the Hilbert space to itself.<ref name="Deutsch1985" />

That is, a classical Turing machine is described by  a 7-[[tuple]] <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math>. See [[Turing machine#Formal definition|the formal definition of a Turing Machine]] for a more in-depth understanding of each of the elements in this tuple.

For a three-tape quantum Turing machine (one tape holding the input, a second tape holding intermediate calculation results, and a third tape holding output):
* The set of states <math>Q</math> is replaced by a [[Hilbert space]].
* The tape alphabet symbols <math>\Gamma</math> are likewise replaced by a Hilbert space (usually a different Hilbert space than the set of states).
* The blank symbol <math>b \in \Gamma</math> is an element of the Hilbert space.
* The input and output symbols <math>\Sigma</math> are usually taken as a discrete set, as in the classical system; thus, neither the input nor output to a quantum machine need be a quantum system itself.
* The [[State transition system|transition function]] <math>\delta : \Sigma \times Q \otimes \Gamma \to \Sigma \times Q \otimes \Gamma \times \{L, R\}</math> is a generalization of a [[transition monoid]] and is understood to be a collection of [[unitary matrix|unitary matrices]] that are [[automorphism]]s of the Hilbert space <math>Q</math>.
* The initial state <math>q_0 \in Q</math> may be either a [[mixed quantum state|mixed state]] or a [[pure state]].
* The set <math>F</math> of ''final'' or ''accepting states'' is a subspace of the Hilbert space <math>Q</math>.

The above is merely a sketch of a quantum Turing machine, rather than its formal definition, as it leaves vague several important details: for example, how often a [[quantum measurement|measurement]] is performed; see for example, the difference between a measure-once and a measure-many QFA. This question of measurement affects the way in which writes to the output tape are defined.

==History==
In 1980 and 1982, physicist [[Paul Benioff]] published articles<ref>{{cite journal |last1=Benioff | first1=Paul | title=The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines | journal=Journal of Statistical Physics |volume=22 | issue=5 | pages=563–591 | year=1980 | doi=10.1007/bf01011339|bibcode=1980JSP....22..563B | s2cid=122949592 }}</ref><ref>{{Cite journal | doi=10.1007/BF01342185 | last1=Benioff | first1=P. | title=Quantum mechanical hamiltonian models of turing machines | journal=Journal of Statistical Physics | volume=29 | issue=3 | pages=515–546 | year=1982|bibcode=1982JSP....29..515B | s2cid=14956017 }}</ref> that first described a quantum mechanical model of [[Turing machines]]. A 1985 article written by Oxford University physicist [[David Deutsch]] further developed the idea of quantum computers by suggesting that [[quantum gate]]s could function in a similar fashion to traditional digital computing [[Binary numeral system|binary]] [[logic gates]].<ref name="Deutsch1985">{{cite journal |last=Deutsch |first=David |author-link=David Deutsch |date=July 1985 |title=Quantum theory, the Church-Turing principle and the universal quantum computer |url=http://www.ceid.upatras.gr/tech_news/papers/quantum_theory.pdf |url-status=dead |journal=[[Proceedings of the Royal Society A]] |volume=400 |issue=1818 |pages=97–117 |bibcode=1985RSPSA.400...97D |doi=10.1098/rspa.1985.0070 |archive-url=https://web.archive.org/web/20081123183419/http://www.ceid.upatras.gr/tech_news/papers/quantum_theory.pdf |archive-date=2008-11-23 |citeseerx=10.1.1.41.2382 |s2cid=1438116}}</ref>

Iriyama, [[Masanori Ohya|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.<ref>{{cite journal |title=Classically Controlled Quantum Computation |date=2007-04-04 |pages=601–620 |author1=Simon Perdrix |author2=Philippe Jorrand |volume=16 |journal=Math. Struct. In Comp. Science |arxiv=quant-ph/0407008 |doi=10.1017/S096012950600538X |issue=4 |s2cid=16142327}} Also: {{cite journal |title=Classically-Controlled Quantum Computation|author=Simon Perdrix and Philippe Jorrand |url=http://dcm-workshop.org.uk./2005/dcm-draft-proceedings.pdf |year=2006 |pages=601–620 |journal=Math. Struct. In Comp. Science |volume=16 |doi=10.1017/S096012950600538X |issue=4 |arxiv=quant-ph/0407008 |citeseerx=10.1.1.252.1823 |s2cid=16142327}}</ref>

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 (complexity)|PP]].<ref>{{cite journal |last=Aaronson |first=Scott |year=2005 |title=Quantum computing, postselection, and probabilistic polynomial-time |journal=[[Proceedings of the Royal Society A]] |volume=461 |issue=2063 |pages=3473–3482 |arxiv=quant-ph/0412187 |bibcode=2005RSPSA.461.3473A |doi=10.1098/rspa.2005.1546 |s2cid=1770389}} Preprint available at [https://arxiv.org/abs/quant-ph/0412187].</ref>

== See also ==
*[[Quantum simulator#Solving physics problems|Quantum simulator § Solving physics problems]]

== References ==
{{Reflist}}

== Further reading ==
* {{cite journal|arxiv=1808.01701|title=Revisiting the simulation of quantum Turing machines by quantum circuits|last1=Molina|first1=Abel|last2=Watrous|first2=John|journal=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences|year=2018|volume=475|issue=2226|doi=10.1098/rspa.2018.0767|pmid=31293355|pmc=6598068}}
* {{cite arXiv|eprint=quant-ph/0405191|title=Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm|last1=Iriyama|first1=Satoshi|last2=Ohya|first2=Masanori|last3=Volovich|first3=Igor|year=2004}}
* {{cite journal |jstor=2397601|title=Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer|journal=Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences|volume=400|issue=1818|pages=97–117|last1=Deutsch|first1=D.|year=1985|bibcode=1985RSPSA.400...97D|doi=10.1098/rspa.1985.0070|citeseerx=10.1.1.41.2382|s2cid=1438116}}

==External links==
* [http://ffden-2.phys.uaf.edu/211.web.stuff/Almeida/history.html The quantum computer – history]

{{quantum computing}}

[[Category:Turing machine]]
[[Category:Quantum complexity theory]]