超级计算能手——量子计算机

1、信息科学面临挑战信息科学面临挑战 信息科学在改善人类生活质信息科学在改善人类生活质 量和推进社会文明发展中发挥着量和推进社会文明发展中发挥着 无可比拟和令人惊叹的作用，但无可比拟和令人惊叹的作用，但 在信息化的进程中人类也面临越在信息化的进程中人类也面临越 来越严重的问题，如当今信息系来越严重的问题，如当今信息系 统的处理能力已接近极限值的程统的处理能力已接近极限值的程 度。度。 现有计算机的运算速度能无限制地增长吗？现有计算机的运算速度能无限制地增长吗？ 1965-1995年微处理器与存储器芯片年微处理器与存储器芯片 集成度的提高基本符合集成度的提高基本符合Moores Law. Gordo

2、n Moore, Intel 公司的创始人之一公司的创始人之一. 现有的密码体系是绝对安全的吗？现有的密码体系是绝对安全的吗？ 密钥的安全性是核心问题。密钥的安全性是核心问题。 所谓所谓“绝对安全绝对安全”是指能经受物理定律所允许的攻击是指能经受物理定律所允许的攻击 而不被破译。而不被破译。 明文明文 明文明文 加密加密 变换变换 脱密脱密 变换变换 密钥密钥K 密钥密钥K 密文密文 密文密文 公开信道公开信道 K K 1 公开密钥公开密钥RSARSA体系基于体系基于“大数因子分解大数因子分解”这类这类 难以计算的数学问题，并不是严格意义上的绝对安全。难以计算的数学问题，并不是严格意义上的绝对

3、安全。 密钥可以克隆是密码体系不安全的根源。密钥可以克隆是密码体系不安全的根源。 一直在国际上广泛应用的两大密码算一直在国际上广泛应用的两大密码算 法法MD5MD5、SHASHA1 1，近期宣布被王小云教授，近期宣布被王小云教授 破解。破解。 20042004年年8 8月，王小云在国际密码大月，王小云在国际密码大 会上首次宣布了对会上首次宣布了对MD5MD5、HAVALHAVAL128128、 MD4MD4和和RIPEMDRIPEMD等四个著名密码算法的破译等四个著名密码算法的破译 结果。结果。 v 20052005年年2 2月月7 7日，美国国家标准技术研究日，美国国家标准技术研究 院发表申

4、明，院发表申明，SHASHA1 1没有被攻破，并且没有没有被攻破，并且没有 足够的理由怀疑它会很快被攻破，开发人员足够的理由怀疑它会很快被攻破，开发人员 在在20102010年前应该转向更为安全的年前应该转向更为安全的SHASHA256256和和 SHASHA512512算法。而仅仅在一周之后，王小云算法。而仅仅在一周之后，王小云 就宣布了破译就宣布了破译SHASHA1 1的消息。的消息。 v 诸如此类问题对现有信息技术提出严峻的诸如此类问题对现有信息技术提出严峻的 挑战。未来信息技术的持续发展要求开拓新挑战。未来信息技术的持续发展要求开拓新 的原理和方法。的原理和方法。 量子力学的奇妙特性量

5、子力学的奇妙特性 量子力学是量子力学是2020世纪初才诞生的，世纪初才诞生的， 是近代物理学两大支柱之一。是近代物理学两大支柱之一。 经典力学：宏观物质的运动规律。经典力学：宏观物质的运动规律。 量子力学：微观粒子的运动规律量子力学：微观粒子的运动规律自然界的运动规律。自然界的运动规律。 经典粒子经典粒子 特性：特性：每时刻的位置、速度完全确定，有确定每时刻的位置、速度完全确定，有确定 的运行轨迹，遵从牛顿力学。的运行轨迹，遵从牛顿力学。 经典的波经典的波 特性：特性：充满整个空间，遵从经典电磁场理论。充满整个空间，遵从经典电磁场理论。 微观粒子微观粒子 特点：同时具有粒子性和波动性。特点：同

6、时具有粒子性和波动性。 设想空间中有一个微观粒子，设想空间中有一个微观粒子， 任何时刻有可能在空间中任何点探任何时刻有可能在空间中任何点探 测到粒子（类似经典波的特性），测到粒子（类似经典波的特性）， 但一旦探测到只能在其中一个探测但一旦探测到只能在其中一个探测 器处发现该粒子（类似经典粒子的器处发现该粒子（类似经典粒子的 特性）。特性）。 C A B A,B,C,为探测器为探测器 多次入射多次入射 （干涉现象）（干涉现象） 遵从量子力学。遵从量子力学。 微观粒子微观粒子 一次入射一次入射 经典粒子在某个时刻只能处于确定的经典粒子在某个时刻只能处于确定的 物理状态上；物理状态上； 量子粒子则可

7、以同时处于各种可能的物量子粒子则可以同时处于各种可能的物 理状态上（叠加态）。理状态上（叠加态）。 D1 D2 单个光子单个光子 分束器分束器 光电探测器光电探测器 单个光子究竟沿哪条路径传送？单个光子究竟沿哪条路径传送？ “薛定谔猫薛定谔猫” 宏观量子叠加态宏观量子叠加态 活死 2 1 t A EPR粒子对粒子对 B EPR佯谬佯谬 EPR效应：非局域性是量子力学的基效应：非局域性是量子力学的基 本性质。本性质。 BABA BA 2 1 ,纠缠态纠缠态 量子信息应运而生量子信息应运而生 量子特性应用到信息领域中可以发挥量子特性应用到信息领域中可以发挥 出独特的功能，在提高运算速度、确保信出独

8、特的功能，在提高运算速度、确保信 息安全、增大信息容量等方面可以突破现息安全、增大信息容量等方面可以突破现 有的经典信息系统的极限，于是诞生了一有的经典信息系统的极限，于是诞生了一 门新兴的交叉学科：门新兴的交叉学科： 量子信息科学量子信息科学 它是量子物理与信息科学相结合的产物。它是量子物理与信息科学相结合的产物。 量量 子子 密密 码码 量量 子子 通通 讯讯 量量 子子 计计 算算 人们坚信，信息技术的发展人们坚信，信息技术的发展 将从将从经典经典跨越到跨越到量子量子的时代。的时代。 近年来，量子信息在理论近年来，量子信息在理论 和试验研究上取得重要突破，和试验研究上取得重要突破， 引起

9、各国引起各国政府、科学界、信息产业界政府、科学界、信息产业界 的高度重视。的高度重视。 二、量子信息的特性二、量子信息的特性 自然界有三要素：物质、能量和信息。自然界有三要素：物质、能量和信息。 相应有三个学科：材料科学、能量科学和信息科学。相应有三个学科：材料科学、能量科学和信息科学。 何谓何谓“信息信息”？ 信息就是我们在适应外部世界和控制外信息就是我们在适应外部世界和控制外 部世界的过程中，同外部世界进行交换的内部世界的过程中，同外部世界进行交换的内 容和名称。容和名称。 “信息就是信息，既不是物质，也不是能信息就是信息，既不是物质，也不是能 量量”。 为全人类带来更丰富的高科为全人类带

10、来更丰富的高科 技成果。技成果。 2020世纪人类把量子力学应用于物世纪人类把量子力学应用于物 质科学和能源科学，导致了构成当代质科学和能源科学，导致了构成当代 文明社会的高科技成果，如核能、半文明社会的高科技成果，如核能、半 导体、激光等。导体、激光等。 2121世纪人类将量子力学世纪人类将量子力学应用应用于信于信 息科学，导致量子信息的诞生，这将息科学，导致量子信息的诞生，这将 量子信息与经典信息的根本区别量子信息与经典信息的根本区别 经典信息经典信息 二进制二进制0或或1组成的数字串，其信息组成的数字串，其信息 单元称为单元称为“比特比特”，为，为0或者或者1。 用量子的语言可描述为态用

11、量子的语言可描述为态 和和 。 经典粒子只能处在经典粒子只能处在 或或 之中的一个态之中的一个态 上。上。 01 01 量子信息量子信息 微观粒子允许同时处在微观粒子允许同时处在 和和 两个两个 态上，这是其波粒二象性的结果。态上，这是其波粒二象性的结果。 01 1212 01 , ,CCC C为任意复数 。1 2 2 2 1 CC （叠加态）（叠加态） 量子信息是经典信息的完善和扩充，正如复数量子信息是经典信息的完善和扩充，正如复数z=x+iyz=x+iy 是实数是实数x x，y y的完善和扩充。的完善和扩充。 量子信息的单元量子信息的单元 称为量子比特。称为量子比特。 量子比特（即量子态）

12、的物理载体：光子，电子，原量子比特（即量子态）的物理载体：光子，电子，原 子，核自旋，子，核自旋， 以量子态作为信息单元，以量子态作为信息单元，“信息信息”就量子就量子 化。化。 以以“比特比特”作为信息单元的是经典信息，作为信息单元的是经典信息， 以以“量子比特量子比特”作为单元的是量子信息。作为单元的是量子信息。 因此，量子信息遵从量子力学规律。因此，量子信息遵从量子力学规律。 信息传输：信息传输：量子态在量子通道中传送量子态在量子通道中传送 信息处理信息处理( (计算计算) )：量子态幺正演化量子态幺正演化 信息提取：信息提取：量子测量量子测量 如，经典信息可以克隆，而量子信息是不可克隆

13、的如，经典信息可以克隆，而量子信息是不可克隆的 （量子不可克隆定理）。（量子不可克隆定理）。 两经典粒子分离后就不关联，而两量子粒子处于纠两经典粒子分离后就不关联，而两量子粒子处于纠 缠态（缠态（EPR粒子）时不论空间分离多开仍然存在量子关粒子）时不论空间分离多开仍然存在量子关 联，对其中一个粒子施行作用必然会影响另一个粒子的联，对其中一个粒子施行作用必然会影响另一个粒子的 状态。状态。 于是，奇特的量子性质就可以产生新的信息功能。于是，奇特的量子性质就可以产生新的信息功能。 三、量子密码三、量子密码 采用量子态采用量子态(量子比特量子比特)作为信息载体，经由量子作为信息载体，经由量子 通道传

14、送，在合法用户之间建立共享的密钥通道传送，在合法用户之间建立共享的密钥(经典随经典随 机数机数)，这个密钥是安全的，任何窃听都会被发现。，这个密钥是安全的，任何窃听都会被发现。 其安全性由量子力学原理所保证：其安全性由量子力学原理所保证： 窃听者若企图通过对量子态的测量来窃窃听者若企图通过对量子态的测量来窃 取信息，则必然会干扰这个量子态本身，取信息，则必然会干扰这个量子态本身， 从而会留下痕迹而被合法用户发现。从而会留下痕迹而被合法用户发现。 窃听者若企图通过复制传送密钥的量子窃听者若企图通过复制传送密钥的量子 态来获得信息，此时量子不可克隆定理态来获得信息，此时量子不可克隆定理 确保这种复

15、制不可能成功。确保这种复制不可能成功。 因此，量子密码术原则上可以提供不可破译、因此，量子密码术原则上可以提供不可破译、 不可窃听的保密通信体系。不可窃听的保密通信体系。目前中国科大已在光目前中国科大已在光 纤中成功地实现纤中成功地实现125125公里量子密钥传输，在自由公里量子密钥传输，在自由 空间中实现空间中实现1313公里传送。公里传送。 量子安全体系量子安全体系 量子量子 身份身份 认证认证 量子量子 比特比特 承诺承诺 量子量子 对策对策 论论 量子密码通信量子密码通信 是目前唯一被证明是目前唯一被证明 绝对安全的保密通绝对安全的保密通 信方法信方法, ,美国美国商业商业 周刊周刊把

16、它列在了把它列在了 改变人们未来生活改变人们未来生活 的十大发明的第三的十大发明的第三 位。位。 四、量子通讯四、量子通讯 长期以来，这种隐形传物无长期以来，这种隐形传物无 论用经典方法或量子方法都认为论用经典方法或量子方法都认为 是不可能的，只是是不可能的，只是“科学幻想科学幻想” 或或“神话神话”而已。而已。 地地 球球 木木 星星 1993年美国年美国IBM的著名科学家的著名科学家Bennet等等 四个国家的六位科学家联名在四个国家的六位科学家联名在Physical Review Letters上发表了一篇开创性论文：上发表了一篇开创性论文： “经由经典和经由经典和EPR通道传送未知量子

17、态通道传送未知量子态”，提，提 出了一种方法可以将某个粒子的未知量子态出了一种方法可以将某个粒子的未知量子态 (未未知量子比特知量子比特)传送给远处的另一个传送给远处的另一个 粒子，使该粒子处在这个未知量子粒子，使该粒子处在这个未知量子 态上，而原先的粒子不被传送，这态上，而原先的粒子不被传送，这 就是所谓就是所谓“量子隐形传态量子隐形传态”。 EPR-source initial state BSM U Classical information ALICE BOB Teleported state Entangled pair 量子隐形传量子隐形传 态原理图态原理图 为实现传送某个物体的未

18、知量子态，可将原为实现传送某个物体的未知量子态，可将原 物的信息分成经典信息和量子信息两部分，物的信息分成经典信息和量子信息两部分， 基本思想基本思想 它们分别经由经典通道和量子通道传送给接受者。它们分别经由经典通道和量子通道传送给接受者。 量子信息是发送者在测量中未提取的其余信息量子信息是发送者在测量中未提取的其余信息 经典信息是发送者对原物进行某种测量而获得的部分信息经典信息是发送者对原物进行某种测量而获得的部分信息 接受者在获得这两种信息之后，就可以接受者在获得这两种信息之后，就可以 制造出原物量子态的精确复制品。制造出原物量子态的精确复制品。 在这个过程中，在这个过程中， 原物始终留在

19、发送者处，被传送的仅仅是原物的量子原物始终留在发送者处，被传送的仅仅是原物的量子 态，而且，发送者对这个量子态始终一无所知；态，而且，发送者对这个量子态始终一无所知； 接受者是将别的物质单元接受者是将别的物质单元(如粒子如粒子)制备成为与原物完全制备成为与原物完全 相同的量子态，他对这个量子态也始终一无所知；相同的量子态，他对这个量子态也始终一无所知； 原物的量子态在测量时已被破坏掉原物的量子态在测量时已被破坏掉不违背不违背“量子量子 不可克隆定理不可克隆定理”； 未知量子态未知量子态(量子比特量子比特)的这种传送，需要经的这种传送，需要经 典信道传送经典信息典信道传送经典信息(即发送者的测量

20、结果即发送者的测量结果)， 传送速度不可能超过光速传送速度不可能超过光速不违背相对论不违背相对论 的原理。的原理。 19971997年，奥地利学者年，奥地利学者( (其第二作者为中国其第二作者为中国 科技大学学生科技大学学生) )在在NatureNature上报道了第一个上报道了第一个 实现光子偏振态隐形传送的试验。该论文轰实现光子偏振态隐形传送的试验。该论文轰 动了学术界和新闻界，后被动了学术界和新闻界，后被NatureNature评为评为 2020世纪最有影响的世纪最有影响的2121篇经典论文之一；篇经典论文之一； 19981998年，意大利学者在年，意大利学者在Physical Revi

21、ew Physical Review LettersLetters上发表了另一个光子隐形传态的论文上发表了另一个光子隐形传态的论文 ；19981998年底，美国学者分别在年底，美国学者分别在ScienceScience和和 NatureNature上报道新的试验。上报道新的试验。 2 2、量子密集编码、量子密集编码 量子密集编码可以实现发送单个光子束传输量子密集编码可以实现发送单个光子束传输 两个比特的信息。两个比特的信息。 量子密集编码原理图量子密集编码原理图 特点：特点： (1) (1) 保密性高；保密性高； (2) (2) 增大信息传送速率，适用于紧急场合。增大信息传送速率，适用于紧急场

22、合。 1、对34位十进制的数进行因子分解，约需要 一年； 2、对200位数需要的时间约相当于宇宙的寿命宇宙的寿命 n数学家证明，数学家证明，这种状况在经典物理范围内是这种状况在经典物理范围内是 不可能从本质上解决的不可能从本质上解决的。 经典计算的极限经典计算的极限(1)(1) 经典计算机的极限(2) 计算机基本上是位（0 and 1）的阵列。 过去50年中，经典计算机的速度每两年增加一倍。 计算机的尺寸每两年缩小一半。 计算机是物理器件，基本工作过程用物理学描述。但 是器件的尺寸再小的话就要考虑量子效应。 Intel 公司cpu集成度 可是当集成电路线宽小于0.1微米时，其波动性质便不可 忽

23、略，这样，不得不考虑量子效应的影响。 Semiconductor Industry Association 尺寸逼近纳米尺度时将出现一系列尺寸逼近纳米尺度时将出现一系列量子量子物理效应物理效应 在一毫米见方的单晶硅片上制成在一毫米见方的单晶硅片上制成 的集成电路可以穿过针眼。的集成电路可以穿过针眼。 90年代中期年代中期Intel公司宣称，公司宣称， 在一枚小硬币尺寸的奔腾在一枚小硬币尺寸的奔腾 (Pentium)芯片上包含芯片上包含500万个万个 晶体管，刻蚀线宽不到微米。晶体管，刻蚀线宽不到微米。 但由摩尔第一定律：电脑芯片每18个月 其上的晶体管翻一番，其主要技术是通 过减少导线和元件尺

24、寸来达到的。随着 尺寸的不断减小，其电子的量子效应不 断增加，以至以经典物理为基础的微电 子学在电脑芯片的发展受到不可逾越的 瓶颈。据科学家估计到2025年，电脑芯 片的速度将达到物理极限。 信息的代价 我们知道，信息是可以被精确 测量，并且需要一定量的计算 机内存空间来存储。 IBM研究实验室的罗尔朗道在 思考物理极限对于计算机处理 信息能力的限制时，提出了朗 道原理。 朗道原理信息的 擦除必然伴随着热量 的释放。 信息的代价 朗道原理指出，只要有一个 比特的信息被擦除就会有一 小部分能量以热的形式释放 到环境中，散失的能量与环 境的温度成比例，在室温中， 大致相当于一个空气分子的 动能。

25、信息的代价 以计算机中逻辑与门为例。在电 路中实现逻辑与门时，有两个输 入和一个输出，用二进制表示为： 1 (Y=AB) 信息的代价 那么在运算结果是“0”时，我们无法确定输入是什么，因 为有三种不同的输入： 1 Received 21 February 2007; Accepted 26 April 2007 澳大利亚科学家在量子科学方面获得了重大的突破，他们在 IQOQI（Institute of Quantum Optics and Quantum Information，量子光学及量子信息学会）成功的实现了首 个用8个钙离子组成的量子字节（Quantum Byte）。 美国伊利诺大学香

26、槟分校的科学家发现了一种解出算法结果 的奇特方法，通过量子计算和量子盘查，在不运行算法的情 况下就能得出结果。 研究人员使用一个基于 光学的量子计算机首次 向人展示了“反事实计 算”，即计算机在不运 行的情况下也能推断出 答案相关的信息。 但是，量子计算机的发展也存在不少因难。目前国际上量子 计算机研制的四大技术难关是： 量子隐性远程传态测量中的波包塌缩； 多自由度系统环境中小系统的量子耗散； 量子退相干效应； 量子固体电路如何在常态（常温、常压等）中运行量子态。 其中的多自由度系统环境中小系统的量子耗 散，直接影响量子计算机的正确读数。因为 在读取的瞬间表示信息的原子状态会发生变 化，从而造

27、成各种失真。为了克服这一难点， 科学家们发明了一种读取方法核磁共振 技术。 我们通过给粒子加一个数值 固定的外磁场，因它们有不 同的极化方向和自旋取向， 从而能够在磁场中以某种特 定状态存在，如果在此基础 上在加一个交变电场，改变 频率便可有效控制粒子的运 动，使之一种运动形式代表 一个数据。 原子在磁场中的不同取向 而对于量子固体电路如何在常态（常温、 常压等）中运行量子态。现在我们可以 通过最新的原子芯片技术，利用在硅片 上刻蚀金属导线。当其通过电流是在其 100微米上形成磁势阱，从而形成BEC （波色爱因斯坦凝聚 ）。在常温下形 成量子态。 现在，用原子实现的量子计算机只有5 个q-bi

28、t，放在一个试管中而且配备有庞 大的外围设备，只能做1+1=2的简单运 算，正如Bennett教授所说，“现在的 量子计算机只是一个玩具，真正做到有 实用价值的也许是5年，10年，甚至是 50年以后”。 到那时会出现一种工业，可以将原子计算设备嵌入到任何 东西当中去。不必再像现在这样将一台PC机放在桌子上，也 许到那时候桌子本身就是一台计算机，汽车轮胎可以计算速 度和闸动力，医生可以将微型计算机插入到人体血液中以杀 死肿瘤细胞管现在这些还只是科学幻想中的故事，但是 随着量子计算机的发展，一定会实现的。 虽然迄今为止，世界上还没有 真正意义上的量子计算机。但 是，世界各地的许多实验室正 在以巨大

29、的热情追寻着这个梦 想。人类探询未来，探索科技 的脚步从未停息 。 3 3、 量子通信网络量子通信网络 A C B D 量子存量子存 储器储器 存储量子信息，处存储量子信息，处 理理(运算运算)量子信息。量子信息。 量子存储器量子存储器 量子通道量子通道 传送量子信息。传送量子信息。 用途：开拓新的通信原理和方法。用途：开拓新的通信原理和方法。 例：例：(1)(1)网络量子密码网络量子密码;(2);(2)分布量子计算。分布量子计算。 2004 2004 年年6 6 月月3 3 日日, ,世界上第一个世界上第一个 量子密码通信网络在美国马萨诸塞州量子密码通信网络在美国马萨诸塞州 剑桥城正式投入运

30、行。主持这套网络剑桥城正式投入运行。主持这套网络 建设的是美国建设的是美国BBN BBN 技术公司。这个量技术公司。这个量 子密码通信网络已成功地实现了该公子密码通信网络已成功地实现了该公 司与哈佛大学之间的连接司与哈佛大学之间的连接, ,且很快就且很快就 延伸至波士顿大学。新的量子密码通延伸至波士顿大学。新的量子密码通 信网络与现有因特网技术完全兼容信网络与现有因特网技术完全兼容, , 网络传输距离约为网络传输距离约为10 10 千米。千米。 五、量子计算机五、量子计算机 经典经典 量子量子 可存储可存储0 0或或1 1（一个数）（一个数） 可同时存储可同时存储0 0和和1 1（两个数）（两

31、个数） 一个存储器一个存储器 两个存储器两个存储器 经经 量量 典典 子子 可存储可存储00,01,1000,01,10或或11(11(一个数一个数) ) 可同时存储可同时存储00,01,10,11(00,01,10,11(四个数四个数) ) N N个存储器个存储器 经典：可存储一个数（经典：可存储一个数（2 2N N个可能的数之中的一个数）个可能的数之中的一个数） 量子：可同时存储量子：可同时存储2 2N N个数个数 因此，量子存储器的存储数据能力是经典的因此，量子存储器的存储数据能力是经典的2 2N N倍，倍， 且随且随N N指数增长。指数增长。 例如，例如，N=250,N=250,量子存

32、储器可同时存储量子存储器可同时存储 比宇宙中原子数目还要多的数据。比宇宙中原子数目还要多的数据。 计算是对数据的变换。计算是对数据的变换。 经典计算机经典计算机对对N个存储器运算一次，只变换一个数据。个存储器运算一次，只变换一个数据。 量子计算机量子计算机对对N个存储器运算一次，同时变换个存储器运算一次，同时变换2 2N N个数据。个数据。 可见：对可见：对N N个量子存储器实行一次操作，个量子存储器实行一次操作， 其效果相当于对经典存储器进行其效果相当于对经典存储器进行2 2N N次操作。次操作。 这就是量子计算机的巨大并行运算能力。这就是量子计算机的巨大并行运算能力。 采用合适的量子算法，

33、这个能力可以大采用合适的量子算法，这个能力可以大 大地提高计算机的运算速度。大地提高计算机的运算速度。 现在广泛使用的现在广泛使用的RSA公开密钥：加密密钥、加密变换、公开密钥：加密密钥、加密变换、 解密变换均是公开的，但解密密钥是保密的。解密变换均是公开的，但解密密钥是保密的。 Shor 量子并行算法量子并行算法 1994年，量子信息领域的里程碑工作，年，量子信息领域的里程碑工作， 获获1998年世界数学家大会最高奖。年世界数学家大会最高奖。 这个算法可以求解这个算法可以求解“大数因子分解大数因子分解”难题。难题。 这类大数因子分解是个难解的数学问题这类大数因子分解是个难解的数学问题(NP问

34、题问题)。 其安全性依赖于其安全性依赖于“单向单向”函数函数 127229？ 很容易计算很容易计算 ？29083 很难计算很难计算 分解分解N 运算步骤（时间）随输入长度运算步骤（时间）随输入长度 logN 指数增长，用经典计算是难以计算的。指数增长，用经典计算是难以计算的。 例例 若若N=250， 要用要用8105年年 N=1000，要用，要用1025年年( (比宇宙年龄还长比宇宙年龄还长) ) N=129位，位，1994年年1600台工作站花了台工作站花了8个月分解成功。个月分解成功。 Shor算法证明，采用量子计算算法证明，采用量子计算 机并行计算，分解机并行计算，分解N N的时间随的时

35、间随logN 的多项式增长的多项式增长(即可解问题即可解问题)。 一旦量子计算机研制成功，现一旦量子计算机研制成功，现 有的有的RSARSA密钥将无密可保。密钥将无密可保。 目前在实验上，一个推广了的目前在实验上，一个推广了的ShorShor 算法已经在核磁共振中得到实现。算法已经在核磁共振中得到实现。 Grove量子搜寻算法量子搜寻算法 问题：从问题：从N个未分类的客体中寻找出某个特定客体。个未分类的客体中寻找出某个特定客体。 例如，从按姓序排列的例如，从按姓序排列的106个电话号码中找出某个特定个电话号码中找出某个特定 的号码。的号码。 经典计算机经典计算机 一个个查询，直到找到所要的号码

36、。平一个个查询，直到找到所要的号码。平 均讲，要查均讲，要查 次，找到的几率为为。次，找到的几率为为。N 2 1 2 1 量子计算机量子计算机 采用并行处理，只需采用并行处理，只需 次，次， 找到的几率接近找到的几率接近100 (Grover算法算法)。 N 这个算法应用广泛：这个算法应用广泛： 寻找最大值，最小值，平均值，下棋，寻找最大值，最小值，平均值，下棋， 例例:可以有效地攻破可以有效地攻破DES(the data encryption standard)密码体系密码体系(问题的本质是从问题的本质是从256=71016可能的可能的 密钥中寻找一个正确的密钥密钥中寻找一个正确的密钥)。

37、若以每秒若以每秒106次的运算速率，经典计算机要花次的运算速率，经典计算机要花1000 年，而量子计算机采用年，而量子计算机采用Grove算法，则低于算法，则低于4分钟。分钟。 GroveGrove算法：算法：“可以在稻可以在稻 草堆里发现一根针！草堆里发现一根针！” 目前，目前，GroveGrove算法已经在核磁共算法已经在核磁共 振和光学系统中实现。振和光学系统中实现。 量子模拟计算量子模拟计算 诺贝尔奖获得者费曼曾提出诺贝尔奖获得者费曼曾提出 这样的问题：这样的问题： 经典计算机能否精确地模拟量子体系的演化？经典计算机能否精确地模拟量子体系的演化？ 回答是：回答是：NO! 量子计算机可以精确地模拟这种演化，提供量子计算机可以精确地模拟这种演化，提供 了研究许多重要量子体系的有效工具，成为科学了研究许多重要量子体系的有效工具，成为科学 研究的重要方法。研究的重要方法。 用途：用途： 高温高密度等离子体高温高密度等离子体高温超导高温超导 晶体固态理论晶体固态理论 格点规范理论格点规范理论 在核磁共振中，量子模拟的初步实验在核磁共振中，量子模拟的初步实验 业已展开。目前已经模拟了量子谐振子和业已展