更改

<!-- Basic definition -->

<!-- Basic definition -->

=== 基础定义 ===

== 基础定义 ==

A '''quantum Turing machine''' ('''QTM''') or '''universal quantum computer''' is an [[abstract machine]] used to 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]]|title=Quantum circuit complexity|conference=34th Annual Symposium on Foundations of Computer Science|pages=352–361|year=1993}}</ref><ref name="newequivalence">{{cite arXiv|eprint=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|date=2018|class=cs.CC}}</ref>

A '''quantum Turing machine''' ('''QTM''') or '''universal quantum computer''' is an [[abstract machine]] used to 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]]|title=Quantum circuit complexity|conference=34th Annual Symposium on Foundations of Computer Science|pages=352–361|year=1993}}</ref><ref name="newequivalence">{{cite arXiv|eprint=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|date=2018|class=cs.CC}}</ref>

<!-- Relation to classical computation -->

<!-- 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|url=|journal=Theoretical Computer Science|volume=292|issue=3|pages=597–610|doi=10.1016/S0304-3975(01)00377-2|via=|arxiv=quant-ph/0003035}}</ref>

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|url=|journal=Theoretical Computer Science|volume=292|issue=3|pages=597–610|doi=10.1016/S0304-3975(01)00377-2|via=|arxiv=quant-ph/0003035}}</ref>

通过过渡矩阵，量子图灵机可以与经典图灵机和概率图灵机相关联。兰斯 · 福特诺（Lance Fortnow）证明，量子图灵机的量子概率矩阵可以被拆解成是指定矩阵与经典或概率图灵机的矩阵的乘积。<ref name="transition" />

通过过渡矩阵，量子图灵机可以与经典图灵机和概率图灵机相关联。兰斯 · 福特诺（Lance Fortnow）证明，量子图灵机的量子概率矩阵可以被拆解成是指定矩阵与经典或概率图灵机的矩阵的乘积。<ref name="transition" />

=== 通俗定义 ===

== 非正式草图定义 ==

{{Unsolved|physics|Is a [[universal quantum computer]] sufficient to [[Algorithmic efficiency|efficiently]] [[Dynamical simulation|simulate]] an arbitrary physical system?}}

{{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" />

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>.

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>.

经典图灵机可以被一个七元有序组所描述，<math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math>。

经典图灵机可以被一个七元有序组所描述，<math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math>。

 

 

 

 

 

 

* The set of states <math>Q</math> is replaced by a [[Hilbert space]].

* The set of states <math>Q</math> is replaced by a [[Hilbert space]].

* The set <math>F</math> of ''final'' or ''accepting states'' is a subspace of the Hilbert space <math>Q</math>.

* 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.

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==

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 name=":2">{{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}} 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|citeseerx=10.1.1.252.1823}}</ref>

In 1980 and 1982, physicist [[Paul Benioff]] published papers<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 }}</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 }}</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 [[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|archiveurl=https://web.archive.org/web/20081123183419/http://www.ceid.upatras.gr/tech_news/papers/quantum_theory.pdf|archivedate=2008-11-23|citeseerx=10.1.1.41.2382}}</ref>

Iriyama、Ohya 和 Volovich 开发了线性量子图灵机 (LQTM) 模型。他们对具有混合状态并允许不可逆转换函数的量子图灵机进行了延伸。允许了没有经典结果的情况对量子测量在。<ref name=":2" />

== See also ==

== 相关内容 ==

Category:Turing machine

Category:Turing machine