58
个编辑
更改
整理
此词条由tueryeye翻译审校，未经专家审核，带来阅读不便，请见谅。{{Short description|Model of quantum computation}}
{{Short description|Model of quantum computation}}
{{Turing}}
{{Turing}}
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>
量子图灵机计算机(QTM)又称为通用量子计算机是一种用来模拟量子计算机效果的抽象机器。虽然它是一个简单的模型，但它能展现出量子计算的所有威力。就像经典图灵机可以模拟人类所能进行的任何计算过程一样，量子图灵机可以描述任何量子算法。尽管说提供等效计算能力的量子电路是一种更常用的模型。<ref name="equivalence" /><ref name="newequivalence" />
量子图灵机计算机'''quantum Turing machine''' (QTM)又称为通用量子计算机是一种用来模拟量子计算机效果的抽象机器。虽然它是一个简单的模型，但它能展现出量子计算的所有威力。就像经典图灵机可以模拟人类所能进行的任何计算过程一样，量子图灵机可以描述任何量子算法。尽管说提供等效计算能力的量子电路是一种更常用的模型。<ref name="equivalence" /><ref name="newequivalence" />
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" />
== 非正式草图定义 ==
== 非正式草图定义 ==
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" />
我们可以通过类比确定有限自动机[[deterministic finite automaton]]到量子有限自动机[[quantum finite automaton]]的转化来理解经典图灵机到量子图灵机的转化。 他们的差异在于，经典图灵机讨论的状态被推广到了Hilbert空间中。Hilbert空间是'''完备的内积空间'''，是有限维欧几里得空间的一个推广。它不局限于实数的情形和有限的维数，但又不失完备性。在量子图灵机中转换函数被一组映射Hilbert空间到自身的酉矩阵[[unitary matrix|unitary matrices]]取代。<ref name="Deutsch1985" />
经典图灵机的诞生是因为图灵想用机器来模拟用纸笔进行数学运算的过程，这样的过程可以被看作下列两种简单的动作：
经典图灵机的诞生是因为图灵想用机器来模拟用纸笔进行数学运算的过程，这样的过程可以被看作下列两种简单的动作：
* 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>.
* <math>Q</math> 非空有穷状态集合被推广到了希尔伯特空间；
* <math>Q</math> 非空有穷状态集合被推广到了Hilbert空间；
* <math>\Gamma</math> 是非空有穷输入字母表，其中不包含特殊的空白符也被推广到了希尔伯特空间；
* <math>\Gamma</math> 是非空有穷输入字母表，其中不包含特殊的空白符也被推广到了Hilbert空间；
* <math>b \in \Gamma</math> 为''空白符''，也是唯一允许出现无限次的字符；
* <math>b \in \Gamma</math> 为''空白符''，也是唯一允许出现无限次的字符；
* 输入和输出符号 <math>\Sigma</math>通常是一个离散集。和经典图灵机的输入输出符号一样，它们不需要是一个量子系统。
* 输入和输出符号 <math>\Sigma</math>通常是一个离散集。和经典图灵机的输入输出符号一样，它们不需要是一个量子系统。
* <math>\delta : \Sigma \times Q \otimes \Gamma \rightarrow \Sigma \times Q \otimes \Gamma \times \{L,R\}</math>是转移函数被推广到了希尔伯特空间。我们也可以理解它们为一些在希尔伯特空间中自同构的酉矩阵。
* <math>\delta : \Sigma \times Q \otimes \Gamma \rightarrow \Sigma \times Q \otimes \Gamma \times \{L,R\}</math>是转移函数[[State transition system|transition function]]被推广到了Hilbert空间。我们也可以理解它们为一些在Hilbert空间中自同构的酉矩阵[[unitary matrix|unitary matrices]] 。
* <math>q_0 \in Q</math>是起始状态，它可以是几种状态的混合也可以是一种状态；
* <math>q_0 \in Q</math>是起始状态，它可以是几种状态的混合也可以是一种状态；
* 停止状态<math>F</math>是<math>Q</math>的子集。
* 停止状态<math>F</math>是<math>Q</math>的子集。
In 1980 and 1982, physicist [[Paul Benioff]] published papers<ref name=":0">{{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 name=":1">{{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>
In 1980 and 1982, physicist [[Paul Benioff]] published papers<ref name=":0">{{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 name=":1">{{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>
物理学家 Paul Benioff 在1980 年和 1982 年发表的论文中，首次描述了图灵机的量子力学模型。<ref name=":0" /><ref name=":1" /> 牛津大学物理学家 David Deutsch 在 1985 年撰写的一篇文章中进一步发展了量子计算机的概念，他提议量子门应该以类似于传统数字计算二进制逻辑门的方式运行。<ref name="Deutsch1985" />
物理学家 Paul Benioff 在1980 年和 1982 年发表的论文中，首次描述了图灵机的量子力学模型。<ref name=":0" /><ref name=":1" /> 牛津大学物理学家 David Deutsch 在 1985 年撰写的一篇文章中进一步发展了量子计算机的概念，他提议量子门[[quantum gate]]应该以类似于传统数字计算二进制逻辑门的方式运行。<ref name="Deutsch1985" />
Iriyama、Ohya 和 Volovich 开发了线性量子图灵机 (LQTM) 模型。他们对具有混合状态并允许不可逆转换函数的量子图灵机进行了延伸。允许了没有经典结果的情况对量子测量在。<ref name=":2" />
Iriyama、Ohya 和 Volovich 开发了线性量子图灵机 (LQTM) 模型。他们对具有混合状态并允许不可逆转换函数的量子图灵机进行了延伸。允许了没有经典结果的情况对量子测量在。<ref name=":2" />
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 name=":3">{{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|doi=10.1098/rspa.2005.1546|bibcode = 2005RSPSA.461.3473A |arxiv=quant-ph/0412187}} Preprint available at [https://arxiv.org/abs/quant-ph/0412187]</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 name=":3">{{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|doi=10.1098/rspa.2005.1546|bibcode = 2005RSPSA.461.3473A |arxiv=quant-ph/0412187}} Preprint available at [https://arxiv.org/abs/quant-ph/0412187]</ref>
*[[Quantum simulator#Solving physics problems|Quantum simulator § Solving physics problems]]
*[[Quantum simulator#Solving physics problems|Quantum simulator § Solving physics problems]]
范畴: 量子复杂性理论
范畴: 量子复杂性理论