1、量子计算机发展简史量子计算机发展简史原著：Simon Bone & Matias Castro翻译：bianca 2003年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.2Gr
2、over算法4.3量子机械系统的模拟5.量子通讯5.1量子通讯是如何工作的5.2量子比特的任务6.当今进展及未来展望7.结论8.术语表9.参照表9.1书籍9.2人物9.3杂志文章9.4网页1.介绍经常会有能使计算机的性能大大改善的新技术出现。从晶体管技术的引进，到超大规模集成电路的持续性发展，科技进步的速度总是如此无情。近日来，现代处理器中晶体管体积的减小成为计算机性能改进的关键所在。然而，这种不断的减小并不能够持续很长的时间。如果晶体管变得太小，那种对量子机械的未知影响将会限制它的性能。因此，看起来这些影响会限制我们的计算机技术，它们真的会吗？ 在1982年，诺贝尔奖获得者物理学家Richa
3、rd Feynman想出了 “量子计算机” 的概念，那是一种利用量子机械的影响作为优势的计算机。有一段时间，“量子计算机”的想法主要仅仅停留在理论兴趣阶段，但最近的发展令这个想法引起了每一个人的注意。其中一个进步就是一种在量子计算机上计算大量数据的算法的发明，由Peter Shor(贝尔实验室)设计。通过使用这种算法，一台量子计算机破解密码可以比任何普通(典型)计算机都要快。事实上，一台能够实现Shor算法的量子计算机能够在大约几秒内破解当今任何密码技术。在这种算法的推动下，量子计算机的话题开始集中在动力上，全世界的研究人员都争当第一个制造出实用量子计算机的人。1.1量子计算机的基本要素在计算
4、机的经典模型中，最基础的构建要素比特，只能存在于两种截然不同的状态之一：0或是1。在量子计算机中，规则改变了。一个原子比特经常被简称为 “量比”(quantum bit) 不仅仅存在于传统的0和1状态中，还可以是一种两者连续或重叠状态。当一个量比处于这种状态时，它可以被认为存在于两种领域中：一种为0，而另外一种为1。一个基于这种量比的操作能够同时有效地影响两个值。因此，极为重要的一点是：当我们在量比上实行单一操作时，我们是在针对两种不同的值进行的。类似的，一个双量比系统能对4个值进行操作，而一个三量比系统就是8个值。因此，增加量比的数目能够以指数方式增加我们从系统获得的“量子并行效应”(量子并
5、行效应)。在拥有正确算法类型的情况下，它能通过这种并行效应以远低于传统计算机所花费的时间内解决特定的问题。 1.2量子计算机的缺点(电子)脱散性使量子计算机如此强大的关键要点是，它对受量子机械规律决定的奇异的亚原子事件的依赖，而这也使它非常脆弱和难以控制。例如，假想一个处于连续状态的量比。一旦它和环境发生了可调节的相互影响，它就将脱散并落入两种传统状态中的一种，这就是脱散性问题。它已经成为了量子计算机作为建立在由连续性状态所带来的量子并行效应上的潜在力量的绊脚石。这个问题很复杂，即使只是看看量比也会引起它的脱散，这使从一台量子计算机获得结果的过程像量子计算机自己做运算一样难。 1.3取得结果当
6、一个利用量子并行效应的计算执行后，不同的领域将会得到许多不同的结果。事实上，我们只能通过关注各种结果之间的冲突来获得一个计算的结果。值得注意的是：关注一台量子计算机的结果(或者任何中间状态)将会阻止任何不同版本之间进一步冲突的发生。例如，可以阻止任何有用的量子计算继续进行。这种冲突可以用一个简单的例子来表明：在托马斯.杨(Young)的双缝干涉试验中，光通过两条平行细缝照向屏幕。展现在屏幕上的明暗条纹的图案是相长和相消的结果。用类似的方法，每种状态的计算结果都相长和相消出一个可以测量的结果。这个结果对于不同的算法有着不同的重要性，并且可以用于手工推算问题结果(例如：见Shors algorit
7、hm - An example)。图1 托马斯.杨(Young)的双缝干涉试验演示了光子的干涉。2.通用计算的理论所有计算机，从Charles Babbage的分析解析机(analytical engine)(1936)到建立在PC基础上的Pentium(tm)，它们的共性之一，是在Alan Turing的著作中所阐述的古典计算理论。事实上，Turing的著作描述了通用的图灵机的概念，一种非常简单的计算机模型，它能够被设计用来执行任何被自然地认为可计算的操作。所有的计算机都必然能够实现通用图灵机。尽管它们中的有些可能比其它的更快、更大或更昂贵，但它们在功能上是相同的，它们都能执行同样的计算任务
8、。2.1加热流失的信息大量的时间都被花费在研究量子理论是否在计算机器上设置了基本限制。结论是，现在普遍相信：物理学并未在计算机器速度、可靠性和记忆容量上设置任何绝对的限制。然而，有一点需要考虑的是，信息可能在计算过程中被丢失。为了使一台计算机能够运行得快，它的操作必须是可逆的。(例如，它的输入必须完全可以从它的输出推出来)。这是因为不可逆的计算将会引起一种可换算成熵的信息的丢失，因此，系统散热的有限能力将会反过来限制计算机的性能。一个信息丢失的例子是一种常见的与门。一个与门有两个输入而只有一个输出，这就意味着在从输入门移动到输出门的过程中，我们损失了一比特的信息。1976年，Charles B
9、ennett证明了可以利用非门建立一种通用计算机，这种计算机在表示具有原始可逆操作的程序时不会降低它的速度。而有一种合适而且通用的非门可以用来制造计算机Toffoli门(见图2)。图2Toffoli门的输入是完全可以从它的输出推断出来的。2.2通用量子计算机Church-Turing理论：“存在或者可以制造一种计算机，这种计算机能够被设计进行任何自然物体能够进行的计算。”在量子计算理论中，已经取得了一系列重大进步。第一个是由Richard Feynman在1982年发现的：一个简单级别的通用模拟器能够模拟任何既定的自然物体的行为。1984年，David Albert做出了第二个发现：他描述了一
10、种“自我调节量子机器人”，这种机器人能够执行任何传统计算机都无法模仿的任务。通过指导这种机器人进行自我调节，它能够获得仅靠从外界环境进行度量绝对无法获得的“主观”信息。最后而且可能也是最重要的发现是由David Deutsch在1989年做出的，他证明了所有既定计算机的计算能力遵从于量子计算机的规则，一种可以从一台单一的通用量子计算机中获得的规则。这种计算机可以通过Toffoli门的量子等价以及添加一些能够带来0和1状态的线性重叠的操作来实现。这样，一台通用量子计算机就完成了。这个发现需要对Church-Turing理论：“存在或者可以建造一种计算机，这种计算机能够被设计进行任何自然物体能够进
11、行的计算。”进行一点调整。2.3人工智能量子计算理论和人工智能领域有一些有趣的联系。对于一台计算机是否真的能实现人工智能的争论已经持续了数年，并且很大程度上是哲学的争论。那些反对这种观点的人解释说：人类的思想，即使只是在理论上，也不可能在图灵机上实现的。量子计算理论允许我们从一个有些微不同的视角来看待意识问题。首先值得注意的是，任何自然物体，从一块岩石到整个宇宙，都可以被看做是一台量子计算机；而任何可察觉的自然过程都可以被视为一种计算。在这些标准下，大脑可以作为一台计算机而意识就是一种计算。争论的下一个阶段主要是基于Church-Turing理论，并且证明：因为每一台计算机在功能上都是等价的，
12、每台既定的计算机一定能模仿其它的计算机，所以用一台量子计算机模仿意识理性思维必然是可能的。一些人相信量子计算机是突破人工智能问题的关键所在，但是另外一些人不同意。牛津大学的Roger Penrose认为，意识需要一种更奇特的(也是未知的)物理学。3.建立一台量子计算机一台量子计算机在设计上没有什么类似传统计算机，例如你不能使用晶体管和二极管。为了制造一台计算机就需要产生一种新的技术，一种能使“量比”在0和1之间以连贯重叠的状态存在的技术。尽管实现这个目标的最优方法仍然是未知的，但已有许多方法在实验中，并被证明取得了不同程度的成功。3.1量子点一个量比执行的范例是“量子点”，它基本上是一个被困在
13、原子牢笼中的单一电子。当量子点暴露在刚好合适波长的激光脉冲下并持续一段时间，电子就会达到一种激发态：而第二次的激光脉冲又会使电子衰落回它的基态。电子的基态和激发态可以被视为量比的0和1状态，而激光在将量比从0状态撞击到1状态或从1撞击到0的应用，能够被看成是一种对取非功能的控制。如果激光持续时间只有取非功能要求的一半，那么电子将同时处于基态和激发态的重叠中，这也等价于量比的连贯性状态。而更多复杂的逻辑功能可以通过使用成对的安排好的量子点被模拟出来。因此，看起来量子点是一个合适的建造量子计算机的候选人。然而不幸的是，有许多实际问题阻止了这种情况的发生：1.电子在衰落回基态之前只能在激发态维持一微
14、秒(百万分之一秒)。需要记住的是，每种激光脉冲需要持续的时间大约是1纳秒。这就对在信息散失前所能做出的运算步骤的数量有了限制。2.构建量子点是一个非常艰难的过程，因为它们如此微?桓龅湫偷牧孔拥阒本督鲇?0个原子(1纳米)。而使用这些量子点制造一台计算机的技术到目前为止还不存在。3.为了避免数以千计的激光射入一个狭小的空间，量子点应当制造以回应不同频率的光。一束能够可靠地进行自我调整的激光将会选择性地瞄准有着不同光频率特性的不同组别的量子点。又一次的，这是一项还不存在的技术。3.2计算流体量子点并不是唯一的经过试验的执行量比，其它技术试图使用个体原子或激光的分化作为信息的媒体，而脱散性是这些技术
15、的普遍问题。人们尝试将这些实验从它们周围环境屏蔽起来，例如在千分之一的绝对零度的温度下将其冷却，然而这些方法在减少这个问题的影响方面取得了极其有限的成功。量子计算领域的最新发展采用了一个根本性的新方法。这种方法放弃了量子媒质应当小并且和它的周围环境隔离的假设，而是使用大量的分子来储存这些信息。当处于磁场中时，一个分子中的每个核子都会在一个特定方向上的旋转，这个旋转特性可以用来描述它的状态，上旋表示1而下旋代表0。核子磁性共振技术可以被用来检测这些旋转状态，特殊无线电波脉冲能够把核子从上旋(1)撞击到下旋(0)，反之亦然。使用这种技术的量子计算机本身就是一个分子，而它的量比就是分子内的那些核子。
16、但是这种技术并不能只使用一个单一分子来实现这些计算，而是用一整“杯”流体分子。这种方法的优势在于，即使液体分子彼此撞击，每个分子中核子的旋转状态仍能保持不变。脱散性仍然是一个问题，但是到目前为止，在这种技术中脱散前的时间已经比任何其它技术的时间要长许多。研究人员相信，几千个原始逻辑操作能够在量比脱散前实现。麻省理工学院的Dr.Gershenfield，是流体计算技术的倡导者之一。他的研究队伍已经能够将1和1加起来，这是一个远远超越其它任何正在研究中的技术能力的简单任务。而能够计算更复杂任务的关键在于拥有更多的原比，但是这要求更多复杂的分子以及大量的核子，因此咖啡因分子成为一个可能的候?蘼壅庵址
17、肿邮鞘裁矗?0量比系统的进步都是显而易见的。Dr.Gershenfield希望这样一个系统在年底，将能够乘以数字15。超过10量比系统的进步可能会更加困难。在一个给定的“计算流体”样本中，将会有大约偶数个上下旋状态，但是将会有一点在超过一个方向上的旋转存在。正是这些少量额外旋转的所发出的表现得好像它是一个单一分子的信号，使它能够被检测出来以及进行运算操作，而剩下的旋转将会有力地彼此抵消掉。这种信号相当微弱，并且在每个量比被加入的时候，以大约2倍的速度持续性减弱。这就会限制一个系统可能拥有的量比的数目，而易读的输出将会更难以检测出来。4.量子计算机的应用非常需要注意的是，一台量子计算机并不一定在
18、所以计算任务上都会比一台传统计算机做得好。例如，乘法运算在一台量子计算机上执行的不比在一台类似的传统计算机上快。为了显示量子计算机的优越性，就需要使用开发量子并行效应能力的算法。这些算法难以阐述，而值得记住的最显著理论化的算法当属Shor的算法和Grover的算法。通过使用好这些算法，量子计算机能够大大优于传统计算机。例如，Shor算法允许以极快的速度因式分解大数字。一台传统计算机在分解1000位阿拉伯数字时需要花费10,000,000,000,000,000,000,000,000年，而一台量子计算机只需大约20分钟。4.1Shor算法Shor的算法一个范例这是Peter Shor在1995
19、年发明的算法，它能够快速地分解大数字。如果它曾经被使用过，它将会对密码系统有着深刻的影响，它会威胁到由公钥密码学所提供的安全性(例如RSA)。受到威胁公钥密码学这是当前最常用的发送密码数据的方法。它通过使用两把密钥来工作，一把公开的，一把私人的。公开的密钥用来给数据加密，而私人的密钥用来解密。公开的密钥可以容易地从私人的密钥获得，而反之却不可能。然而，一个掌握着你公开密钥的窃听者原则上可以计算出你的私人密钥，因为它们在数学上是相联系的。为了破解私人密钥，需要分解公开密钥，然而这项任务被认为是无法处理的。例如，1234乘以3433容易算出来，但计算4236322的因子就不那么容易了。分解一个数的
20、质因子的计算复杂度随该数增长而迅速膨胀。破解RSA129(有129位阿拉伯数字)时，花费了1600位因特网用户8个月的时间。密码破译着认为，更多的数字应当被加到密钥中以抵抗计算机性能的增长(这将花费比宇宙年龄还长的时间来计算RSA140)。然而，对于使用运行Shor算法的一台量子计算机，密钥中的阿拉伯数字个数对问题的难度有着极小的影响。破译RSA140只需花费几秒钟的时间。Shor算法一个范例这部分的目的是说明Shor算法有关的基本步骤。为了使问题相对简单易懂，我们将考察找到数字15的质因子问题。因为算法主要由三步组成，讲解将会分为3个阶段.阶段1算法的第一个阶段是将记忆寄存器放入一段它所有可
21、能状态的连贯重叠中。字母“Q”将会用来表示一个处于连贯状态的量比。图3 一个3量比寄存器可以同时表示8个传统状态当一个量比处于连贯状态中，它可以被认为存在于两个不同的领域中。它作为“1”存在于一个领域中，而在另一个领域中，以“0”存在(见图1)。将这种想法扩展到3比特寄存器，我们可以想像为寄存器存在于8种不同的领域，在每个领域都可以表现一种传统的状态(例如，000, 001, 010, 011, 100, 101, 110, 111)。为了储存数字15，需要一个4比特的寄存器(能够同时在连贯状态下表现数字0到15)。在寄存器上执行的计算可以被当做并行的一整组计算，每个领域一个。事实上，一个在寄
22、存器上执行的计算是执行在寄存器所能够表现的所有可能值上的。阶段2第二个阶段的算法使用寄存器执行一个运算。运算细节如下：1.数字N是我们希望分解的，N=15。2.挑选一个随机数N，1XN-1。3.X达到存放在寄存器(寄存器A)中的大小，然后除以N。4.这个操作的余数被放在第二个位寄存器中(寄存器B)。图4 第二阶段的操作这个操作之后，寄存器B包含有各个领域结果的叠加。这可以通过一个例子来极好的证明：如果我们令X为2，那么寄存器B中对应于寄存器A中的每个可能值的内容如下。表格1 寄存器B的内容，N=15, X=2。注意到寄存器B的内容符合一个重复的序列(1,2,4,8,1,2,4,8.)，而这些重
23、复的频率可以被称作f。在当前这种情况下，重复的频率(1, 2, 4, 8)有4个值，所以f=4。阶段3最后一个阶段可能是最难以理解的。重复的频率，f，在使用一台量子计算机时将会被发现，这是通过在寄存器B上执行一个复杂的操作，然后察看那些引起每个领域的结果彼此干扰的内容实现的。作为f的结果而发生的值在接下来的等式中被使用，以计算一个可能的质因子。图5 用来计算质因子的等式结果数字并不能保证它是一个质因子，但是是的可能性很大。而生成f值的干扰容易使正确答案作为不正确的答案而互相抵消掉。在我们的例子中，f=4的值确实给出了一个正确的结果3。答案并不能保证正确的事实并不重要，因为它可以通过乘法很容易地
24、检查出来。如果答案是错误的，用不同的X值重复上述计算将会很有可能得到正确的解。4.2Grover算法Lov Grover曾经写过一个算法，使用量子计算机用比传统计算机快的速度检索一个未排序的数据库通常，这需要花费N/2个数字的时间来在一个具有N个入口的数据库中搜索发现一个特定的入口。Grover的算法使在N叉检索中进行相同的搜索变得可能。随着数据库的规模和综合程度增长，这种时间上的节省变得具有显著意义。这种算法所带来的加速是量子并行结构的结果。数据库有效地分布在大量的领域，并且允许一次单一的搜索定位要求的入口。更多数量的操作(与叉N成比例)要求实现，以满足显示一个可读结果的要求。Grover的
25、算法在密码系统领域有着重要的应用。使用这种算法破解数据加密标准(DES)，一种用来保护银行间的经济事务及其它事物的标准，在理论上是可能的。这个标准是建立在一个双方都事先知道的56-比特的数字的基础上的，这个数字被用作加密和解密数据的密钥。如果一个加密文档及它的原始资料都可以获得，那么就可能找到那个56-比特的密钥。一个使用传统方式的穷举搜索必须在找到正确解前搜索2的55次方个密钥。即使每秒钟尝试10亿个密钥，也需要花费超过一年的时间，而相比较而言Grover的算法找到密钥只需185次检索。对于传统的DES，一种阻止现代计算机破解密码的方法(例如，如果计算机越来越快)，仅仅只要在密钥上添加额外的
26、数字，就会使搜索的次数呈指数增长。然而，这对于量子算法速度的影响是可以忽略不计的。4.3量子机械系统的模拟1982年，Feynman推测说，量子计算机将能够比传统计算机更大程度地精确模拟量子机械系统。据推测，一台拥有几十个量子比特的量子计算机能够进行模拟，而这对于一台传统计算机来说，所需的时间是不现实的。这应当归因于计算机时间和内存的使用是按照讨论中的量子系统的规模呈指数增长的。对于传统计算机，一个量子系统的动力学可以用近似值模拟。然而，一台量子计算机能够被“设计”，通过诱使它的变量发生交互作用来模拟一个系统的行为。它们模拟了正在讨论中的系统特性。例如，一台量子计算机能够模拟“笋瓜模型”(一种
27、描述电子在晶体中移动的模型)，而这样的任务是超出当今传统计算机的工作范围的。5.量子通讯在量子计算方面的研究开创了无旋转领域的量子沟通。这部分研究的目标是通过使用量子机械影响的特性，提供安全可靠的通讯设施。5.1量子通讯是如何工作的量子通讯利用光的偏振(例如，一个光子振动的方向)对数据进行编码。在一个方向上的振动可以被视为0，而另一个为1。常用的有两种偏振方式，直线型和对角型(见图6)。图6 光的偏振可以被用来对数据进行编码。为了接收数据，滤光器的偏振化方向必须与光子的相匹配。量子通讯开发的特性是，为了接收正确的信息，必须测量光子并使用正确的滤光器偏振方向。例如，和信息传送的偏振方向相同。如果
28、一个接收器是处于直线型的偏振方向，那么就会发射出对角偏振的光子，然后一个完全随机的结果就会出现在接收器上。使用这种方法，特性信息能够发送而使窃听者无法不被发现地偷听。这种机械装置工作原理如下：1.发送者用随机偏振方式传送信息至接收者。2.接收者检测这个信息并记录下来(仍然使用随机偏振方式)。3.然后，发送者通过公共线路通知接收者他所使用的偏振方式。4.接收者和发送者对在正确偏振方式下获得的信息进行随机选取，进行比较。5.如果一个窃听者中途截取并转寄信息，那么错误发生的比率将会比预期的要高，这就会引起接收者和发送者的警觉。6.如果检测出窃听者，那么整个过程将会被重复。例如，假设有一个发送者叫Al
29、ice，她希望传送信息给Bob而不希望被窃听者Eve听到。他们就会遵循上述步骤。如果Eve试图偷听，她就需要测量来自Alice的比特，然后再转寄给Bob(她不能仅仅察看信息，因为这样做会改变信息内容)。她必须使用随机偏振方式，因为她不知道Alice所使用的。可能，Eve会接收到50%的正确信息，而另外的50%由随机的值组成。而大约一半的随机值是正确的，这意味着Eve最好情况下可以将75%的正确信息发送给Bob。假设通讯线路上的噪音是可以忽略的，Bob将能够检测出Eve偷听了，因为他按照正确的偏振方向所收到的信息包含超过25%的错误。他通过和Alice在公共线路上对随机选取的信息进行比较以检测错
30、误。另外一种Eve搅乱Bob和Alice通讯的方法是中途截取信息，再将她自己的发送出去。Alice和Bob讨论的一组随机选择的值将会阻碍Eve，并暴露出Eve修改了信息。无论Eve截取的信号有多么微小，Alice和Bob总能够发现她在线上偷听。这个系统只能在通讯线路的噪音可以忽略的情况下工作。如果线路有，例如25%的噪音，就无法将窃听者从噪音中区分出来。英国电信已经成功地实现了在超过10公里的距离上只有9%的错误的线路，这为量子通讯提供了一个具有希望的未来。5.2量子比特的任务一个量子通讯不同的方法是量子比特的任务。使用这种方法，人们可以比较或结合信息，同时保持每个独立文献的隐秘性。这种技术的
31、一个可能应用是合同出价(令公司提出它们最可能的出价，而不仅仅是比最高价位高)。这种方法的基本操作如下：1.Alice向Bob发送出一串光子，所有这些光子都具有相同的偏振方式。2.Bob接收到这些光子，随机地改变他的偏振方式，然后记录下结果。3.当Bob的偏振方式和Alice的相同时，通过告知他他所见的1和0的形式，Alice能够向Bob证明她所发出的信息。这个系统的缺点是，Alice能够通过创建成对的光子而只向Bob发送一个来进行作弊。这些配对的光子有着奇怪的量子特性，无论它们分开多远，对一个的观察将会影响到令一个在接收者面前的样子。Alice可以通过修改她手中的副本来改变Bob的光子。研究者
32、们已经发现这个问题一段时间了，而 Mayor 最近证明了，这是所有量子比特系统的一个普遍缺点。6.当今进展及未来展望最近，在“流体计算”技术方面由Dr.Gershenfield和Dr.chuang(Los Alamos国家实验室，新墨西哥州)领导的工作给予量子计算一个有前景的未来。事实上，Dr.Gershenfield相信，如果现在进步的速度持续下去的话，在不到10年的时间内，量子联合处理器将会变成现实。其它技术，例如量子点，当我们的技术进步后，可能会产生出类似的结果。而乐观者指出，现在研究人员所试验的问题看起来像是技术问题而不是根本性问题。尚未解决，并且许多人，包括IBM公司托马斯.沃森研究中心的Rolf Landauer，认为量
