量子計算-Shor演算法

建議閱讀時間：10分鐘

量子計算

量子計算的概念源起於十九世紀八十年代，然而人們真正認識到量子計算的威力是在大約十年後。

1994年，美國麻省理工數學家彼得·舒爾（Peter Shor）提出了一個針對整數分解問題的量子演算法，即舒爾演算法（Shor』s algorithm），宣稱可以在量子計算機上多項式時間內分解大整數。這是一個具有轟動性的結論。

眾所周知，大整數分解問題是數論中的經典困難問題，在Shor演算法提出之前，沒有已知演算法可以在多項式時間內分解大整數分解問題。

著名的公鑰密碼體制RSA正是基於大整數分解問題的困難性來進行加密的。據微軟研究院的人士估計，破解2048比特強度的RSA密鑰可能需要當今最快的經典計算機耗費10億年以上的時間，而運行Shor演算法的量子計算機只需要不到100秒就可以完成。

Shor演算法的提出，不僅對RSA密碼體制構成了威脅，更讓人們認識到，量子計算具有非常強大的計算與應用潛力。從而促使量子計算機的研究邁上一個新的台階。

Shor演算法——廬山真面目

簡單來講，Shor演算法包含兩個部分：

量子力學態疊加原理使得量子信息單元的狀態可以處於多種可能性的疊加狀態，從而導致量子信息處理從效率上相比於經典信息處理具有更大潛力

普通計算機中的2位寄存器在某一時間僅能存儲4個二進位數（00、01、10、11）中的一個，而量子計算機中的2位量子位（qubit）寄存器可同時存儲這四種狀態的疊加狀態。

隨著量子比特數目的增加，對於n個量子比特而言，量子信息可以處於2種可能狀態的疊加，配合量子力學演化的並行性，可以展現比傳統計算機更快的處理速度。舒爾演算法的設計充分利用了以上量子力學特性，使得加速成為可能。

I. 從周期得到因子

II. 找尋周期

舒爾演算法的基本思想是利用量子存儲以及量子並行性，同時得到所有可能狀態模數運算後的函數值，對函數值進行測量後利用量子糾纏得到函數值所對應的所有原像的疊加態。最後利用量子傅里葉變換得到周期。

具體來說，需要經過以下四步：

與傳統情況類似，在這些轉化之後，一個測量值將會產生一個近似方程周期的值(你可以獲得「波峰」，就像傅立葉變換中的，而準確性會更高一點)。

使用量子傅立葉變換，我們能夠解決排序和因數問題，這二者相同。量子傅立葉變換可以讓一台量子計算機進行相位估計(酉運算元特徵值的近似值)，從而有利於解決一大類被稱為隱含子群的問題，求周期與離散對數問題是其中具有代表性的兩個問題。

實驗進展與面臨困難

自從1994年舒爾演算法被提出以來，有許多物理實驗用來驗證舒爾演算法的正確性。

2001年，量子計算領域的開拓者之一，Chuang，設計了一個基於分子NMR（核磁共振）的實驗分解整數15。該實驗結果發表在了《自然》雜誌上。這是第一次以實驗的方式實現Shor演算法的主要原理驗證。

其後至今的近二十年內，有許多其它類似實驗相繼驗證了舒爾演算法的可行性。

然而目前為止，實驗上，利用舒爾演算法可以分解的最大整數僅為21。換句話說，該實驗的可拓展性非常具有挑戰性，這也是量子計算機研製目前所面臨的一個主要難題。

祝學習愉快！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！