量子计算机发展带来的思考(论文资料).doc

量子计算机发展带来的思考科学技术的创新与发展国外究竟为什么能发明出这些各式各样的计算机呢？这些意味着什么呢？作为即将腾飞的的大国怎样学会这种创新，怎样在量子信息发展的初期占领这块高地，成为世界科技的引领者？在阅读一些文献、论文和熟悉量子信息特别是量子计算机的发展的基础上我做了一些总结和思考，希望和大家共同分享、探讨上面提出的问题。2010量子计算机发展带来的思考 科学技术的创新与发展一、引言自从20世纪30年代以来，图灵机、计算这些重要的概念在科学的天空中就一直闪烁着无限的光彩。尤其是近年来量子计算机、生物计算机、DNA计算等领域的创新工作引起了了世人的广泛关注。我们不禁问这样的问题，国外究竟为什么能发明出这些各式各样的计算机呢？这些意味着什么呢？作为即将腾飞的的大国怎样学会这种创新，怎样在量子信息发展的初期占领这块高地，成为世界科技的引领者？在阅读一些文献、论文和熟悉量子信息特别是量子计算机的发展的基础上我做了一些总结和思考，希望和大家共同分享、探讨上面提出的问题。二、伟大的创新源于理论1、计算理论1.1什么是计算广义上讲，一个函数变化如把x变成了f(x)就是一个计算！如果我们把一切都看作是信息，那么更精确的讲，计算就是对信息的变换！如果采用这种观点，我们会发现，其实自然界充满了计算！也可以说，计算就是某个系统完成了一次从输入到输出的变换！ 这样理解不要紧，你会发现，现实世界到处都是计算了！因为我们完全可以把所有的自然界存在的过程都抽象成这样的输入输出系统，所有的大自然存在的变量都看作是信息，因而计算无处不在！也的确，正是采取了这样的观点，国外才有可能发明什么DNA计算机、生物计算机、量子计算机这些新鲜玩艺！因为人家把DNA的化学反应、量子世界的波函数变换都看作是计算了，自然就会人为地把这些计算组合起来构成计算机了。1.2图灵机 所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。它工作的时候是这样的：从读写头在纸带上读出一个方格的信息，并且根据它当前的内部状态开始对程序进行查表，然后得出一个输出动作，也就是是否往纸带上写信息，还是移动读写头到下一个方格。程序也会告诉它下一时刻内部状态转移到哪一个。因此，图灵机只要根据每一时刻读写头读到的信息和当前的内部状态进行查表就可以确定它下一时刻的内部状态和输出动作了。对图灵机的计算能力的估价目前一般以强Church-Turing论题为据:任何算法过程都可以用图灵机进行有效模拟。由于随机算法的引人Church-Turing强论题后来被修改为更强的论题:任何算法过程都可用概率图灵机进行有效模拟。在这个问题的启发下, Deutsch与其他一些物理学家认识到, 一个数学问题的计算复杂性的P与NP分类没有绝对性, 而在此之前人们一直认为这种分类不依赖具体使用的计算系统。正是这个认识, 使得量子计算的研究得到广泛关注。随后, Deutsch 提出是否可以用物理学定律推导出任何更强的Church-Turing论题的问题, Deutsch选用被认为是物理学最基本规律的量子力学理论进行考虑, 提出了通用量子计算机的概念。1.3量子图灵机正如经典计算机建立在通用图灵机基础之上，量子计算机亦可建立在量子图灵机基础上量子图灵机可类比于经典计算机的概率运算前面提到的通用图灵机的操作是完全确定性的，用q代表当前读写头的状态，s代表当前存储单元内容，d取值为L，R，N分别代表读写头左移、右移或不动，则在确定性算法中，当q，s给定时，下一步的状态q，,s，及读写头的运动d完全确定我们也可以考虑概率算法，即当q,s给定时，图灵机以一定的概率(q,s,q，,s，,d)变换到状态q，,s，及实行运动d概率函数(q,s,q，,s，,d)为取值O，1的实数，它完全决定了概率图灵机的性质经典计算机理论证明，对解决某些问题，概率算法比确定性算法更为有效量子图灵机非常类似于上面描述的经典概率图灵机，现在q,s,q, ,s, 相应地变成了量子态，而概率函数(q,s,q，,s，,d)则变成了取值为复数的概率振幅函数(q,s,q，,s，,d)，量子图灵机的性质由概率振幅函数确定正因为现在的运算结果不再按概率叠加，而是按概率振幅叠加，所以量子相干性在量子图灵机中起本质性的作用，这是实现量子并行计算的关键量子计算机可以等效为一个量子图灵机，但量子图灵机是一个抽象的数学模型，如何在物理上构造出量子计算机呢?2、物理学基础（量子力学）从物理观点看, 计算机是一个物理系统, 计算过程是一个物理过程。量子计算机是一个量子力学系统, 量子计算过程就是这个量子力学系统内量子态的演化过程。量子力学中与量子计算关系最为密切的两个特性是叠加态与纠缠态。由于量子态具有量子叠加和量子纠缠的性质, 使得量子计算有许多不同于经典计算机的新特点。信息一旦量子化，描述“原子水平上的物质结构及其属性”的量子力学特性便成为量子信息的物理基础。此时由于信息载体量子的微观特征，量子化的信息也变得多姿多彩。这些微观特征主要表现在：1）量子态相干性：微观系统中量子间相互干涉的现象成为量子信息诸多不可思议特性的重要物理基础；2）量子态纠缠性：N（大于1）个量子在特定的（温度、磁场）环境下可以处于较稳定的量子纠缠状态，对其中某个子系统的局域操作会影响到其余子系统的状态；3）量子态叠加性：量子状态可以叠加，因此量子信息也可以叠加，所以可以同时输入或操作 N个量子比特的叠加态；4）量子不可克隆定理：量子力学的线性特性确保对任意量子态无法实现精确的复制。量子不可克隆定理和测不准原理构成量子密码技术的物理基础。 利用量子信息实现通信的过程是使每一个微观粒子，通过自身的物理特性携带经典信息0和1的叠加信号后实现的数据传输的技术。事实上，经典计算机也是量子力学的产物，它的器件也利用了诸如量子隧道现象等量子效应。但仅仅应用量子器件的信息技术，并不等于现在所说的量子信息。目前的量子信息主要是基于量子力学的相干特征，重构信息密码、信息计算和信息通讯的基本原理。3、第一次的融合（量子计算机与可逆计算）量子计算机的概念源于对可逆计算机的研究，而研究可逆计算机是为了克服计算机中的能耗问题早在六七十年代，人们就发现，能耗会导致计算机芯片的发热，影响芯片的集成度，从而限制了计算机的运行速度LandauerTM最早考虑了这个问题，他考察了能耗的来源，指出：能耗产生于计算过程中的不可逆操作例如，对两比特的异或操作，因为只有一比特的输出，这一过程损失了一个自由度。因此是不可逆的，按照热力学，必然会产生一定的热量但这种不可逆性是不是不可避免的呢?事实上，只要对异或门的操作如图1所示的简单改进，即保留一个无用的比特，该操作就变为可逆的因此物理原理并没有限制能耗的下限，消除能耗的关键是将不可逆操作改造为可逆操作(见图1)Bennett 后来更严格地考虑了此问题，并证明了，所有经典不可逆的计算机都可以改造为可逆计算机，而不影响其计算能力因为计算机中的每步操作都可以改造为可逆操作，在量子力学中它就可以用一个幺正变换来代表BenioffCs 最早用量子力学来描述可逆计算机在量子可逆计算机中，比特的载体成为二能级的量子体系，体系处于0>和ll>上，但不处于它们的叠加态量子可逆计算机的研究，其核心任务为，对应于具体的计算，寻找合适的哈密顿量来描述早期的量子可逆计算机，实际上是用量子力学语言表述出来的经典计算机，它没有利用量子力学的本质特性，如量子叠加性和相干性Feymann首先指出l6，这些量子特性可能在未来的量子计算机中起本质作用，如用来模拟量子系统Deutsehl7 找到一类问题，对该类问题，量子计算机存在多项式算法”，而经典计算机则需要指数算法但最具轰动性的结果却是Shor给出的关于大数因子分解的量子多项式算法81(见第三节)，因为此问题在经典公钥体系中有重要应用Shot的发现掀起了研究量子计算机的热潮，从此后，量子计算机的发展日新月异另外值得指出的是计算与能量的关系。由热力学定律知, 计算的另一个资源是能量。经典计算作为一种机械的过程与能量的消耗是有关联的。在现代的经典计算中, 计算机消耗电能看似平常, 亦很少有人研究经典计算与能量的关系。然而在量子计算当中, 理论上计算是不消耗任何能量的。热力学第二定律描述为一个封闭系统的嫡绝不会减少。一个系统的嫡是该系统的状态函数直觉地说嫡是系统混乱程度的度量若系统越是无规律的混乱则其嫡高若系统越是有规律的整齐, 则其嫡越低。对于计算机擦除位信息与能量或嫡的关系有,原理 , 第一形式假设计算机擦除位的信息, 散发到环境中的能量的总量至少是, 其中, 称为常数,是计算机所在的环境温度。原理第二形式假设计算机擦除位的信息, 环境的嫡增量至少是, 其中。是常数。由原理可知若在计算中存在信息擦除, 则该计算需要能量。在年, 经典计算机进行一个基本逻辑运算约消耗能量月。若在计算中不存在信息擦除,则由定律知计算所消耗的能量没有下限,也就是说在这种情况下的计算理论上可以不消耗任何能量。上述陈述成立的关键是不擦除信息, 是否可以进行计算下面引人可逆计算的概念。三、抢占量子计算机研制的高地1、理论研究理论上已证明量子图灵机可以等价为一个量子逻辑电路，因此可以通过一些量子逻辑门的组合来构成量子计算机量子逻辑门按其输入比特的个数可分为单比特、二比特、及三比特逻辑门等因为量子逻辑门是可逆的，所以其输入和输出比特数相等，量子逻辑门对输入比特进行一个确定的幺正变换，得到输出比特Deutsch最早考虑了用量子逻辑门来构造计算机的问题他发现，几乎所有的三比特量子逻辑门都是通用逻辑门通用逻辑门的含义是指，通过该逻辑门的级联，可以以任意精度逼近任何一个幺正操作后来不少人发展了Deutseh的结果，最后Deutsch和Lloyd各自独立地证明几乎所有的二比特量子逻辑门都是通用的，这里“几乎”是指，二比特通用量子逻辑门的集合是所有二比特逻辑门的集合的一个稠密子集实验上通常用一些具体的量子逻辑门来构造计算机。Barenco等人证明，一个二比特的异或门和对一比特进行任意操作的门可构成一个通用量子门集。相对来说，单比特逻辑门在实验上比较容易实现，现在的不少实验方案都集中干制造量子异或门。2、硬件设计（量子逻辑门的实现）2.1基本要求1) 可扩展的、具有良好特性的量子位系统2) 能够初化量子位为某个基态3) 具有足够长的相干时间来完成量子逻辑门操作4) 能够实现一套通用量子逻辑门操作5) 能够测量量子位6) 能够使活跃量子位和静止量子位互相转化7) 能够使活跃量子位准确地在不同的位置之间传送2.2 几种方案 1) 利用原子和光腔的相互作用2) 利用冷阱束缚离子3) 利用电子或核自旋共振2.3量子计算的困难及其克服途径量子计算的优越性主要体现在量子并行处理上，无论是量子并行计算还是量子模拟，本质性地利用了量子相干性失去了量子相干性，量子计算的优越性就消失殆尽但不幸的是，在实际系统中，量子相干性却很难保持消相干(即量子相干性的衰减)主要源于系统和外界环境的耦合因为在量子计算机中，执行运算的量子比特不是一个孤立系统，它会与外部环境发生相互作用，其作用结果即导致消相干Unruh定量分析了消相干效应，结果表明，量子相干性的指数衰减不可避免Unruh的分析揭示了消相干的严重性，这一结果无疑是对量子计算机的信奉者的当头一棒因为量子计算机本质性地利用了量子相干性，相干性的丢失就会导致运算结果出错，这就是量子错误除了消相干会不可避免地导致量子错误外，其他一些技术原因，例如量子门操作中的误差等，也会导致量子错误因此，现在的关键问题就变成，在门操作和量子存储都有可能出错的前提下，如何进行可靠的量子运算?Shor在此方向取得一个本质性的进展，这就是量子纠错的思想。量子纠错是经典纠错码的量子类比。3、软件3.1量子算法量子计算必须有高效的量子算法才能发挥其计算优势, 目前对量子算法已经有了很多研究。量子并行原理虽然可以仅通过一次变换产生所有计算结果, 然而测量时只能得到一个结果, 而且不能选择所需的结果。量子算法的中心思想是利用量子态的相干性, 使客观所需的结果增强, 同时使非所需的结果减弱, 这样客观所需的结果在测量时就会以相当高的概率出现。Geove算法Shor算法3.2量子计算机程序设计语言虽然通用的量子计算硬件量子计算机的制造尚未获得成功, 但以通用量子计算机为运行载体的通用量子计算机软件的研究在学术界已经有所涉及。由于量子计算的软件包括量子操作系统、量子程序语言及其编译程序等的研究文献不多, 也没有实际的产品,我们对量子程序仅做简单介绍。按照较统一的认识量子程序的逻辑体系一般与经典计算机类似, 为便于控制并使用通用量子计算机, 必须通过量子计算机程序设计语言来描述待解问题, 因此, 量子计算机程序设计语言将作为未来通用量子计算机上的一种重要系统软件。现有量子算法一般固化于专用量子计算设备中, 如果需要改变量子算法就必须重新设计量子计算设备, 实际上, 这就相当于一台求解特定具体问题不是一类特定问题的专用计算设备。一方面, 量子计算机程序设计语言的研究是为了适应未来量子计算机的实际工作需要, 另一方面, 亦可有助于发现新的量子算法并促进量子计算机的快速诞生。量子程序设计语言近期发展趋势可能是：1) 提高量子程序设计语言的级别2) 研究并发量子程序设计语言3) 着重研究语言的语义与语用4) 研究语言在现有量子设备上的实现。国内南京大学徐家福等在国外学者工作基础之上提出一种基于Java语言扩展而得的命令式量子程序设计语言NDDJava,并设计出其处理系统。通过在经典计算机上模拟实现, 正确运行了几种量子算法,达到了预期效果。四、科学的发展源于需求（量子计算机强大的功能）1、P到NP算法中的计算量，顾名思义，是指解决某问题所需要计算的时间。问题的计算时间若以计算项数幂次上升的计算量完成，我们称此问题为P-问题（P 为英文多项式Polynomial的第一字母），包含所有此类问题的集合以 P 表示。因此P问题是一个凡能用 O(n) 计算量解决的问题的集合。NP 是英文 nondeterministic polynomial 的缩写，意思就是非确定性的多项式时间。大家都猜测可能在 P 之外还存在一类问题，其计算量是呈计算项数指数增加的，包含所此类问题的集合以 NP 表示。NP中有一批互依的问题又称之为 NP-complete类。1971年古克 (Stephen A. Cook) 发表了The Complexity of Theorem Proving Procedures论文把P之外的问题归成了三大类，即 NP, NP-complete 以及 NP-hard 。对经典计算机而言，一个呈幂次上升的计算量应该可以解决，但对一个呈指数上升的计算量在 n 相当大时则毫无希望。因此我们面临的一个问题是在如何将一个呈指数上升的计算量问题，简化成一个幂次上升的计算量问题。 经典计算中存在着一大类NP问题。这类问题在经典计算机上是不能计算的，但是量子计算可以把其中的一部分NP问题变成P问题，即问题的复杂度随着比特位数的增长以多项式数量级上升。这类问题原则上是可以计算的。一个具体的例子就是大因数分解，按经典计算复杂性理论，这个问题不存在有效算法，所以被利用来进行经典密钥分配。但是如果用量子计算机结合Shor量子算法，这个问题就变成了P问题。 例如，为了对一个400位的阿拉伯数字进行因子分解，目前最快的超级计算机将耗时上百亿年，这几乎等于宇宙的整个寿命；而具有相同时钟脉冲速度的量子计算机只需要大约一分钟。因此，对于目前的密码系统，即使人们几乎无法利用经典算法对其进行破解，但如果人们拥有了一台量子计算机，那么目前的密码系统将毫无保密性可言！这一后果是对目前的密码系统的巨大挑战，因而对基于经典保密系统的行业(如军事、国家安全、金融等)的信息安全构成根本的威胁。 Shor算法的核心是利用数论中的一些定理，将大数因子分解转化为求某个函数的周期。在量子计算机中Shor算法的每一步骤都是可以通过多项式算法来完成的。所以，在量子计算机中Shor算法是有效的算法。如果量子计算机能够实现，世界上许多保密系统将受到严重的威胁。因此，为了保证这些领域的信息安全，也为了拓宽人类对微观世界的认识，发展量子信息学刻不容缓：一方面，开发由量子力学基本原理保证其保密性的量子密码系统，另一方面，研制按照量子力学基本原理运行的量子计算机。2、量子态模拟除了进行一些超快速计算外，量子计算机另一方面的重要用途是用来模拟量子系统早在1982年，Feymann就猜测，量子计算机可以用来模拟一切局域量子系统，这一猜想，在1996年由Lloyd证明为正确的_l 首先得指出，模拟量子系统是经典计算机无法胜任的工作作为一个简单的例子，考虑由40个白旋为12的粒子构成的一个量子系统。利用经典计算机来模拟，至少需要内存为2 010 M，而计算其时间演化。就需要求一个2 0×2 0维矩阵的指数，这一般来讲，是无法完成的而利用量子计算机，上述问题就变得轻而易举，只需要40个量子比特，就足以用来模拟Lloyd进一步指出，大约需要几百至几千个量子比特，即可精确地模拟一些具有连续变量的量子系统，例如格点规范理论和一些量子引力模拟这些结果表明，模拟量子系统的演化，很可能成为量子计算机的一个主要用途只有注重基础的理论研究才来在创新的道路上走的更远更深。面对量子信息科学快速的发展我们要做好全面的工作，无论从理论研究，量子逻辑门的物理系统实现，还是量子算法甚至量子计算机程序设计语言还有量子纠错量子编码希望都能在全国展开研究。一项技术的进步有时不是一个部门一个学科就能完成的，未来的我们无论在哪个岗位上希望都还能科学的思考，带着神圣和光荣完成那看似平凡的工作。参考文献：1、段路明,郭光灿.量子信息讲座 2、图灵机与计算问题3、吴楠,宋方敏.量子计算与量子计算机4、夏培肃.量子计算J计算机研究与发展