這位理論計算機科學家描述了他走向質因數分解演算法（Factoring Algorithm），進而引發量子計算（Quantum Computing）熱潮的歷程。
彼得·秀爾（Peter Shor）在他的麻省理工學院（MIT）辦公室。（照片由Christopher Harting提供。）
大衛·齊耶勒（David Zierler）是加州理工學院傳承計畫（Caltech Heritage Project）的 Ronald and Maxine Linde 主任。進行這次訪談時，他是美國物理學會（American Institute of Physics）的口述歷史學家（Oral Historian）。萊恩·達恩（Ryan Dahn）是《PHYSICS TODAY》的資深副主編及科學史學家。
1990年代初期，現今被稱為量子資訊科學（Quantum Information Science）的領域，當時是一個次要的學科分支，聚集了少數理論物理學家、數學家與電腦科學家。這個領域常被視為一個晦澀偏門、毫無實際應用的研究分支，因為當時還沒有人能證明在某種情境下，量子電腦（那時僅存在於理論中）會遠比傳統電腦更有效率。
這一切在 1994 年發生了改變，當時 Peter Shor 提出了第一批能讓量子電腦將原本在古典電腦上「極度難解」的問題變得可行的演算法之一。他的演算法格外受到矚目，因為它能快速分解大數的質因數，而這對資安領域有深遠影響：許多至今仍在使用的重要數位加密系統，其關鍵假設正是——在古典電腦上分解大數需要極為漫長、幾乎不可行的運算時間。
秀爾的論文引發了科學家和政策制定者對量子計算的熱烈關注。時至今日，各大學、政府和私人企業已在這個蓬勃發展的量子資訊科學領域投入了數十億美元。
秀爾與美國物理學會（《Physics Today》的出版單位）大衛·齊耶勒的一次口述歷史訪談，時間是在2020年。以下是經節錄、註釋並略作編輯的訪談紀錄。
齊耶勒：秀爾演算法（Shor’s algorithm）是怎麼來的？當時你在研究什麼，促使你意識到自己發現了這個演算法？
秀爾：在美國，理論計算機科學界有，我想現在也還是如此，兩個主要的學術會議。分別是春季舉辦的STOC（計算理論研討會，Symposium on Theory of Computing），以及秋季舉辦的FOCS（計算機科學基礎研討會，Symposium on Foundations of Computer Science）。那時候，這兩個會議確實就像是理論計算機科學學者的《物理評論快報》（Physical Review Letters）一樣。能在STOC和FOCS發表大量論文，對職涯發展非常有幫助。
所以在程序委員會開會（決定研討會論文錄取名單）前，大家會到全國各地演講自己的研究成果。烏梅什·瓦茲拉尼（Umesh Vazirani）在1993年春季的STOC有篇論文。1他在那場會議之前曾來貝爾實驗室（Bell Labs）演講，所以應該是在1992年的晚秋或初冬。我聽了那場演講，覺得它聽起來非常有趣。
他離開之後，我就開始思考這個主題，並去貝爾實驗室圖書館查找了許多關於量子計算的早期論文，例如理查·費曼（Richard Feynman）、戴維·多伊奇（David Deutsch），以及多伊奇和理察·喬薩（Richard Jozsa）的論文。那時的相關論文其實不多。
總之，我讀了那些論文，然後我開始思考量子電腦到底能用來做什麼。當然，這是一個非常瘋狂、遙不可及的想法，所以我沒跟任何人說。
接下來的STOC，我剛好是程序委員會的成員，而丹·賽蒙（Dan Simon）投稿了一篇現在被稱為賽蒙演算法（Simon's algorithm）的論文。2那的確是一篇很棒的論文，但STOC的委員會還是把它拒絕了。
齊耶勒：委員會當時是怎麼想的？為什麼會拒絕這篇論文？
秀爾：這不過是對伊森·伯恩斯坦（Ethan Bernstein）和瓦茲拉尼工作的小幅改進，難道我們真的還要在我們的會議中再收一篇這種crazy的量子計算論文嗎？
齊耶勒：crazy，是什麼意思？為什麼這些論文會被貼上crazy的標籤？
秀爾：它們太超前了。完全不切實際。這完全是一個跟現實生活毫無關聯的理論模型，而且沒有人真的理解它。我一直很後悔當時沒有站出來極力推薦說：「我們一定要收下這篇。」但我沒有。顯然我當時應該這麼做。
總之，我們拒絕了那篇論文。後來，我開始思考這篇論文的內容，這篇論文是利用週期性設計了一個能比傳統電腦更快得多的演算法來解決賽蒙問題。我知道週期性對於離散對數問題（Discrete Log Problem）來說非常重要，3而賽蒙演算法也是利用了週期性。所以我開始思考這部分，然後我想出了我覺得可以用在離散對數上的量子傅立葉轉換（Quantum Fourier Transform），接著我解出一個離散對數的一個特殊情況，這其實在一般電腦上也能以多項式時間（Polynomial Time）4完成，我覺得這很有前景。後來，我才終於推進到真正的離散對數問題。
齊耶勒：那時候的量子計算技術已經發展到什麼程度？你在討論那些傳統電腦無法完成的事情時，量子計算進展到哪一個階段，讓你認為這是可行的？
秀爾：我們當時根本不知道這是可行的。在質因數分解演算法提出後的前幾年，大家都完全相信這是做不到的。總之，我終於完成了一個能在多項式時間內解決離散對數的演算法。
一開始，我並沒有告訴太多人關於這個演算法。我跟傑夫·拉加里亞斯（Jeff Lagarias）說了，他發現了一個小錯誤，我後來在論文裡把它修正了。然後我又告訴了我的老闆大衛·約翰遜（David Johnson）以及其他幾位同事，接著在亨利·藍道（Henry Landau）星期二的研討會上演講（1994年四月）。那個週末，我感冒在家，結果接到瓦茲拉尼的電話，他說：「我聽說你知道怎麼用量子電腦做質因數分解。跟我說說吧。」
齊耶勒：他是從哪裡聽到這個消息的？
秀爾：這其實像是傳話遊戲（Telephone Game）。我那場星期二的演講是關於怎麼解離散對數問題，因為那時我還沒想到怎麼分解質因數。所以是參加演講的人告訴了另外一個人，再傳給別人，最後有人跟烏梅什·瓦茲拉尼說我知道怎麼用量子電腦做質因數分解。其實，如果你檢視離散對數和質因數分解，這兩個問題很相似，而且它們也都用於公鑰加密系統（Public Key Crypto Systems）。只要有人找到一個質因數分解的演算法，就會有一個對應的離散對數演算法，反之亦然。所以當我宣布我找到離散對數演算法，並在星期二的演講中說明時，消息就這樣一傳十、十傳百，傳到後來．烏梅什聽說我有一個質因數分解的演算法。
我在電話裡向烏梅什解釋了質因數分解演算法，之後我被邀請在五月初到康乃爾大學（Cornell University）舉辦的演算法數論研討會（Algorithmic Number Theory Symposium）發表演講。我想我大概是在舉辦前一週被邀請，所以是四月底了，然後我就搭飛機過去演講。再後來，聖塔菲研究所（Santa Fe Institute）舉辦了一場量子計算的會議。因為某些原因，我沒辦法去，所以烏梅什就在那裡演講相關內容。再接著，科學記者開始得知這個消息，新聞很快就傳開了。
齊耶勒：以您獨到的角度來看，這件事有什麼令人興奮的地方？為什麼大家這麼關注？這項突破帶來了什麼樣的前景？
秀爾：我想在這之前，計算機科學家都絕對相信擴展的邱奇–圖靈論題（Extended Church–Turing Thesis），這個論題是說，基本上任何電腦能在多項式時間內完成的事情，圖靈機（Turing machine）5也可以在多項式時間內做到。這項結果顯示這個假設未必成立。因此，這真的動搖了計算機科學的根基。當然，這沒有影響任何現在計算機科學界正在進行的實際工作，但正因如此才讓計算機科學家覺得這很有意思。我想物理學家會覺得這很有趣，是因為這代表量子力學可能又有了新的應用。密碼學家則會認為這很重要，因為質因數分解是網路上所有安全的基礎，如果有人能破解它，我們就得緊急應變，全面替換這些加密協定。
哈佛大學於2012年展出一台可運作的圖靈機。（攝影：Rocky Acosta／CC BY 3.0。）
齊耶勒：量子力學有了哪些新的應用？你可以多說明一點嗎？
秀爾：就是計算啊。也就是說，如果你能用量子力學建造一台電腦，能完成傳統電腦做不到的事情。這就是量子力學中一個非常重要的應用。
齊耶勒：那這種興奮感有多少已經變成現實了？
秀爾：我想大家對量子電腦仍然很興奮。我的意思是，目前並沒有那麼多問題是量子電腦能解決而傳統電腦不能解決的。至少，我們目前還沒有發現那麼多，但的確有一些——例如分子、材料設計，還有本身就是量子力學系統的實際計算特性，這些領域一旦在我們能造出更大的機器後，確實會有更好的表現。如果你看看製藥業在模擬分子時耗費了全世界運算能力的多少比例——模擬分子的最大難題是它們必須遵守量子力學的規則——這佔了當今全球使用的運算能力中的相當大一部分。所以，如果能用量子電腦做得更好，那市場潛力就非常巨大。
註釋：
1. 烏梅什·瓦茲拉尼（Umesh Vazirani），現任加州大學柏克萊分校（University of California, Berkeley）電機與計算機科學系羅傑·A·斯特勞赫（Roger A. Strauch）講座教授，他在1993年與當時的學生伊森·伯恩斯坦（Ethan Bernstein）共同發表一篇論文，首次提出了量子複雜度理論（Quantum Complexity Theory）的概念，並奠定了量子計算的數學基礎。他們還提出了一個特定問題，是量子電腦能夠遠比傳統電腦更快解決的。
2. 丹尼爾·賽蒙（Daniel Simon）是亞馬遜雲端運算服務（Amazon Web Services，AWS）的首席資安工程師。1994年，他在蒙特婁大學（University of Montreal）做博士後期間，發表了一篇論文，首次闡述了他現今知名的演算法，這個演算法在量子電腦上的運行速度遠快於傳統電腦。
3. 離散對數（Discrete Logarithms，簡稱 Discrete Logs）是將對數的概念推廣至數學群（Mathematical Groups）上，而非僅限於實數。離散對數問題則是尋找滿足某種指數關係的特定整數。這類問題對傳統電腦來說求解極其耗時，因此被用作許多知名數位加密機制的基礎。
4. 一個演算法若被稱為在多項式時間內運行的，表示其執行時間受到一個與輸入大小有關的某個多項式函數所限制。(註: 一個問題的計算時間m(n)不大於問題大小n的多項式倍數，以數學描述的話，則可說m(n)=O(nK)，K是某個常數)這些演算法通常被認為是高效率的，因為隨著輸入大小增加，其運算時間的增長相對緩慢。這類演算法通常與那些執行時間被指數函數所限制的演算法作對比，後者的效率則低得多。
5. 艾倫·圖靈（Alan Turing）在1936年於理論上構想的一種簡單計算裝置，能夠在一條無限長的紙帶上操作數學符號（這些符號取自於一個有限集）。圖靈機（Turing machine）能夠執行任何一台真實電腦能做到的運算，只是所需時間更長。擴展的邱奇–圖靈論題（extended Church–Turing thesis）本質上主張，如果一個演算法在圖靈機上的運行時間可以用指數函數來描述，那麼在任何其他電腦上的運行時間也會是指數級的。秀爾演算法（Shor's algorithm）似乎推翻了這個論題。
參考資料：
- P. W. Shor, in Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE (1994), 124. https://doi.org/10.1109/SFCS.1994.365700
- P. W. Shor, SIAM J. Comput. 26, 1484 (1997). https://doi.org/10.1137/S0097539795293172
- R. P. Feynman, Int. J. Theor. Phys. 21, 467 (1982). https://doi.org/10.1007/BF02650179
- D. Deutsch, Proc. R. Soc. Lond. A 400, 97 (1985). https://doi.org/10.1098/rspa.1985.0070
- D. Deutsch, R. Jozsa, Proc. R. Soc. Lond. A 439, 553 (1992). https://doi.org/10.1098/rspa.1992.0167
- E. Bernstein, U. Vazirani, in Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, Association for Computing Machinery (1993), 11. https://doi.org/10.1145/167088.167097
本文感謝Physics Today (American Institute of Physics) 同意物理雙月刊進行中文翻譯並授權刊登。原文刊登並收錄於Physics Today, Apr. 2025雜誌內 ( DOI: 10.1063/pt.ifad.hcak )。原文採訪: David Zierler 改編/註譯:Ryan Dahn。中文編譯：劉雨恩，國立台灣大學物理系學生。
Physics Bimonthly (The Physics Society of Taiwan) appreciates Physics Today (American Institute of Physics) authorizing Physics Bimonthly to translate and reprint in Mandarin. The article is contributed by Francis Duck and was published in (Physics Today, Apr. 2025; DOI: 10.1063/pt.ifad.hcak ). The article in Mandarin is translated and edited by Y. Ｅ, Liu, studying at the Department of Physics, National Taiwan University.
