量子图灵机 - 版本历史

Tueryeye：加入了用户 tueryeye的链接

2023-02-15T02:35:39Z

加入了用户 tueryeye的链接

2022年5月2日 (一) 05:34 薄荷

2022-05-02T05:34:46Z

薄荷：/* 非正式草图定义 */

2022-05-02T05:34:18Z

非正式草图定义

薄荷：/* 编者推荐 */

2022-05-02T05:33:57Z

编者推荐

薄荷：/* 编者推荐 */

2022-05-02T05:14:16Z

编者推荐

2022年5月2日 (一) 05:13 薄荷

2022-05-02T05:13:17Z

显示更改

Tueryeye：阅读三遍

2022-03-31T04:33:28Z

阅读三遍

Tueryeye：阅读第二遍

2022-03-31T04:29:41Z

阅读第二遍

Tueryeye：删除一些唐突的原文

2022-03-31T04:26:06Z

删除一些唐突的原文

Tueryeye：整理

2022-03-31T04:21:45Z

整理

←上一版本		2023年2月15日 (三) 02:35的版本
第76行：		第76行：

	----		----
−	~~本中文词条由tueryeye翻译，~~[[用户:薄荷\|薄荷]]编辑，如有问题，欢迎在讨论页面留言。	+	本中文词条由[[tueryeye]]翻译，[[用户:薄荷\|薄荷]]编辑，如有问题，欢迎在讨论页面留言。

@@ 第4行： / 第4行： @@
 }}
 == 基础定义 ==
-'''量子图灵机 quantum Turing machine (QTM)''' 又称为'''通用量子计算机'''，是一种用来模拟量子计算机效果的抽象机器。尽管说提供等效计算能力的量子电路是一种更常用的模型，但是量子图灵机是一个简单但能展现出量子计算的所有威力的模型。就像经典图灵机可以模拟人类所能进行的任何计算过程一样，量子图灵机可以描述任何量子算法。<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>
+'''量子图灵机 quantum Turing machine (QTM)''' 又称为'''通用量子计算机'''，是一种用来模拟量子计算机效果的抽象机器。尽管说提供等效计算能力的量子电路是一种更常用的模型，但是量子图灵机是一个简单但能展现出量子计算的所有威力的模型。就像经典图灵机可以模拟人类所能进行的任何计算过程一样，量子图灵机可以描述任何量子算法。<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|title=Revisiting the simulation of quantum Turing machines by quantum circuits|date=2018|class=cs.CC}}</ref>
 == 与经典计算的关系 ==
-通过[[过渡矩阵]]，量子图灵机可以与经典图灵机和概率图灵机相关联。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">{{cite journal|author=Fortnow|first=Lance|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>
@@ 第46行： / 第46行： @@
 ==历史==
-物理学家 Paul Benioff 在1980 年和 1982 年发表的论文中，首次描述了图灵机的量子力学模型。<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>牛津大学物理学家 David Deutsch 在 1985 年撰写的一篇文章中进一步推广了量子计算机的概念，他提议量子门[[quantum gate]]应该以类似于传统数字计算二进制逻辑门的方式运行。<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">{{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>牛津大学物理学家 David Deutsch 在 1985 年撰写的一篇文章中进一步推广了量子计算机的概念，他提议量子门[[quantum gate]]应该以类似于传统数字计算二进制逻辑门的方式运行。<ref name="Deutsch1985">{{cite journal|last=Deutsch|first=David|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>

@@ 第12行： / 第12行： @@
 == 非正式草图定义 ==
-我们可以通过类比确定有限自动机[[deterministic finite automaton]]到量子有限自动机[[quantum finite automaton]]的转化来理解经典图灵机 Turing machine (TM)到量子图灵机的转化。 他们的差异在于，经典图灵机讨论的状态被推广到了Hilbert空间中。Hilbert空间是完备的内积空间，是有限维欧几里得空间的一个推广。它不局限于实数的情形和有限的维数，但又不失完备性。在量子图灵机中转换函数被一组映射Hilbert空间到自身的酉矩阵 unitary matrix取代。<ref name="Deutsch1985" />
+我们可以通过类比确定有限自动机 deterministic finite automaton到量子有限自动机 quantum finite automaton的转化来理解经典图灵机 Turing machine (TM)到量子图灵机的转化。 他们的差异在于，经典图灵机讨论的状态被推广到了Hilbert空间中。Hilbert空间是完备的内积空间，是有限维欧几里得空间的一个推广。它不局限于实数的情形和有限的维数，但又不失完备性。在量子图灵机中转换函数被一组映射Hilbert空间到自身的酉矩阵 unitary matrix取代。<ref name="Deutsch1985" />
@@ 第45行： / 第44行： @@
 以上只是一个量子图灵机的草图，而不是它的正式定义，因为它的一些重要细节仍然定义模糊：例如，我们以什么样的频率执行对于状态的观测；什么是一次观测量子有限自动机 measure-once和多次观测量子有限自动机 measure-many QFA之间的区别。这些观测问题会影响我们如何定义写入和输出纸带的方式。
 ==历史==

@@ 第65行： / 第65行： @@
 *[https://swarma.org/?p=3652 神经网络与图灵机的复杂度博弈]
 ::1931年，天才数学家图灵提出了著名的图灵机模型，它奠定了人工智能的数学基础。1943年，麦克洛克 & 皮茨（McCulloch & Pitts）两人提出了著名的人工神经元模型，该模型一直沿用至今，它奠定了所有深度学习模型的基础。那么，这两个开山之作究竟是怎样一种相爱相杀的关系呢？天才数学家冯诺依曼指出，图灵机和神经元本质上虽然彼此等价，我们可以用图灵机模拟神经元，也可以用神经元模拟图灵机，但是它们却位于复杂度王国中的不同领地。神经网络代表了一大类擅长并行计算的复杂系统，它们自身的结构就构成了对自己最简洁的编码；而图灵机则代表了另一类以穿行方式计算的复杂系统，这些系统以通用图灵机作为复杂度的分水岭：一边，系统的行为可以被更短的代码描述；另一边，我们却无法绕过复杂度的沟壑。而先进的深度学习研究正在试图将这两类系统合成为一个：神经图灵机。
 ===课程推荐===
@@ 第70行： / 第71行： @@
 ::本课程将围绕图灵机，详细介绍图灵机的定义、图灵机的计算、图灵机框架的模拟、通用图灵机、以及图灵停机问题，说明算法的上界。

←上一版本		2022年5月2日 (一) 05:14的版本
第55行：		第55行：

	Scott Aaronson 定义了具有后选择功能的量子图灵机，他证明了这种机器上的时间复杂度类 (PostBQP) 等于经典复杂度 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>		Scott Aaronson 定义了具有后选择功能的量子图灵机，他证明了这种机器上的时间复杂度类 (PostBQP) 等于经典复杂度 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>
		+
		+
		+	==参考文献==
		+	<references/>


	==编者推荐==		==编者推荐==
		+	===集智文章推荐===
		+	*[https://swarma.org/?p=3652 神经网络与图灵机的复杂度博弈]
		+	::1931年，天才数学家图灵提出了著名的图灵机模型，它奠定了人工智能的数学基础。1943年，麦克洛克 & 皮茨（McCulloch & Pitts）两人提出了著名的人工神经元模型，该模型一直沿用至今，它奠定了所有深度学习模型的基础。那么，这两个开山之作究竟是怎样一种相爱相杀的关系呢？天才数学家冯诺依曼指出，图灵机和神经元本质上虽然彼此等价，我们可以用图灵机模拟神经元，也可以用神经元模拟图灵机，但是它们却位于复杂度王国中的不同领地。神经网络代表了一大类擅长并行计算的复杂系统，它们自身的结构就构成了对自己最简洁的编码；而图灵机则代表了另一类以穿行方式计算的复杂系统，这些系统以通用图灵机作为复杂度的分水岭：一边，系统的行为可以被更短的代码描述；另一边，我们却无法绕过复杂度的沟壑。而先进的深度学习研究正在试图将这两类系统合成为一个：神经图灵机。
		+
		+	===课程推荐===
		+	*[https://campus.swarma.org/course/1155 图灵机]
		+	::本课程将围绕图灵机，详细介绍图灵机的定义、图灵机的计算、图灵机框架的模拟、通用图灵机、以及图灵停机问题，说明算法的上界。
		+
		+	*[https://campus.swarma.org/course/1153 人工智能2020]
		+	::本课程为北京师范大学系统科学学院张江教授开设的研究生课程《人工智能》课程回放。课程偏重理论，辅以编程实践，将粗粒度的梳理人工智能重要的理念、算法、模型。前面会包含一些人工智能之前的理论计算机模型，图灵机等，后面系统从两方面讲解，一是符号派的人工智能，包括搜索、推理、表示等；二是连接派的人工智能，机器学习，强调理论机器学习基础。

		+	===文章推荐===
		+	*[https://pattern.swarma.org/paper?id=9207a15c-9b1d-11ea-abd6-0242ac1a0005 分子计算：通向化学图灵机的途径。]
		+	::为了顺应快速增长的信息存储和处理需求，需要新的计算策略。分子计算的想法（即通过分子、超分子或生物分子方法进行基本计算，而不是通过电子方法）长期以来一直吸引着研究人员。使用分子和(生物)大分子进行计算的前景并非没有先例。自然中充满了以高效率、低能量成本和高密度信息编码来处理和存储数据的示例。根据通用计算方法运行的计算机的设计和组装，例如图灵机中的计算机，未来可能会以化学的方式实现。从这个角度来看，本文章重点介绍了到目前为止已经设计和合成的分子和(生物)大分子系统，目的是将它们用于计算目的；还提出了分子图灵机的蓝图，它基于一个催化装置，它沿着聚合物带滑动，在移动时，以氧原子的形式在这条带上打印二进制信息。
		+	[[文件:展示现代计算技术和未来分子计算的发现和进展的时间表.jpg\|缩略图\|右]]

		+	*[https://pattern.swarma.org/paper?id=14ecc15e-8860-11ea-b132-0242ac1a000b 使用图灵机的图灵模式：出现和低层次结构形成。]
		+	::尽管阿兰·图灵(Alan Turing)在1952年发表的关于形态发生的论文中提出了常微分方程的反应扩散模型，反映了他对数学生物学的兴趣，但他从未被认为接近过细胞自动机的定义。然而，他对形态发生的处理，特别是他发现的与对称破缺导致的某些形式的不均匀分布有关的困难，是将他的普遍计算理论与他的生物模式形成理论联系起来的关键。建立这样的联系并不能克服图灵所担心的特殊困难，无论如何，这个问题已经在生物学上得到了解决。但相反，这里开发的方法抓住了图灵最初关心的问题，并通过算法概率的概念为更一般的问题提供了一个低级解决方案，从而将图灵模式形成和通用计算这两个他对科学最重要的贡献联系在了一起。本文将展示使用此方法的一维模式的实验结果，而不会损失对n维模式泛化的一般性。

@@ 第53行： / 第53行： @@
 * The set <math>F</math> of ''final'' or ''accepting states'' is a subspace of the Hilbert space <math>Q</math>.
-* <math>Q</math> 非空有穷状态集合被推广到了Hilbert空间；
+* <math>Q</math> 为被推广到了Hilbert空间的状态集；
-* <math>\Gamma</math> 是非空有穷输入字母表，其中不包含特殊的空白符也被推广到了Hilbert空间；
+* <math>\Gamma</math> 是输入字母表；
 * <math>b \in \Gamma</math> 为''空白符''，也是唯一允许出现无限次的字符；
 * 输入和输出符号 <math>\Sigma</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>\delta : \Sigma \times Q  \otimes \Gamma \rightarrow \Sigma \times Q \otimes \Gamma \times \{L,R\}</math>是被推广到了Hilbert空间的转移函数[[State transition system|transition function]]。我们也可以理解它们为一些在Hilbert空间中自同构的酉矩阵[[unitary matrix|unitary matrices]] 。
 * <math>q_0 \in Q</math>是起始状态，它可以是几种状态的混合也可以是一种状态；
 * 停止状态<math>F</math>是<math>Q</math>的子集。

@@ 第64行： / 第64行： @@
 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.
-以上只是一个量子图灵机的草图，而不是它的正式定义，因为它的一些重要细节仍然定义模糊：例如，我们以什么样的频率执行对于状态的观测；什么是一次观测量子有限自动机和多次观测量子有限自动机 QFA 之间的区别。这些观测问题会影响我们如何定义写入和输出纸带的方式。
+以上只是一个量子图灵机的草图，而不是它的正式定义，因为它的一些重要细节仍然定义模糊：例如，我们以什么样的频率执行对于状态的观测；什么是一次观测量子有限自动机measure-once  [[quantum finite automaton]]和多次观测量子有限自动机 measure-many [[quantum finite automaton]] 之间的区别。这些观测问题会影响我们如何定义写入和输出纸带的方式。
 ==历史==
@@ 第70行： / 第70行： @@
 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 年撰写的一篇文章中进一步发展了量子计算机的概念，他提议量子门[[quantum gate]]应该以类似于传统数字计算二进制逻辑门的方式运行。<ref name="Deutsch1985" />
+物理学家 Paul Benioff 在1980 年和 1982 年发表的论文中，首次描述了图灵机的量子力学模型。<ref name=":0" /><ref name=":1" /> 牛津大学物理学家 David Deutsch 在 1985 年撰写的一篇文章中进一步推广了量子计算机的概念，他提议量子门[[quantum gate]]应该以类似于传统数字计算二进制逻辑门的方式运行。<ref name="Deutsch1985" />
 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>
-Iriyama、Ohya 和 Volovich 开发了线性量子图灵机 (LQTM) 模型。他们对具有混合状态并允许不可逆转换函数的量子图灵机进行了延伸。允许了没有经典结果的情况对量子测量在。<ref name=":2" />
+Iriyama、Ohya 和 Volovich 开发了线性量子图灵机 linear quantum Turing machine (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>
 Scott Aaronson 定义了具有后选择功能的量子图灵机，他证明了这种机器上的时间复杂度类 (PostBQP) 等于经典复杂度 PP。<ref name=":3" />
 == 相关内容 ==

@@ 第7行： / 第7行： @@
 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>
-量子图灵机计算机'''quantum Turing machine''' (QTM)又称为通用量子计算机是一种用来模拟量子计算机效果的抽象机器。虽然它是一个简单的模型，但它能展现出量子计算的所有威力。就像经典图灵机可以模拟人类所能进行的任何计算过程一样，量子图灵机可以描述任何量子算法。尽管说提供等效计算能力的量子电路是一种更常用的模型。<ref name="equivalence" /><ref name="newequivalence" />
+量子图灵机'''quantum Turing machine''' (QTM)又称为通用量子计算机是一种用来模拟量子计算机效果的抽象机器。尽管说提供等效计算能力的量子电路是一种更常用的模型，但是量子图灵机'''quantum Turing machine''' 是一个简单但能展现出量子计算的所有威力的模型。就像经典图灵机可以模拟人类所能进行的任何计算过程一样，量子图灵机可以描述任何量子算法。<ref name="equivalence" /><ref name="newequivalence" />
@@ 第15行： / 第15行： @@
 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" />
+通过过渡矩阵[[Stochastic matrix|transition matrices]]，量子图灵机可以与经典图灵机和概率图灵机相关联。Lance Fortnow证明，量子图灵机的量子概率矩阵可以被拆解成是指定矩阵与经典或概率图灵机的矩阵的乘积。<ref name="transition" />
 == 非正式草图定义 ==
@@ 第22行： / 第22行： @@
 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" />
+我们可以通过类比确定有限自动机[[deterministic finite automaton]]到量子有限自动机[[quantum finite automaton]]的转化来理解经典图灵机到量子图灵机'''quantum Turing machine'''的转化。 他们的差异在于，经典图灵机讨论的状态被推广到了Hilbert空间中。Hilbert空间是'''完备的内积空间'''，是有限维欧几里得空间的一个推广。它不局限于实数的情形和有限的维数，但又不失完备性。在量子图灵机中转换函数被一组映射Hilbert空间到自身的酉矩阵[[unitary matrix|unitary matrices]]取代。<ref name="Deutsch1985" />
 经典图灵机的诞生是因为图灵想用机器来模拟用纸笔进行数学运算的过程，这样的过程可以被看作下列两种简单的动作：
@@ 第29行： / 第29行： @@
 * 把笔尖从纸的一处移动到另一处；
-假设有一条纸带无限长，并且被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。假设我们有一个执笔机器又称为读写头（'''HEAD），'''它本身也可以具有一个状态。就像人今天可能因为某件事心情很好，也可能因为另一件事情很抑郁一样，它的状态会随着它的遭遇所改变。更重要的是执笔机器当前关注的纸上的某个位置的符号和当前的状态决定了下一步的动作。在遇到停止状态<math>F</math>之前执笔机器可以
+现在我们假设有一条纸带无限长，并且被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。假设我们有一个执笔机器又称为读写头（'''HEAD），'''它本身也可以具有一个状态。就像人今天可能因为某件事心情很好，也可能因为另一件事情很抑郁一样，它的状态会随着它的遭遇所改变。更重要的是执笔机器当前关注的纸上的某个位置的符号和当前的状态决定了下一步的动作。在遇到停止状态<math>F</math>之前执笔机器可以
 * 1. 写入（替换）或擦除当前符号；
@@ 第37行： / 第37行： @@
 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]].