量子信息学引论第讲精选文档.ppt

量子信息学引论第讲本讲稿第一页，共七十一页前一讲回顾5.1 5.1 量子量子FourierFourier变换变换和经典离散和经典离散FourierFourier变换形式相同变换形式相同速度指数倍提高速度指数倍提高但不能直接用来加速经典但不能直接用来加速经典FourierFourier变换变换5.2 5.2 相位估计相位估计相位估计则是许多量子算法的关键。相位估计则是许多量子算法的关键。酉算子酉算子U U具有本征矢量具有本征矢量|u,|u,其对应的本征值为其对应的本征值为 e e2 2p pij j,相位估计的目的相位估计的目的:得到得到j j的值。的值。2本讲稿第二页，共七十一页3相位估计回顾第一步第一步:第二步第二步第二步第二步:本讲稿第三页，共七十一页5.3 应用:求阶与因数分解5.3.1 5.3.1 应用应用:求阶求阶 (order-finding)(order-finding)5.3.2 5.3.2 应用应用:因数分解因数分解 (factoring)(factoring)4本讲稿第四页，共七十一页5.3 应用:求阶与因数分解相位估计步骤能用来解决一系列有趣的问相位估计步骤能用来解决一系列有趣的问题题,其中包括其中包括:求阶和因数分解求阶和因数分解求阶问题与因数分解问题等价。求阶问题与因数分解问题等价。5本讲稿第五页，共七十一页求阶和因数分解的快速量子算法为何有价值?(1)(1)它提供了量子计算机可能在本质上比经典它提供了量子计算机可能在本质上比经典计算机强大的证据计算机强大的证据,也提供了对强也提供了对强Church-Church-TuringTuring论题的一个可信的挑战。论题的一个可信的挑战。(2)(2)这两个问题本身都有足够价值这两个问题本身都有足够价值,值得研究值得研究其新算法。其新算法。(3)(3)求阶和因数分解的有效算法能用来破解求阶和因数分解的有效算法能用来破解RSARSA公钥密码系统。公钥密码系统。(4)(4)RSARSA的安全性假设建立在用经典计算机分的安全性假设建立在用经典计算机分解因数是困难的。解因数是困难的。6本讲稿第六页，共七十一页5.3.1 应用:求阶(order-finding)求阶的定义求阶的定义求阶的量子算法求阶的量子算法7本讲稿第七页，共七十一页求阶的定义 对于正整数对于正整数 x x 和和 N N,x x N,如常r=N+1 会有什么样的结果？有N+1个不同的余数,但是周期是N，因此一定小于最多等于N。本讲稿第九页，共七十一页求阶问题是经典计算机上的难题求阶问题是对某个固定的求阶问题是对某个固定的 x x 和和 N N 来确定阶来确定阶r r。求阶被认为是经典计算机上的一个难题。求阶被认为是经典计算机上的一个难题。理由理由:还不知道一个采用还不知道一个采用O(L)O(L)位的多项式资源的算位的多项式资源的算法来解此问题。其中，法来解此问题。其中，是表示给定是表示给定N N 所需的比特位数所需的比特位数.用相位估计算法可得求阶的有效量子算法。用相位估计算法可得求阶的有效量子算法。10本讲稿第十页，共七十一页求阶的量子算法用于求阶的量子算法恰巧就是对应于下面用于求阶的量子算法恰巧就是对应于下面酉算子上的相位估计算法：酉算子上的相位估计算法：其中其中 ，L 是量子比特的数目是量子比特的数目.11本讲稿第十一页，共七十一页相位估计中U的本征态U U的本征态的本征态:其中其中,整数整数s s 满足满足:12本讲稿第十二页，共七十一页相位估计中U的本征值 估计出相位估计出相位 s/r,s/r,即可设法得到阶即可设法得到阶 r.r.13本讲稿第十三页，共七十一页推导以上本征方程14本讲稿第十四页，共七十一页推导以上本征方程15本讲稿第十五页，共七十一页推导以上本征方程16因为因为x xr r=x=x0 0mod mod N N本讲稿第十六页，共七十一页相位估计中U的本征值 可以估计出相位可以估计出相位 s/r,s/r,采用连分数算法即可得采用连分数算法即可得到阶到阶r r。17本讲稿第十七页，共七十一页Box 5.3:连分数算法(The continued fractions algorithm)基本思想基本思想:只用整数来描述所有的实数只用整数来描述所有的实数.方法方法:分裂与倒置分裂与倒置(split and invert)(split and invert)对于任意有理数对于任意有理数,经过有限步经过有限步,此算法即可完成此算法即可完成.例例:31/13:31/13的连分数展开为的连分数展开为:2,2,1,1,2.:2,2,1,1,2.18本讲稿第十八页，共七十一页例子本讲稿第十九页，共七十一页连分数展开把求阶问题还原为相位估计把求阶问题还原为相位估计,是通过从相位估计算法是通过从相位估计算法的结果的结果 来得到希望的答案来得到希望的答案 r r。我们只知我们只知 近似到近似到 2L+12L+1位位,但我们事先知道但我们事先知道 为一为一个有理数个有理数 (两个有界整数的比值两个有界整数的比值)。这样，如果我们能够计算最近于此这样，如果我们能够计算最近于此 的分数，就可得的分数，就可得到到r r。20本讲稿第二十页，共七十一页定理 5.1 设设 s/r s/r 是一个有理数是一个有理数,使得使得则则 s/r s/r 是是 的连分数的一个渐近值的连分数的一个渐近值.21本讲稿第二十一页，共七十一页注意，注意，j j是对是对 s/rs/r的近似，精确到的近似，精确到2L+12L+1位。位。又因为又因为 ,所以：所以：定理5.1的应用22结论：给定 j,连分数算法可有效地产生出没有公因子的 s 和 r，使得s/r=s/r,r 是阶的候选对象，可以通过计算xr mod N,看是否为1，如果是，r是x 模N的阶。我们的任务就完成了。本讲稿第二十二页，共七十一页进行相位估计的两个条件 (1)(1)能够用有效的步骤来实施一个能够用有效的步骤来实施一个 操作操作,其中其中j j为任意常数为任意常数.(2)(2)能够有效地制备本征态能够有效地制备本征态 ，或本征态，或本征态的叠加态。而的叠加态。而 的本征值并不是简单的的本征值并不是简单的值。值。23本讲稿第二十三页，共七十一页实现第一个条件通过模幂通过模幂(modular exponentiation)(modular exponentiation)可满足相可满足相位估计的第一个条件位估计的第一个条件.采用模幂采用模幂,则可用则可用 个门来实现相估位计中需要的个门来实现相估位计中需要的 24本讲稿第二十四页，共七十一页Box 5.2 模幂(modular exponentiation)25用可逆运算得到用可逆运算得到x xz z(mod(mod N N),),首先计算首先计算x x2 2(mod(mod N N)，x x4 4(mod(mod N),N),直到直到x x2 2 j j(mod(mod N N),),即可得到：即可得到：本讲稿第二十五页，共七十一页实现第二个条件需要一些技巧：制备需要一些技巧：制备 要求我们知道要求我们知道 r r ，而我们事先并不知道而我们事先并不知道r r，所以直接制备所以直接制备 不可能。不可能。幸运的是幸运的是,如果我们注意到如果我们注意到,则我们可以绕过制备则我们可以绕过制备 的问题。的问题。26本讲稿第二十六页，共七十一页推导:(5.44)式27本讲稿第二十七页，共七十一页推导过程由于本讲稿第二十八页，共七十一页相位估计步骤的第一阶段 注意注意:右边省略了归一化因子右边省略了归一化因子29本讲稿第二十九页，共七十一页图5.4 求阶算法的量子线路第二个寄存器已被证明可以被初始化到第二个寄存器已被证明可以被初始化到|1|1态完成态完成求解运算。求解运算。不过不过,若利用练习若利用练习5.14,5.14,它也可被初始化它也可被初始化到到|0|0态态.这个线路也可用来进行因数分解。这个线路也可用来进行因数分解。30本讲稿第三十页，共七十一页量子Fourier变换的乘积表示31本讲稿第三十一页，共七十一页图5.1 量子Fourier变换的有效线路此线路可从量子此线路可从量子FourierFourier变换的乘积表示式中推出。变换的乘积表示式中推出。图中没示出线路末尾的交换门图中没示出线路末尾的交换门(swam gate),(swam gate),用交换门用交换门把量子位的次序反过来。把量子位的次序反过来。图中也没有显示出输出中的归一化因子图中也没有显示出输出中的归一化因子 。32本讲稿第三十二页，共七十一页其中其中x x与与N N互质；互质；（2 2）算法:量子求阶输入：（输入：（1 1）一个黑箱）一个黑箱U Ux,Nx,N能执行变换：能执行变换：（3 3）L L个量子位初始化到个量子位初始化到|1,|1,位初始化到位初始化到|0|0输出：满足输出：满足x xr r=1(mod=1(modN N)的最小整数的最小整数r r 0 0。运行时间：运行时间：O(O(L L3 3)个操作。成功率：个操作。成功率：O(1)O(1)33本讲稿第三十三页，共七十一页算法:量子求阶(步骤)34本讲稿第三十四页，共七十一页5.3.2 应用:因数分解(factoring)给定一个正合数给定一个正合数N N，它是由哪些素数相乘而，它是由哪些素数相乘而得？得？最好的经典算法：最好的经典算法：O O(exp(N)(exp(N)因数分解有什么用？因数分解有什么用？破解密码破解密码35参考文献：A.Ekert and J.Jozsa,Rev.Mod.Phys.68,733(1996).本讲稿第三十五页，共七十一页合数和素数合数和素数素数素数(又称质数又称质数)指在一个大于指在一个大于1的的自然数自然数中，除了中，除了1和和此整数自身外，没法被其他自然数此整数自身外，没法被其他自然数整除整除的数的数合数合数指在一个大于指在一个大于1的的自然数自然数中，除了中，除了1和此整数自身外，和此整数自身外，还有其他自然数还有其他自然数整除整除的数的数本讲稿第三十六页，共七十一页37MIPS是Million Instructions Per Second的缩写，每秒处理的百万级的机器语言指令数。这是衡量CPU速度的一个指标。像是一个Intel 80386 电脑可以每秒处理3百万到5百万机器语言指令，既我们可以说80386是3到5MIPS的CPU。MIPS只是衡量CPU性能的指标。本讲稿第三十七页，共七十一页因数分解与求阶问题等价。因数分解与求阶问题等价。即即,一个求阶的快速算法可以容易地转成因数分一个求阶的快速算法可以容易地转成因数分解的快速算法。解的快速算法。38因数分解与求阶问题等价本讲稿第三十八页，共七十一页因数分解与求阶问题等价39本讲稿第三十九页，共七十一页把因数分解问题还原为求阶问题分两步进行分两步进行:(1)(1)证明如果能够找到方程证明如果能够找到方程 的一个非平凡解，的一个非平凡解，则，则可以计算出可以计算出N N的一个因子。的一个因子。定理定理5.25.240本讲稿第四十页，共七十一页41(2)(2)证明一个任意选取的与证明一个任意选取的与N N互质的数互质的数y y，非常可，非常可能具有一个偶数阶能具有一个偶数阶 r r,并且并且,因而因而 是是 的一个非平凡解。的一个非平凡解。定理定理5.35.3 把因数分解问题还原为求阶问题本讲稿第四十一页，共七十一页定理 5.242本讲稿第四十二页，共七十一页定理 5.2gcd=greatest common divisor(最大公约数)lcm=least common multiple(最小公倍数)本讲稿第四十三页，共七十一页定理 5.344本讲稿第四十四页，共七十一页算法:利用求阶进行因数分解输入输入:一个合数一个合数N.N.输出输出:N:N的一个非凡因子的一个非凡因子.运行时间运行时间:操作操作.成功率成功率O(1).O(1).45本讲稿第四十五页，共七十一页算法:用求阶来进行因数分解(步骤)1.1.如果如果N N为偶为偶,返回因子返回因子2.2.2.2.确定是否有确定是否有 ,其中其中 若是若是,返回因子返回因子a.(a.(采用练习采用练习5.175.17的经典算法的经典算法).).3.3.在在1 1到到N-1N-1的范围内随机选取的范围内随机选取x x。若。若则返回因子则返回因子 gcd(gcd(x x,N N)。46本讲稿第四十六页，共七十一页算法:用求阶来进行因数分解(步骤)4.4.采用求阶子程序来求采用求阶子程序来求 x x mod mod N N 的阶的阶 r.r.5.5.如果如果r r为偶数为偶数,且且 则计算则计算 和和并验证其是否为非平凡因子并验证其是否为非平凡因子,如果是如果是,则返则返回此因子，否则回此因子，否则,算法失败算法失败.47本讲稿第四十七页，共七十一页Box 5.4:用量子算法分解15N=15,x=7,t=11,N=15,x=7,t=11,保证误差保证误差e e1/4|0|0|0第一寄存器做第一寄存器做HadamardHadamard变换变换48本讲稿第四十八页，共七十一页用量子算法分解15(续)49计算计算f(f(k k)=)=x xk k modmodN N，结果放在第二寄存器中结果放在第二寄存器中本讲稿第四十九页，共七十一页用量子算法分解15(续)假设第二寄存器被测量（隐含测量原理），随假设第二寄存器被测量（隐含测量原理），随机得到机得到1 1，7 7，4 4，1313，假设得到，假设得到4 4，则其状态，则其状态应用应用FourierFourier反变换后，第一寄存器得到不同状反变换后，第一寄存器得到不同状态的概率分布为：态的概率分布为：50本讲稿第五十页，共七十一页用量子算法分解15(续)也就是几乎以也就是几乎以1/41/4的概率得到，的概率得到，0 0，512512，10241024，15361536。假设得到。假设得到l l=1536=1536，从，从1536/20481536/2048用连续分用连续分数可得到，数可得到，r=4r=4是是x=7x=7的阶。的阶。r r是偶数且是偶数且51故算法有效：计算最大公因子故算法有效：计算最大公因子gcd(7gcd(72 2-1,15)=3,-1,15)=3,gcd(7gcd(72 2+1,15)=5,+1,15)=5,得到因子得到因子3,53,5本讲稿第五十一页，共七十一页 用核磁共振(NMR)法实验实现对15 的因数分解NATURE VOL 414,20/27 DECEMBER,2001,p883.52本讲稿第五十二页，共七十一页5.4 量子Fourier变换的一般应用5.4.1 5.4.1 求周期求周期 (period-finding)(period-finding)5.4.2 5.4.2 离散对数离散对数 (discrete lorithm)(discrete lorithm)5.4.3 5.4.3 隐子群问题隐子群问题 (the hidden subgroup(the hidden subgroup problem)problem)5.4.4 5.4.4 其它量子算法其它量子算法?53本讲稿第五十三页，共七十一页5.4.1 求周期(period-finding)54设设f 是是一一个个周周期期函函数数,它它的的输输出出是是一一个个位位,且且对对于于某某个个未未知知的的0r2L使使得得f(x+r)=f(x),其其中中,x,r0,1,2,.给给定定一一个个量量子子黑箱黑箱U,它执行变换它执行变换 问问:需要多少个黑箱调用及其它操作才能确定需要多少个黑箱调用及其它操作才能确定r?采用量子算法采用量子算法,需要对需要对U调用一次调用一次,以及其它以及其它个操个操作作。本讲稿第五十四页，共七十一页算法:求周期55本讲稿第五十五页，共七十一页算法:求周期(续)56本讲稿第五十六页，共七十一页5.4.2 离散对数(discrete lorithm)刚考虑的求周期问题是一个简单的问题刚考虑的求周期问题是一个简单的问题,因为其中函数的定义域和值域都是整数因为其中函数的定义域和值域都是整数.当函数更复杂时如何当函数更复杂时如何?57本讲稿第五十七页，共七十一页一个奇怪的周期函数考虑函数考虑函数 其中所有的变量都是整数其中所有的变量都是整数,r,r 是满足是满足 的最小整数的最小整数.此为周期函数此为周期函数,因为因为 其周期为二元数其周期为二元数:58本讲稿第五十八页，共七十一页离散对数问题以上函数看似奇怪以上函数看似奇怪,但它在密码学中很有用但它在密码学中很有用.确定确定s s允许我们解所谓的离散对数问题允许我们解所谓的离散对数问题:给定给定 a a 和和 ,求求s s 是什么是什么?59本讲稿第五十九页，共七十一页算法:离散对数60本讲稿第六十页，共七十一页算法:离散对数(续)61本讲稿第六十一页，共七十一页隐子群问题所有已知的快速量子算法都可被描所有已知的快速量子算法都可被描述为解决隐子群问题述为解决隐子群问题.(the hidden subgroup problem)62本讲稿第六十二页，共七十一页其中，其中，是一个适当选取的是一个适当选取的X X上的二进制上的二进制操作操作.求求K K的一个生成集的一个生成集.隐子群问题:定义设设f f 是从一个有限生成群是从一个有限生成群G G 到一个有限集合到一个有限集合X X上的上的函数函数,f f 在一个子群在一个子群K K 的陪集上是一个常数的陪集上是一个常数,且在每个陪且在每个陪集上的值都不同集上的值都不同.给定一个量子黑盒来执行酉变换给定一个量子黑盒来执行酉变换63本讲稿第六十三页，共七十一页隐子群问题是承诺问题隐子群问题的形式为隐子群问题的形式为:F(x):F(x)被承诺具有被承诺具有如此这般的性质如此这般的性质,表征此性质表征此性质.这是一个承诺问题这是一个承诺问题,它抓住了对于可比它抓住了对于可比经典算法指数加快的量子算法类的重经典算法指数加快的量子算法类的重要约束要约束.64本讲稿第六十四页，共七十一页5.4.4 其它量子算法?用隐子群问题作为描述量子算法的框架用隐子群问题作为描述量子算法的框架,意味着有更多的难题可从考虑各种群意味着有更多的难题可从考虑各种群G G和函数和函数f f 来解决来解决.书中只描述了对于书中只描述了对于AbelianAbelian群来解此问题群来解此问题,对于非对于非AbelianAbelian群如何群如何?如何迈出隐子群问题的局限如何迈出隐子群问题的局限?65本讲稿第六十五页，共七十一页本章回顾5.1 5.1 量子量子FourierFourier变换变换和经典离散和经典离散FourierFourier变换形式相同变换形式相同速度指数倍提高速度指数倍提高但不能直接用来加速经典但不能直接用来加速经典FourierFourier变换变换5.2 5.2 相位估计相位估计5.3 5.3 应用应用:求阶与因数分解求阶与因数分解5.4 5.4 量子量子FourierFourier变换的一般应用变换的一般应用本讲稿第六十六页，共七十一页下面的内容1、量子搜索有兴趣的同学自己看。2、量子计算机的物理实现。简谐振子量子计算机简谐振子量子计算机 光学光子量子计算机光学光子量子计算机 光学腔量子电动力学光学腔量子电动力学 离子阱离子阱 核磁共振核磁共振 超导量子计算机超导量子计算机 量子点量子计算机量子点量子计算机 其它实施方案其它实施方案本讲稿第六十七页，共七十一页本讲结束 谢谢大家!68本讲稿第六十八页，共七十一页RSA密码系统69本讲稿第六十九页，共七十一页RSA使用说明70本讲稿第七十页，共七十一页例子：71本讲稿第七十一页，共七十一页