量子计算算法介绍_龙桂鲁

物理# 39 卷 ( 2010年) 12 期 http:PPww w. wuli. ac. cn 量子计算和量子信息专题 量子计算算法介绍* 龙桂鲁­ (清华大学原子分子与纳米科学重点实验室 清华大学物理系 北京 100084) 摘 要 量子计算机利用量子力学原理进行计算, 具有量子并行计算的优势, 能够超越经典计算 1990 年中期, 量 子算法取得突破,舒尔( Sho r)构造了大数质因子的量子算法, 葛洛沃( G rover)构造了无序数据库的量子搜索算法, 引 起了人们对量子计算的重视,极大地推动了量子计算的研究. 文章简单介绍了几个典型的量子算法以及量子算法研 究的一些新进展. 关键词 量子算法,舒尔( Sho r)算法,葛洛沃( Gro ver)算法, 量子计算机 Introduction to quantum algorithms Long Gu-i Lu­ (K ey L aboratory f or A tomic and M olecu lar N anosc iences and Depar tment of Phy sic s, T singhua Univer sity , Bei j ing 100084, China) Abstract Quantum informat ion is an int erdisciplinary science involving quantum mechanics, in formation theory, and computer science. It is of strategic importance and has far-reaching inf luence. Born in the late 1970s, it has developed very fast s ince the mid- 1990s. Quantum inf ormat ion science includes quantum com- put ing, quantum communicat ion, and so on. T he combinat ion of diff erent branches of science has led t o many new research topics in science and t echnology, and many remarkable achievements have been made. T his paper w ill int roduce the basics of quantum information science, including some very import ant quantum algorithms such as Shor. s algorit hm and Grover. s algorithm. T he former factorizes an integ er in polynomial steps, while the lat ter finds a marked it em w ith a square- root increase in speed compared to classical algo- rithms. O ther recent studies of quantum algorithms will also be reviewed. Keywords quantum algorit hms, Shor algorit hm, Grover algorit hm, quantum computer * 国家自然科学基金(批准号: 10775076)、国家重点基础研究发展 计划(批准号: 2006CB921106)资助项目 2010- 10- 19收到 ­ Em ail: gl long@ tsinghu a. edu. cn 1 引言 量子计算机由两条不同的路线发展出来. 一条 路线是发展可逆计算机, 可逆计算机可以由计算结 果反逆推出输入,因为可逆计算机可以大大减少热 耗.班尼奥夫( Benio ¯ )首先利用量子力学原理构造 了可逆的量子计算机[ 1] . 量子计算机发展的另一条 路线是科学研究的需求,费曼( Feynman)指出, 对一 个量子力学体系进行模拟, 需要的计算资源是体系 大小的指数函数,经典计算机是无法满足模拟需要 的.对量子体系的模拟,必须使用以量子力学原理进 行计算的量子计算机 [ 2] . 早期量子计算机的研究非常少. 1994年, 舒尔 ( Shor)构造了大数质因子分解的量子算法[ 3] ,可以 用多项式的复杂度进行大数质因子分解. 1996年, 葛洛沃( Gr over)给出了一个量子搜索算法[ 4] , 可以 平方根地加速无序数据库的搜索. 这些算法显示出 量子计算机具有超越经典计算机的强大功能, 引起 了学术界和西方国家的国防安全部门的重视, 极大 地推动了量子计算机研究的发展. 从此量子计算机 的研究成为国际上的持续的前沿研究领域. #803# http:PPw ww . w uli. ac. cn 物理# 39 卷 ( 2010 年) 12期 我们在本文中简单介绍量子计算的基本知识,重 点介绍几个重要的量子算法, 并简单介绍最近的相关 发展.如需要比较详细系统的阅读, 请参考文献[ 5 ) 7] , 一些近期量子信息的进展可以参考文献[ 8) 11] . 2 量子幺正操作和量子逻辑门 根据量子力学理论, 孤立量子系统态矢量随时 间的动力学演化遵从 SchrÊ dinger 方程: iÜ 9 | W( t)4 9t = H^ | W( t)4 . ( 1) 同时, 在量子力学中, 孤立系统的态| W( t )4随时间的 演化还可以通过演化算符 U( t , t0 )来描述: | W( t)4 = U( t , t0) | W( t0)4 . ( 2) 当哈密顿量 H^ 不显含时间时, 利用初始条件 U( t, t0 ) = 1,可求得演化算符为 U( t, t0) = e- iÜH^ ( t- t0) . ( 3) 在量子力学中,如果算符 A 满足如下关系, 则称之 为幺正算符, AA ­ = A ­ A = I , ( 4) 其中 I 为单位矩阵.显然,由于 H^ 是厄米算符, 演化 算符 U( t , t 0)满足幺正算符的要求, 即 UU + = U + U = I , ( 5) 因此, 幺正算符 U( t, t 0)对应的变化通常被称为幺正 变换或幺正操作.演化算符的幺正性使得量子信息 过程有如下一些特殊的性质: ( 1) 保几率性,即量子 态的归一化性质不随时间的改变而改变, 量子系统 的总几率保持不变; ( 2)可逆性,即量子信息处理中 的所有逻辑操作都是可逆的. 在量子信息处理过程中, 系统的幺正演化通过 量子逻辑门来完成, 根据作用的量子位数目, 量子逻 辑门被分为单量子比特门、二量子比特门和多量子 比特门. 常见的单量子比特门主要有 U I , U x , Uy , Uz 和Walsh-Hadamard门 H .在基矢{ | 04 = 1 0 , | 14 = 0 1 }下,几个常见的单量子比特门的矩阵可 表示为 U I = I = 1 0 0 1 , ( 6) U x = Rx = 0 1 1 0 , ( 7) U y = - iRy = 0 - 1 1 0 , (8) U z = Rz = 1 0 0 - 1 , (9) H = 1 2 1 1 1 - 1 . (10) 量子控制非门 ( CNOT 门)是最常用的二比特 量子门之一, 其中的两个量子比特分别为控制比特 与目标比特. 当控制比特为| 04时,它不改变目标位; 当控制比特为| 14时,它将目标位翻转. CNOT 门的 矩阵表示为 CNOT = 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 . (11) 英国科学家道亦奇( Deutsch)证明了任意的酉 变换都可以用一组有限数目的简单酉变换的组合来 构造,这些简单的酉变换称为基本逻辑门 [ 12] . 巴兰 克( Barenco)、班尼特( Bennet t )、克里夫 ( Cleve)、狄 文琴佐( Divincenzo )、马国鲁斯( Magolus)、舒尔等 在 1995年给出了利用单量子比特旋转门和 CNOT 门构造任意酉变换的一般方法, 并给出了 4个比特 下的具体结果 [ 13] ,任意数目的体系中的分解解析表 达式在文献[ 14]中给出.如何使用最少的基本逻辑 门来实现一个给定的酉变换, 是一个重要的量子计 算问题, 目前已经有许多这方面的研究. 3 量子并行性与量子算法 量子并行计算贯穿于量子算法之中, 使得量子 算法与经典算法相比,以更高的效率得到所期望的 计算结果.量子并行性是指, 如果将量子计算过程中 实施某个函数 f ( x )的幺正操作 U f , U f 作用在量子 寄存器的输入叠加态上,则它将对每个基矢进行作 用, 并将所有结果进行线性叠加, 产生一个输出叠加 态. 因此,只需要应用一次 U f 就可以同时计算出不 同 x 值对应的函数 f ( x ) . Uf E i | i4| 04 = E i | i4| f ( i )4 . (12) 量子计算机是服从量子力学规律的新型计算模 型, 通常,我们需要用量子计算机模拟量子物理系统 #804# 量子计算和量子信息专题 物理# 39 卷 ( 2010年) 12 期 http:PPww w. wuli. ac. cn 随时间的演化: U = eiH t ,从而完成某一计算任务, 这 就需要给出具体的算法, 即给出量子逻辑门序列来 实现这个幺正操作. 量子算法的任务是将一系列量 子逻辑门组织起来, 实现对量子计算机状态的幺正 操作, 使量子计算机按照者的意愿随时间演化, 达到预期的输出状态. 量子算法目前可以归为以下几个种类: ( 1)模拟 量子力学体系性质的量子仿真.从理论上说, 量子计 算机对此类问题具有指数化的加速; ( 2)基于葛洛沃 量子搜索算法的量子振幅放大类算法. 量子振幅放 大算法即放大所需要的输出值的振幅. 它的基本思 想是对量子态进行幺正变换, 从而放大所需要的输 出值, 使得在测量的时候可以很大的概率得到该结 果,例如,这类算法包括了葛洛沃搜索算法及其改进 和推广算法 [ 4, 15, 16] ; ( 3)相位估计量子算法. 舒尔算 法就属于这一类算法.它的思想是通过量子酉变换, 估算特定态的相位, 而这个相位与本征值成正比; ( 4) /相对黑盒0指数加速的量子算法.这类算法是一 些特别设定问题的算法,在这些问题中, 量子算法显 示出明显的优越性, 如道亦奇算法等. 4 量子仿真 假设体系 S是我们需要研究的体系, 而量子计 算机体系是 P, 量子仿真的任务就是要在量子计算 机中仿真体系 S的动力学演化等性质. 在经典计算 机上进行仿真往往需要进行很多的简化, 如在原子 核结构理论的计算中,通常只能取价核子,并且局限 在轻核和中等质量的原子核中. 而利用量子计算则可以不采用这些简化.如果体 系 S和量子计算机体系P 之间存在着可逆的映射 <, | W S ( 0)4 = <| W P ( 0)4,则我们可以先在量子计算机中 研究 P体系的演化, | W P ( T )4 = V P ( T ) | W P ( 0)4, 然 后再通过逆映射,仿真所需要研究的体系 S 的演化, | W S ( T ) = <- 1 | W S ( T ) 4[ 17] . 而对应于量子计算机的演 化 V P 可以利用最基本的量子门进行构造. 量子仿真可能会成为量子计算机的一个最大的 应用方向. 根据一般的估计,具有几千个以上数目的 量子比特的量子计算机在较短的时间内实现可能比 较困难,但是只要能够有几十个量子比特的量子计 算机, 就可以做相当多的实际量子体系的仿真.量子 仿真的研究已经成为当前的热点研究方向之一, 例 如已经演示了量子体系的三体相互作用[ 18]、四体相 互作用 [ 19]、氢分子的结合能 [ 20, 21]等. 5 /相对黑盒0指数加速的量子算法 量子黑盒是执行某种计算任务的幺正操作. 它 可以作为量子计算的一段子程序, 当量子黑盒的输 入为量子叠加态时,与输入为经典态时相比,它可以 实现计算的指数加速,对应的算法称为/相对黑盒0 指数加速的量子算法. /相对黑盒0指数加速的量子算法的一个典型代 表是 Deutsch- Jo zsa 问题及其算法 [ 22] .在要求精确 解的时候, Deutsch- Jo zsa 问题的经典解没有多项 式算法, 量子算法具有指数加速的优势. Deutsch- Jo zsa 问题是指: 假设有一个 n位输入的量子黑盒, 它的计算函数为 f {0, 1} n y 0, 1 , (13) 如果对所有的输入 x , f ( x )都是 0 或者 1,称 f ( x ) 是常数函数; 如果对一半的输入 x , f ( x )= 0,对另一 半的输入 x , f ( x ) = 1,则称 f 是对称函数. Deutsch - Jozsa问题希望判定 f 是否为常数函数. 如果利用经典态作为输入, 共需 2n + 1次计算 来解决此问题.而利用量子叠加态作为输入,则只需 要运行一次量子黑盒, 就可以得到肯定的结果. 过程 如下:首先,利用 1个辅助量子位,将 n+ 1量子位的 Walsh- Hadamard变换 H á ( n+ 1)作用在| 04n | 14态 上, 得到输入态 H á ( n+ 1) | 04n | 14 = 1 2 n/ 2 E 2n- 1 x= 0 | x4 1 2 (| 04- | 14) . (14) 然后进行 Uf 操作,得到 U f H á ( n+ 1) | 04n | 14 = 1 2n/ 2 E 2n- 1 x= 0 (- 1) f ( x) | x4 1 2 ( | 04- | 14) . (15) 再对前 n个输入量子位进行 H á n操作,得到 1 2 n/ 2 E 2n- 1 x= 0 (- 1) f ( x) E 2n- 1 y= 0 (- 1) x#y | y4 . (16) 此时测量前 n个量子位, 如果测得| 00 , 04态时, 说明 f ( x ) 是常数函数; 如果测得的状态不是 | 00 , 04态时, 说明 f ( x )是对称函数. 可见, 相对 于经典算法的 2n + 1次计算, Deutsch- Jozsa 量子 算法只需一次黑盒计算就解决问题,它实现了/相对 黑盒0的指数加速. #805# 量子计算和量子信息专题 http:PPw ww . w uli. ac. cn 物理# 39 卷 ( 2010 年) 12期 6 舒尔大数质因子分解算法 舒尔大数质因子分解算法[ 3]是一个典型的实现 指数加速的量子算法.根据经典计算复杂性理论, 分 解大数质因子属于 NP 困难问题(即没有多项式算 法的问题, 但不是 NPC 问题) ,而在量子计算机上利 用舒尔大数质因子分解算法, 可以在多项式时间解 决这一问题,实现了计算的指数加速. 找两个质数的乘积是一个很容易进行的运算. 可是如果反过来,把一个乘积分解成两个质数的乘 积,则相对于前者是一个麻烦得多的问题.一般情况 下,一个大数 N , 我们要将其分解, 约需要计算 N = 2 1 2 log 2 N步. 计算的步数与大数的位数成指数增长 关系. 一个 600位的大数,使用目前最快的计算机, 居然要用比整个宇宙的年龄还要长的时间才能分解 出.目前广泛使用的 RSA 密钥系统的基础即是假定 不存在快的大数分解算法.而使得 RSA 密钥系统受 到巨大挑战,同时也推动了人类对量子计算机的研 究.在量子计算机上实现舒尔的大数分解算法,分解 一个 L 位的大数, 计算步数下降为 O(L 3) . 假定要分解的大数为N ,舒尔算法的过程如下: ( 1) 随机选取 a( a< N 并与N 互质) ,用量子算 法求函数 f ( x )= axmodN 的周期T . ( 2) 若 T 为奇数, 则返回 1, 重新选取 a; 若 T 为偶数,则取 y= aT/ 2 . ( 3) 求得 y 后, 用欧几里德辗转相除法求得 y- 1, y+ 1 与 N 的最大公约数n 1 , n2 , 则可以找到 质因子. 以上算法的关键在于求得函数 f ( x ) = axmodN 的周期 T ,这是量子计算机体现其优越性的地方. 以 上算法在经典计算机上进行时,需要使用比量子计 算机指数多的物理资源, 同时计算步骤也是呈指数 增加的. 7 相位估计算法[ 23, 24] 假设酉算符 U 有一个本征矢量| u4, 相应的本 征值是 e2Pi<, <是未知的. 相位估计算法的目的就是 要将相位 <估算出来. 这个算法可以用于构造许多 其他量子算法. 算法的输入: ( 1) 一个能够运行受控 U j 运算的 系统, j 是一个任意的整数; ( 2) U的一个具有本征 值 e2Pi标准

excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载