量子計算機詳解課件

量子計算機林曉菲2004-05-14主要內(nèi)容量子計算機的發(fā)展及現(xiàn)狀從計算機科學(xué)表述的量子力學(xué)原理量子計算基礎(chǔ)量子算法舉例—shor算法參考文獻主要內(nèi)容量子計算機的發(fā)展及現(xiàn)狀從計算機科學(xué)表述的量子力學(xué)原理量子計算基礎(chǔ)量子算法舉例—shor算法參考文獻量子計算機的發(fā)展及現(xiàn)狀三大熱點

量子計算機

量子密碼術(shù)量子通信量子計算機20世紀(jì)后半頁計算機技術(shù)大行其道，人類進入信息時代。隨著計算機芯片的集成度越來越高元件越做越小，集成電路技術(shù)現(xiàn)在正逼近其極限。原件小型化過程量子計算機從大規(guī)模集成電路的發(fā)展史看，單粒子晶體管似乎是必然趨勢。當(dāng)一個晶體管里包含的雜質(zhì)電子數(shù)目只有一個或少數(shù)幾個時，量子行為便為主要性質(zhì)，這時計算方式必然要用量子力學(xué)才能正確處理。早在60年代,Landauer就已研究計算過程的可逆性與統(tǒng)計力學(xué)的關(guān)系。量子計算機的概念源于對可逆計算機的研究。量子計算機早期量子計算機，實際上是用量子力學(xué)語言描述的經(jīng)典計算機，并沒有用到量子力學(xué)的本質(zhì)特性，如量子態(tài)的疊加性和相干性。Feynman，F(xiàn)redkin，Toffoli

等人考慮由量子力學(xué)原理確定計算規(guī)則發(fā)生的現(xiàn)象后,發(fā)現(xiàn)計算理論與物理學(xué)規(guī)律密不可分。量子計算機Deutch

指出,這種以量子力學(xué)原理決定的計算過程

(即量子計算)很多方面體現(xiàn)出與經(jīng)典計算非常不同的行為。八十年代初期，一些物理學(xué)家證明一臺計算機原則上可以以純粹的量子力學(xué)的方式運行之后很長一段時間，因為科學(xué)家們不能找到實際的系統(tǒng)可供進行量子計算機的實驗，而且還尚不清楚量子計算機解決數(shù)學(xué)問題是否會比常規(guī)計算機快，這一研究領(lǐng)域漸趨冷清。量子計算機進入20世紀(jì)90年代，實驗技術(shù)和理論模型的進步為量子計算機的實現(xiàn)提供了可能。要使量子計算成為現(xiàn)實，一個核心問題就是克服消相干。而量子編碼是迄今發(fā)現(xiàn)的克服消相干最有效的方法。主要的幾種量子編碼方案是：量子糾錯碼、量子避錯碼和量子防錯碼。量子計算機目前已經(jīng)提出的在實驗上實現(xiàn)對微觀量子態(tài)的操縱方案主要利用了原子和光腔相互作用、冷阱束縛離子、電子或核自旋共振、量子點操縱、超導(dǎo)量子干涉等。尤其值得一提的是1994年美國貝爾實驗室的PeterW.Shor證明運用量子計算機能有效地進行大數(shù)的因式分解。量子計算機幾年后Grover提出“量子搜尋算法”，可以破譯DES密碼體系。于是各國政府紛紛投入大量的資金和科研力量進行量子計算機的研究美，英，德，法，加拿大，日本，中國大陸，臺灣，新加坡，印度等已先后成立專門研究量子計算機的研究群。量子密碼術(shù)量子密碼術(shù)是密碼術(shù)與量子力學(xué)結(jié)合的產(chǎn)物，它利用了系統(tǒng)所具有的量子性質(zhì)。首先想到將量子物理用于密碼術(shù)的是美國科學(xué)家威斯納。1970年，威斯納提出，可利用單量子態(tài)制造不可偽造的“電子鈔票”。但這個設(shè)想的實現(xiàn)需要長時間保存單量子態(tài)，不太現(xiàn)實。量子密碼術(shù)貝內(nèi)特和布拉薩德在研究中發(fā)現(xiàn)，單量子態(tài)雖然不好保存但可用于傳輸信息。1984年，貝內(nèi)特和布拉薩德提出了第一個量子密碼術(shù)方案，稱為BB84方案，由此迎來了量子密碼術(shù)的新時期。1992年，貝內(nèi)特又提出一種更簡單，但效率減半的方案，即B92方案。量子密碼術(shù)量子密碼術(shù)并不用于傳輸密文，而是用于建立、傳輸密碼本。根據(jù)量子力學(xué)的不確定性原理以及量子不可克隆定理，任何竊聽者的存在都會被發(fā)現(xiàn)，從而保證密碼本的絕對安全，也就保證了加密信息的絕對安全。量子密碼術(shù)最初的量子密碼通信利用的都是光子的偏振特性，在長距離的光纖傳輸中，光的偏振性會退化，造成誤碼率的增加。目前主流的實驗方案則用光子的相位特性進行編碼。與偏振編碼相比，相位編碼的好處是對光的偏振態(tài)要求不那么苛刻。目前，在量子密碼術(shù)實驗研究上進展最快的國家為英國、瑞士和美國。量子通信量子通信系統(tǒng)的基本部件包括量子態(tài)發(fā)生器、量子通道和量子測量裝置。按其所傳輸?shù)男畔⒎譃閮深悾航?jīng)典量子通信和量子通信。經(jīng)典量子通信主要用于量子密鑰的傳輸。量子通信量子通信可用于量子隱形傳送和量子糾纏的分發(fā)。隱形傳送指的是脫離實物的一種“完全”的信息傳送。從物理學(xué)角度，可以這樣來想象隱形傳送的過程：先提取原物的所有信息，然后將這些信息傳送到接收地點，接收者依據(jù)這些信息，選取與構(gòu)成原物完全相同的基本單元，制造出原物完美的復(fù)制品。量子通信量子力學(xué)的不確定性原理不允許精確地提取原物的全部信息，這個復(fù)制品不可能是完美的。因此長期以來，隱形傳送不過是一種幻想而已。

1997年，在奧地利留學(xué)的中國青年學(xué)者潘建偉與荷蘭學(xué)者波密斯特等人合作，首次實現(xiàn)了未知量子態(tài)的遠(yuǎn)程傳輸。這是國際上首次在實驗上成功地將一個量子態(tài)從甲地的光子傳送到乙地的光子上。主要內(nèi)容量子計算機的發(fā)展及現(xiàn)狀從計算機科學(xué)表述的量子力學(xué)原理量子計算基礎(chǔ)量子算法舉例—shor算法參考文獻量子力學(xué)原理量子計算機以量子力學(xué)建立邏輯體系，與量子計算機有關(guān)的量子力學(xué)的原理，即量子狀態(tài)的主要性質(zhì)包括：

●狀態(tài)疊加●干涉性

●糾纏

●不可復(fù)制性與不確定性●狀態(tài)變化

量子力學(xué)原理狀態(tài)疊加設(shè){|n>}為可能的量子狀態(tài),則{∑iaik|k}也是一個可能的量子狀態(tài)。對應(yīng)于量子計算,這表示量子計算機可以代表經(jīng)典計算機的很多狀態(tài)。它使得大規(guī)模的量子并行存儲成為可行,如n能階系統(tǒng)至少可存2n個數(shù)據(jù),由于理論上n無上限。因此,可以利用此特性作大規(guī)模的存儲。又由于各狀態(tài)之間有相位相干,存儲過程是平行的。量子力學(xué)原理干涉性狀態(tài)疊加時，依各狀態(tài)間的相位關(guān)系可能出現(xiàn)相長或相消的狀態(tài)，這是經(jīng)典計算機的布爾狀態(tài)所不具備的特征。狀態(tài)變化

量子依照幺正變換法則，有系統(tǒng)的漢密爾頓算子決定其變化。量子力學(xué)原理

干涉性，狀態(tài)變化這兩個性質(zhì)是量子并行計算的基礎(chǔ)，因為系統(tǒng)的各個狀態(tài)按照幺正變換同時變化，故一次量子計算可以同時作用在多個數(shù)據(jù)上。量子計算機的優(yōu)越性主要體現(xiàn)在量子并行計算上量子力學(xué)原理糾纏整體的狀態(tài)波函數(shù)不變并不一定表示各成份狀態(tài)的波函數(shù)不變,這說明各成分波函數(shù)間有非定域的關(guān)聯(lián)性。不可復(fù)制性與不確定性

不能精確的復(fù)制一個狀態(tài)，也不能在不打擾該狀態(tài)的情況下觀察此狀態(tài)量子力學(xué)原理糾纏，不可復(fù)制性與不確定性是量子加密，密碼術(shù)，量子通信的基礎(chǔ)。借助于糾纏性質(zhì)，原則上可以實現(xiàn)超距的重生-滅體過程。量子狀態(tài)的不可復(fù)制性與不確定性是的量子通信免于被竊聽或者即使被竊聽也無法解讀。主要內(nèi)容量子計算機的發(fā)展及現(xiàn)狀從計算機科學(xué)表述的量子力學(xué)原理量子計算基礎(chǔ)量子算法舉例—shor算法參考文獻量子計算基礎(chǔ)量子比特量子寄存器量子門量子網(wǎng)路量子比特在經(jīng)典計算機中，運算的基本單元是比特（bit），它的基本狀態(tài)是二值布爾邏輯狀態(tài)（0或1）在量子計算機中，運算的基本單元是量子比特（q-bit），它的基本狀態(tài)是兩種狀態(tài)的疊加。

量子比特規(guī)定原子在基態(tài)時記為|0〉，在激發(fā)態(tài)時原子的狀態(tài)記為|1〉。原子除了保持上述兩種狀態(tài)之外，還可以處于兩種態(tài)的線性疊加，記為

|φ〉=a|1〉+b|0〉

a和b分別代表原子處于兩種態(tài)的幾率幅

量子比特量子比特一種典型的量子比特—量子點

它基本上是一個被困在原子牢籠中的單一電子。當(dāng)量子點暴露在剛好合適波長的激光脈沖下并持續(xù)一段時間，電子就會達到一種激發(fā)態(tài)：而第二次的激光脈沖又會使電子衰落回它的基態(tài)。電子的基態(tài)和激發(fā)態(tài)可以被視為量比的0和1狀態(tài)，而激光在將量比從0狀態(tài)撞擊到1狀態(tài)或從1撞擊到0的應(yīng)用，能夠被看成是一種對取非功能的控制。

量子比特一種典型的量子比特—量子點如果激光持續(xù)時間只有取非功能要求的一半，那么電子將同時處于基態(tài)和激發(fā)態(tài)的重疊中，這也等價于量比的連貫性狀態(tài)。而更多復(fù)雜的邏輯功能可以通過使用成對的安排好的量子點被模擬出來。因此，看起來量子點是一個合適的建造量子計算機的候選人。

量子寄存器存儲一系列量子比特的體系稱為量子寄存器假如有一個由三個比特構(gòu)成的寄存器在經(jīng)典計算機中，可以表示0~7共8個數(shù)，并且在某一時刻，只能表示其中的一個數(shù)

000001010011100101110111量子寄存器

若此寄存器器是由量子比特構(gòu)成，每個量子比特可以處于|0〉或|1〉或

|0〉與|1〉的疊加態(tài)，既在某時刻一個量子存儲器可以表示8個數(shù)。

0〉|0〉|0〉+|0〉|0〉|1〉+|0〉|1〉|0〉+|0〉|1〉|1〉+|1〉|0〉|0〉+|1〉|0〉|1〉+|1〉|1〉|0〉+|1〉|1〉|1〉

量子寄存器3個量子比特的系統(tǒng)量子寄存器3個量子比特的系統(tǒng)可以同時表示8個傳統(tǒng)狀態(tài)量子門在經(jīng)典計算機中，邏輯判斷是按真值表進行任何邏輯運算均可以歸類于3項基本的布爾操作：非（NOT），與（AND），或（OR）這些基本的邏輯運算稱為門量子門與經(jīng)典計算機的門相對應(yīng)的，量子計算機中的量子門由幺正變換實施。量子門的真值表較經(jīng)典的真值表要廣泛得多。量子門是實現(xiàn)量子并行計算的基石。

量子門可以作為實現(xiàn)量子計算的通用邏輯門的Fredkin

門和Toffoli門Fredkin門的真值表量子門Toffoli門及其真值表量子門異或（XOR）門及其對應(yīng)操作量子網(wǎng)路將量子門按某種方式連接，構(gòu)成量子網(wǎng)路，以進行復(fù)雜的運算。

利用XOR門與轉(zhuǎn)動門構(gòu)成的Toffolli門量子網(wǎng)路K-位寄存器上作分離（快速）傅立葉變換的量子網(wǎng)路主要內(nèi)容量子計算機的發(fā)展及現(xiàn)狀從計算機科學(xué)表述的量子力學(xué)原理量子計算基礎(chǔ)量子算法舉例—shor算法參考文獻shor算法1994年，PeterShor提出利用量子計算機將大數(shù)的素因子分解從NP問題簡化為P問題。Shor算法使雙密鑰系統(tǒng)土崩瓦解（如RSA算法），是量子計算機理論的里程碑。RSA算法以發(fā)明者的名字命名RonRivest,

Adi

Shamir

，

LeonardAdleman

RSA算法是第一個能同時用于加密和數(shù)字簽名的算法，也被認(rèn)為是目前最優(yōu)秀的公鑰方案之一。RSA的安全性依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明RSA算法PrivateKey（p，q，r）

其中：p,

q

是兩個相異的質(zhì)數(shù)

r

是與

(p-1)(q-1)

互質(zhì)的數(shù)Publickey（m，n）

其中：

m滿足rm

==

1

mod

(p-1)(q-1)n

=

pq

RSA算法加密目標(biāo)

對a加密，假設(shè)

a

<

n加密結(jié)果

b

==

am

mod

n,

(0

<=

b

<

n)解密過程

c

==

br

mod

pq

(0

<=

c

<

pq)

RSA算法

c

==

br

mod

pq

(0

<=

c

<

pq)

r

是與

(p-1)(q-1)

互質(zhì)的數(shù)

n

=

pq

RSA算法求數(shù)N的因子等效于求余因子函數(shù)的周期余因子函數(shù)

fa,N(x)=axmod

N,

其中:a為與N互素的可隨機選定的數(shù)

a<Nx=0,1,2,3,4,?RSA算法設(shè)該函數(shù)的周期為r當(dāng)r為偶數(shù)，且rmodN!=+1時

C=gcd

(ar/2

-1,N),D=gcd

(ar/2

+1,N)C和D即為N的兩個因子RSA算法舉例：

取p=3，q=5，r=7

則m=7n=15

取a=2

則b=8RSA算法對n=15進行分解余因子函數(shù)fa,N(x)=axmod

Na可取

2,4,7,8,11,13,14

隨機選a=7ax為1,7,49,343,2401,16807,...axmod15的值為

1,7,4,13,1,7,4,13,1,7,...

RSA算法可見周期r=4

且滿足r為偶數(shù)，

ar/2modN≠±1于是，C=gcd

(ar/2

-1,N)=3

D=gcd

(ar/2

+1,N)=5

為N的兩個質(zhì)因子shor算法對N進行分解設(shè)數(shù)N

在二進制中位數(shù)為L取輸入寄存器為2L位,輸出寄存器為L位它們的初始狀態(tài)均設(shè)為0,兩個寄存器總初始態(tài)為|0〉|0〉利用“轉(zhuǎn)動”門操作，將輸入寄存器設(shè)置為

Shor算法將余因子函數(shù)作用于輸出寄存器,使其成為對輸出寄存器進行測量，若有s種可能的測量結(jié)果，則測量后與其他s-1種結(jié)果相關(guān)的態(tài)均不存在Shor算法設(shè)z=fl,N(x)是某個最小值l所對應(yīng)的測量結(jié)果，周期性要求所有的測量結(jié)果應(yīng)可以表達為fjr+l,N(x)

其中，r是余因子函數(shù)的周期

j=0,1,2,?,A，A≈

22L/r。測量后，輸入寄存器的狀態(tài)為Shor算法測量周期r對輸入寄存器進行傅里葉變換

Shor算法若r可整除22L,有A=22L/r–1,故方括號內(nèi)的函數(shù)，僅當(dāng)c為22L/r的倍數(shù)時有非零值22L/rShor算法這一步的意義是：周期為r的狀態(tài)函數(shù)的傅里葉變換得到周期為22L/r的狀態(tài)函數(shù)將f(c)以及c=j*22L/r

代入得

Shor算法對此時的輸入寄存器進行測量，可得到滿足c/22L=k/r,(k=0,1,2,?)的c值將c/22L消到一個不可約的分?jǐn)?shù)后，就可以得到r得值。已經(jīng)證明，此算法重復(fù)O(㏒r)可得到所需的結(jié)果Shor算法Shor算法對于r不能整除22L的一般情況，情況比較復(fù)雜，可以通過一系列的數(shù)學(xué)和物理變化經(jīng)過O(㏒N)次重復(fù)計算后，得到r的值Shor算法Shor算法Shor

算法為一種隨機運算法，但因量子計算具有高度并行能力，每次運算可同時處理22L

個數(shù)據(jù)，故允許重復(fù)計算從惡熱得到高幾率的結(jié)果(~1)。卻又不至於影響計算的有效性。從上可知，以量子計算分解大數(shù)質(zhì)因子所需的步數(shù)為㏒N的多項式，即將問題簡化為P問題。shor算法經(jīng)典因子分解與量子因子分解的比較因為L(L+1)/2≤L2

當(dāng)L>5,則2L>L2

設(shè)L=200,2L/2=2100≈1030

設(shè)經(jīng)典計算機的運算速度約1012

次/秒作1030

次運算需1018

秒,而宇宙的壽命約為1017秒在量子計算機上采用量子算法,

需要作的運算次數(shù)約為L2≈4×104

同樣的運算速度,10-8

秒可完成shor算法舉例：取N=15，a=7

15需要四位二進制表示，于是設(shè)置輸入寄存器為8位，輸出寄存器為4位。設(shè)置寄存器的狀態(tài)，并用余因子函數(shù)對其作用后，兩個寄存器的總狀態(tài)為（余數(shù)共有1，4，7，13四個）

shor算法舉例：取N=15，a=7

(1/16)(|0〉|1〉+|1〉|7〉+|2〉|4〉+|3〉|13〉+|4〉|1〉+|5〉|7〉+|6〉|4〉+|7〉|13〉+|8〉|1〉+|9〉|7〉+|10〉|4〉+|11〉|13〉+|12〉|1〉+|13〉|7〉+|14〉|4〉+|15〉|13〉)shor算法舉例：取N=15，a=7

對輸出寄存器進行測量，將隨機得到1，4，7，13中的一個，假設(shè)測得的是7

則輸入輸出寄存器的狀態(tài)為

shor算法舉例：取N=15，a=7

(1/16)(|1〉|7〉+|5〉|7〉

+|13〉|7〉+|9>|7>)=(1/16)(|1〉+|5〉+|9〉+|13〉)|7〉shor算法舉例：取N=15，a=7

對輸入寄存器進行傅里葉變換，得到

c=64

將c/22L約分得1/4，即