第２５卷第５期 白城师范学院学报 Ｖｏ１．２５，Ｎｏ．５ ２０１１年ｌ０月 Ｊｏｕｒｎａｌ ｏｆＢａｉｃｈｅｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ Ｏｃｔ．，２０１１ 量子算法的研究进展 马宏源，杨晓翠，李伟 （白城师范学院物理系，吉林白城１３７０００） 摘要：文章在介绍量子算法原理的基础上，重点介绍了Ｓｈｏｒ算法，Ｇｒｏｖｅｒ量子搜索算 法以及量子进化算法的研究进展．最后阐述了量子算法主要面临的问题及研究前景． 关键词：量子计算机；量子计算；量子算法 中图分类号：０４１３．１ 文献标识码：Ａ 文章编号：１６７３－３１１８（２０１１）０５－０００５－０３ 关于量子计算的研究可追溯到上个世纪中叶， 钥分配协议．量子计算下可以有效地求解两个素数 它是通过量子并行计算利用量子理论中量子态的 乘积的整数解问题的核心是Ｓｈｏｒ整数求阶量子算 叠加和纠缠等特性来求解问题的．量子计算机对每 法的提出，该算法是一个概率算法，算法运行一次 一个叠加分量实现的变换相当于一种经典计算，所 成功的概率是４‘Ｐ（ｒ）／，ｔｒ２（‘Ｐ是欧拉函数，ｒ是ｚ 中 有这些经典计算同时完成，并按一定的概率振幅叠 所选元素的阶）．Ｄ ＭｃＡｎａｌｌｙ在２００２年提出了一种 加起来，给出量子计算机的输出结果，这种计算称 新的整数求阶算法，该算法执行两次Ｓｈｏｒ整数求 为量子并行计算．量子并行处理大大提高了量子计 阶量子算法得到ｚ 中所选元素阶的概率大于 算机的效率，使得其可以完成经典计算机无法完成 ６０％，执行四次Ｓｈｏｒ整数求阶量子算法，得到所选 的工作，例如一个很大的自然数的因子分解．量子 元素阶的概率大于９０％，但是该算法本质上仍依 相干性在所有的量子超快速算法中得到了本质性 赖于Ｓｈｏｒ整数求阶量子算法的成功率．但Ｓｈｏｒ算 的利用．因此，用量子态代替经典态的量子并行计 法使用了大量的计算资源以至于很难在实验上实 算，可以达到经典计算机不可比拟的运算速度和信 现，迄今为止实验上使用Ｓｈｏｒ算法分解的最大数 息处理功能，同时节省了大量的运算资源．量子计 是ｌ５．中国科大合肥微尺度物质科学国家实验室 算这一独特的计算方式引起了各研究领域众多学 杜江峰教授领导的杜江峰课题组首次提出了用于 者的兴趣．首先是Ｓｈｏｒ提出了震惊世界的大整数 大数分解的绝热量子算法，并利用该新算法首次在 素因子分解量子算法，随后Ｇｒｏｖｅｒ发表了一个乱 实验上实现了２１的分解，所使用的量子比特数不 序数据库搜索的量子算法．近年来，量子进化算法 到Ｓｈｏｒ算法分解ｌ５所使用的比特数的一半，而且 的研究也取得了令人鼓舞的成就．…这些算法无 实验中分解时间更快．尽管无法严格证明新算法的 一不展示了量子计算与经典计算相比所具有的显 时间复杂度，在有限的数值模拟中新算法有着与 著优越性． Ｓｈｏｒ算法类似的效率。绝热量子计算的直接物理依 １ 整数分解量子算法 据是量子力学中的绝热定理，因此对绝热量子算法 １９９４年，Ｐ ｗ Ｓｈｏｒ提出了一个在多项式时间 的研究依赖于绝热定理的成立条件．２００４年，加拿 内求解整数分解问题和有限域上离散对数问题的 大的研究小组对绝热定理自洽性提出了质疑，从而 量子计算算法，它在密码学上的重要意义是：利用 引发了一系列的相关理论的探索．在这种对基本定 该算法可以在多项式时间内成功破译ＲＳＡ公钥密 理存在争议的情况下，实验的研究无疑是最有说服 码系统，ＥＣＣ公钥密码体系和Ｄｉｆｉｆｅ—Ｈｅｌｌｍａｎ密 力的．杜江峰课题组通过控制磁场中的核自旋的演 收稿日期：２０１１—０９—０５ 作者简介：马宏源（１９８３——），女，白城师范学院物理系讲师，理学硕士，研究方向：量子光学 基金项目：白城青年基金项目“典型量子算法的研究”（［２０１０］Ｃ１５号）成果之一． ５ 白城师范学院学报 第２５卷第５期 化，首次在实验上发现了绝热定理成立条件的非充 分必要性，相关研究成果发表在２００８年８月８日 出版的《物理评论快报》上．长期以来，如何进一步 提高整数求阶量子算法的成功概率一直是整数分 解问题量子算法研究的难点．２０１ １年，付向群等人 基于量子Ｆｏｕｒｉｅｒ变换给出了一个新的整数分解量 子算法，通过利用多次量子Ｆｏｕｒｉｅｒ变换和变量代 换，使得ｒ变成相位因子（ｒ是从模Ｎ整数环中所 选元素的阶），进而可使非零的非目标态的几率幅 １９９８年，针对目标元素个数Ｍ＝１的情况，Ｂｉ— ｈａｍ Ｅ等人证明了不可能存在比Ｇｒｏｖｅｒ量子搜索 算法更快更有效的以非均匀为起点的量子算法；随 后，Ｚａｌｋａ Ｃ等人于Ｉ９９９年证明了利用量子黑盒作 为工具的量子搜索算法不可能有更快的计算速度， 即在算法成功率高于５０％时，使用黑盒调用的量 子搜索算法中Ｇｒｏｖｅｒ搜索算法是最优的．但Ｇｒｏｖｅｒ 搜索算法也存在一定的问题，即当目标元素个数逐 渐接近时，有证明Ｇｒｏｖｅｒ量子搜索算法成功率将 变为零，算法成功的概率大于３／４，高于Ｓｈｏｒ整数 分解量子算法，且不再依赖于ｒ的大小． 从Ｓｈｏｒ算法中，我们可以看出量子算法的共 性：量子计算是用量子比特来代表信息，用量子力 学理论来描述有关信息表示和信息处理的所有问 题．其中信息的演变遵从薛定谔方程，信息的提取 是对量子系统的量子状态进行测量坍塌的结果，信 息计算和信息处理是量子比特的一系列么正变换． ２ Ｇｒｏｖｅｒ量子搜索算法 众所周知，要在经典计算机上从有Ｎ个记录 的无序数据库中搜索出指定的记录，算法的时间复 杂性为Ｏ（Ｎ）．因为搜索数据库是在外存进行的， 所以当记录数Ｎ充分大时，搜索工作犹如“大海捞 针”一样的困难与烦琐．Ｇｒｏｖｅｒ于１９９７年在物理学 界顶尖杂志Ｐｈｙｓｉｃｓ Ｒｅｖｉｅｗ Ｌｅｔｔｅｒ上发表了一个乱 序数据库搜索的量子算法，其时间复杂性为Ｏ （￣／Ｎ）．此量子搜索算法与经典搜索算法相比达到 数量级的加速，特别适用于求解那些需要用穷举法 对付的ＮＰ类问题．相对于传统搜索算法要克服由 解空间过大而导致的需要搜索的路径过多的问题， 量子算法面临的主要是解集的振幅太小的问题．所 以传统搜索算法主要是要避免在无效路径上进行 搜索，而搜索所有的路径对量子算法来说不是困难 所在．量子算法要解决的则是如何减少、消除非解 路径上的振幅，并把它转移到解路径上来．打一个 比喻，搜索算法解决问题就像看一幅巨大的图画并 把目标从中找出来，而传统的方法就好像一个近视 的人为了看清图，不得不离图很近，所以每次只能 看到一个或几个点．因此为了在有限的时间内看到 目标点，他不得不利用结构信息跳跃着选择注视 点；而量子算法好像站在远处了望的人，他可以同 时看到整幅图画，只是他看到的是一幅模糊的图 画，而为了看清目标，他必须设法把目标的“颜色” 加浓，同时使其他点的颜色变淡，从而使目标更突 出．“颜色”的深浅在这里就相当于振幅的大小． ６ 会降低．因此，科学家们不断改进算法，以提高 Ｇｒｏｖｅｒ量子搜索算法的成功率．２００３年，Ｙｏｕｎｅｓ Ａ 提出了一个量子搜索算法，它的成功率为８７． ８８％．２００５年，Ｇｒｏｖｅｒ给出了一种新的成功率达到 ９２．６％的量子搜索算法．２００７年，孙力等人在量子 计算仿真程序上进行了３量子位的Ｇｒｏｖｅｒ量子搜 索算法的实验验证，实现了以核磁共振和多量子算 符代数理论为基础，多量子位Ｇｒｏｖｅｒ量子搜索算 法的核磁共振脉冲序列设计方法．同年，马宏源等 人 在热腔中实现了Ｇｒｏｖｅｒ量子搜索算法．２００９ 年，张煜东等人提出了基于扩大搜索空间的改进算 法，增加一个新参数ｉ使得算法可调。求逆问题的 仿真实验表明该方法在同等迭代次数的条件下，成 功概率高于传统Ｇｒｏｖｅｒ算法，且如果迭代次数不 限，则成功概率可以更高． ３量子进化算法 一 量子进化算法是进化算法和量子计算相结合 的一种新的优化算法，它比传统进化算法有更好的 种群多样性和全局寻优能力．它一方面吸取量子计 算方面的一些概念和理论，如量子位、量子叠加态 等，采用量子比特编码染色体，可以使一个量子染 色体同时表征多个态的叠加，利用量子门作为更新 算子来完成进化搜索．另一方面，基于进化机制将 进化论、群智能、免疫原理、混沌理论、神经网络、多 智能体系统等领域的一些思想、机制、操作和研究 成果融入量子计算，设计新的量子计算模式、搜索 操作、优化算法和相应的信息处理系统．由于量子 计算的内在并行性，量子进化算法在许多领域的应 用都获得了成功，同时获得了比传统进化算法更高 的搜索效率．但量子进化算法解决复杂优化问题的 能力不强，容易陷人局部最优的僵局，而且量子进 化算法是采用查表的方式更新量子门的，所以需要 设定较多的参数，同时实现起来较为复杂．为了使 量子进化算法能够更有效的解决实际的优化问题， 探索新的量子进化算法有重要意义． 量子算法的研究进展 １９９６年，Ｎａｒａｙａｎａｎ等人 首次提出了量子遗 传算法（ＱＩＧＡ）的概念，将量子理论与进化算法相 结合．Ｈａｎ等人于２０００年提出了一种遗传量子算 法，然后实现了组合优化问题的求解，扩展为量子 进化算法．量子进化算法利用当前最优个体的信息 来更新量子旋转门，以加速算法收敛．若进一步引 入量子交叉、变异和灾变等操作，则可以克服早熟 收敛现象．２００４年，马淑霞等人 改进了量子进化 算法仅靠量子门进行迭代的作用，将下降搜索理论 对的问题复杂，相应地，算法复杂性一般也很高．我 们认为，对于后者，量子算法的研究可能会在很大 程度上改变这种局面．目前量子算法的研究正处于 个重大突破的前夜，因为量子计算机的研制在技 术上还存在巨大障碍．但是由于传统的半导体技术 发展已经接近极限，可以预测现在的计算机技术必 然要发生重大变革．尽管目前量子算法的研究仍处 于实验室阶段，但由于量子算法在性能和效率上具 有传统算法无法比拟的优越性，因此它终有一天必 一应用到量子进化算法中，降低了个体在进化时产生 将会取代传统算法． 退化的可能性，加快了收敛速度．２００６年，杨淑嫒 等人【６ 将进化算法和量子理论结合，提出一种新 参考文献： 的理论框架——量子进化理论及其学习算法，该算 ［１］王凌．量子进化算法研究进展［Ｊ］．控制与决幕，２００８，２３（１２）： 法在防止算法早熟的同时能使算法更快收敛，并用 １３２１—１３２６． 一个染色体表示多个状态：模拟量子坍塌的随机观 ［２］Ｚｈａｎ Ｑｉａｎｃｈｕａｎ．Ｑｕａｎｔｕｍ ｃｏｍｐｕｔｉｎｇ ａｎｄ ｑｕａｍｔｕｍ ｉｎｆｏｒｍａｔｉｏｎ 察能带来丰富的种群．２００８年，Ｍｉｎｇ等人借助“波 （Ｉ）一Ｑｕｍａｔｕｒｅ ｃｏｍｐｕｔｉｎｇ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｔｓｉｎｇｈｕａ Ｕｎｉｖｅｍｉｔｙ Ｐｒｅｓｓ， ２Ｏｏ４． 粒二向性”特征将传统遗传算法和量子进化算法 ［３］马宏源，王洪福，张寿．在热腔中实现Ｇｒｏｖｅｒ量子搜索算法［Ｊ］． 进行了类比．为达到种群弱链接，Ｇｕｏ等人于２００９ 延边大学学报，２００８，３４（１）：２７—３Ｏ． 年利用复杂网络理论类比量子进化中的各个个体 ［４］Ｎａｒａｙａｎａｎ Ａ，Ｍｏｏｒｅ Ｍ．Ｑｕａｎｔｕｍ—ｉｎｓｐｉｒｅｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ 问关系，提出一种将种群分解成局部小群，各小群 ［Ｃ］．ＩＥＥＥ Ｃｏｎｇｒｅｓｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ．Ｎｏ￣ｙａ，１９９６： ６１—６６． 进行局部进化并能有效避免早熟的算法．２０１ １年， ［５］马淑霞．基于下降搜索的量子进化算法［Ｊ］．西南交通大学学 钱洁等人 提出了量子进化算法在模式理论、多 报，２００４（３）：３９０—３９３． 目标进化、算法研究、应用等方面的进一步研究内 ［６］杨淑媛，焦李成，刘芳．量子进化算法［Ｊ］．工程数学学报，２００６， 容． ２３（２）：２３５—２４６． ４结束语 ［７］钱洁．量子进化算法研究现状综述［Ｊ］．控制与决策，２０１１，２３ （１２）：１３２１—１３２６． 自从Ｓｈｏｒ算法发表以来，国际计算机科学界 ［８］钟诚，陈国良．量子计算及其应用［Ｊ］．广西大学学报，２００２，２７ 十分重视量子计算理论和技术的研究．我国计算机 （１）：８３—８６． 界从１９９７年左右开始涉足此领域，并取得若干重 ［９］张镇九．量子计算机的物理实现［Ｊ］．高等函授学报，２０００，１３ 要的成果 ¨，这是一个良好的开端．量子计算技 （６）：１—７． 术对人工智能的发展有深远的影响．对于现在的人 ［１Ｏ］马雷．量子计算与量子计算机［Ｊ］．物理教学，２００６，２８（６）：７— ９． 工智能来说，面临的两个主要问题是：（１）缺乏统 ［１１］张镇九，张昭理．量子计算机进展［Ｊ］．计算机工程，２００４，３０ 一的基本理论的指导，经验的成分较多．知识表示 （８）７—９． 能力与自然语言理解能力还不够．（２）人工智能面 Ｔｈｅ Ｒｅｓｅａｒｃｈ Ｐｒｏｇｒｅｓｓ ｉｎ Ｑｕａｎｔｕｍ Ａｌｇｏｒｉｔｈｍｓ ＭＡ Ｈｏｎｇ—ｙｕａｎ，ＹＡＮＧ Ｘｉａｏ—ｃｕｉ，ＬＩ Ｗｅｉ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｐｈｙｓｉｃｓ，Ｂａｉｅｈｅｎｇ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｂａｉｃｈｅｎｇ １３７０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｅｓｓａｙ ｍａｉｎｌｙ ｉｎｔｒｏｄｕｃｅｄ Ｓｈｏｒ ａｌｇｏｒｉｔｈｍ，Ｇｒｏｖｅｒ ｑｕａｎｔｕｍ ｅｖｏｌｕｔｉｏｎ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｈｅ ｐｒｏ— ｇｒｅｓｓ ｏｆ ｑｕａｎｔｕｍ ｅｖｏｌｕｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｑｕａｎｔｕｍ ａｌｇｏｒｉｈｔｍ ｔｈｅｏｒｙ．Ｉｔ ｅｘｐｏｕｎｄｅｄ ｔｈｅ ｍａｊｏｒ ｐｒｏｂｌｅｍｓ ａｎｄ ｒｅｓｅａｒｃｈ ｐｒｏｓｐｅｃｔ ｗｈｉｃｈ ｑｕａｎｔｕｍ ａｌｇｏｒｉｔｈｍ ｈａｄ ｔｏ ｃｏｎｆｒｏｎｔ． Ｋｅｙ Ｗｏｒｄｓ：Ｑｕａｎｔｕｍ ｃｏｍｐｕｔｅｒ；Ｑｕａｎｔｕｍ ｃｏｍｐｕｔａｔｉｏｎ；Ｑｕａｎｔｕｍ ａｌｇｏｒｉｈｔｍ 责任编辑：王丽萍 ７
