量子计算机发展简史

量子计算机发展简史原著：SimonBone&MatiasCastro翻译：bianca2003年3月26日内容摘要听起来好像有点奇怪，计算机的未来可以被建筑在一杯咖啡周围。那些咖啡因分子恰巧是构建“量子计算机”－－一种能够保证提供可在几秒钟内破解密码的思想回应功能的新型计算机的可能组成部件。内容目录1.介绍1.1量子计算机的基本要素1.2量子计算机的缺点－－(电子)脱散性1.3取得结果2.通用计算的理论2.1加热流失的信息2.2通用量子计算机2.3人工智能3.建立一台量子计算机3.1量子点3.2计算流体4.量子计算机的应用4.1Shor算法－－Shor的算法－－一个范例4.2Grover算法4.3量子机械系统的模拟5.量子通讯5.1量子通讯是如何工作的5.2量子比特的任务6.当今进展及未来展望7.结论8.术语表9.参照表9.1书籍9.2人物9.3杂志文章9.4网页1.介绍经常会有能使计算机的性能大大改善的新技术出现。从晶体管技术的引进，到超大规模集成电路的持续性发展，科技进步的速度总是如此无情。近日来，现代处理器中晶体管体积的减小成为计算机性能改进的关键所在。然而，这种不断的减小并不能够持续很长的时间。如果晶体管变得太小，那种对量子机械的未知影响将会限制它的性能。因此，看起来这些影响会限制我们的计算机技术，它们真的会吗？在1982年，诺贝尔奖获得者－－物理学家RichardFeynman想出了“量子计算机”的概念，那是一种利用量子机械的影响作为优势的计算机。有一段时间，“量子计算机”的想法主要仅仅停留在理论兴趣阶段，但最近的发展令这个想法引起了每一个人的注意。其中一个进步就是一种在量子计算机上计算大量数据的算法的发明，由PeterShor(贝尔实验室)设计。通过使用这种算法，一台量子计算机破解密码可以比任何普通(典型)计算机都要快。事实上，一台能够实现Shor算法的量子计算机能够在大约几秒内破解当今任何密码技术。在这种算法的推动下，量子计算机的话题开始集中在动力上，全世界的研究人员都争当第一个制造出实用量子计算机的人。1.1量子计算机的基本要素在计算机的经典模型中，最基础的构建要素－－比特，只能存在于两种截然不同的状态之一：0或是1。在量子计算机中，规则改变了。一个原子比特－－经常被简称为“量比”(quantumbit)－－不仅仅存在于传统的0和1状态中，还可以是一种两者连续或重叠状态。当一个量比处于这种状态时，它可以被认为存在于两种领域中：一种为0，而另外一种为1。一个基于这种量比的操作能够同时有效地影响两个值。因此，极为重要的一点是：当我们在量比上实行单一操作时，我们是在针对两种不同的值进行的。类似的，一个双量比系统能对4个值进行操作，而一个三量比系统就是8个值。因此，增加量比的数目能够以指数方式增加我们从系统获得的“量子并行效应”(量子并行效应)。在拥有正确算法类型的情况下，它能通过这种并行效应以远低于传统计算机所花费的时间内解决特定的问题。1.2量子计算机的缺点－－(电子)脱散性使量子计算机如此强大的关键要点是，它对受量子机械规律决定的奇异的亚原子事件的依赖，而这也使它非常脆弱和难以控制。例如，假想一个处于连续状态的量比。一旦它和环境发生了可调节的相互影响，它就将脱散并落入两种传统状态中的一种，这就是脱散性问题。它已经成为了量子计算机作为建立在由连续性状态所带来的量子并行效应上的潜在力量的绊脚石。这个问题很复杂，即使只是看看量比也会引起它的脱散，这使从一台量子计算机获得结果的过程像量子计算机自己做运算一样难。1.3取得结果当一个利用量子并行效应的计算执行后，不同的领域将会得到许多不同的结果。事实上，我们只能通过关注各种结果之间的冲突来获得一个计算的结果。值得注意的是：关注一台量子计算机的结果(或者任何中间状态)将会阻止任何不同版本之间进一步冲突的发生。例如，可以阻止任何有用的量子计算继续进行。这种冲突可以用一个简单的例子来表明：在托马斯.杨(Young)的双缝干涉试验中，光通过两条平行细缝照向屏幕。展现在屏幕上的明暗条纹的图案是相长和相消的结果。用类似的方法，每种状态的计算结果都相长和相消出一个可以测量的结果。这个结果对于不同的算法有着不同的重要性，并且可以用于手工推算问题结果(例如：见Shor'salgorithm-Anexample)。图1托马斯.杨(Young)的双缝干涉试验演示了光子的干涉。2.通用计算的理论所有计算机，从CharlesBabbage的分析解析机(analyticalengine)(1936)到建立在PC基础上的Pentium(tm)，它们的共性之一，是在AlanTuring的著作中所阐述的古典计算理论。事实上，Turing的著作描述了通用的图灵机的概念，一种非常简单的计算机模型，它能够被设计用来执行任何被自然地认为可计算的操作。所有的计算机都必然能够实现通用图灵机。尽管它们中的有些可能比其它的更快、更大或更昂贵，但它们在功能上是相同的，它们都能执行同样的计算任务。2.1加热流失的信息大量的时间都被花费在研究量子理论是否在计算机器上设置了基本限制。结论是，现在普遍相信：物理学并未在计算机器速度、可靠性和记忆容量上设置任何绝对的限制。然而，有一点需要考虑的是，信息可能在计算过程中被丢失。为了使一台计算机能够运行得快，它的操作必须是可逆的。(例如，它的输入必须完全可以从它的输出推出来)。这是因为不可逆的计算将会引起一种可换算成熵的信息的丢失，因此，系统散热的有限能力将会反过来限制计算机的性能。一个信息丢失的例子是一种常见的与门。一个与门有两个输入而只有一个输出，这就意味着在从输入门移动到输出门的过程中，我们损失了一比特的信息。1976年，CharlesBennett证明了可以利用非门建立一种通用计算机，这种计算机在表示具有原始可逆操作的程序时不会降低它的速度。而有一种合适而且通用的非门可以用来制造计算机－－Toffoli门(见图2)。图2Toffoli门的输入是完全可以从它的输出推断出来的。2.2通用量子计算机Church-Turing理论：“存在或者可以制造一种计算机，这种计算机能够被设计进行任何自然物体能够进行的计算。”在量子计算理论中，已经取得了一系列重大进步。第一个是由RichardFeynman在1982年发现的：一个简单级别的通用模拟器能够模拟任何既定的自然物体的行为。1984年，DavidAlbert做出了第二个发现：他描述了一种“自我调节量子机器人”，这种机器人能够执行任何传统计算机都无法模仿的任务。通过指导这种机器人进行自我调节，它能够获得仅靠从外界环境进行度量绝对无法获得的“主观”信息。最后而且可能也是最重要的发现是由DavidDeutsch在1989年做出的，他证明了所有既定计算机的计算能力遵从于量子计算机的规则，一种可以从一台单一的通用量子计算机中获得的规则。这种计算机可以通过Toffoli门的量子等价以及添加一些能够带来0和1状态的线性重叠的操作来实现。这样，一台通用量子计算机就完成了。这个发现需要对Church-Turing理论：“存在或者可以建造一种计算机，这种计算机能够被设计进行任何自然物体能够进行的计算。”进行一点调整。2.3人工智能量子计算理论和人工智能领域有一些有趣的联系。对于一台计算机是否真的能实现人工智能的争论已经持续了数年，并且很大程度上是哲学的争论。那些反对这种观点的人解释说：人类的思想，即使只是在理论上，也不可能在图灵机上实现的。量子计算理论允许我们从一个有些微不同的视角来看待意识问题。首先值得注意的是，任何自然物体，从一块岩石到整个宇宙，都可以被看做是一台量子计算机；而任何可察觉的自然过程都可以被视为一种计算。在这些标准下，大脑可以作为一台计算机而意识就是一种计算。争论的下一个阶段主要是基于Church-Turing理论，并且证明：因为每一台计算机在功能上都是等价的，每台既定的计算机一定能模仿其它的计算机，所以用一台量子计算机模仿意识理性思维必然是可能的。一些人相信量子计算机是突破人工智能问题的关键所在，但是另外一些人不同意。牛津大学的RogerPenrose认为，意识需要一种更奇特的(也是未知的)物理学。3.建立一台量子计算机一台量子计算机在设计上没有什么类似传统计算机，例如你不能使用晶体管和二极管。为了制造一台计算机就需要产生一种新的技术，一种能使“量比”在0和1之间以连贯重叠的状态存在的技术。尽管实现这个目标的最优方法仍然是未知的，但已有许多方法在实验中，并被证明取得了不同程度的成功。3.1量子点一个量比执行的范例是“量子点”，它基本上是一个被困在原子牢笼中的单一电子。当量子点暴露在刚好合适波长的激光脉冲下并持续一段时间，电子就会达到一种激发态：而第二次的激光脉冲又会使电子衰落回它的基态。电子的基态和激发态可以被视为量比的0和1状态，而激光在将量比从0状态撞击到1状态或从1撞击到0的应用，能够被看成是一种对取非功能的控制。如果激光持续时间只有取非功能要求的一半，那么电子将同时处于基态和激发态的重叠中，这也等价于量比的连贯性状态。而更多复杂的逻辑功能可以通过使用成对的安排好的量子点被模拟出来。因此，看起来量子点是一个合适的建造量子计算机的候选人。然而不幸的是，有许多实际问题阻止了这种情况的发生：1.电子在衰落回基态之前只能在激发态维持一微秒(百万分之一秒)。需要记住的是，每种激光脉冲需要持续的时间大约是1纳秒。这就对在信息散失前所能做出的运算步骤的数量有了限制。2.构建量子点是一个非常艰难的过程，因为它们如此微?Ｒ桓龅湫偷牧孔拥阒本督鲇?0个原子(1纳米)。而使用这些量子点制造一台计算机的技术到目前为止还不存在。3.为了避免数以千计的激光射入一个狭小的空间，量子点应当制造以回应不同频率的光。一束能够可靠地进行自我调整的激光将会选择性地瞄准有着不同光频率特性的不同组别的量子点。又一次的，这是一项还不存在的技术。3.2计算流体量子点并不是唯一的经过试验的执行量比，其它技术试图使用个体原子或激光的分化作为信息的媒体，而脱散性是这些技术的普遍问题。人们尝试将这些实验从它们周围环境屏蔽起来，例如在千分之一的绝对零度的温度下将其冷却，然而这些方法在减少这个问题的影响方面取得了极其有限的成功。量子计算领域的最新发展采用了一个根本性的新方法。这种方法放弃了量子媒质应当小并且和它的周围环境隔离的假设，而是使用大量的分子来储存这些信息。当处于磁场中时，一个分子中的每个核子都会在一个特定方向上的旋转，这个旋转特性可以用来描述它的状态，上旋表示1而下旋代表0。核子磁性共振技术可以被用来检测这些旋转状态，特殊无线电波脉冲能够把核子从上旋(1)撞击到下旋(0)，反之亦然。使用这种技术的量子计算机本身就是一个分子，而它的量比就是分子内的那些核子。但是这种技术并不能只使用一个单一分子来实现这些计算，而是用一整“杯”流体分子。这种方法的优势在于，即使液体分子彼此撞击，每个分子中核子的旋转状态仍能保持不变。脱散性仍然是一个问题，但是到目前为止，在这种技术中脱散前的时间已经比任何其它技术的时间要长许多。研究人员相信，几千个原始逻辑操作能够在量比脱散前实现。麻省理工学院的Dr.Gershenfield，是流体计算技术的倡导者之一。他的研究队伍已经能够将1和1加起来，这是一个远远超越其它任何正在研究中的技术能力的简单任务。而能够计算更复杂任务的关键在于拥有更多的原比，但是这要求更多复杂的分子以及大量的核子，因此咖啡因分子成为一个可能的候?Ｎ蘼壅庵址肿邮鞘裁矗?0量比系统的进步都是显而易见的。Dr.Gershenfield希望这样一个系统在年底，将能够乘以数字15。超过10量比系统的进步可能会更加困难。在一个给定的“计算流体”样本中，将会有大约偶数个上下旋状态，但是将会有一点在超过一个方向上的旋转存在。正是这些少量额外旋转的所发出的表现得好像它是一个单一分子的信号，使它能够被检测出来以及进行运算操作，而剩下的旋转将会有力地彼此抵消掉。这种信号相当微弱，并且在每个量比被加入