走近量子纠缠--量子计算机
简介:回顾计算机发展的历史,自从第一台经典计算机问世以来,它在“大小”领域经历了巨大的变化,从一个占据几栋建筑的巨大物体到人们的手掌和口袋。在过去的20年里,计算机技术经历了一次巨大的革命性飞跃。单个芯片上三极管的数量和运行速度都在逐年呈指数级增长。波士顿哈佛大学附近的克莱数学研究所在新的千年发布了一条信息:将提供一百万美元的奖金来寻找当时七个突出的数学问题的答案。到目前为止,12年过去了,俄罗斯数学家佩雷尔曼·格里戈里·佩雷尔曼在2006年只解决了“庞加莱猜想”中的一个问题。然而,佩雷尔曼天生对名利无动于衷,拒绝接受这个奖项。他还拒绝接受同年授予他的诺贝尔数学奖“领域”。据说这件事也给了一位数学数学家一个幕后故事。然而,这是一个题外话,这里没有显示。
七个千年奖之一是计算机算法领域中众所周知的P/NP问题。
众所周知,计算机的发明为许多需要大量数值计算的问题提供了捷径。计算机的计算能力是普通人工计算无法比拟的。一台超级计算机每秒可以连续执行数亿次运算。一般来说,需要数值计算的问题的计算量与代表问题大小的变量数n有关。变量n的数量越大,解决问题所需的计算时间t就越长。当然,计算时间T也取决于所使用的计算方法。计算机算法是对各种计算方法的研究。
所需计算量T和变量数N之间的函数关系根据问题而变化。在某些问题中,t和n是线性相关的;但在其他问题上,这是一个平方关系。指数也有可能随着n的增加而增加。
研究算法的科学家根据T随n增加的函数形式将需要大量计算的问题分成几种不同的类型。第一种类型称为P型,或多型。计算p型问题所需的时间t和n是多项式级数。多项式问题是一个可以用计算机解决的问题。只要计算机足够快,内存足够大,并且使用了正确的算法,答案今天将永远可用。然而,对于另一个NP-型问题,还没有找到成功的算法,所以当与n的关系在多项式级数中增加时,问题的答案可以在时间内得到解决。然而,这并不意味着该算法不存在。因此,这是一种不能确定t和n是否是多项式级数的问题。此外,还有一个最困难的问题,属于NP-Hard。
在NP型中,有一个子集是数学家最感兴趣的,它被称为NP完全整数。这个子集中的任何两个问题相互转换所需的时间是与n成多项式级数关系的。因此,如果我们找到一个多项式算法来解决一个NP完全问题,我们也有一个多项式算法来解决所有的NP完全问题,这叫做证明“NP=P”。另一方面,如果你能证明这个NP完全整数的多项式算法不存在,那么你就证明了“NP!=P .克莱数学学院的百万美元奖将授予那些证明了“NP=P”或“NP!=P”。
看下图,可能更容易理解生产计划/生产计划问题:
大多数数学家认为结论应该是p!=NP,但是很难严格证明这个结论。否则,答案怎么会有百万美元的奖金呢?然而,2010年8月,惠普实验室的一名研究人员声称证明了磷不是磷。然而,当时他只是在自己的网站上宣布了这件事,然后似乎就没有了追随者。因此,这应该是一个悬而未决的问题。
算法问题的本质是计算速度问题。从理论上讲,当前经典类型的计算机将永远无法处理计算中的指数增长问题。这些题目包括著名的“旅行推销员问题”,用于秘密通信的大数的素数分解问题等。,以及获胜问题,据说属于最难的NP-Hard类。我不敢说量子计算机能解决这些困难,但它们总是提供另一种完全不同于经典图灵机的选择性,并根据量子定律运行。
不幸的是,量子理论的诞生已经有大约100年的历史,而经典计算机使用的芯片制造技术已经涉及到量子理论。然而,基于数亿经典比特的计算机科学家们在半个多世纪后才知道量子计算。如果这项研究早点进行,计算机科学可能会受益匪浅。回顾计算机发展的历史,自从第一台经典计算机问世以来,它在“大小”领域经历了巨大的变化,从一个占据几栋建筑的巨大物体到人们的手掌和口袋。在过去的20年里,计算机技术经历了一次巨大的革命性飞跃。单个芯片上三极管的数量和运行速度都在逐年呈指数级增长。正是这种快速的发展将很快使经典计算机达到极限。到那时,三极管的尺寸将达到原子尺度。经典电脑的基本原理是,无论是40多年前充满整个房子的巨大物体,还是现在的移动电话电脑,一切都将保持不变。基本建设单位是比特。无论是用灯泡大小的电子管实现的一点点,还是用芯片上的三极管(微米大小)表达的一点点,都遵循牛顿力学定律。直到费曼在使用经典计算机模拟子系统时观察到“指数减速”的问题,计算机科学家和物理学家才开始携手研究“量子计算机”的物理实现和算法。
有些人还把研究“可逆计算”的IBM科学家兰道尔视为量子计算之父。人们相信他在1961年在“可逆计算”领域的发现导致了量子计算机的研究。然而,事实上,可逆计算的研究仅仅与量子计算机有关,并不直接导致量子计算的发展。此外,在他去世之前(直到1999年去世),兰道尔本人也不遗余力地批评量子计算机的研究。他认为量子计算机“没有考虑所有可能的噪声源,也没有考虑实际生产中的误差和缺陷,这基本上是不可能的。”
当然,尽管费曼早在1982年就预见到了量子元素超强的计算功能,但直到1996年贝尔实验室的肖尔开发出一种算法后,量子计算机的研究才逐渐成为学术界和一些大型工业研究部门的焦点。计算机学者开始使用和理解量子力学的奇妙定律。物理学家也将目光转向计算机科学,关心并讨论了适用于量子元素运算法则的算法。如果肖尔的算法应用于量子计算机,一个大整数可以在多项式时间内分解成几个素数的乘积。换句话说,如果将来建造一台真正实用的量子计算机,并在其上使用W.Shor算法和其他量子算法,上述NP问题可以转化为p型问题。
2001年初,IBM研究中心的科学家开发了一台只有五位的量子计算机,并成功地用它来计算寻序,这是实现肖尔算法的第一步。
经典计算机的存储容量可以用位数来衡量。它的运行速度可以由每秒的位转换次数决定。量子计算机也是如此,除了组成它们的最小信息单位不同于经典比特,而是前面描述的量子比特。
尽管量子计算机似乎有很大的潜力,但它们很难实现。增加量子位的数量并不容易!我们今天使用的便携式计算机至少有几十亿比特的硬盘存储空间。然而,如前所述,IBM研究中心开发了一种只有五位的量子计算设备,这引起了轰动。
如前几节所述,量子计算设备的潜力来源于量子系统不与环境交互时的不确定性。一旦与环境相互作用,量子设备将崩溃到某个状态,计算无法进行。难点在于如何将量子计算系统从其环境中分离出来,使其既能保持独立的计算能力,又需要可访问性,以便人们能够控制计算过程并获得输出结果。
实现上述环境非常困难。这就是为什么直到最近十年,只有几个实验室和几个带有十几个量子位的计算设备被实现。其中一些设备是基于核磁共振(类似于成像中使用的磁共振成像)的实验。在实验中,核磁共振机核心被喷洒了一些流体化的有机液体,然后液体被射频脉冲激发以将其转换成高速处理器,并且解决该问题的算法被编码成射频脉冲。有些是基于三维超导量子位的计算设备。
下图显示了IBM的3比特硅芯片。
(比例尺:8毫米x 4毫米)
这些照片来自互联网,参考了国际商用机器公司的最新报告。
2011年5月,一匹黑马冲出了量子计算机领域。加拿大的D-波公司宣布,它已经建造了第一台128比特的“商用量子计算机”——D-波-1。据说它还以1000万美元的天价卖给了美国的洛克希德·马丁公司。消息一发布,就在业界引起了轩然大波。许多量子计算机专家质疑D-Wave-One能否被称为真正的“量子计算机”?
D-Wave声称他们的超导绝热量子计算机使用了所谓的“量子退火算法”,这种算法可以比经典算法更有效地解决离散优化问题。然而,它只能解决这个特殊目的的问题。因此,当然,它不是一般意义上的量子计算机。有些人认为费曼提到的模拟机器最多只能解决某种问题。至于这个模拟过程的量子组成,还不清楚。在他们的博客页面上,有一些关于“离散优化问题”等的流行描述,感兴趣的读者可以阅读:
http://dwave . WordPress . com/2011/05/11/learning-to-program-the-d-wave-one/
要实现通用量子计算、满足不同的计算要求、运行各种量子算法、实现输入、输出、保持量子相干态和纠缠态以实现可靠的计算是极其困难的。此外,量子计算的纠错问题也很难解决。专家认为,要制造一台通用可靠的量子计算机,还有很长的路要走。
即使是亲自进行实验的专家,也很难从他们现在进行的实验中描述和想象量子计算机的未来形态。因此,科学家们一直在关注物理学的新领域,并提出各种各样的想法:超导性不能被利用吗?也许是固态核磁共振?也许用激光捕获的冷却离子?也许量子计算机不应该像经典计算机那样用人工技术制造,而是应该与生物工程和基因研究结合起来?事实上,生物体的生长过程已经证明,自然本身已经完成了人类想要人工实现的目标中最困难的部分。在生物中,普通分子已经根据量子定律进行了最复杂的计算。量子计算机已经存在于自然界。为什么人类应该做不止一件事?当然,科学家和工程师总是在探索物质的奥秘,开发更先进的技术和制造新事物。他们永远不会放弃。
上一篇:细菌蛋白能当领鞭虫“春药”
下一篇:自闭症干预措施首次表现出持久益处