量子信息學(xué)引論第11講

清華大學(xué)2012.11.28Introductionto

QuantumInformationScience第11講量子信息學(xué)引論1前一講回顧5.1量子Fourier變換和經(jīng)典離散Fourier變換形式相同速度指數(shù)倍提高但不能直接用來加速經(jīng)典Fourier變換5.2相位估計相位估計則是許多量子算法的關(guān)鍵。酉算子U具有本征矢量|u>,其對應(yīng)的本征值為e2pij,相位估計的目的:得到j(luò)的值。23相位估計回顧第一步:第二步:5.3應(yīng)用:求階與因數(shù)分解5.3.1應(yīng)用:求階(order-finding)5.3.2應(yīng)用:因數(shù)分解(factoring)45.3應(yīng)用:求階與因數(shù)分解相位估計步驟能用來解決一系列有趣的問題,其中包括:

求階和因數(shù)分解求階問題與因數(shù)分解問題等價。5求階和因數(shù)分解的快速量子算法

為何有價值?它提供了量子計算機(jī)可能在本質(zhì)上比經(jīng)典計算機(jī)強(qiáng)大的證據(jù),也提供了對強(qiáng)Church-Turing論題的一個可信的挑戰(zhàn)。這兩個問題本身都有足夠價值,值得研究其新算法。求階和因數(shù)分解的有效算法能用來破解RSA公鑰密碼系統(tǒng)。RSA的安全性假設(shè)建立在用經(jīng)典計算機(jī)分解因數(shù)是困難的。65.3.1應(yīng)用:求階(order-finding)求階的定義求階的量子算法7求階的定義

對于正整數(shù)x

和N,x<N,且無公因子,則x

模N

的階r被定義為:使得成立的最小的正整數(shù)r.例:若x=5,N=21,則r=6.8階的一個重要性質(zhì):

練習(xí)5.11:證明x的r階滿足

9證明提示：如果r>N,如常r=N+1會有什么樣的結(jié)果？有N+1個不同的余數(shù),但是周期是N，因此一定小于最多等于N。求階問題是經(jīng)典計算機(jī)上的難題求階問題是對某個固定的x

和N來確定階r。求階被認(rèn)為是經(jīng)典計算機(jī)上的一個難題。理由:還不知道一個采用O(L)位的多項(xiàng)式資源的算法來解此問題。其中，

是表示給定N所需的比特位數(shù).用相位估計算法可得求階的有效量子算法。10求階的量子算法用于求階的量子算法恰巧就是對應(yīng)于下面酉算子上的相位估計算法：

其中，L是量子比特的數(shù)目.11相位估計中U的本征態(tài)U的本征態(tài):

其中,整數(shù)s滿足:12相位估計中U的本征值

估計出相位s/r,即可設(shè)法得到階r.13推導(dǎo)以上本征方程14推導(dǎo)以上本征方程15推導(dǎo)以上本征方程16因?yàn)閤r=x0modN相位估計中U的本征值

可以估計出相位s/r,采用連分?jǐn)?shù)算法即可得到階r。17Box5.3:連分?jǐn)?shù)算法

(Thecontinuedfractionsalgorithm)基本思想:只用整數(shù)來描述所有的實(shí)數(shù).方法:分裂與倒置(splitandinvert)對于任意有理數(shù),經(jīng)過有限步,此算法即可完成.例:31/13的連分?jǐn)?shù)展開為:[2,2,1,1,2].18例子連分?jǐn)?shù)展開把求階問題還原為相位估計,是通過從相位估計算法的結(jié)果來得到希望的答案r。我們只知近似到2L+1位,但我們事先知道為一個有理數(shù)(兩個有界整數(shù)的比值)。這樣，如果我們能夠計算最近于此的分?jǐn)?shù)，就可得到r。

20定理5.1

設(shè)s/r是一個有理數(shù),使得則s/r是的連分?jǐn)?shù)的一個漸近值.21注意，j是對s/r的近似，精確到2L+1位。又因?yàn)?所以：定理5.1的應(yīng)用22結(jié)論：給定j,連分?jǐn)?shù)算法可有效地產(chǎn)生出沒有公因子的s\

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

是階的候選對象，可以通過計算xr\modN,看是否為1，如果是，r是x

模N的階。我們的任務(wù)就完成了。進(jìn)行相位估計的兩個條件(1)能夠用有效的步驟來實(shí)施一個操作,其中j為任意常數(shù).(2)能夠有效地制備本征態(tài)，或本征態(tài)的疊加態(tài)。而的本征值并不是簡單的值。23實(shí)現(xiàn)第一個條件通過模冪(modularexponentiation)可滿足相位估計的第一個條件.采用模冪,則可用個門來實(shí)現(xiàn)相估位計中需要的

24Box5.2模冪(modularexponentiation)25用可逆運(yùn)算得到xz(mod

N),首先計算x2(mod

N)，x4(mod

N),…,直到x2j(mod

N),

即可得到：實(shí)現(xiàn)第二個條件需要一些技巧：制備要求我們知道r

，而我們事先并不知道r，所以直接制備不可能。幸運(yùn)的是,如果我們注意到,則我們可以繞過制備的問題。26推導(dǎo):(5.44)式27推導(dǎo)過程由于相位估計步驟的第一階段

注意:右邊省略了歸一化因子29圖5.4求階算法的量子線路第二個寄存器已被證明可以被初始化到|1>態(tài)完成求解運(yùn)算。

不過,若利用練習(xí)5.14,它也可被初始化到|0>態(tài).這個線路也可用來進(jìn)行因數(shù)分解。30量子Fourier變換的乘積表示31圖5.1量子Fourier變換的有效線路此線路可從量子Fourier變換的乘積表示式中推出。圖中沒示出線路末尾的交換門(swamgate),用交換門把量子位的次序反過來。圖中也沒有顯示出輸出中的歸一化因子。32

其中x與N互質(zhì)；（2）算法:量子求階輸入：（1）一個黑箱Ux,N能執(zhí)行變換：

（3）L個量子位初始化到|1>,位初始化到|0>輸出：滿足xr=1(modN)的最小整數(shù)r>0。運(yùn)行時間：O(L3)個操作。成功率：O(1)33算法:量子求階(步驟)345.3.2應(yīng)用:因數(shù)分解(factoring)給定一個正合數(shù)N，它是由哪些素數(shù)相乘而得？最好的經(jīng)典算法：O(exp(N))因數(shù)分解有什么用？破解密碼35參考文獻(xiàn)：A.EkertandJ.Jozsa,Rev.Mod.Phys.68,733(1996).合數(shù)和素數(shù)素數(shù)(又稱質(zhì)數(shù))指在一個大于1的自然數(shù)中，除了1和此整數(shù)自身外，沒法被其他自然數(shù)整除的數(shù)合數(shù)指在一個大于1的自然數(shù)中，除了1和此整數(shù)自身外，還有其他自然數(shù)整除的數(shù)37MIPS是MillionInstructionsPerSecond的縮寫，每秒處理的百萬級的機(jī)器語言指令數(shù)。這是衡量CPU速度的一個指標(biāo)。像是一個Intel80386電腦可以每秒處理3百萬到5百萬機(jī)器語言指令，既我們可以說80386是3到5MIPS的CPU。MIPS只是衡量CPU性能的指標(biāo)。

因數(shù)分解與求階問題等價。即,一個求階的快速算法可以容易地轉(zhuǎn)成因數(shù)分解的快速算法。38因數(shù)分解與求階問題等價因數(shù)分解與求階問題等價39把因數(shù)分解問題還原為求階問題分兩步進(jìn)行:證明如果能夠找到方程的一個非平凡解，，則可以計算出N的一個因子。

定理5.24041(2)證明一個任意選取的與N互質(zhì)的數(shù)y，非常可能具有一個偶數(shù)階r,并且,

因而是的一個非平凡解。

定理5.3

把因數(shù)分解問題還原為求階問題定理5.242定理5.2gcd=greatestcommondivisor(最大公約數(shù))lcm=leastcommonmultiple

(最小公倍數(shù))定理5.344算法:利用求階進(jìn)行因數(shù)分解輸入:一個合數(shù)N.輸出:N的一個非凡因子.運(yùn)行時間:操作.成功率O(1).45算法:用求階來進(jìn)行因數(shù)分解(步驟)如果N為偶,返回因子2.確定是否有,其中

若是,返回因子a.(采用練習(xí)5.17的經(jīng)典算法).在1到N-1的范圍內(nèi)隨機(jī)選取x。若則返回因子gcd(x,N)。46算法:用求階來進(jìn)行因數(shù)分解(步驟)采用求階子程序來求xmod

N

的階r.5. 如果r為偶數(shù),且則計算和

并驗(yàn)證其是否為非平凡因子,如果是,則返回此因子，否則,算法失敗.47Box5.4:用量子算法分解15N=15,x=7,t=11,保證誤差e<1/4初態(tài)|0>|0>第一寄存器做Hadamard變換48用量子算法分解15

(續(xù))49計算f(k)=xkmodN，結(jié)果放在第二寄存器中用量子算法分解15

(續(xù))假設(shè)第二寄存器被測量（隱含測量原理），隨機(jī)得到1，7，4，13，假設(shè)得到4，則其狀態(tài)應(yīng)用Fourier反變換后，第一寄存器得到不同狀態(tài)的概率分布為：50用量子算法分解15

(續(xù))也就是幾乎以1/4的概率得到，0，512，1024，1536。假設(shè)得到l=1536，從1536/2048用連續(xù)分?jǐn)?shù)可得到，r=4是x=7的階。r是偶數(shù)且51故算法有效：計算最大公因子gcd(72-1,15)=3, gcd(72+1,15)=5,得到因子3,5

用核磁共振(NMR)法

實(shí)驗(yàn)實(shí)現(xiàn)對15的因數(shù)分解NATUREVOL414,20/27DECEMBER,2001,p883.525.4量子Fourier變換的一般應(yīng)用5.4.1求周期(period-finding)5.4.2離散對數(shù)(discretelorithm)5.4.3隱子群問題(thehiddensubgroupproblem)5.4.4其它量子算法?535.4.1求周期(period-finding)54設(shè)f是一個周期函數(shù),它的輸出是一個位,且對于某個未知的0<r<2L使得f(x+r)=f(x),其中,x,r0,1,2,….給定一個量子黑箱U,它執(zhí)行變換

問:需要多少個黑箱調(diào)用及其它操作才能確定r?

采用量子算法,需要對U調(diào)用一次,以及其它個操作。算法:求周期55算法:求周期(續(xù))565.4.2離散對數(shù)(discretelorithm)剛考慮的求周期問題是一個簡單的問題,因?yàn)槠渲泻瘮?shù)的定義域和值域都是整數(shù).當(dāng)函數(shù)更復(fù)雜時如何?57一個奇怪的周期函數(shù)考慮函數(shù)其中所有的變量都是整數(shù),r是滿足

的最小整數(shù).此為周期函數(shù),因?yàn)槠渲芷跒槎獢?shù):58離散對數(shù)問題以上函數(shù)看似奇怪,但它在密碼學(xué)中很有用.確定s允許我們解所謂的離散對數(shù)問題:

給定a

和

,求s

是什么?59算法:離散對數(shù)60算法:離散對數(shù)(續(xù))61隱子群問題所有已知的快速量子算法都可被描述為解決隱子群問題.(thehiddensubgroupproblem)

62其中，是一個適當(dāng)選取的X上的二進(jìn)制操作.求K的一個生成集.隱子群問題:定義

設(shè)f是從一個有限生成群G到