量子信息学引论第11讲

清华大学2012.11.28Introductionto

QuantumInformationScience第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求阶和因数分解的快速量子算法

为何有价值?它提供了量子计算机可能在本质上比经典计算机强大的证据,也提供了对强Church-Turing论题的一个可信的挑战。这两个问题本身都有足够价值,值得研究其新算法。求阶和因数分解的有效算法能用来破解RSA公钥密码系统。RSA的安全性假设建立在用经典计算机分解因数是困难的。65.3.1应用:求阶(order-finding)求阶的定义求阶的量子算法7求阶的定义

对于正整数x

和N,x<N,且无公因子,则x

模N

的阶r被定义为:使得成立的最小的正整数r.例:若x=5,N=21,则r=6.8阶的一个重要性质:

练习5.11:证明x的r阶满足

9证明提示：如果r>N,如常r=N+1会有什么样的结果？有N+1个不同的余数,但是周期是N，因此一定小于最多等于N。求阶问题是经典计算机上的难题求阶问题是对某个固定的x

和N来确定阶r。求阶被认为是经典计算机上的一个难题。理由:还不知道一个采用O(L)位的多项式资源的算法来解此问题。其中，

是表示给定N所需的比特位数.用相位估计算法可得求阶的有效量子算法。10求阶的量子算法用于求阶的量子算法恰巧就是对应于下面酉算子上的相位估计算法：

其中，L是量子比特的数目.11相位估计中U的本征态U的本征态:

其中,整数s满足:12相位估计中U的本征值

估计出相位s/r,即可设法得到阶r.13推导以上本征方程14推导以上本征方程15推导以上本征方程16因为xr=x0modN相位估计中U的本征值

可以估计出相位s/r,采用连分数算法即可得到阶r。17Box5.3:连分数算法

(Thecontinuedfractionsalgorithm)基本思想:只用整数来描述所有的实数.方法:分裂与倒置(splitandinvert)对于任意有理数,经过有限步,此算法即可完成.例:31/13的连分数展开为:[2,2,1,1,2].18例子连分数展开把求阶问题还原为相位估计,是通过从相位估计算法的结果来得到希望的答案r。我们只知近似到2L+1位,但我们事先知道为一个有理数(两个有界整数的比值)。这样，如果我们能够计算最近于此的分数，就可得到r。

20定理5.1

设s/r是一个有理数,使得则s/r是的连分数的一个渐近值.21注意，j是对s/r的近似，精确到2L+1位。又因为,所以：定理5.1的应用22结论：给定j,连分数算法可有效地产生出没有公因子的s\

和r\，使得s/r=s\/r\,r\

是阶的候选对象，可以通过计算xr\modN,看是否为1，如果是，r是x

模N的阶。我们的任务就完成了。进行相位估计的两个条件(1)能够用有效的步骤来实施一个操作,其中j为任意常数.(2)能够有效地制备本征态，或本征态的叠加态。而的本征值并不是简单的值。23实现第一个条件通过模幂(modularexponentiation)可满足相位估计的第一个条件.采用模幂,则可用个门来实现相估位计中需要的

24Box5.2模幂(modularexponentiation)25用可逆运算得到xz(mod

N),首先计算x2(mod

N)，x4(mod

N),…,直到x2j(mod

N),

即可得到：实现第二个条件需要一些技巧：制备要求我们知道r

，而我们事先并不知道r，所以直接制备不可能。幸运的是,如果我们注意到,则我们可以绕过制备的问题。26推导:(5.44)式27推导过程由于相位估计步骤的第一阶段

注意:右边省略了归一化因子29图5.4求阶算法的量子线路第二个寄存器已被证明可以被初始化到|1>态完成求解运算。

不过,若利用练习5.14,它也可被初始化到|0>态.这个线路也可用来进行因数分解。30量子Fourier变换的乘积表示31图5.1量子Fourier变换的有效线路此线路可从量子Fourier变换的乘积表示式中推出。图中没示出线路末尾的交换门(swamgate),用交换门把量子位的次序反过来。图中也没有显示出输出中的归一化因子。32

其中x与N互质；（2）算法:量子求阶输入：（1）一个黑箱Ux,N能执行变换：

（3）L个量子位初始化到|1>,位初始化到|0>输出：满足xr=1(modN)的最小整数r>0。运行时间：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把因数分解问题还原为求阶问题分两步进行:证明如果能够找到方程的一个非平凡解，，则可以计算出N的一个因子。

定理5.24041(2)证明一个任意选取的与N互质的数y，非常可能具有一个偶数阶r,并且,

因而是的一个非平凡解。

定理5.3

把因数分解问题还原为求阶问题定理5.242定理5.2gcd=greatestcommondivisor(最大公约数)lcm=leastcommonmultiple

(最小公倍数)定理5.344算法:利用求阶进行因数分解输入:一个合数N.输出:N的一个非凡因子.运行时间:操作.成功率O(1).45算法:用求阶来进行因数分解(步骤)如果N为偶,返回因子2.确定是否有,其中

若是,返回因子a.(采用练习5.17的经典算法).在1到N-1的范围内随机选取x。若则返回因子gcd(x,N)。46算法:用求阶来进行因数分解(步骤)采用求阶子程序来求xmod

N

的阶r.5. 如果r为偶数,且则计算和

并验证其是否为非平凡因子,如果是,则返回此因子，否则,算法失败.47Box5.4:用量子算法分解15N=15,x=7,t=11,保证误差e<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是偶数且51故算法有效：计算最大公因子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是一个周期函数,它的输出是一个位,且对于某个未知的0<r<2L使得f(x+r)=f(x),其中,x,r0,1,2,….给定一个量子黑箱U,它执行变换

问:需要多少个黑箱调用及其它操作才能确定r?

采用量子算法,需要对U调用一次,以及其它个操作。算法:求周期55算法:求周期(续)565.4.2离散对数(discretelorithm)刚考虑的求周期问题是一个简单的问题,因为其中函数的定义域和值域都是整数.当函数更复杂时如何?57一个奇怪的周期函数考虑函数其中所有的变量都是整数,r是满足

的最小整数.此为周期函数,因为其周期为二元数:58离散对数问题以上函数看似奇怪,但它在密码学中很有用.确定s允许我们解所谓的离散对数问题:

给定a

和

,求s

是什么?59算法:离散对数60算法:离散对数(续)61隐子群问题所有已知的快速量子算法都可被描述为解决隐子群问题.(thehiddensubgroupproblem)

62其中，是一个适当选取的X上的二进制操作.求K的一个生成集.隐子群问题:定义

设f是从一个有限生成群G到