谷娟

摘 要：量子計算表現(xiàn)出的并行性是其相對于經(jīng)典運算的優(yōu)勢特征。目前已知的最為成功的兩類量子算法是基于Shor的量子Fourier變換算法和基于Grover的量子搜索算法。量子計算和量子算法理論的基本框架已經(jīng)成型，各方面研究進展日新月異，但最終實現(xiàn)實用價值的量子計算，還需要解決眾多問題。其中，何種物理系統(tǒng)最終適用于量子計算機迄今尚無定論，盡管如此，堅信實現(xiàn)量子計算已不存在不可逾越的障礙的信念正激勵著學(xué)術(shù)界的巨大研究熱情。

關(guān)鍵詞：量子計算;量子算法;優(yōu)化;實現(xiàn)困難

隨著人類在信息量處理速度方面的需求越來越高，當前計算機性能的提升速度滿足不了人類在信息處理速度方面的需求。十九世紀初提出并建立的量子力學(xué)理論帶來計算機的革命性發(fā)展了新的解決辦法，量子獨有的相干性和糾纏性等特性為量子計算帶來了完全不同于經(jīng)典計算的獨特運算方式。經(jīng)過近一個世紀的發(fā)展，2009年美國國家標準技術(shù)研究院研制的世界上首臺通用編程量子計算機面世。量子計算是應(yīng)用量子力學(xué)原理來進行有效計算的新穎計算模式，它利用量子疊加性、糾纏性和量子的相干性實現(xiàn)量子的并行計算。量子計算從本質(zhì)上改變了傳統(tǒng)的計算理念。

一、量子計算的優(yōu)勢特征

1982年美國物理學(xué)家費曼（R.P.Feynman ）提出量子計算概念，但由于量子態(tài)的測不準原則以及量子系統(tǒng)容易受噪聲干擾，量子運算很容易出錯。直到1994年美國計算機專家Shor證明了量子計算機能快速分解大因數(shù)，并實現(xiàn)了第一套量子算法編碼，量子計算以及量子計算機的研究才進入實驗時代。

經(jīng)典比特具有0和1兩種狀態(tài)。量子比特與經(jīng)典比特的不同之處在于：一個量子比特除了可以像經(jīng)典比特一樣處于0和1這樣的狀態(tài)之外，還可以處于既非0又非0的狀態(tài)上，這個中間狀態(tài)稱為疊加態(tài)（Superposition）。量子疊加態(tài)是決定量子計算不同于經(jīng)典計算的關(guān)鍵特性之一，也是量子并行計算的理論基礎(chǔ)。相同位數(shù)的寄存器，量子計算機可以記錄的信息量是傳統(tǒng)計算機的指數(shù)倍，它的運算速度和信息處理能力是經(jīng)典計算機所無法比擬的。因此，量子并行計算體現(xiàn)了量子計算最重要的優(yōu)越性。

二、量子算法

量子算法作為量子計算科學(xué)的重要部分，在過去的十幾年中得到了廣泛的發(fā)展并取得了一系列驚人的成就。目前已知的最為成功的兩類量子算法是基于Shor的量子Fourier變換算法和基于Grover的量子搜索算法。1989年，Deutsch首次提出了Deutsch量子算法。該算法第一次很好的展示了量子計算機的并行性。1994年，Shor提出大數(shù)質(zhì)因子分解量子算法并實現(xiàn)了該算法的量子編碼，此后，Grover算法、量子智能算法等量子算法相繼被提出，量子算法的研究工作也得到了各國研究者的關(guān)注。

（一） Shor大數(shù)質(zhì)因子分解算法

1994年， Shor提出了離散對數(shù)問題和大整數(shù)質(zhì)因子分解問題的量子算法，證明了這兩個重要且復(fù)雜的問題屬于BQP類，極大地促進了量子計算的發(fā)展，使人們第一次清楚地看到了量子計算獨具優(yōu)勢的重要應(yīng)用前景。從此，世界眾多研究小組加入了該研究行列，量子計算研究領(lǐng)域取得了許多重大進步，

Shor的另一項同樣重要的成果是率先提出了量子糾錯碼[18，19]，這使得容錯的量子計算成為可能[19]。量子計算在密碼學(xué)領(lǐng)域也取得了迅速的發(fā)展，這就意味著目前廣泛應(yīng)用于政府、軍事以及金融機構(gòu)等重要方面的RSA公鑰密碼體系的安全性可能面臨著致命的威脅，僅這一點就足以引起人們對量子算法研究的極大關(guān)注。

Shor算法本身已經(jīng)相當成熟，對其改進和優(yōu)化的空間不大。Shor算法是目前為止已經(jīng)提出的最好的量子算法，該算法不但具有傳統(tǒng)算法無法比擬的優(yōu)勢，而且其巧妙的理論構(gòu)思以及表現(xiàn)出的實際應(yīng)用價值，都是十分寶貴的。Shor算法及其模擬實現(xiàn)，對量子通信和量子密碼學(xué)的發(fā)展都具有極其重要的參考價值。

（二）Grover數(shù)據(jù)庫搜索算法

對于無序數(shù)據(jù)庫，搜索的規(guī)模隨著數(shù)據(jù)庫規(guī)模的增長而成線性增長。Grover提出量子搜索算法，將搜索問題完成時間縮小，對經(jīng)典問題起到了二次加速的作用。

Grover算法適宜于解決在無序數(shù)據(jù)庫中搜索某一個特定數(shù)據(jù)的問題。Grove：算法利用量子并行性，并沒有像Shor算法一樣實現(xiàn)問題的指數(shù)加速，然而搜索算法的廣泛應(yīng)用性卻很好的彌補了這一點?，F(xiàn)實中有許多問題，如最短路徑問題、圖的著色問題、排序問題及密碼的窮舉攻擊問題等，都可以將Grover算法視為通用算法求解。事實上，目前Grover算法已經(jīng)在核磁共振和光學(xué)系統(tǒng)中得到實現(xiàn)。

Grover算法是目前最經(jīng)典的量子算法之一，然而它也存在著某些缺陷。對Grover算法的改進研究也成為了目前量子算法方面的一個熱門研究領(lǐng)域。

（三）量子智能算法

自Shor算法和Grover算法提出以后，量子計算方法表現(xiàn)出的獨特計算方式以及在信息處理方面展現(xiàn)的巨大潛力引起了研究者的廣泛關(guān)注。自Shor因子分解算法和Grover搜索算法提出后，雖然眾多研究者在量子算法領(lǐng)域進行了大量的研究，但迄今為止并沒有取得重大突破。而智能算法向來是算法研究領(lǐng)域的一個熱點，量子智能計算將量子理論原理與智能計算相結(jié)合，利用量子并行計算特性很好的彌補了智能算法中的某些不足之處，如：加快算法的收斂速度及避免早熟現(xiàn)象等。

目前己有的量子智能算法研究包括：量子進化算法、量子免疫計算、量子退火計算、量子神經(jīng)網(wǎng)絡(luò)和量子聚類算法等。其中，量子進化算法和量子神經(jīng)網(wǎng)絡(luò)成為目前學(xué)術(shù)研究的熱點并取得了相當不錯的成績。

目前量子進化算法的應(yīng)用研究領(lǐng)域也很有限，量子進化算法的研究還不夠成熟，很多理論和應(yīng)用的研究還需要深化和推廣，進一步研究的空間還很大。

三、量子計算的物理實現(xiàn)

量子計算和量子算法理論的基本框架已經(jīng)成型，各方面研究進展日新月異，但最終實現(xiàn)實用價值的量子計算，還需要解決眾多問題。其中，量子計算的前提是量子計算的物理實現(xiàn)，但量子計算機技術(shù)上的實現(xiàn)卻遇到嚴重的困難，何種物理系統(tǒng)能最終適用于量子計算機迄今尚無定論，盡管如此，堅信實現(xiàn)量子計算已不存在不可逾越的障礙的信念正激勵著學(xué)術(shù)界的巨大研究熱情去推進相關(guān)研究進展。

參考文獻：

[1]首次在國際上實現(xiàn)量子分解算法.中國科學(xué)院院刊，2008，23（1）：76-76.

[2]彭衛(wèi)豐，孫力.SHOR量子算法的優(yōu)化及應(yīng)用研究.計算機應(yīng)用與軟件，2009，26（5）：239-246.

[3]李士勇，李盼池.量子計算與量子優(yōu)化算法.哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2009.

[4]周正威，黃運鋒，張永生等.量子計算的研究進展[J].物理學(xué)進展，2005，25（4）： 368-385.