第27卷第1期廣西大學(xué)學(xué)報(bào)(自然科學(xué)版)Journal of guangxi UniversitatEd)M:,202文章編號(hào):1001-7445(2002)01-0083-04量子計(jì)算及其應(yīng)用鐘誠(chéng)2,陳國(guó)良(1.廣西大學(xué)計(jì)算機(jī)與信息工程學(xué)院,廣西南寧530004;2.中國(guó)科技大學(xué)計(jì)箅機(jī)系,國(guó)家高性能計(jì)算中安徽合肥230027)摘要:討論量子計(jì)算杋模型及其物理實(shí)現(xiàn)方案、量子計(jì)算過程、量子計(jì)算模型和量子并行算法,分析量子計(jì)算的指數(shù)級(jí)存儲(chǔ)容量和指數(shù)加速特征,并簡(jiǎn)述量子計(jì)算和量子信息技術(shù)在保密通信、密碼系統(tǒng)、數(shù)據(jù)庫(kù)搜索等重要領(lǐng)域的應(yīng)用關(guān)鍵詞:量子力學(xué);量子計(jì)算機(jī);量子信息;量子并行算法中圖分類號(hào):TP301文獻(xiàn)標(biāo)識(shí)碼:A電子、計(jì)算機(jī)與信息技術(shù)發(fā)展一日千里.電子元器件日益微型化的結(jié)果是使得一個(gè)微電子元件所包含的原子數(shù)目可以達(dá)到一個(gè)或幾個(gè),一個(gè)邏輯操作的耗能將達(dá)到不可逆邏輯操作的熱力學(xué)極限KT量級(jí).這使得經(jīng)典計(jì)算機(jī)芯片內(nèi)集成電子元件的數(shù)量受到很大的限制,CPU速度的增長(zhǎng)開始減緩.此種趨勢(shì)促使人們考慮研究遵循量子力學(xué)原理的量子計(jì)算機(jī)和量子計(jì)算技術(shù).20世紀(jì)后期以來科學(xué)家們?cè)诹孔佑?jì)算機(jī)的研制、量子計(jì)算和量子通信技術(shù)等方面取得了令人鼓舞的成就.專家門預(yù)測(cè),21世紀(jì)將是研究、開發(fā)與應(yīng)用“量子計(jì)算機(jī)”、“量子計(jì)算”和“量子通信”技術(shù)的新時(shí)代,相信在可預(yù)見的不久的將來量子計(jì)算機(jī)將從實(shí)驗(yàn)室走向市場(chǎng),量子信息技術(shù)將在科學(xué)研究、軍事和國(guó)民經(jīng)濟(jì)各領(lǐng)域得到廣泛應(yīng)用.本文從計(jì)算機(jī)科學(xué)的角度簡(jiǎn)述量子計(jì)算的有關(guān)問題以及量子信息技術(shù)的應(yīng)用,以期引起更多的讀者對(duì)量子計(jì)算和量子通信技術(shù)的關(guān)注1量子計(jì)算機(jī)模型及其物理實(shí)現(xiàn)方案前提岀的量子計(jì)算機(jī)模型主要有量子 Turing機(jī)模型、量子門組線路模型和量子細(xì)胞自動(dòng)機(jī)模型等.量子 Turing機(jī)模型可以用多項(xiàng)式大小的量子門組網(wǎng)絡(luò),或者用量子門組網(wǎng)絡(luò)多項(xiàng)式大小的時(shí)間來模擬.實(shí)現(xiàn)量子計(jì)算杋的物理方案有離子阱( (lon Trap)、腔量子電動(dòng)力學(xué)(腔QED)、核磁共振(NRM)和量子點(diǎn)( Quantum Dot)等.離子阱方案的主要優(yōu)點(diǎn)是阱中的超冷離子處于一個(gè)幾乎與外界隔絕的空間中,由環(huán)境引起的消相干效應(yīng)非常小,因此使得量子計(jì)算的并行度較高;其主要缺點(diǎn)是時(shí)鐘速度太慢用數(shù)目極大的激光束脈沖操作各個(gè)離子執(zhí)行邏輯運(yùn)算時(shí),運(yùn)算速度難以提高.腔量子電動(dòng)力學(xué)方案的主要優(yōu)點(diǎn)是兩個(gè)量子位之間相互作用的時(shí)間尺度大大小于離子阱方案,因此其可以在單位時(shí)間內(nèi)完成更多的操作步驟.利用核磁共振技術(shù)實(shí)現(xiàn)量子計(jì)算機(jī)較為成熟.而量子點(diǎn)方案的優(yōu)點(diǎn)則是量子位可以是嵌套在固體材料中的固態(tài)量子器件,這與經(jīng)典計(jì)算機(jī)的大規(guī)模集成電路的設(shè)計(jì)相似1-4.20世紀(jì)90年代以前,研究量子計(jì)算機(jī)似乎只是物理學(xué)家感興趣的事情.但是,自從1994年AT8T公司的科學(xué)家 PeterShor發(fā)表震驚世界的大整數(shù)素因子分解量子算法(此中國(guó)煤化工數(shù)學(xué)家大會(huì)最高獎(jiǎng))以來,立刻引起了越來越多的計(jì)算機(jī)科學(xué)家對(duì)量子計(jì)算的CNMHG量子信息技術(shù)的研究熱潮截止到2000年,美國(guó)已成功地建立4個(gè)量子位的離子阱量子計(jì)算機(jī),同時(shí)美國(guó)和德國(guó)的科學(xué)家利收稿日期:2001-10-25;修訂日期:2002-01-10基金項(xiàng)目:國(guó)家973計(jì)劃(G1998030403)作者簡(jiǎn)介:鐘誠(chéng)(1964-),男,廣西桂平人,廣西大學(xué)教授,中國(guó)科技大學(xué)博士生84廣西大學(xué)學(xué)報(bào)(自然科學(xué)版)第27卷用核磁共振技術(shù)成功地建立5個(gè)量子位的量子計(jì)算系統(tǒng),在中國(guó)則利用核磁共振技術(shù)成功地建立3個(gè)量子位的量子計(jì)算機(jī);據(jù)最新報(bào)道,2001年日本利用核磁共振技術(shù)已研制出16個(gè)量子位的實(shí)驗(yàn)性量子計(jì)算機(jī)原型.目前,各國(guó)正向建立更多量子位的、實(shí)用的量子計(jì)算機(jī)的目標(biāo)努力,并不斷取得新進(jìn)展2量子計(jì)算過程眾所周知經(jīng)典的馮·諾依曼數(shù)字電子計(jì)算機(jī)是遵照?qǐng)D靈( Turing)計(jì)算模型設(shè)計(jì)和制造的.這是因?yàn)閺慕?jīng)典意義上而言,“計(jì)算”屬于數(shù)學(xué)范疇,“計(jì)算”的理論與方法可以脫離具體的物理過程,依靠純粹的思辨和抽象的邏輯推理構(gòu)造岀來.但是,“計(jì)算”本質(zhì)上可以看作是計(jì)算儀器的物理系統(tǒng)所執(zhí)行的一個(gè)物理過程.根據(jù)采用的計(jì)算設(shè)備的不同,這一物理過程也不盡不相同,它可以是人腦所完成的“計(jì)算”、算盤操作的“計(jì)算”和電子計(jì)算機(jī)控制的“計(jì)算”,等等.不管采用何種計(jì)算設(shè)備,“計(jì)算”的一般過程是:首先輸入原始數(shù)據(jù),從物理的角度看這可以解釋為在計(jì)算系統(tǒng)中制備岀一個(gè)初始物理態(tài);然后執(zhí)行計(jì)算,這過程實(shí)際是按照算法規(guī)定的步驟,將給定的初始物理態(tài)演化成對(duì)應(yīng)輸岀物理態(tài)的過程;最后輸岀計(jì)箅結(jié)果,這可以看作對(duì)演化的物理末態(tài)進(jìn)行測(cè)量得到所需信息的過程.量子計(jì)算機(jī)是一種遵循量子力學(xué)原理完成計(jì)算仼務(wù)的系統(tǒng),它采用量子態(tài)編碼信息,其存儲(chǔ)量子信息的基本單元是稱為量子位( qubit的量子雙態(tài)系統(tǒng)(或者說是一個(gè)二維 Hilbert空間).可以將量子計(jì)算機(jī)看成是由一系列量子門構(gòu)成的電路.假設(shè)該電路由n個(gè)邏輯門構(gòu)成并作用在m個(gè)量子位上.一個(gè)量子位是一個(gè)微觀粒子構(gòu)成的兩基態(tài){0,1}系統(tǒng).一個(gè)量子位除了可以處于0態(tài)和1態(tài)之外,還可以處于它們的迭加態(tài).量子位的迭加態(tài)φ>可表示如下:φ>=p。10>十p11>.其中υ和p均為復(fù)數(shù),表示基態(tài)0和1的振幅(概率幅)p|和|p1|2分別表示系統(tǒng)處于基態(tài)0和的概率,且滿足歸化,即滿足>||2=1.當(dāng)對(duì)量子系統(tǒng)的迭加態(tài)|ψ>進(jìn)行測(cè)量時(shí),量子寄存器的狀態(tài)以|p。|2的概率處于|0>態(tài),以|p1|2的概率處于>態(tài)與經(jīng)典計(jì)算機(jī)的數(shù)據(jù)表示相似,量子計(jì)算機(jī)的數(shù)據(jù)用量子寄存器中所有量子位的共同量子狀態(tài)來表示,一般地,一個(gè)n位經(jīng)典計(jì)算機(jī)的寄存器僅處于惟一的狀態(tài)(0或1)中,而一個(gè)n位的量子寄存器卻可以處于2"個(gè)基態(tài)的相干迭加態(tài)|ψ>中.迭加態(tài)|y>和基態(tài);>的關(guān)系可表示如下:y>=p,②其中為復(fù)數(shù),表示振幅(概率幅),p|2給出迭加態(tài)|ψ>在受到與量子計(jì)算系統(tǒng)相糾纏的儀器測(cè)量發(fā)生散落時(shí)坍縮到基態(tài)|,>的概率且滿足>P12=1.量子寄存器用于存儲(chǔ)量子位信息量子寄存器的狀態(tài)描述量子計(jì)算機(jī)的狀態(tài).一個(gè)n個(gè)量子位的量子寄存器能夠同時(shí)存儲(chǔ)2″個(gè)狀態(tài)信息(即2個(gè)數(shù)據(jù)),因此,量子計(jì)算機(jī)具有經(jīng)典計(jì)算機(jī)無可比擬的、指數(shù)級(jí)的海量存儲(chǔ)能力.量子門對(duì)量子寄存器進(jìn)行操作,實(shí)現(xiàn)量子態(tài)的轉(zhuǎn)換(即實(shí)現(xiàn)對(duì)量子寄存器中的數(shù)據(jù)進(jìn)行計(jì)算、處理)量子計(jì)算的過程是:首先制備岀處于迭加、等振幅(等概率)的量子初態(tài),然后按照算法需要對(duì)迭加態(tài)不斷進(jìn)行演化(量子門操作,幺正變換),最后對(duì)最終的迭加態(tài)進(jìn)行測(cè)量使其以接近于1的概率坍縮到所希望的態(tài),從而得到所需的計(jì)算結(jié)果.對(duì)于量子計(jì)算系統(tǒng),因?yàn)榭梢灾苽涑鲇筛鱾€(gè)互不相同的態(tài)迭加所形成的初始態(tài),量子計(jì)算機(jī)具有對(duì)這些初始態(tài)同時(shí)進(jìn)行演化的能力,也即量子計(jì)算機(jī)可以沿著各條互不相同的路徑同時(shí)演化初始迭加態(tài),直至荻得對(duì)應(yīng)的輸出的迭加態(tài).對(duì)于一個(gè)n個(gè)量子位的量子寄存器,由于其同時(shí)存儲(chǔ)了2狀態(tài)信息(2個(gè)數(shù)據(jù)),所以對(duì)量子寄存器進(jìn)行一次量子門操作即可實(shí)現(xiàn)對(duì)2個(gè)狀態(tài)信息(2個(gè)數(shù)據(jù))進(jìn)行計(jì)算、處理這說眀量子計(jì)算機(jī)具有天然的并行性極大地加快對(duì)海量信息處理的速度,使得大規(guī)模復(fù)雜問題能夠在有限的指定的時(shí)間內(nèi)完成.量子計(jì)算系統(tǒng)中國(guó)煤化工處理”特性使得它具有比經(jīng)典計(jì)算機(jī)更快速、更強(qiáng)大的信息處理能力,特別適CNMHG(參見: Kevin markObenland Using Simulation to Assess the Feasibility ot Quantum Computing. Ph.D.DissertationUniversity of Southern California, 1998.8.)3量子計(jì)算模型和量子并行算法量子算法具有量子態(tài)相干迭加、量子并行、量子態(tài)糾纏和測(cè)量坍縮等特性.由于量子計(jì)算的過程是1期鐘誠(chéng)等:量子計(jì)算及其應(yīng)用量子系統(tǒng)初態(tài)φ>經(jīng)過與量子計(jì)算機(jī)控制系統(tǒng)的相互作用,隨時(shí)間演化成所需末態(tài)丨φ灬>的過程,所以假設(shè)量子計(jì)算機(jī)控制系統(tǒng)由量子門U,(i=1,2,…,m)和量子門后的測(cè)量算符M,表述,演化計(jì)算得到的中間結(jié)果用態(tài)矢序列{φ'ψφ'ψ……φ-ψn-1}表述,那么一個(gè)簡(jiǎn)化的量子計(jì)算模型可描述如下MnUm……M2U2M1U1(|y>)=MnUm……M2U2M1(|y1>)=MnCm……MU2(|y1>)對(duì)于上述量子計(jì)算模型中的每一次變換U-1(|ψ-1>)→|ψ>,在設(shè)計(jì)量子算法時(shí)可以用幺正變換矩陣和態(tài)矢量相乘來實(shí)現(xiàn).設(shè)有某個(gè)量子算法∫,U′表示一個(gè)量子門完成的線性變換,當(dāng)將U/作用于某個(gè)迭加態(tài)時(shí),根據(jù)量子算法的并行性,它會(huì)同時(shí)作用到該迭加態(tài)的所有基態(tài)上,并將所有結(jié)果進(jìn)行迭加以產(chǎn)生一個(gè)新的迭加態(tài).因此,為了計(jì)算函數(shù)∫(x),僅需應(yīng)用一次U’操作即可并行計(jì)算出x取2個(gè)不同值的f(x)的結(jié)果其中,x>10>表示系統(tǒng)由兩個(gè)量子寄存器組成,第1個(gè)量子寄存器|x>表示基態(tài)(存儲(chǔ)自變量α的值),第2個(gè)量子寄存器⑩>用于存儲(chǔ)計(jì)算∫(x)的結(jié)果,其初始值為O.為了獲取計(jì)算結(jié)果,需要對(duì)量子寄存器進(jìn)行測(cè)量.所謂測(cè)量是將系統(tǒng)的狀態(tài)投影到某個(gè)基態(tài)上,提取岀相應(yīng)的概率幅.當(dāng)測(cè)量第1個(gè)量子寄存器時(shí),會(huì)導(dǎo)致系統(tǒng)狀態(tài)從迭加態(tài)坍縮到某個(gè)確定的基態(tài)|x>上,由于第1個(gè)量子寄存器和第2個(gè)量子寄存器是糾纏在一起的,所以第2個(gè)量子寄存器會(huì)關(guān)聯(lián)坍縮到某個(gè)確定的結(jié)果態(tài)‖f(x)>上,為此,在設(shè)計(jì)量子算法時(shí)需要確保最后得到的結(jié)果態(tài)的概率最大.例如,若希望得到x=101的結(jié)果∫(101),那么量子算法的控制應(yīng)使得基態(tài)101>對(duì)應(yīng)的概率幅最大,這樣測(cè)量時(shí)第2個(gè)量子寄存器即坍縮到態(tài)|f(101)>上4量子計(jì)算技術(shù)的應(yīng)用1)量子信息保密通信.量子信息是用量子態(tài)編碼的信息,量子態(tài)具有事先不可確定的特性,即量子態(tài)是未知態(tài),量子信息滿足“量子態(tài)不可完全克隆(No- Cloning)定理”,這樣在量子信道上傳輸量子信息過程中,即使竊聽者截獲了用量子態(tài)表示的密鑰,他也不可能完全恢復(fù)出原本的密鑰信息,從而他不能破譯秘密信息,這是因?yàn)榛謴?fù)密鑰是破譯密碼系統(tǒng)的關(guān)鍵θ.此外,A.K.Pati等人利用量子力學(xué)的線性性證明仼意未知量子態(tài)拷貝的完全刪除也是不可能的,即密碼攻擊者不能破壞量子信息傳輸?shù)耐暾?因此,在量子信道上可以實(shí)現(xiàn)量子信息的保密通信.目前,美國(guó)和英國(guó)已實(shí)現(xiàn)在46KM的光纖中進(jìn)行點(diǎn)對(duì)點(diǎn)的量子密鑰傳送,而且美國(guó)還實(shí)現(xiàn)在1KM以遠(yuǎn)的自由空間傳送量子密鑰,瑞士則實(shí)現(xiàn)了在水底光纜傳送量子密鑰(2)經(jīng)典計(jì)算難題的量子算法.大整數(shù)素因子的分解問題是著名的公開密鑰密碼系統(tǒng)RAS安全性的基礎(chǔ).因?yàn)閷?duì)于一個(gè)足夠大的整數(shù)(比如500位以上的整數(shù)),即使是用高性能超級(jí)并行計(jì)算機(jī),要在現(xiàn)實(shí)的可接受的有限時(shí)間內(nèi),分解岀它是由哪兩個(gè)素?cái)?shù)相乘的是一件十分困難的工作,所以多年來人們直認(rèn)為RSA密碼系統(tǒng)在計(jì)算上是安全的.然而,石破天驚, Peter Shor于1994年發(fā)表的大整數(shù)素因子分解量子算法(簡(jiǎn)稱Shor算法)表明,在量子計(jì)算機(jī)上只要花費(fèi)多項(xiàng)式的時(shí)間即可以接近于1的概率成功分解岀任意的大整數(shù),這使得RSA密碼系統(tǒng)安全性極大地受到威脅.因此,Shor算法的發(fā)現(xiàn)給量子計(jì)算機(jī)的研究注入新活力,并引發(fā)了量子計(jì)算研究的(3)亂序數(shù)據(jù)庫(kù)的快速搜索.我們都知道,要在經(jīng)典中國(guó)煤化工勺無序的數(shù)據(jù)庫(kù)中搜索出指定的記錄,算法的時(shí)間復(fù)雜性為O(N).因?yàn)樗阉鲾?shù),,以當(dāng)記錄數(shù)N充分大時(shí),搜索工作猶如“在一大堆干草中搜尋出一根針”一樣的煩與難.于是,人們另辟渠道.L·K· Grover于1997年在物理學(xué)界鼎尖雜志《 Physics Review Letters》上發(fā)表了一個(gè)亂序數(shù)據(jù)庫(kù)搜索的量子算法,其時(shí)間復(fù)雜性為O(√N(yùn)).此量子搜索算法與經(jīng)典搜索算法相比達(dá)到√N(yùn)數(shù)量級(jí)的加速,特別適用于求解那些需要用窮舉法對(duì)付的NP類問題廣西大學(xué)學(xué)報(bào)(自然科學(xué)版)第27卷5結(jié)束語(yǔ)自從Shor算法發(fā)表以來,國(guó)際計(jì)算機(jī)科學(xué)界十分重視量子計(jì)算理論和技術(shù)的研究,并取得若干重要的成果.我國(guó)計(jì)算機(jī)界從1997年左右開始涉足此領(lǐng)域,這是一個(gè)良好的開端.雖然量子計(jì)算機(jī)目前離實(shí)際應(yīng)用尚有一段距離但是量子計(jì)算和量子信息技術(shù)所展現(xiàn)出的前景是光輝、燦爛的,它將對(duì)科學(xué)研究、軍事和國(guó)民經(jīng)濟(jì)建設(shè)產(chǎn)生巨大、深遠(yuǎn)的影響參考文獻(xiàn)[1] Vlatko Vedral, Martin B Plenio. Basics of Quantum Computation. Progress in Quantum Electronics[J].1998,22[2 Privman V, Vagner I D, Kventsel G. Quantum computation in quantum-Hall systems J. Physics Letters A, 1998239(3):141-146[3 Paolo Zanardi. Mario Rasetti Holonomic Quantum Computation[J]. Physics Letters A,1999.264(2-3):94-99[4 Jones J A NMR quantum computation[J]. Progress in Nuclear Magnetic Resonance Spectroscopy, 2001, 38(4)325-360[5 Vilela Mendes R, Ricardo Coutinho. On the Computation of Quantum Characteristic exponents[J. Physics Letters A,1998,239(4-5):239-245.[6]陸向艷,鐘誠(chéng).密鑰恢復(fù)技術(shù)分析[J].廣西大學(xué)學(xué)報(bào)(自然科學(xué)版),2001,26(1):36-39.Quantum computation and its applicationsZHONG Cheng.2, CHEN Guo-liang(1. College of Computer and Information Engineering, Guangxi University, Nanning 530004, China: 2. Dept Of Computer Science, University of Science and Technology of China, Hefei 230027. ChinaAbstract: In this paper, the quantum computer model and its physical implementation, quantum com-putation procedure, quantum computation approach, design of quantum parallel algorithms are discussed, and the characteristic of exponential storage and speed-up of quantum algorithms is analyzedThe applications of quantum computation technologies in secret communication, cryptography systemand database searching are also discussedKey words quantum mechanics; quantum computer; quantum information; quantum parallel algorithms(責(zé)任編輯唐漢民劉海濤張曉云)中國(guó)煤化工CNMHG