量子計算的優(yōu)勢特征、算法和物理實現(xiàn)

谷娟

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

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

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

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

1982年美國物理學(xué)家費曼（R.P.Feynman ）提出量子計算概念，但由于量子態(tài)的測不準(zhǔn)原則以及量子系統(tǒng)容易受噪聲干擾，量子運算很容易出錯。直到1994年美國計算機專家Shor證明了量子計算機能快速分解大因數(shù)，并實現(xiàn)了第一套量子算法編碼，量子計算以及量子計算機的研究才進(jì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類，極大地促進(jìn)了量子計算的發(fā)展，使人們第一次清楚地看到了量子計算獨具優(yōu)勢的重要應(yīng)用前景。從此，世界眾多研究小組加入了該研究行列，量子計算研究領(lǐng)域取得了許多重大進(jìn)步，

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

Shor算法本身已經(jīng)相當(dāng)成熟，對其改進(jìn)和優(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)用性卻很好的彌補了這一點。現(xiàn)實中有許多問題，如最短路徑問題、圖的著色問題、排序問題及密碼的窮舉攻擊問題等，都可以將Grover算法視為通用算法求解。事實上，目前Grover算法已經(jīng)在核磁共振和光學(xué)系統(tǒng)中得到實現(xiàn)。

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

（三）量子智能算法

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

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

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

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

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

參考文獻(xià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ìn)展[J].物理學(xué)進(jìn)展，2005，25（4）： 368-385.