量子图灵机
此词条由tueryeye翻译审校，未经专家审核，带来阅读不便，请见谅。
基础定义
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.[1][2]
量子图灵机quantum Turing machine (QTM)又称为通用量子计算机是一种用来模拟量子计算机效果的抽象机器。尽管说提供等效计算能力的量子电路是一种更常用的模型，但是量子图灵机quantum Turing machine 是一个简单但能展现出量子计算的所有威力的模型。就像经典图灵机可以模拟人类所能进行的任何计算过程一样，量子图灵机可以描述任何量子算法。[1][2]
与经典计算的关系
Quantum Turing machines can be related to classical and probabilistic Turing machines in a framework based on 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.[3]
通过过渡矩阵transition matrices，量子图灵机可以与经典图灵机和概率图灵机相关联。Lance Fortnow证明，量子图灵机的量子概率矩阵可以被拆解成是指定矩阵与经典或概率图灵机的矩阵的乘积。[3]
非正式草图定义
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 or mixed states in a Hilbert space; the transition function is replaced by a collection of unitary matrices that map the Hilbert space to itself.[4]
我们可以通过类比确定有限自动机deterministic finite automaton到量子有限自动机quantum finite automaton的转化来理解经典图灵机到量子图灵机quantum Turing machine的转化。 他们的差异在于，经典图灵机讨论的状态被推广到了Hilbert空间中。Hilbert空间是完备的内积空间，是有限维欧几里得空间的一个推广。它不局限于实数的情形和有限的维数，但又不失完备性。在量子图灵机中转换函数被一组映射Hilbert空间到自身的酉矩阵unitary matrices取代。[4]
经典图灵机的诞生是因为图灵想用机器来模拟用纸笔进行数学运算的过程，这样的过程可以被看作下列两种简单的动作：
- 在纸带上写上或删除某个符号；
- 把笔尖从纸的一处移动到另一处；
现在我们假设有一条纸带无限长，并且被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。假设我们有一个执笔机器又称为读写头（HEAD），它本身也可以具有一个状态。就像人今天可能因为某件事心情很好，也可能因为另一件事情很抑郁一样，它的状态会随着它的遭遇所改变。更重要的是执笔机器当前关注的纸上的某个位置的符号和当前的状态决定了下一步的动作。在遇到停止状态[math]\displaystyle{ F }[/math]之前执笔机器可以
- 1. 写入（替换）或擦除当前符号；
- 2. 移动 HEAD， 'L'向左一步， 'R'向右一步或者'N'不移动；
- 3. 保持当前状态或者转到另一状态。
That is, a classical Turing machine is described by a 7-tuple [math]\displaystyle{ M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle }[/math].
总的来说，经典图灵机可以被一个七元有序组所描述，[math]\displaystyle{ M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle }[/math]。
- The set of states [math]\displaystyle{ Q }[/math] is replaced by a Hilbert space.
- The tape alphabet symbols [math]\displaystyle{ \Gamma }[/math] are likewise replaced by a Hilbert space (usually a different Hilbert space than the set of states).
- The blank symbol [math]\displaystyle{ b \in \Gamma }[/math] corresponds to the zero-vector.
- The input and output symbols [math]\displaystyle{ \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 transition function [math]\displaystyle{ \delta : \Sigma \times Q \otimes \Gamma \rightarrow \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 matrices that are automorphisms of the Hilbert space [math]\displaystyle{ Q }[/math].
- The initial state [math]\displaystyle{ q_0 \in Q }[/math] may be either a mixed state or a pure state.
- The set [math]\displaystyle{ F }[/math] of final or accepting states is a subspace of the Hilbert space [math]\displaystyle{ Q }[/math].
- [math]\displaystyle{ Q }[/math] 为被推广到了Hilbert空间的状态集；
- [math]\displaystyle{ \Gamma }[/math] 是输入字母表；
- [math]\displaystyle{ b \in \Gamma }[/math] 为空白符，也是唯一允许出现无限次的字符；
- 输入和输出符号 [math]\displaystyle{ \Sigma }[/math]通常是一个离散集。和经典图灵机的输入输出符号一样，它们不需要是一个量子系统。
- [math]\displaystyle{ \delta : \Sigma \times Q \otimes \Gamma \rightarrow \Sigma \times Q \otimes \Gamma \times \{L,R\} }[/math]是被推广到了Hilbert空间的转移函数transition function。我们也可以理解它们为一些在Hilbert空间中自同构的酉矩阵unitary matrices 。
- [math]\displaystyle{ q_0 \in Q }[/math]是起始状态，它可以是几种状态的混合也可以是一种状态；
- 停止状态[math]\displaystyle{ F }[/math]是[math]\displaystyle{ 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 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.
以上只是一个量子图灵机的草图，而不是它的正式定义，因为它的一些重要细节仍然定义模糊：例如，我们以什么样的频率执行对于状态的观测；什么是一次观测量子有限自动机measure-once quantum finite automaton和多次观测量子有限自动机 measure-many quantum finite automaton 之间的区别。这些观测问题会影响我们如何定义写入和输出纸带的方式。
历史
In 1980 and 1982, physicist Paul Benioff published papers[5][6] 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 gates could function in a similar fashion to traditional digital computing binary logic gates.[4]
物理学家 Paul Benioff 在1980 年和 1982 年发表的论文中，首次描述了图灵机的量子力学模型。[5][6] 牛津大学物理学家 David Deutsch 在 1985 年撰写的一篇文章中进一步推广了量子计算机的概念，他提议量子门quantum gate应该以类似于传统数字计算二进制逻辑门的方式运行。[4]
Iriyama, 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.[7]
Iriyama、Ohya 和 Volovich 开发了线性量子图灵机 linear quantum Turing machine (LQTM) 模型。他们对具有混合状态并允许不可逆转换函数的量子图灵机进行了延伸。允许了在没有经典结果的情况下对量子的测量。[7]
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.[8]
Scott Aaronson 定义了具有后选择功能的量子图灵机，他证明了这种机器上的时间复杂度类 (PostBQP) 等于经典复杂度 PP。[8]
相关内容
Category:Turing machine
类别: 图灵机
范畴: 量子复杂性理论
This page was moved from wikipedia:en:Quantum Turing machine. Its edit history can be viewed at 量子图灵机/edithistory
- ↑ 1.0 1.1 Andrew Yao (1993). Quantum circuit complexity. 34th Annual Symposium on Foundations of Computer Science. pp. 352–361.
- ↑ 2.0 2.1 Abel Molina; John Watrous (2018). "Revisiting the simulation of quantum Turing machines by quantum circuits". arXiv:1808.01701 [cs.CC].
- ↑ 3.0 3.1 Fortnow, Lance (2003). "One Complexity Theorist's View of Quantum Computing". Theoretical Computer Science. 292 (3): 597–610. arXiv:quant-ph/0003035. doi:10.1016/S0304-3975(01)00377-2.
- ↑ 4.0 4.1 4.2 4.3 Deutsch, David (July 1985). "Quantum theory, the Church-Turing principle and the universal quantum computer" (PDF). Proceedings of the Royal Society A. 400 (1818): 97–117. Bibcode:1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382. doi:10.1098/rspa.1985.0070. Archived from the original (PDF) on 2008-11-23.
- ↑ 5.0 5.1 Benioff, Paul (1980). "The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines". Journal of Statistical Physics. 22 (5): 563–591. Bibcode:1980JSP....22..563B. doi:10.1007/bf01011339.
- ↑ 6.0 6.1 Benioff, P. (1982). "Quantum mechanical hamiltonian models of turing machines". Journal of Statistical Physics. 29 (3): 515–546. Bibcode:1982JSP....29..515B. doi:10.1007/BF01342185.
- ↑ 7.0 7.1 Simon Perdrix; Philippe Jorrand (2007-04-04). "Classically-Controlled Quantum Computation". Math. Struct. In Comp. Science. 16 (4): 601–620. arXiv:quant-ph/0407008. doi:10.1017/S096012950600538X. also Simon Perdrix and Philippe Jorrand (2006). "Classically-Controlled Quantum Computation" (PDF). Math. Struct. In Comp. Science. 16 (4): 601–620. CiteSeerX 10.1.1.252.1823. doi:10.1017/S096012950600538X.
- ↑ 8.0 8.1 Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". Proceedings of the Royal Society A. 461 (2063): 3473–3482. arXiv:quant-ph/0412187. Bibcode:2005RSPSA.461.3473A. doi:10.1098/rspa.2005.1546. Preprint available at [1]