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

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

求階和因數(shù)分解求階問題與因數(shù)分解問題等價。5第五頁，共七十一頁，編輯于2023年，星期五求階和因數(shù)分解的快速量子算法

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

對于正整數(shù)x

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

模N

的階r被定義為:使得成立的最小的正整數(shù)r.例:若x=5,N=21,則r=6.8第八頁，共七十一頁，編輯于2023年，星期五階的一個重要性質(zhì):

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

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

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

是表示給定N所需的比特位數(shù).用相位估計算法可得求階的有效量子算法。10第十頁，共七十一頁，編輯于2023年，星期五求階的量子算法用于求階的量子算法恰巧就是對應(yīng)于下面酉算子上的相位估計算法：

其中，L是量子比特的數(shù)目.11第十一頁，共七十一頁，編輯于2023年，星期五相位估計中U的本征態(tài)U的本征態(tài):

其中,整數(shù)s滿足:12第十二頁，共七十一頁，編輯于2023年，星期五相位估計中U的本征值

估計出相位s/r,即可設(shè)法得到階r.13第十三頁，共七十一頁，編輯于2023年，星期五推導(dǎo)以上本征方程14第十四頁，共七十一頁，編輯于2023年，星期五推導(dǎo)以上本征方程15第十五頁，共七十一頁，編輯于2023年，星期五推導(dǎo)以上本征方程16因為xr=x0modN第十六頁，共七十一頁，編輯于2023年，星期五相位估計中U的本征值

可以估計出相位s/r,采用連分數(shù)算法即可得到階r。17第十七頁，共七十一頁，編輯于2023年，星期五Box5.3:連分數(shù)算法

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

20第二十頁，共七十一頁，編輯于2023年，星期五定理5.1

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

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

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

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

24第二十四頁，共七十一頁，編輯于2023年，星期五Box5.2模冪(modularexponentiation)25用可逆運算得到xz(mod

N),首先計算x2(mod

N)，x4(mod

N),…,直到x2j(mod

N),

即可得到：第二十五頁，共七十一頁，編輯于2023年，星期五實現(xiàn)第二個條件需要一些技巧：制備要求我們知道r

，而我們事先并不知道r，所以直接制備不可能。幸運的是,如果我們注意到,則我們可以繞過制備的問題。26第二十六頁，共七十一頁，編輯于2023年，星期五推導(dǎo):(5.44)式27第二十七頁，共七十一頁，編輯于2023年，星期五推導(dǎo)過程由于第二十八頁，共七十一頁，編輯于2023年，星期五相位估計步驟的第一階段

注意:右邊省略了歸一化因子29第二十九頁，共七十一頁，編輯于2023年，星期五圖5.4求階算法的量子線路第二個寄存器已被證明可以被初始化到|1>態(tài)完成求解運算。

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

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

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

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

定理5.240第四十頁，共七十一頁，編輯于2023年，星期五41(2)證明一個任意選取的與N互質(zhì)的數(shù)y，非常可能具有一個偶數(shù)階r,并且,

因而是的一個非平凡解。

定理5.3

把因數(shù)分解問題還原為求階問題第四十一頁，共七十一頁，編輯于2023年，星期五定理5.242第四十二頁，共七十一頁，編輯于2023年，星期五定理5.2gcd=greatestcommondivisor(最大公約數(shù))lcm=leastcommonmultiple

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

若是,返回因子a.(采用練習(xí)5.17的經(jīng)典算法).在1到N-1的范圍內(nèi)隨機選取x。若則返回因子gcd(x,N)。46第四十六頁，共七十一頁，編輯于2023年，星期五算法:用求階來進行因數(shù)分解(步驟)采用求階子程序來求xmod

N

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

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

(續(xù))49計算f(k)=xkmodN，結(jié)果放在第二寄存器中第四十九頁，共七十一頁，編輯于2023年，星期五用量子算法分解15

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

(續(xù))也就是幾乎以1/4的概率得到，0，512，1024，1536。假設(shè)得到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第五十一頁，共七十一頁，編輯于2023年，星期五

用核磁共振(NMR)法

實驗實現(xiàn)對15的因數(shù)分解NATUREVOL414,20/27DECEMBER,2001,p883.52第五十二頁，共七十一頁，編輯于2023年，星期五5.4量子Fourier變換的一般應(yīng)用5.4.1求周期(period-finding)5.4.2離散對數(shù)(discretelorithm)5.4.3隱子群問題(thehiddensubgroupproblem)5.4.4其它量子算法?53第五十三頁，共七十一頁，編輯于2023年，星期五5.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)用一次,以及其它個操作。第五十四頁，共七十一頁，編輯于2023年，星期五算法:求周期55第五十五頁，共七十一頁，編輯于2023年，星期五算法:求周期(續(xù))56第五十六頁，共七十一頁，編輯于2023年，星期五5.4.2離散對數(shù)(discretelorithm)剛考慮的求周期問題是一個簡單的問題,因為其中函數(shù)的定義域和值域都是整數(shù).當(dāng)函數(shù)更復(fù)雜時如何?57第五十七頁，共七十一頁，編輯于2023年，星期五一個奇怪的周期函數(shù)考慮函數(shù)其中所有的變量都是整數(shù),r是滿足

的最小整數(shù).此為周期函數(shù),因為其周期為二元數(shù):58第五十八頁，共七十一頁，編輯于2023年，星期五離散對數(shù)問題以上函數(shù)看似奇怪,但它在密碼學(xué)中很有用.確定s允許我們解所謂的離散對數(shù)問題:

給定a

和

,求s

是什么?59第五十九頁，共七十一頁，編輯于2023年，星期五算法:離散對數(shù)60第六十頁，共七十一頁，編輯于2023年，星期五算法:離散對數(shù)(續(xù))61第六十一頁，共七十一頁，編輯于2023年，星期五隱子群問題所有已知的快速量子算法都可被描述為解決隱子群問題.(thehiddensubgroupproblem)

62第六十二頁，共七十一頁，編輯于2023年，星期五其中，是一個適當(dāng)選取的X上的二進制操作.求K的一個生成集.隱子群問題:定義

設(shè)f是從一個有限生成群G到一個有限集合X上的函數(shù),f在一個子群K

的陪集上是一個常數(shù),且在每個陪集上的值都不同