>经常会有能使计算机的性能大大改善的新技术出现。从晶体管技术的引进，到超大规模集成电路的持续性发展，科技进步的速度总是如此无情。近日来，现代处理器中晶体管体积的减小成为计算机性能改进的关键所在。然而，这种不断的减小并不能够持续很长的时间。如果晶体管变得太小，那种对量子机械的未知影响将会限制它的性能。因此，看起来这些影响会限制我们的计算机技术，它们真的会吗？ 在1982年，诺贝尔奖获得者－－物理学家Richard Feynman想出了 “量子计算机” 的概念，那是一种利用量子机械的影响作为优势的计算机。有一段时间，“量子计算机”的想法主要仅仅停留在理论兴趣阶段，但最近的发展令这个想法引起了每一个人的注意。其中一个进步就是一种在量子计算机上计算大量数据的算法的发明，由Peter Shor(贝尔实验室)设计。通过使用这种算法，一台量子计算机破解密码可以比任何普通(典型)计算机都要快。事实上，一台能够实现Shor算法的量子计算机能够在大约几秒内破解当今任何密码技术。在这种算法的推动下，量子计算机的话题开始集中在动力上，全世界的研究人员都争当第一个制造出实用量子计算机的人。</P>>>>当一个利用量子并行效应的计算执行后，不同的领域将会得到许多不同的结果。事实上，我们只能通过关注各种结果之间的冲突来获得一个计算的结果。值得注意的是：关注一台量子计算机的结果(或者任何中间状态)将会阻止任何不同版本之间进一步冲突的发生。例如，可以阻止任何有用的量子计算继续进行。这种冲突可以用一个简单的例子来表明：在托马斯.杨(Young)的双缝干涉试验中，光通过两条平行细缝照向屏幕。展现在屏幕上的明暗条纹的图案是相长和相消的结果。用类似的方法，每种状态的计算结果都相长和相消出一个可以测量的结果。这个结果对于不同的算法有着不同的重要性，并且可以用于手工推算问题结果(例如：见Shor's algorithm - An example)。</P>: q+ \+ ?* c5 O7 `! I* e# ^8 ]& I>. m) W" }" M9 L- F/ }9 q><IMG src="http://www.frontfree.net/articles/pages/0000000724/young.gif"></P>>所有计算机，从Charles Babbage的分析解析机(analytical engine)(1936)到建立在PC基础上的Pentium(tm)，它们的共性之一，是在Alan Turing的著作中所阐述的古典计算理论。事实上，Turing的著作描述了通用的图灵机的概念，一种非常简单的计算机模型，它能够被设计用来执行任何被自然地认为可计算的操作。所有的计算机都必然能够实现通用图灵机。尽管它们中的有些可能比其它的更快、更大或更昂贵，但它们在功能上是相同的，它们都能执行同样的计算任务。</P>' i* D+ q7 I4 v6 B, E>大量的时间都被花费在研究量子理论是否在计算机器上设置了基本限制。结论是，现在普遍相信：物理学并未在计算机器速度、可靠性和记忆容量上设置任何绝对的限制。然而，有一点需要考虑的是，信息可能在计算过程中被丢失。为了使一台计算机能够运行得快，它的操作必须是可逆的。(例如，它的输入必须完全可以从它的输出推出来)。这是因为不可逆的计算将会引起一种可换算成熵的信息的丢失，因此，系统散热的有限能力将会反过来限制计算机的性能。一个信息丢失的例子是一种常见的与门。一个与门有两个输入而只有一个输出，这就意味着在从输入门移动到输出门的过程中，我们损失了一比特的信息。</P>>1976年，Charles Bennett证明了可以利用非门建立一种通用计算机，这种计算机在表示具有原始可逆操作的程序时不会降低它的速度。而有一种合适而且通用的非门可以用来制造计算机－－Toffoli门(见图2)。</P>>, o* ]8 G$ N5 L' s3 @& | align=left><IMG src="http://www.frontfree.net/articles/pages/0000000724/toffoli.gif"></P>9 L" Y% p0 m/ m- X0 {>Church-Turing理论：“存在或者可以制造一种计算机，这种计算机能够被设计进行任何自然物体能够进行的计算。”</P>7 P) J; q$ Q# u+ Q, j3 g>在量子计算理论中，已经取得了一系列重大进步。第一个是由Richard Feynman在1982年发现的：一个简单级别的通用模拟器能够模拟任何既定的自然物体的行为。1984年，David Albert做出了第二个发现：他描述了一种“自我调节量子机器人”，这种机器人能够执行任何传统计算机都无法模仿的任务。通过指导这种机器人进行自我调节，它能够获得仅靠从外界环境进行度量绝对无法获得的“主观”信息。最后而且可能也是最重要的发现是由David Deutsch在1989年做出的，他证明了所有既定计算机的计算能力遵从于量子计算机的规则，一种可以从一台单一的通用量子计算机中获得的规则。这种计算机可以通过Toffoli门的量子等价以及添加一些能够带来0和1状态的线性重叠的操作来实现。这样，一台通用量子计算机就完成了。这个发现需要对Church-Turing理论：“存在或者可以建造一种计算机，这种计算机能够被设计进行任何自然物体能够进行的计算。”进行一点调整。</P>' g$ R& i, A0 ~8 P>量子计算理论和人工智能领域有一些有趣的联系。对于一台计算机是否真的能实现人工智能的争论已经持续了数年，并且很大程度上是哲学的争论。那些反对这种观点的人解释说：人类的思想，即使只是在理论上，也不可能在图灵机上实现的。</P>>量子计算理论允许我们从一个有些微不同的视角来看待意识问题。首先值得注意的是，任何自然物体，从一块岩石到整个宇宙，都可以被看做是一台量子计算机；而任何可察觉的自然过程都可以被视为一种计算。在这些标准下，大脑可以作为一台计算机而意识就是一种计算。争论的下一个阶段主要是基于Church-Turing理论，并且证明：因为每一台计算机在功能上都是等价的，每台既定的计算机一定能模仿其它的计算机，所以用一台量子计算机模仿意识理性思维必然是可能的。</P>>一些人相信量子计算机是突破人工智能问题的关键所在，但是另外一些人不同意。牛津大学的Roger Penrose认为，意识需要一种更奇特的(也是未知的)物理学。</P>3 x- V) n0 }1 R# `>一台量子计算机在设计上没有什么类似传统计算机，例如你不能使用晶体管和二极管。为了制造一台计算机就需要产生一种新的技术，一种能使“量比”在0和1之间以连贯重叠的状态存在的技术。尽管实现这个目标的最优方法仍然是未知的，但已有许多方法在实验中，并被证明取得了不同程度的成功。</P>8 t; |, t3 @+ f" F, O( d>一个量比执行的范例是“量子点”，它基本上是一个被困在原子牢笼中的单一电子。当量子点暴露在刚好合适波长的激光脉冲下并持续一段时间，电子就会达到一种激发态：而第二次的激光脉冲又会使电子衰落回它的基态。电子的基态和激发态可以被视为量比的0和1状态，而激光在将量比从0状态撞击到1状态或从1撞击到0的应用，能够被看成是一种对取非功能的控制。</P>>如果激光持续时间只有取非功能要求的一半，那么电子将同时处于基态和激发态的重叠中，这也等价于量比的连贯性状态。而更多复杂的逻辑功能可以通过使用成对的安排好的量子点被模拟出来。因此，看起来量子点是一个合适的建造量子计算机的候选人。然而不幸的是，有许多实际问题阻止了这种情况的发生：$ {2 S: r0 M! ^7 A. I$ g$ c>量子点并不是唯一的经过试验的执行量比，其它技术试图使用个体原子或激光的分化作为信息的媒体，而脱散性是这些技术的普遍问题。人们尝试将这些实验从它们周围环境屏蔽起来，例如在千分之一的绝对零度的温度下将其冷却，然而这些方法在减少这个问题的影响方面取得了极其有限的成功。</P> x& s% r3 }3 u; A; t>量子计算领域的最新发展采用了一个根本性的新方法。这种方法放弃了量子媒质应当小并且和它的周围环境隔离的假设，而是使用大量的分子来储存这些信息。当处于磁场中时，一个分子中的每个核子都会在一个特定方向上的旋转，这个旋转特性可以用来描述它的状态，上旋表示1而下旋代表0。核子磁性共振技术可以被用来检测这些旋转状态，特殊无线电波脉冲能够把核子从上旋(1)撞击到下旋(0)，反之亦然。</P>>使用这种技术的量子计算机本身就是一个分子，而它的量比就是分子内的那些核子。但是这种技术并不能只使用一个单一分子来实现这些计算，而是用一整“杯”流体分子。这种方法的优势在于，即使液体分子彼此撞击，每个分子中核子的旋转状态仍能保持不变。脱散性仍然是一个问题，但是到目前为止，在这种技术中脱散前的时间已经比任何其它技术的时间要长许多。研究人员相信，几千个原始逻辑操作能够在量比脱散前实现。</P>>麻省理工学院的Dr.Gershenfield，是流体计算技术的倡导者之一。他的研究队伍已经能够将1和1加起来，这是一个远远超越其它任何正在研究中的技术能力的简单任务。而能够计算更复杂任务的关键在于拥有更多的原比，但是这要求更多复杂的分子以及大量的核子，因此咖啡因分子成为一个可能的候?Ｎ蘼壅庵址肿邮鞘裁矗?0量比系统的进步都是显而易见的。Dr.Gershenfield希望这样一个系统在年底，将能够乘以数字15。</P>* G4 g: o( E6 h5 L$ M>超过10量比系统的进步可能会更加困难。在一个给定的“计算流体”样本中，将会有大约偶数个上下旋状态，但是将会有一点在超过一个方向上的旋转存在。正是这些少量额外旋转的所发出的表现得好像它是一个单一分子的信号，使它能够被检测出来以及进行运算操作，而剩下的旋转将会有力地彼此抵消掉。这种信号相当微弱，并且在每个量比被加入的时候，以大约2倍的速度持续性减弱。这就会限制一个系统可能拥有的量比的数目，而易读的输出将会更难以检测出来。</P>>非常需要注意的是，一台量子计算机并不一定在所以计算任务上都会比一台传统计算机做得好。例如，乘法运算在一台量子计算机上执行的不比在一台类似的传统计算机上快。为了显示量子计算机的优越性，就需要使用开发量子并行效应能力的算法。这些算法难以阐述，而值得记住的最显著理论化的算法当属Shor的算法和Grover的算法。通过使用好这些算法，量子计算机能够大大优于传统计算机。例如，Shor算法允许以极快的速度因式分解大数字。一台传统计算机在分解1000位阿拉伯数字时需要花费10,000,000,000,000,000,000,000,000年，而一台量子计算机只需大约20分钟。</P>>这是Peter Shor在1995年发明的算法，它能够快速地分解大数字。如果它曾经被使用过，它将会对密码系统有着深刻的影响，它会威胁到由公钥密码学所提供的安全性(例如RSA)。</P>>受到威胁－－公钥密码学- b- X! u% s. P. F8 Z% n>例如，1234乘以3433容易算出来，但计算4236322的因子就不那么容易了。分解一个数的质因子的计算复杂度随该数增长而迅速膨胀。破解RSA129(有129位阿拉伯数字)时，花费了1600位因特网用户8个月的时间。密码破译着认为，更多的数字应当被加到密钥中以抵抗计算机性能的增长(这将花费比宇宙年龄还长的时间来计算RSA140)。然而，对于使用运行Shor算法的一台量子计算机，密钥中的阿拉伯数字个数对问题的难度有着极小的影响。破译RSA140只需花费几秒钟的时间。</P>5 Y) x; K0 d5 n) m) _6 i) F. l' I>这部分的目的是说明Shor算法有关的基本步骤。为了使问题相对简单易懂，我们将考察找到数字15的质因子问题。因为算法主要由三步组成，讲解将会分为3个阶段...</P>>阶段1</P>2 R) ^1 e: K: B' D" ?, Z2 z# Q- Q9 g| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) | Powered by Discuz! X2.5 |