您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 公司方案 > 量子信息学引论第11讲
清华大学2012.11.28IntroductiontoQuantumInformationScience第11讲量子信息学引论1前一讲回顾•5.1量子Fourier变换–和经典离散Fourier变换形式相同–速度指数倍提高–但不能直接用来加速经典Fourier变换•5.2相位估计–相位估计则是许多量子算法的关键。–酉算子U具有本征矢量|u,其对应的本征值为e2pij,相位估计的目的:得到j的值。23相位估计回顾第一步:第二步:5.3应用:求阶与因数分解•5.3.1应用:求阶(order-finding)•5.3.2应用:因数分解(factoring)45.3应用:求阶与因数分解•相位估计步骤能用来解决一系列有趣的问题,其中包括:求阶和因数分解•求阶问题与因数分解问题等价。5求阶和因数分解的快速量子算法为何有价值?(1)它提供了量子计算机可能在本质上比经典计算机强大的证据,也提供了对强Church-Turing论题的一个可信的挑战。(2)这两个问题本身都有足够价值,值得研究其新算法。(3)求阶和因数分解的有效算法能用来破解RSA公钥密码系统。(4)RSA的安全性假设建立在用经典计算机分解因数是困难的。65.3.1应用:求阶(order-finding)•求阶的定义•求阶的量子算法7求阶的定义对于正整数x和N,xN,且无公因子,则x模N的阶r被定义为:使得成立的最小的正整数r.例:若x=5,N=21,则r=6.8x=5N=21rx^rx^rmodN011155225431252046251653125176156251778125583906254919531252010976562516114882812517阶的一个重要性质:练习5.11:证明x的r阶满足9证明提示:如果rN,如常r=N+1会有什么样的结果?有N+1个不同的余数,但是周期是N,因此一定小于最多等于N。求阶问题是经典计算机上的难题•求阶问题是对某个固定的x和N来确定阶r。•求阶被认为是经典计算机上的一个难题。•理由:还不知道一个采用O(L)位的多项式资源的算法来解此问题。其中,是表示给定N所需的比特位数.•用相位估计算法可得求阶的有效量子算法。)log(NL10求阶的量子算法•用于求阶的量子算法恰巧就是对应于下面酉算子上的相位估计算法:其中,L是量子比特的数目.11相位估计中U的本征态•U的本征态:其中,整数s满足:12相位估计中U的本征值估计出相位s/r,即可设法得到阶r.1311012expmod2exprksksiskUuxNrrisurpp推导以上本征方程14NxrskiruUkrksmod2exp1110p1211expmod,set1andusefortheconveniencebelowrmmismxNmkrrkpNxrsirskirkrkmod2exp*2exp11ppNxrskirrsikrkmod2exp12exp1pp推导以上本征方程1511212expexpmod2expmodrkkrisiskxNrrrisrxNrpppNxrskirrsikrkmod2exp12exp1pprsirsri02exp2exppp推导以上本征方程16NxrsiNxrskirrsikrkmod02expmod2exp12exp011ppp因为xr=x0modNskrkursiNxrskirrsippp2expmod2exp12exp10相位估计中U的本征值可以估计出相位s/r,采用连分数算法即可得到阶r。172expssisUuurpBox5.3:连分数算法(Thecontinuedfractionsalgorithm)•基本思想:只用整数来描述所有的实数.•方法:分裂与倒置(splitandinvert)•对于任意有理数,经过有限步,此算法即可完成.•例:31/13的连分数展开为:[2,2,1,1,2].18例子3151111222221331113132222155111312连分数展开•把求阶问题还原为相位估计,是通过从相位估计算法的结果来得到希望的答案r。•我们只知近似到2L+1位,但我们事先知道为一个有理数(两个有界整数的比值)。•这样,如果我们能够计算最近于此的分数,就可得到r。20定理5.1设s/r是一个有理数,使得则s/r是的连分数的一个渐近值.21注意,j是对s/r的近似,精确到2L+1位。又因为,所以:定理5.1的应用LNr222121112222LLsrrj22结论:给定j,连分数算法可有效地产生出没有公因子的s\和r\,使得s/r=s\/r\,r\是阶的候选对象,可以通过计算xr\modN,看是否为1,如果是,r是x模N的阶。我们的任务就完成了。进行相位估计的两个条件(1)能够用有效的步骤来实施一个操作,其中j为任意常数.(2)能够有效地制备本征态,或本征态的叠加态。而的本征值并不是简单的值。23实现第一个条件•通过模幂(modularexponentiation)可满足相位估计的第一个条件.采用模幂,则可用个门来实现相估位计中需要的24Box5.2模幂(modularexponentiation)25用可逆运算得到xz(modN),首先计算x2(modN),x4(modN),…,直到x2j(modN),即可得到:实现第二个条件•需要一些技巧:制备要求我们知道r,而我们事先并不知道r,所以直接制备不可能。•幸运的是,如果我们注意到,则我们可以绕过制备的问题。26推导:(5.44)式271110rssur推导过程1110001100112expmod12expmodrrrkssskrrkksiskuxNrrriskxNrrpp由于11002122expexpexp2exp1exp20for0rrssiskiskikAArrrikAAikAkrppppp相位估计步骤的第一阶段注意:右边省略了归一化因子29图5.4求阶算法的量子线路•第二个寄存器已被证明可以被初始化到|1态完成求解运算。不过,若利用练习5.14,它也可被初始化到|0态.•这个线路也可用来进行因数分解。30量子Fourier变换的乘积表示31图5.1量子Fourier变换的有效线路•此线路可从量子Fourier变换的乘积表示式中推出。•图中没示出线路末尾的交换门(swamgate),用交换门把量子位的次序反过来。•图中也没有显示出输出中的归一化因子。32其中x与N互质;(2)算法:量子求阶,modNkxjkjj212log12Lt输入:(1)一个黑箱Ux,N能执行变换:(3)L个量子位初始化到|1,位初始化到|0输出:满足xr=1(modN)的最小整数r0。运行时间:O(L3)个操作。成功率:O(1)33算法:量子求阶(步骤)345.3.2应用:因数分解(factoring)•给定一个正合数N,它是由哪些素数相乘而得?•最好的经典算法:O(exp(N))•因数分解有什么用?–破解密码35参考文献:A.EkertandJ.Jozsa,Rev.Mod.Phys.68,733(1996).合数和素数素数(又称质数)指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数合数指在一个大于1的自然数中,除了1和此整数自身外,还有其他自然数整除的数37MIPS是MillionInstructionsPerSecond的缩写,每秒处理的百万级的机器语言指令数。这是衡量CPU速度的一个指标。像是一个Intel80386电脑可以每秒处理3百万到5百万机器语言指令,既我们可以说80386是3到5MIPS的CPU。MIPS只是衡量CPU性能的指标。•因数分解与求阶问题等价。•即,一个求阶的快速算法可以容易地转成因数分解的快速算法。38因数分解与求阶问题等价因数分解与求阶问题等价39把因数分解问题还原为求阶问题分两步进行:(1)证明如果能够找到方程的一个非平凡解,,则可以计算出N的一个因子。定理5.24041(2)证明一个任意选取的与N互质的数y,非常可能具有一个偶数阶r,并且,因而是的一个非平凡解。定理5.3把因数分解问题还原为求阶问题定理5.242定理5.2gcd=greatestcommondivisor(最大公约数)lcm=leastcommonmultiple(最小公倍数)定理5.344算法:利用求阶进行因数分解输入:一个合数N.输出:N的一个非凡因子.运行时间:操作.成功率O(1).45算法:用求阶来进行因数分解(步骤)1.如果N为偶,返回因子2.2.确定是否有,其中若是,返回因子a.(采用练习5.17的经典算法).3.在1到N-1的范围内随机选取x。若则返回因子gcd(x,N)。46算法:用求阶来进行因数分解(步骤)4.采用求阶子程序来求xmodN的阶r.5.如果r为偶数,且则计算和并验证其是否为非平凡因子,如果是,则返回此因子,否则,算法失败.47Box5.4:用量子算法分解15•N=15,x=7,t=11,保证误差1/4•初态|0|0•第一寄存器做Hadamard变换48用量子算法分解15(续)49计算f(k)=xkmodN,结果放在第二寄存器中用量子算法分解15(续)•假设第二寄存器被测量(隐含测量原理),随机得到1,7,4,13,假设得到4,则其状态•应用Fourier反变换后,第一寄存器得到不同状态的概率分布为:50用量子算法分解15(续)•也就是几乎以1/4的概率得到,0,512,1024,1536。假设得到l=1536,从1536/2048用连续分数可得到,r=4是x=7的阶。r是偶数且5115mod1415mod7mod22/Nxr•故算法有效:计算最大公因子gcd(72-1,15)=3,gcd(72+1,15)=5,得到因子3,5用核磁共振(NMR)法实验实现对15的因数分解•NATUREVOL414,20/27DECEMBER,2001,p883.525.4量子Fourier变换的一般应用•5.4.1求周期(period-finding)•5.4.2离散对数(discretelorithm)•5.4.3隐子群问题(thehiddensubgroupproblem)•5.4.4其它量子算法?535.4.1求周期(period-finding)54设f是一个周期函数,它的输出是一个位,且对于某个未知的0r2L使得f(x+r)=f(x),其中,x,r0,1,2,….给定一个量子黑箱U,它执行变换问:需要多少个黑箱调用及其它操作才能确定r?采用量子算法,需要对U调用一次,以及其它个操作。xfyxyxU2LO算法:求周期55算法:求周期(续)565.4.2离散对数(discretelorithm)•刚考虑的求周期问题是一个简单的问题,因为其中函数的定义域和值域都是整数.•当函数更复杂时如何?57一个奇怪的周期函数•考虑函数其中所有的变量都是整数,r是满足的最小整数.•此为周期函数,因为其周期为二元数:58离散对数问题•以上函数看似奇怪,但它在密码学中很有用.•确定s允许我们解所谓的离散对数问题:给定a和,求s是什么?59sab算法:离散对数60算法:离散对数(续)61隐子群问题•所有已知的快速量子算法都可被描
本文标题:量子信息学引论第11讲
链接地址:https://www.777doc.com/doc-3956143 .html