图灵机与量子图灵机的比较分析

摘要

现在所有的计算设备都是基于图灵机的。众所周知，经典物理学足以解释宏观现象，但不能解释像电子干涉这样的微观现象。近年来，利用量子物理效应进行了计算设备的加速和缩小;然而，这些设备的计算原理也是基于经典物理学。本文试图从数学上分析通用量子图灵机(UQTM)能够比任何其他经典计算模型更快地计算的可能性。我们主要对通用图灵机(UTM)和UQTM的计算能力进行了比较研究。也就是说，在相等的情况下，我们试图证明UQTM可以在多项式时间内解决任何np完全问题。结果分析表明，UQTM在任何计算中都具有较快的速度。

关键字

量子;量子计算机;量子图灵机;通用图灵机;通用量子图灵机。

介绍

量子是一个离散的能量量，其大小与它所代表的辐射频率成正比。任何其他物理量的类似离散量，如动量或电荷被称为量子[1,3]。位(二进制数字)是计算机中最小的信息单位，计算机唯一能理解的是经典计算机的基本单位。经典计算机只工作于二进制值，称为位，每个位通常有一个值表示为0或1。位的一种最直观的表示形式是开或关的开关或引引式的“onâ '  '或offâ '  ' '电路的一部分。在todayâ '  ' s现代计算机中，这种表示形式仍然是晶体管，高电压可能表示1，低电压可能表示0。二态系统(0→1)是经典计算设备的组成部分。量子比特(Qubit)是量子信息的单位。量子比特既表示系统的状态内存，也表示系统的纠缠状态。量子纠缠是被实验证实的自然性质。

量子纠缠是指电子、光子、分子等粒子在物理上相互作用，然后分离。这种相互作用被称为纠缠。量子比特(Qubit)可以存在于一种叠加态中，可以表示为α|0>+β|1>，其中α、β表示满足|α|2 +|β|2=1的复数。任何状态测量结果为> >，概率为|α|2和|1>，概率为|β|2。一个n-量子比特系统可以存在于两个基态的任何叠加态中。量子纠缠是量子叠加的一种形式。量子计算机也有两个特征值，0和1，但由于它们的非经典行为，这些单位被称为量子位或量子比特。一个量子比特可以取任何值，即量子比特0或量子比特1的线性组合。

因此，虽然经典位可以取南北方的任何值，但任何方向都是非法的。一个量子比特(Qubit)的值为[2]的东北角。然而，在测量时，只能读取这些值中的一个，即北或南。为了确定读取量的南北相对部分的线性组合的系数，必须通过对原始量子比特状态的重复测量来找到。只有能展示量子现象的东西才能用来容纳量子比特。简单的开/关开关不可能保持开或关的线性组合。另一方面，电子或核自旋和光子的偏振态是自然的候选。这些量子态要么自旋要么极化，必须能够以某种方式进行操纵，以便将该值分配给每个比特[3]。图1显示了结合物理现象的状态的二元转变。

图灵机

我们感兴趣的是设计一种能够解决我们两个目标的自动机(机器)。(i)识别(ii)计算。图灵机(TM)是下推自动机(PDA)的一种推广，它是一个磁带，而不是一个磁带和堆栈。假定磁带的潜在长度为无限大，并将其划分为单元格，每个单元格包含一个输入符号。TM的头部能够在磁带上读写，可以向左或向右移动，也可以保持静止。图灵机(TM)是计算机的抽象版本;这已经被用来正式定义什么是可计算的。Churchâ '  ' s论文[4]支持图灵机(TM)可以刺激通用计算机系统的行为这一事实。1936年，英国数学家艾伦·图灵提出了图灵机的概念。图灵机接受被称为Type 1语言或递归可枚举语言的语法定义的语言。 Turing Machine is idealized in that they have an infinite memory, which comes in the form of an “infinite tape” (infinite on both the sides). The idea is that this tape consists of cells each of which can take one symbol from some underlying alphabet Σ, and that there is a „read/write head‟ which moves over the tape one position at a time and can either read from or write to the tape. It is practical to assume that the input string is written on the tape (from left to right).

当机器启动时，读/写头位于存放输入字符串第一个符号的单元格上。我们进一步假设磁带不再包含任何符号，所有剩余的单元格都是空的。为了描述机器所做的事情(即在何种情况下它将磁头向左或向右移动，或者从磁带中读取或写入磁带)，我们需要有一个状态的概念，就像我们对其他自动机所做的那样。和之前一样，有一个特定的启动状态，这一次我们需要一个动作停止来告诉我们机器何时完成了计算。

UTM的抽象模型:

图灵机(TM)由一个有限控件组成，它可以处于一个有限的状态集中的任何一个。有一种被分成正方形或格子的带子;每个单元格可以保存有限数量的符号中的任何一个。图2显示了TM及其组件的模型。

最初，将从输入字母中选择的有限长度的符号串放在磁带上。所有其他的磁带单元格，无限地向左右延伸，最初保存一个特殊的符号，称为空白。空白是纸带符号，但不是输入符号，除了输入符号和空白之外，还可以有其他纸带符号。有一个磁带头符号扫描。图灵机的工作步骤如下。

a.下一个状态可以选择与当前状态相同。

b.在扫描到的单元格中写入磁带符号。这个磁带符号替换了单元格中的任何符号。可选地，写入的符号可以与当前存在的符号相同。

c.左右移动磁带头。在我们的形式主义中，我们要求移动，并且不允许头对头保持静止。这一限制并没有限制图灵机(TM)可以计算什么，因为任何带有固定磁头的移动序列都可以被压缩，下一个磁带磁头也可以被压缩，下一个磁带磁头移动也可以被压缩为单个状态变化、一个新的磁带符号以及向左或向右移动。

图灵机的数学描述:

TM可以执行加法、减法、乘法和除法等计算。纸带上的数字以0的形式表示。假设i是一个正整数，那么oi表示这个整数。假设用1分隔两个整数。假设f是一个可计算函数，它有参数a1,a2,a3，使得f (a1,a2,a3) =m，其中a1,a2,a3和m是一些自然数，那么f被称为TM m计算。这样的函数f被称为是图灵可计算的或简单可计算的。TM计算如下所定义的整数函数。F1 (a1, a2, a3......，an)→m。如果f1为所有参数a1, a2, a3定义......then total函数类似于递归语言。由TM计算的函数f1(a1, a2, a3......，an)被称为部分递归函数，如果f对某些值定义，而不是对a1, a2, a3......，an的所有值定义。计算该函数的TM对于某些输入停止，对于其他输入(如n!)可能不会停止。， log2n等等… total recursive function. Figure-6 shows a sample difference between Total Recursive Function and Partial Recursive Function.

图灵机改造:

图灵机有很多改进。

a.双向无限TM。L被双向无限带图灵机识别当且仅当它被单向无限带识别时。图7显示了这个机器模型。

b.多重TM: I如果一种语言L能被多带图灵机接受，那么它也能被单带图灵机接受。图8显示了这种TM的理论结构。

c和s之间的区域，显然离线TM只是多个TM的特例。离线TM可以通过使用比M多一个磁带来模拟任何TM。离线TM所做的第一件事是将自己的输入复制到额外的磁带上，然后刺激M，就好像额外的磁带是Mâ '  ' s的输入。

量子图灵机

量子图灵机(QTM)是由David Deutsch在1985年定义的。QTM是量子物理计算机的精确模型。有两种方式来思考QTM， (i)概率图灵机的量子物理模拟;(ii)在复杂构型叠加空间中的变换计算。QTM是基于量子物理的计算设备的最通用模型。就像普通的图灵机一样。量子图灵机M由一个有限控制器、一个无限磁带和一个磁带头组成。量子图灵机被定义为由处理器、移动磁头和磁带组成的量子系统，服从由其组件之间的局部相互作用决定的一元时间演化，并允许处于计算配置的叠加状态。Deutsch指出，计算构型之间的全局转换函数应该由只依赖于局部构型的局部转换函数来确定。Bernstein和Vazirani发现了受限类量子图灵机的局部转换函数的一个简单描述，其中头部在每一步都必须向右或向左移动。由于上述特征构成了理论计算机科学领域中更易于处理的量子图灵机的另一种定义，因此即使在不需要移动磁头或更一般地当机器有多个磁带时，找到一个有效的一般特征也是一个有趣的问题[7,8]。

MÃⅰÂ′Â′s配置的叠加。这个线性映射由下面的矩阵Mâ '  ' s configuration指定。这个线性映射由下面的矩阵M6指定。M6的每一行和每一列都对应于M的构型，设c1和c2为M的构型，则M6的c2行和c1列对应的项在元组上求值δ，该元组将c1和c2进行一步变换。如果不存在这样的元组，则对应的条目将为Zero。我们称这个矩阵M6为m的时间演化矩阵。在量子图灵机中，δ与每个状态和符号以及每个可能的下一步移动相关联，这是一个复杂的概率振幅(我们要求它是一个可行的复数)。我们还要求机器定义的线性变换是幺正的。BQP是量子图灵机识别的语言L的集合，在有界概率规则下，以多项式时间运行。如果我们将可能的振幅集限制为{0，±2/3，±4/ 5,1}BPP⊆BQP，则类BQP不会改变。肖尔已经证明了BQP中存在因式分解问题。 It is not known to be in BPP.

QTM可以看作是一个物理模型:

量子图灵机是一种量子系统，由处理器、双边无限磁带和在磁带上读写符号的磁头组成。它的配置由处理器配置q由有限集q的符号决定，磁带配置T由有限集q的符号表示，磁带配置T由有限集é符号表示，而离散化的头部位置à ¶Â。图10是一个将QTM视为物理系统的示例[6,7,8]。

然而，全球各地正在进行各种研究，以使量子计算的这一假设能够像量子计算机的开发一样实际实现。它仍处于起步阶段。

结论

本文对“图灵Machineâ ' ”和“量子图灵Machineâ ' ”两种计算模型进行了比较分析。这项研究是基于这两个模型的计算能力。说明图灵机可以根据实际应用进行修改。在此基础上，提出了单带、多带、k头、多带等模型。但是，量子图灵机的计算速度和可接受的语言数量比其他任何计算模型都要好。随着未来的工作，深入研究量子图灵机，并发现它相对于传统计算模型的更多优势，将是一件有趣的事情。

参考文献

王志强，王志强，量子图灵机与量子下推自动机的比较研究，计算机工程学报，vol . 3(1)， 2012, pp. 2932-2935。 王志强，王志强，量子有限自动机，量子下推自动机与量子图灵机的研究，计算机科学与技术，vol . 3(2)， 2012, pp. 366 - 366。 费曼，用计算机模拟物理，国际。j .系统结构。理论物理。，21 (1982), pp. 467-488. 《量子理论、丘奇-图灵原理与通用量子计算机》，Roy.Soc。伦敦爵士。A, 400(1985)，第97-117页。[5] Deutsch D.，量子计算网络，Proc. Roy.Soc。伦敦爵士。A, 425(1989)，第73-90页。 BenioffP。，The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines, J. Stat. Phys., 22 (1980), pp. 563-591. 摩尔，柯兰驰菲尔德，量子自动机与量子文法，理论。第一版。科学通报237(1-2)(2000)275-306。 尼尔森M.，庄毅，量子计算与量子信息，剑桥大学出版社，2000