量子信息學引論第11講

清華大學2012.11.28Introductionto

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

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

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

對于正整數(shù)x

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

模N

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

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

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

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

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

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

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

估計出相位s/r,即可設法得到階r.13推導以上本征方程14推導以上本征方程15推導以上本征方程16因為xr=x0modN相位估計中U的本征值

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

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

20定理5.1

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

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

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

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

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

N),首先計算x2(mod

N)，x4(mod

N),…,直到x2j(mod

N),

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

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

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

不過,若利用練習5.14,它也可被初始化到|0>態(tài).這個線路也可用來進行因數(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。運行時間：O(L3)個操作。成功率：O(1)33算法:量子求階(步驟)345.3.2應用:因數(shù)分解(factoring)給定一個正合數(shù)N，它是由哪些素數(shù)相乘而得？最好的經(jīng)典算法：O(exp(N))因數(shù)分解有什么用？破解密碼35參考文獻：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的縮寫，每秒處理的百萬級的機器語言指令數(shù)。這是衡量CPU速度的一個指標。像是一個Intel80386電腦可以每秒處理3百萬到5百萬機器語言指令，既我們可以說80386是3到5MIPS的CPU。MIPS只是衡量CPU性能的指標。

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

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

因而是的一個非平凡解。

定理5.3

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

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

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

N

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

并驗證其是否為非平凡因子,如果是,則返回此因子，否則,算法失敗.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ù))假設第二寄存器被測量（隱含測量原理），隨機得到1，7，4，13，假設得到4，則其狀態(tài)應用Fourier反變換后，第一寄存器得到不同狀態(tài)的概率分布為：50用量子算法分解15

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

用核磁共振(NMR)法

實驗實現(xiàn)對15的因數(shù)分解NATUREVOL414,20/27DECEMBER,2001,p883.525.4量子Fourier變換的一般應用5.4.1求周期(period-finding)5.4.2離散對數(shù)(discretelorithm)5.4.3隱子群問題(thehiddensubgroupproblem)5.4.4其它量子算法?535.4.1求周期(period-finding)54設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)剛考慮的求周期問題是一個簡單的問題,因為其中函數(shù)的定義域和值域都是整數(shù).當函數(shù)更復雜時如何?57一個奇怪的周期函數(shù)考慮函數(shù)其中所有的變量都是整數(shù),r是滿足

的最小整數(shù).此為周期函數(shù),因為其周期為二元數(shù):58離散對數(shù)問題以上函數(shù)看似奇怪,但它在密碼學中很有用.確定s允許我們解所謂的離散對數(shù)問題:

給定a

和

,求s

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

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

設f是從一個有限生成群G到