您好、欢迎来到现金彩票网!
当前位置:2019年正版全年资料 > 通用图灵机 >

3 量子图灵机 --- 量子计算机有多快

发布时间:2019-06-12 05:07 来源:未知 编辑:admin

  1936年,太平洋西岸还在一片战火纷飞中,美洲大陆的普林斯顿宁静的校园里却也在悄悄的改变世界。教授阿隆佐丘奇和他的博士生图灵分别利用自己发明的演算和图灵机模型,提交了论文来探讨计算的极限是什么。他们的结论(猜想)之后被称为

  这句(意义稍显含混不清的也没有被证明过的)话直接奠定了之后计算机科学蓬勃发展的基础。方向已经被指得很明显:造出图灵机吧,之后(几乎)就没有我们不能做的了(当然不包括不可判定问题们,图灵他们的本意其实就是向希尔伯特证明存在不可判定问题)。

  之所以叫做论题而不是猜想是因为:1.“可以有效计算的函数”本身就没有过准确定义,于是不可能被证明。2. 几乎没有人在乎证明,图灵机明显已经无比强大了。

  时间飞转至49年后的1985年,另外一场革命也开始孕育。英国物理学家德意奇(David Deutsch)发表了关于“量子图灵机”的论文。德意奇肯定看了3年前费曼的论文,“simulating physics with computers,其中费曼第一次提出了利用量子力学来实现计算。之后一些物理学家,包括来自阿贡国家实验室的Paul Benioff,从物理上也设计出了一些模型,表示从能量等角度,费曼的设想没有问题,物理上是可以实现的。德意奇开始想如果这些物理学家所说的量子计算机可以实现的话, 那么一定也要限定可计算的范围,也一定有一个量子版本的“丘奇-图灵论题”。而他论文中提出的这个版本(丘奇-图灵-德意奇论题),比原版要好太多:

  其中所有的名词都可以被准确定义。而它的哲学意义和现实意义更是深远。在现实上看,现在的我们发现模拟各种物理系统已经是所有理工科的日常之一,从飞机机翼周围气流的流体力学到宇宙的演化到分子动力学,无一不有计算机模拟参与。从哲学意义上看,我们的世界可不可能就是运行在一台机器上的模拟程序?如果这个论题为真,是不是意味着世界就是完全可以被理解的了(只要能理解这台机器就能理解世界)? 不过随着弦论等高深的物理理论的出现,现在所有的物理理论和科学家们越来越明显的倾向于这个论题为假。

  所幸的是在限定为量子力学系统后,德意奇证明了他论文后面所定义的量子图灵机可以模拟所有物理系统---这便奠定了现在所有设想利用量子计算机模拟量子系统的想法的理论基础。基于量子物理,德意奇的量子图灵机(Quantum Turing Machine, QTM)和图灵的概率图灵机(Probabilistic TM,PTM)定义非常类似,几乎可以沿用纸带模型(在此假设读者熟悉概率图灵机)。QTM由:

  是代表空字符。和图灵机一样,只要可数,字符集的元素个数完全不影响。于是我们和经典计算机一样,一般都取0, 1,空字符的集合。

  意思为纸带空间是具体的纸带配置(configuration)的集合。一个纸带配置是一个把纸带用字符涂满的方式(可以用空字符)。我们还用字母

  来表示当时QTM的探头(probe)位置。探头位置表示内存纸带上被探头指向并且将改写的格子位置。

  的概率。然后探头位置可以左移或者右移一位(因为量子计算是可逆计算,所以探头必须也可以向左移动)。

  先转移到一个不确定的状态,再转移到一个确定的状态。这是使用PTM时难以想象的。

  而QTM和非确定图灵机(Nondeterministic TM,NTM)的区别在于:在最后的状态中,QTM只能以一定概率取出所有可能性中的一种,而NTM假设我们知道最后状态的所有信息。

  现在我们都知道,图灵机是现代计算机的原型(Prototype)。而原型的作用在于,在避开8核,256Gb SSD, DDR4等这些参数和名词之后,我们能准确的知道一台计算机能做什么,不能做什么,能有多块。更精确的说,它用来定义复杂度类(Complexity class)。复杂度类以各种原型能解决与否,来把问题分类。

  在多项式时间内能被非确定图灵机(Non-deterministic TM)决定的问题属于

  在多项式时间内能被概率图灵机(Probabilistic TM)以大于2/3的概率(或者任意确定的大于1/2)决定的问题属于

  在多项式时间内能被概率图灵机(Probabilistic TM)以大于1/2的概率(这个概率可以取决于输入长度

  。这个类几乎是只存在在理论上,因为离1/2太近的概率我们不运行很多次(指数级别)是分辨不出来的。

  在多项式时间内能被量子图灵机(Probabilistic TM)以大于2/3的概率(或者任意确定的大于1/2)决定的问题属于

  多项式时间/空间意思是算法的操作步数(number of steps)在O(n^k)的范围内,n是输入图灵机的字符串的长度,k是任意常数。

  P和NP还有函数版本,把1和2中的“决定”换成“计算出”即可,有些地方叫他们作FP,FNP, 很多地方也就放在P和NP里面了。还有很多别的有意思的复杂度类,比如芝加哥大学的教授Laszlo Babai提出的MA(Merlin Arthur), 亚瑟梅林协议。MA基于以欧洲中古传说的两个人物命名的交互式证明系统。基本想法是:想象一个无所不能的魔法师梅林(一个假设能力很强的TM)是证明者,而勇武有力的亚瑟王(一个Probabilistic TM)是个验证者,亚瑟不能完全相信神秘莫测的梅林,从而需要在自己能力范围内测试梅林是否诚实,如果一个问题他们俩在有限轮交互内能验证就属于MA。当然MA也有量子版本,把验证者换成QTM则成了QMA。更一般的交互式证明系统是IP, 其中验证者可以是任何TM。交互式证明系统非常重要也非常有趣,以后如有机会我们可以细谈。

  到现在为止,复杂度类已经有513个,他们都被收录在理论计算机学家Scott Aaronson创立的Complexity Zoo里。

  大家也关心复杂度类之间的关系,然而这非常复杂:P是否等于NP,P是否等于BPP等都是著名的悬而未决的问题。

  首先,BPP肯定属于BQP。对于每一台PTM,我们可以构造一台QTM使得状态转移函数里的(模平方)概率等于PTM里面的概率即可。这可以让人稍微心安:量子计算机至少和经典计算机一样快。

  但是人们最关心的问题是:BQP和NP是什么关系?BQP和P是什么关系?从上面QTM和NTM的分析来看,因为最后一步可以储存机器中所有的信息,NTM貌似要更强大,所以NP似乎包含BQP,。但是直觉往往是不准的,我们连P是否是等于NP都不知道。

  到现在我们也不知道以上问题的答案。这也使得九十年代初期人们对量子计算机开始心灰意冷--- 我们为什么要花大价钱造一台不知道有多快的机器?直到94年彼得秀尔(Peter Shor)提出质数分解算法才拯救了量子世界---至少有一个我们还不知道怎么有效解决的问题可以被量子计算机以指数级别的加速解决了。

  陆陆续续一直有新的量子算法提出,也有些复杂度理论的结论出现(比如2009年证明的QIP=Pspace)但是BQP在复杂度这个动物园里到底在哪我们还一直找不到。但是因为秀尔算法和格罗夫算法,人们还是以极大的热情在建造量子计算机。

  所以,问题的答案是:我们也不知道量子计算机有多快,但是有些特定问题它比经典计算机要快很多。

  其实从某种意义上来说,量子图灵机已经是一个有点“过时”的概念了,很少有人使用:首先,量子图灵机模型只是告诉我们了量子计算机的下限(至少和经典计算机一样快), 却并没有真正告诉我们它真正能有多快。其次,经典图灵机的令人振奋之处在于图灵构造了通用图灵机,一台“无所不能”的图灵机,而Umesh Vazirani的通用量子图灵机也是用的一台经典图灵机构造的,而使得使用这个过于抽象的概念让人有点兴趣索然,不过这也奠定了现在“经典控制,量子数据”(Classical control, quantum data)的思路。第三点,也是最重要的一点,1993年姚期智教授证明了方便直观很多的量子线路模型可以在多项式时间内模拟任何量子图灵机,这个模型一直沿用至今。但是从历史角度讲,它还是非常重要,有一个非常重要的结论就是用量子图灵机模型证明的:做T步的量子计算,我们对概率幅的精度只需要O(log T)。这保证了量子计算机是“数位”(digital)的,而不是“模拟(analog)的, 所以我们能造出来。XD

http://infomisa.net/tongyongtulingji/163.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有