Algorithm 版 (精华区)

发信人: ssos (存在与虚无·戒酒戒网), 信区: Algorithm
标  题: 量子计算机2
发信站: 哈工大紫丁香 (2001年11月14日16:40:03 星期三), 站内信件

量子计算机
    1982年，美国著名物理学家R.Feynman首次提出了把量子力学和计算机结合起来的可
能性。接着在1985年，英国牛津大学的D.Deutsch初步阐述了量子计算机的概念，并且指
出了量子计算机可能比经典图灵计算机具有更强大的功能。由于当时没有可以操作的实
例进一步显示量子计算机在解决具体问题时的实际功效，量子计算机的发展在很长的时
间里始终徘徊不前。直到1995年提出了大数因子化量子算法、并原则上表明它可以在冷
却离子系统中实现，量子计算机的研究才变成物理学家、计算机专家和数论学家共同关
心的重大交
叉科研领域。量子计算机的出现，并不是要在通常的计算问题中取代传统的电子计算机
,而是要针对特定的问题，完成经典计算机难以胜任的高难度计算工作,如大数Shor因子
化[2]和巨数据库Grover量子搜索[3]。
    众所周知,所谓的大数因子化是把一个大数分解为所有素数因子的乘积。破译某些编
码时需要进行这样数字计算，如目前大量的金融交易是在一种叫作“RSA公开码”的、依
赖于大数因子化的密码技术保护下进行的。在传统计算机中，一个n位二进制数是由一串
有n个0或1组成的数串描述。任何一个十进制数x=a020+a121+a222+…..+an2n可以唯一地
表达为一个二进制数anan-1…a2a1a0,其中aI=0,1。存储大数ｘ通常约需要n=log2x个数
据位。如果用１，２，３，、、、直到去除ｘ，经典计算过程通过约步运算，可以最后
找到ｘ的全部素数因子。显然，计算的步数s=en(ln2)/2    与这个大数的数据位数呈ｅ
指数关系。随着ｎ变大，步数将是一个天文数字。因此，这是一项极为困难的计算。按
照现有的算法，对于一个400位数字的分解，使用现今最快的超级计算机也要花几十亿年
时间才能完成。然而我们知道,人类的历史才不过几百万年,这样的计算必定是无效的。

    令人吃惊的是，1995年，应用D.Deutsch的量子计算机理论，美国电报电话公司的P
eterW.Shor发现，通过量子力学的基本原理和概念,完成一个n位大数的因子分解所用的
计算步数只是n的多项式函数，而不是n的指数函数。因而，Shor的算法原则上可以在一
年左右的时间内分解一个400位大数，从而有可能使现在所用的大部分复杂加密方案失效
。他的发现在信息金融领域产生了极大的影响。这是因为现有的加密系统大多是建立在
大数难于分解的基础之上的。很难想象，这样一种影响竟会来自于计算机科学领域之外
的、令人“头晕目眩”量子力学。需要指出的是，虽然许多实验和理论研究在探索这样
一种方法的可行性，但迄今为止还没有人能建造出一台实用的量子计算机。因此，在看
得见的将来，敏感的数据的传统加密还是安全的。
   表现量子计算独特能力的另一项算法是贝尔实验室的L.K.Grover设计的量子搜索。计
算机在搜索藏在有n个对象的数据库中的一个特定的对象时，经典的搜索过程要比较每一
个对象,平均说来需要进行n／2次尝试才有较大的可能找到那个对象。经典搜索的一个日
常生活的例子是在一个按人名索引的、共有Ｎ个人的电话簿里，找到确定号码的人，通
常要找Ｏ（Ｎ）次才能成功。Grover把它换成量子力学问题就是：对于Ｎ个态的均匀相
干叠加，通过若干次基本的么正变换可以把其中一个特定分量的几率放大为１。令人惊
讶的是,Grover的量子搜索可以通过大约根号次尝试就找出所需的对象。1998年初,IBM公
司加洲阿尔登研究中心的Issac.Chuang等人利用氯仿核磁共振实现了两个量子数据位的
量子搜索实验[4]，成为为量子计算的第一个演示实例。Shor的算法和Grover量子搜索的
成功，不仅激励物理学家们直接涉足于信息科学，同时也促使计算机科学的专家开始了
解量子力学的意义和应用。

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]