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