量子计算与不确定性原理pdf 高清下载

【摘要】

对量子计算的计算潜力的高度期望源于量子力学的各种特性,如叠加原理、纠缠现象、破坏性和建设性的量子干扰.相对于经典计算,量子计算具有某些假定的优势,例如量子算法的运行速度比经典算法快;但另一方面却似乎存在影响经典算法但不影响量子算法的障碍,障碍之一是传统上归因于WernerHeisenberg的两个不确定性原理.Heisenberg最初制定的不确定性原理涉及用于测量量子系统的非量子仪器必然会对该系统造成影响.这个原理与其后来的发展有所不同,因为后来发现的不确定性所假定的是不交换可观察量在测量方面存在固有的不能精确测量的特性.在目前的技术发展状况以及当前对量子力学的形式表述与诠释的情况下,这两种不确定性皆有可能对量子计算的速度造成不良影响.近年来,针对这两种不确定性原理有了新的研究成果:１)Ozawa对Heisenberg原理提出了修改,将两种不确定性纳入其内进行并列考虑,从而可以减小HeisＧenberg原理的不确定性程度;２)在考虑到熵不确定性的情况下,Heisenberg不确定性可被视为Hirschmann不确定性的下界,因此除了在测量上的不确定性之外,量子计算还必须考虑来自其他如信息学的不确定性因素.

【作者】

南京大学计算机科学与技术系

南京大学软件新技术国家重点实验室

【文件截图】

【原文部分内容】

　当前以随机存取机模型或图灵机模型为基础的经典计算机在理论上和实践上都遵循经典物理学的定律。自量子力学诞生起,物理学界就普遍认为量子物理定律为综合物理世界的理论,而经典力学定律必须从其中推导出来(由于量子物理等式包含经典物理未有的Planck常数ћ,学界一般尝试将极限值ћ→０应用于量子等式来推导出经典等式);换句话说,现代量子物理学认为宇宙是一个量子系统,其按照与经典物理学定律不同的量子物理定律运行。量子系统与经典系统有着不同的特征,包括:一个量子系统可同时处于多个经典态,即所谓的叠加态(superposition);一个量子系统在演化过程中可受量子干扰而产生所谓的量子干涉(quantuminterference);在空间上隔离的两个量子系统之间亦可以有若干交互关系(correlation),即所谓的纠缠关系(entanglement)。上述涉及基础理论的现象促进量子计算领域发展的主要动因,而非仅仅在于计算速度的快慢或加密能力的强弱。

在量子力学定律的基础上,量子计算研究量子计算机的计算能力、量子算法、计算复杂性等。这方面的研究始于２０世纪８０年代初期,当时的经典计算机模型为模拟计算机。最初的量子计算机模型亦为量子模拟计算机,由Manin[１],FeyＧnman[２]和Benioff[３]同时期提出。冷战造成的阻隔,使得MaＧnin出版于１９８０年的Vychislimoeinevychislimoe(俄语,书名可翻译为«可计算与不可计算»)一书虽然先于Feynman和Benioff提出了量子模拟计算机的可能性,但到最近才获得了国际学界的认可。２０世纪８０年代,经典计算机模型逐步向数字计算模型转化,Deutsch在１９８５年设计了通用量子图灵机模型[４],从而建立了一个量子数字计算范式。

随后,２０世纪９０年代初Simon[５]和Deutsch等[６]提出了用于判定函数若干特性的量子算法,以及Bernstein等发展出来的量子复杂性理论[７]。但是,直到１９９４年Shor提出求解整数的质因子分解问题和离散对数问题的多项式量子算法[８],量子计算研究才有了明显的进度。Shor提出的这两种算法的重要性在于其在密码学上具有实际用途,并给目前经典计算系统普遍使用的加密算法(如RSA算法)带来了挑战。RSA是一个基于大数分解的公钥加密系统,能否解决其公钥的问题取决于所使用的数字能否在合理的时间内进行质因子分解。随着计算机处理器速度的提升,以及求解数字分解时间的缩短,公钥长度必须及时延长。目前,推荐公钥长度为２０４８bits(等于６１７个十进制数位)或以上。因为尚未发现一种仅需多项式时间的经典分解算法,所以RSA的假设是求解质因子分解问题所需的时间应在多项式时间之上。一般认为,Shor的量子算法能够在多项式时间内基于一个量子计算机求解大数质因子分解问题;为了应对量子加密算法对经典加密技术所造成的挑战,目前学界已展开了以此为对象的经典密码学研究,即RSA 后加密学(postＧRSA cryptograＧphy)[９]。

除了上述的理论性动机,就应用而言,量子计算的主要驱动力来自两个方面:１)需要突破硬件的限制;２)希望在计算时间复杂度上超越经典算法,即对多项式以上的时间复杂度问题提供解决方法。

就硬件的限制而言,１９６５年Intel的Moore估计,因电子器件的体积逐渐变小,集成电路上的晶体管数量将每年增加一倍[１０]。晶体管的稀有特性是管件越小其计算能力就越强,因为与大型晶体管相比,小型晶体管可以以更小的功率和更快的速度操作开关,这意味着使用更多、更快的晶体管无需更大功率或产生更多的余热。Moore对这种计算能力的指数式增长进行了预测,坊间非正式地称其为“摩尔定律”。Moore在１９７５年对摩尔定律进行了修改,认为晶体管数量将每两年增加一倍,这显示了芯片的微型化在过去１０年内已明显减速。然而,２０００年初,高端芯片的运行速度已进入坪曲线,而生产芯片的成本一直上升。其中一个有趣的观察是,电子组__件正逐渐接近原子尺度,因此使储存与操作比特变得越来越难;再进一步的观察是,当电子器件的尺度变得与原子一样小时,其功能将受到量子物理效应的干扰,从而导致经典计算机无法正常运算。在这两个观察的基础上,对经典系统计算能力的指数式增长的预期将在未来１０~２０年内完全失效。这显然是发展量子计算的一个强烈动机。

从摩尔定律推出的结果被认为有两个:１)小型化使器件密度增加,导致计算机存储量亦随同增加,因此为运算提供了更大的储存空间;２)处理器的运行速率也有可能随之增加,使之能够加速计算过程１)。计算机科学家Sedgewick对此却另有异议。他指出,随着计算机的加速,现有的算法反而会减速。Sedgewick的逻辑推论如下:假设有一个时间复杂度为O(nlogn)的算法,其中n 为问题的规模,如果将处理器速率增加一倍,便可以以nlogn２ 的时间运行该算法;如果再将存储器空间加倍,同一算法所需的空间便有可能扩大至填满有限的储存器;原来的储存器只能处理n 输入数据,现在则能处理２n 数据,因此算法的运行时间即为２nlog２n２ ＝nlogn＋n,比原来的复杂度多了一个线性因素n。

就计算时间复杂度而言,经典计算机使用nbits来同时储存n 个信息数字(informationdigits)或一个经典状态。而量子计算中的叠加原则指出,n 个量子比特可用来同时储存２n 个信息数字或２n 个量子经典状态。假设有一个用于n 个经典比特(一个经典状态)的函数f,则需要T(１)＝s 个时间单位,当将f 应用于n 个量子比特(２n 经典状态)时,运算所需时间同样是T(２n)＝s 个时间单位,即在同一时段内,一个量子计算机能够同时处理２n 个值,而一个经典计算机只能处理n 个值。这种内在并行性似乎表示使用量子系统计算问题比使用经典系统计算问题具有时间上的优势。但这个说法存在两方面的问题。１)一个并行算法的计算速度不一定比串行算法快。NC 复杂度指能够在并行计算机上使用O(nk)个处理器,并在综合对数(polylogarithmic)时间O(logcn)内求解的一类难题,其中n 为输入规模,k 和c 皆为常数。NC 并行性复杂度是计算复杂性理论中的P 复杂性类(意即多项式时间算法)的一个子集合。正如复杂度科学中的P＝NP 问题为未知,P＝NC 的真假亦为未知。如果答案是肯定的,所有多项式时间算法都可以有并行性版本,并能够使用多项式数量的处理器来求解。２)但在２０世纪７０年代有学者发现,有些难题难以进行并行化处理[１１]。这些难题被称为“P 固有串行难题”,并有自己独特的复杂性,称为“完全复杂性”。譬如,电路求值问题已被证明隶属此类[１２]。这类计算的问题似乎有一个共同点:没有并行算法能够求解这些问题或并行算法的并行性很低。因此,对整个P 完全类来说,即使使用更多处理器,也不会有效地提高计算速度。

【下载地址】

链接：https://pan.baidu.com/s/1CLL2RoF5QT_6xA4-O2fumA 提取码：3qgk