量子計算的優勢特征、算法和物理實現

谷娟

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

關鍵詞：量子計算;量子算法;優化;實現困難

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

一、量子計算的優勢特征

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

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

二、量子算法

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

（一） Shor大數質因子分解算法

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

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

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

（二）Grover數據庫搜索算法

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

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

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

（三）量子智能算法

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

目前己有的量子智能算法研究包括：量子進化算法、量子免疫計算、量子退火計算、量子神經網絡和量子聚類算法等。其中，量子進化算法和量子神經網絡成為目前學術研究的熱點并取得了相當不錯的成績。

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

三、量子計算的物理實現

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

參考文獻：

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

[2]彭衛豐，孫力.SHOR量子算法的優化及應用研究.計算機應用與軟件，2009，26（5）：239-246.

[3]李士勇，李盼池.量子計算與量子優化算法.哈爾濱：哈爾濱工業大學出版社，2009.

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