量子計算及其應用

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