量子图灵机
基础定义
量子图灵机 quantum Turing machine (QTM) 又称为通用量子计算机，是一种用来模拟量子计算机效果的抽象机器。尽管说提供等效计算能力的量子电路是一种更常用的模型，但是量子图灵机是一个简单但能展现出量子计算的所有威力的模型。就像经典图灵机可以模拟人类所能进行的任何计算过程一样，量子图灵机可以描述任何量子算法。[1][2]
与经典计算的关系
通过过渡矩阵，量子图灵机可以与经典图灵机和概率图灵机相关联。Lance Fortnow证明，量子图灵机的量子概率矩阵可以被拆解成是指定矩阵与经典或概率图灵机的矩阵的乘积。[3]
非正式草图定义
我们可以通过类比确定有限自动机 deterministic finite automaton到量子有限自动机 quantum finite automaton的转化来理解经典图灵机 Turing machine (TM)到量子图灵机的转化。 他们的差异在于，经典图灵机讨论的状态被推广到了Hilbert空间中。Hilbert空间是完备的内积空间，是有限维欧几里得空间的一个推广。它不局限于实数的情形和有限的维数，但又不失完备性。在量子图灵机中转换函数被一组映射Hilbert空间到自身的酉矩阵 unitary matrix取代。[4]
经典图灵机的诞生是因为图灵想用机器来模拟用纸笔进行数学运算的过程，这样的过程可以被看作下列两种简单的动作：
- 在纸带上写上或删除某个符号；
- 把笔尖从纸的一处移动到另一处；
现在我们假设有一条纸带无限长，并且被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。假设我们有一个执笔机器又称为读写头（HEAD），它本身也可以具有一个状态。就像人今天可能因为某件事心情很好，也可能因为另一件事情很抑郁一样，它的状态会随着它的遭遇所改变。更重要的是执笔机器当前关注的纸上的某个位置的符号和当前的状态决定了下一步的动作。在遇到停止状态[math]\displaystyle{ F }[/math]之前执笔机器可以
- 1. 写入（替换）或擦除当前符号；
- 2. 移动 HEAD， 'L'向左一步， 'R'向右一步或者'N'不移动；
- 3. 保持当前状态或者转到另一状态。
总的来说，经典图灵机可以被一个七元有序组所描述，[math]\displaystyle{ M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle }[/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空间的转移函数。我们也可以理解它们为一些在Hilbert空间中自同构的酉矩阵。
- [math]\displaystyle{ q_0 \in Q }[/math]是起始状态，它可以是几种状态的混合也可以是一种状态；
- 停止状态[math]\displaystyle{ F }[/math]是[math]\displaystyle{ Q }[/math]的子集。
以上只是一个量子图灵机的草图，而不是它的正式定义，因为它的一些重要细节仍然定义模糊：例如，我们以什么样的频率执行对于状态的观测；什么是一次观测量子有限自动机 measure-once和多次观测量子有限自动机 measure-many QFA之间的区别。这些观测问题会影响我们如何定义写入和输出纸带的方式。
历史
物理学家 Paul Benioff 在1980 年和 1982 年发表的论文中，首次描述了图灵机的量子力学模型。[5][6]牛津大学物理学家 David Deutsch 在 1985 年撰写的一篇文章中进一步推广了量子计算机的概念，他提议量子门quantum gate应该以类似于传统数字计算二进制逻辑门的方式运行。[4]
Iriyama、Ohya 和 Volovich 开发了线性量子图灵机 linear quantum Turing machine (LQTM) 模型。他们对具有混合状态并允许不可逆转换函数的量子图灵机进行了延伸。允许了在没有经典结果的情况下对量子的测量。[7]
Scott Aaronson 定义了具有后选择功能的量子图灵机，他证明了这种机器上的时间复杂度类 (PostBQP) 等于经典复杂度 PP。[8]
参考文献
- ↑ Andrew Yao (1993). Quantum circuit complexity. 34th Annual Symposium on Foundations of Computer Science. pp. 352–361.
- ↑ Abel Molina; John Watrous (2018). "Revisiting the simulation of quantum Turing machines by quantum circuits". arXiv:1808.01701 [cs.CC].
- ↑ 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 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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]
编者推荐
集智文章推荐
- 1931年，天才数学家图灵提出了著名的图灵机模型，它奠定了人工智能的数学基础。1943年，麦克洛克 & 皮茨（McCulloch & Pitts）两人提出了著名的人工神经元模型，该模型一直沿用至今，它奠定了所有深度学习模型的基础。那么，这两个开山之作究竟是怎样一种相爱相杀的关系呢？天才数学家冯诺依曼指出，图灵机和神经元本质上虽然彼此等价，我们可以用图灵机模拟神经元，也可以用神经元模拟图灵机，但是它们却位于复杂度王国中的不同领地。神经网络代表了一大类擅长并行计算的复杂系统，它们自身的结构就构成了对自己最简洁的编码；而图灵机则代表了另一类以穿行方式计算的复杂系统，这些系统以通用图灵机作为复杂度的分水岭：一边，系统的行为可以被更短的代码描述；另一边，我们却无法绕过复杂度的沟壑。而先进的深度学习研究正在试图将这两类系统合成为一个：神经图灵机。
课程推荐
- 本课程将围绕图灵机，详细介绍图灵机的定义、图灵机的计算、图灵机框架的模拟、通用图灵机、以及图灵停机问题，说明算法的上界。
- 量子力学作为现代物理学的两大核心理论之一，成功描述了微观物理体系的演化规律，奠定了现代信息科学特别是微电子学和光电子学的物理理论基础。量子概念的引入深刻地揭示了一系列与宏观体系截然不同的物理机制，在近年来逐渐发展出了包含量子通信、量子计算、量子模拟、量子测量等量子信息科学的全新研究领域和方向。
本中文词条由tueryeye翻译，薄荷编辑，如有问题，欢迎在讨论页面留言。
本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。