秀爾的算法和詩_風聞

儘管費曼等人在1981年MIT會議上揭開了量子計算的序幕，但並未引起很大的反響，直到十幾年後，美國數學家秀爾提出“秀爾量子算法”，才讓量子計算研究開始步入快車道……

撰文 | 張天蓉

01 秀爾其人

彼得·秀爾（Peter Shor，1959 -，也稱彼得·肖）目前是麻省理工學院（MIT）的應用數學教授，他出生於紐約市，在華盛頓特區和加利福尼亞州長大。秀爾從小表現出極高的數學天賦，就讀高中時，他獲得美國1977年數學奧林匹克競賽第三名，同年又贏得國際數學奧林匹克競賽銀牌。1981年，他在加州理工學院獲得數學學士學位，1985年，他在麻省理工學院獲得應用數學博士學位。

在麻省理工學院獲得博士學位後，秀爾在加州大學伯克利分校做了一年的博士後，然後接受了新澤西州貝爾實驗室的職位。正是在那裏，他開發了Shor算法，解決了大質數的因式分解問題。

費曼1981年在MIT作有關量子計算的主題發言時，秀爾還是加州理工的大四學生。他並不知道費曼演講的內容，因為他主攻數學。不過，秀爾也對物理感興趣，聽過費曼的理論物理課。1985年，他又讀到大衞·多伊奇關於量子圖靈機、量子計算以及量子邱奇-圖靈論題的文章。

秀爾發現，多伊奇和費曼在考慮量子計算時，都在思考着量子的基礎，使他直覺意識到這很重要。不能“閉上嘴去計算”，必須思考量子的古怪性，繼而才能思考量子古怪性的可能用途。

之後，秀爾聽了查爾斯·本內特在貝爾實驗室做的一次量子信息報告，以及1992年優曼許·沃茲內尼到貝爾實驗室來做關於量子圖靈機報告。秀爾開始思考是否可以用量子計算機更有效地解決一個實際問題，但沒能真正取得進展，直到讀到丹·西蒙的文章。據説丹·西蒙的出發點是想證明數字計算機比量子計算機強大，但他最終找到一個問題顯示了相反的結果。

圖1：彼得·秀爾的貢獻

西蒙用了一個傅里葉變換來找出一個函數的週期。這點啓發秀爾開始尋求在量子計算機上解決離散對數問題的方法。離散對數問題是一個有名的難題，如果你解決了它，很容易就找到了因數分解算法，就可以破解一些公鑰加密系統，例如RSA。

秀爾算法一出，立刻帶來了兩個顯著效應，一是展示了量子計算可以在質因數分解問題上實現比經典計算機近乎指數級別的加速，二是對密碼學界的研究造成了不小的衝擊，因為它可以用於破解互聯網上廣泛使用的RSA協議，給信息安全提出了新的挑戰。這些都極大地引起了學界對量子計算、量子通信的重視和投入，開啓了量子計算研究的熱潮。

然而，因為量子比特的特殊性，無法直接觀測，因而缺乏有效的糾錯手段。兩個主要的量子力學原理，海森堡不確定性原理和量子不可克隆定理，被視為糾錯的最大阻礙。海森堡不確定性原理是説你無法完整地測量出量子態，量子不可克隆定理則是説你無法複製一個未知量子態。

面對以上挑戰，秀爾再次挺身而出，構造了第一個量子糾錯碼方案，他把3位重複碼嵌入另⼀個碼。也就是説，將⼀個邏輯量子位，用9個物理量子位進行編碼。秀爾的方案可以防止並糾正任何⼀個物理量子位上發生的任意量子錯誤。在這些發展之後，人們開始尋找其它的量子糾錯碼。

秀爾也提出了辦法來克服量子態退相干不可測量的問題，以及量子比特不可克隆的困難，基本思想就是利用量子糾纏這個量子世界的獨特現象。秀爾讓編碼⼀個邏輯量子比特的9個物理量子比特互相糾纏在一起。有關量子糾纏這方面我們不予詳細介紹，有興趣者可參考相關文獻。

在這兩個量子計算的重大突破之後，人們終於相信實際構建一台量子計算機是有巨大應用潛力和原理上可行的了，實驗物理學家和工程師們正式登上歷史舞台，並取得了豐碩的成果。

02 秀爾算法

秀爾量子算法是量子計算的一塊金字招牌。

因為假如有了可用的量子計算機，我們便可以用秀爾算法破解目前保障銀行安全常用的RSA加密算法。RSA的基礎是因數分解問題。加密過程中將兩個互素數p和q相乘得到N = p*q。加密是作一次乘法就完成的簡單操作，但是反過來的解碼過程則非常困難。

對經典計算機而言，RSA算法作“質因數分解”的解碼過程的時間複雜度是指數級別。例如，要分解d個十進制數字相乘的整數N，蠻力算法需要遍歷所有素數p直到sqrt(N），檢查是否p能整除N。分解d=230的N需要1025次運算。2021年最快的經典計算機每秒鐘運算1200萬億次（1.2x1015 /s，也得運算2000年左右）。

然而，秀爾量子算法[1]展示了：在量子計算機上，因數分解問題可以在N的多項式時間內被有效解決，即足夠大的量子計算機可以破解RSA。IBM於2001年成功展示秀爾算法實例，使用7個量子比特的量子計算機，將15分解成3×5，之後又分解21=3x7。這兩個數字都很小，但卻表明了秀爾算法具體實現的可能性。

秀爾的整個算法，分為經典算法和量子算法兩部分。經典算法用來完成經典計算方法本就可以在多項式時間內完成的部分，而將最困難的“傅里葉變換估算週期”，留給量子算法解決。

圖2：秀爾算法總體流程圖

如圖2所示，秀爾算法將一個大整數分解為兩個素數因子的過程，轉化成了兩部分：“外圍的”數論部分和“內部的”週期查找問題。數論部分可以用經典計算機在多項式時間複雜度內完成。但是，週期查找問題對經典而言關鍵且困難，對此問題經典算法的複雜度是指數級別，而秀爾用量子計算機可將複雜度降到多項式級別。

秀爾算法中只有“週期查找”這一步，是需要在量子計算機上完成的，其他都可在經典計算機上完成。量子計算機運行完“計算週期”的子程序後，就會將結果，即週期r，返回給經典計算機，讓它繼續完成計算過程。

實際上，量子計算和經典計算各有利弊。量子比特的特點是疊加態，有可能被利用來實現並行計算而加快算法，但是，在量子計算的過程中一般不進行（或少進行）測量，因為測量伴隨着疊加態的塌縮，一旦塌縮到一個本徵態，便失去了量子計算的優勢，而經典計算有容易掌控的優越性。因此，專家們認為，量子計算機或許永遠不會單獨存在，而是一直和經典計算機配合執行任務，各展其長。輸出、輸入以及複雜度簡單的部分由經典計算完成，特殊問題的困難部分由量子計算完成，就像秀爾算法這樣，便是用經典與量子配合起來完成破解RSA密鑰的過程。此外，與許多量子算法一樣，秀爾算法是概率性的。也就是説，它以高概率給出正確答案，並且通過算法的重複來降低失敗的概率。

總結一下秀爾量子算法：

1，經典部分，利用數論知識，將因式分解化為週期查找問題；

2，量子部分，使用傅里葉變換計算經典部分要求的週期。

下面兩個視頻，分別概括了秀爾算法中的這兩個過程：經典部分和量子部分【前往“返樸”觀看視頻】。

圖3（視頻1）：秀爾算法的經典部分

圖4（視頻2）：秀爾算法的量子部分

從視頻2中我們看到：秀爾算法的量子計算部分，幾乎利用了量子計算機的所有優勢：一是疊加性，即量子位的多重表示。就是用哈達瑪達門（Hadamard）製造出均勻疊加，疊加態可以同時進行平行運算，但卻不能測量。因為一旦測量，便會塌縮到所有本徵態的其中之一。因此，最好的辦法是將量子算法部分“包”在經典部分的中間，例如秀爾的量子部分包括QFT（量子傅里葉變換）在內。從經典部分給量子部分輸入少量的參數，量子給經典返回週期的數值。而將大量計算量，利用量子比特的平行運算能力，在量子計算機內部完成。量子計算部分被包住了，不測量就不會塌縮！然而，秀爾也巧妙地利用了量子態之間的糾纏性，引起部分塌縮但仍然保持疊加態。另外，量子傅里葉變換利用了量子相干性，因為物理中干涉衍射，其數學本質就是傅里葉變換。

03 糾錯和容錯

量子比特既棘手又脆弱。有用的量子計算機需要使用有效的糾錯技術。

秀爾是怎樣具體進行量子糾錯呢？再次回想一下經典糾錯，比如説：用“000”和“111”來代表“0”和“1”的方案，如果“000”中有一個比特發生了翻轉，我們通過讀出這三個比特發現錯誤，就可以糾正它。當然也有可能兩個比特同時發生錯誤，這時糾錯則將導致最終的錯誤。這樣的話，會不會“越糾越錯”呢？經典糾錯不會，因為根據概率規則，兩個錯誤同時發生的概率是發生一個錯誤概率的平方，而經典計算出錯概率很小，例如假設是萬分之一，那麼這個小概率的平方只有億分之一，更多的重複編碼，可以把錯誤率逐步降低到幾乎為0，這就是經典糾錯的基本機制。

圖5：秀爾糾錯碼，將單個量子比特的狀態印在九個量子比特上

量子糾錯遵循同樣的思想。但量子比特除了（0、1）翻轉之外，還有相位的變化。量子比特位的0和1發生翻轉的錯誤，被定義為X錯誤，符號（相位）發生翻轉的錯誤被定義為Z錯誤，這兩種錯誤也有可能同時發生，這時將其定義為XZ錯誤。因此，量子糾錯需要糾正這三類錯誤（X、Z 、XZ）。糾正X錯誤的情況與經典情況一樣；為了糾正Z錯誤，可以用“000”和“111”的疊加態“+++”和“---”來編碼。如此，一共就需要9個物理量子位，巧妙地組成某種嵌套式的編碼，就可以同時糾正X和Z的錯誤，以及XZ錯誤了。這個用9個量子比特來代表一個邏輯量子比特，就是當年秀爾提出的第一個量子糾錯碼[2]，圖5。

原則上，秀爾的“9個量子比特”代碼可以保護單個邏輯量子比特免受錯誤的影響。但是，如果錯誤測量本身存在錯誤怎麼辦？那麼，在嘗試糾正不存在的錯誤時，計算系統可能會翻轉一個位，並在不知不覺中引入一個真正的錯誤。在某些情況下，這可能會導致一系列錯誤在代碼中的傳播。

因此，在1996年，秀爾又提出了容錯的概念。只要錯誤發生的概率低於某個閾值，容錯代碼便可以處理由環境、量子比特的不完美操作甚至糾錯過程本身引入的錯誤。

如此一來，科學家們希望實現的目標便是“容錯量子計算”。在這種計算中，建立起足夠的冗餘和適當的編碼，使得即使有幾個量子比特出現錯誤，系統仍能運行並返回準確的答案。量子比特數的擴張，以及量子糾錯技術的重大進展，是實現量子計算的關鍵和挑戰。

04 秀爾和詩

難得的是，秀爾不僅是數學家，還是一位詩人。他從小就喜歡詩歌，父親給他讀詩。在過去的四十年裏，他也偶爾寫詩和翻譯詩歌，出版過詩集。例如，秀爾有一首“量子”之詩，描寫量子現象之詭異[3]。

The Quantum（by Peter Shor）I am the spooky action at a distance,The seething chaos that fills up empty space,The wave function collapse that you shall never witness,The living grin upon the dead cat’s face.Am I a wave? Am I a particle? Am I analog or digital?The answers surely must be both or none.My laws say quarks and clocks alike show interference,That if you watch a state, it never changes,That two entangled systems act as one.I make superconductors lose all their resistance,I make the atom split, the laser gleam,And although you may be bewildered by my strangeness,I am real! … You are living in a dream!

我將它翻譯成中文：

《量子自述》（作者，彼得·秀爾）

吾乃深遠幽之靈，

盈虛空間沸而騰。

波函數潰無以證，

死貓鮮活笑面迎。

亦粒亦波詭異事，

二者兼之或非矣？

夸克時鐘皆干涉，

二物糾纏如我律。

吾令原子激光耀，

吾令超導電阻失。

妖物鬼魅大師惑，

君於夢境餘為實。

參考資料

[1] The Early Days of Quantum Computation，Peter W. Shor, arxiv:2208.09964, https://arxiv.org/abs/2208.09964

[2] Shor, Peter W. (1995). “Scheme for reducing decoherence in quantum computer memory”. Physical Review A. 52 (4)

[3] PeterShorHomePage：https://math.mit.edu/~shor/

本文經授權轉載自微信公眾號“墨子沙龍”。

特 別 提 示

1. 進入『返樸』微信公眾號底部菜單“精品專欄“，可查閲不同主題系列科普文章。

2. 『返樸』提供按月檢索文章功能。關注公眾號，回覆四位數組成的年份+月份，如“1903”，可獲取2019年3月的文章索引，以此類推。