彼得·肖爾：量子計算的早期歲月（上）_風聞
返朴-返朴官方账号-关注返朴（ID：fanpu2019）,阅读更多！2022-08-30 10:36
譯者按
從1911年的首屆會議開始，索爾維物理學會議就一直對量子物理的發展起着推動作用。
今年5月，第28屆索爾維會議在布魯塞爾召開，會議主題為“量子信息的物理”。量子計算先驅彼得·肖爾出席會議並做了報告。這是肖爾的報告文稿，將收入會議文集中。
蒙索爾維國際物理學化學研究會慷慨允諾，我們得以把這篇文章翻譯刊載出來。
這是文章的上半段，講述了上世紀80、90年代期間，量子計算起步階段學界的一些趣事：比如費曼對是否應該“探討自然成因”前後不同的看法、他在“負概率”一文中未提及作為動機的貝爾定律；肖爾受“西蒙問題”的啓發解決了離散對數問題，而他之後關於離散對數問題的講座被“以訛傳訛”為解決了因數分解問題，以及物理學家知道他這一工作的始末……
撰文 | 彼得·肖爾（美國麻省理工學院應用數學系教授，Shor算法提出者）
翻譯 | 左芬（博士，上海微觀紀元數字科技有限公司）
這個演講最初是為了紀念1981年在恩迪科特大樓舉辦的物理與計算會議的40週年而準備的，所以我覺得我應該從1981年説起。
我那時是加州理工的大四學生，所以當費曼為恩迪科特大樓會議準備主題發言時我已經在那兒了，而那次發言成為了最早仔細審視量子計算的幾次嘗試之一。
我在加州理工的時候什麼消息也沒聽到，事實上我很久以後才讀到費曼的文章。
不過我倒是想提一下我聽他在加州理工的另一個講座，因為那個講座表明他那時正在思考物理學基礎方面的問題。
費曼的報告是關於負概率的。
在報告開頭，他解釋説他一直在思考貝爾定理，因為它説明量子物理不可能是一種局域的、實在的隱變量理論。
這就意味着，量子力學的任何解釋要麼要求非局域性，要麼要求非實在性（這裏局域性意味着信息不能超光速傳播，而實在性意味着你能測量的東西對應着粒子的具體性質）。
費曼解釋説他所做的就是仔細審查證明貝爾定理用到的前提，看裏面是否存在隱藏的假設。
他確實找到了一個——那就是所有概率都必須在0和1之間。
這並不像初聽起來那麼古怪——簡諧振子的維格納函數的行為就恰好這樣，而且費曼也提到了這一點。
他接着展示了他發現的關於負概率的一些結果；報告的這部分內容我記得不是很清楚了。
更早的時候，在1964年的系列講座上，費曼曾説：
“我來告訴你大自然到底是怎樣的。如果你直接接受她表現出來的樣子，你會發現她是迷人的、令人愉快的。如果你能忍住，就不要老是問自己，‘它怎麼會是那樣子的呢？’，因為你會‘深陷泥潭’，進入到一個沒人能逃脱的死衚衕中。沒人知道它為何那樣。”
但是這時，15年後，他卻在探討自然為何會是這樣的一個可能的原由。從這裏你可以看出來費曼並沒有採納他自己的建議。
當然，也許他的建議不是給終身教授，而是給研究生們的；對他們來説，那可能是很好的建議——在量子力學的基礎上得出新的、重大的結果是相當難的，所以它對研究生來説不是一個好的課題。
幾年後的1983年，費曼把報告中的一些想法寫了下來，寫成了一篇叫做“負概率”的文章，但文章在那好多年後才得以發表。
那篇文章有趣的地方在於，它並沒有提到作為動機的貝爾定理。
他的文章首先討論了維格納函數，這些函數確實給出了負值的概率。費曼接着將維格納函數推廣到自旋系統的量子比特。
而費曼在他的報告中講述的原始動機已經被消除量子場論中的無窮大所取代。因此想必費曼的原始想法並不奏效——他沒能利用負概率解決愛因斯坦-波多爾斯基-羅森（EPR）悖論。
我不知道究竟是什麼導致了動機的改變。難道他覺得試圖找出一種更好的方式來理解貝爾定理這個動機太丟人了，因為這牽涉到量子力學的基礎，所以他想出了一個更加體面的？或者是還有別的什麼原因？
我還想説説那個年代另一篇有趣的文章。
1985年，大衞·多伊奇寫了一篇關於量子圖靈機、量子計算以及量子邱奇-圖靈論題的文章。
多伊奇的動機部分源自於量子力學的基礎——他宣稱有了量子計算機，就有可能檢驗量子力學的埃弗裏特（多世界）解釋。
他在文章中説：
對這些性質的直觀説明給埃弗裏特之外的所有量子理論解釋帶來了無法承受的壓力。
我想表明在這一點上我並不認同他，儘管他一直沒有改變觀念。
1985年，費曼寫了他1982年文章的續篇，其中給出瞭如何建造量子計算機的詳盡得多的提議。不過這一提議仍然不太切實可行，因為它在構建初態和躍遷振幅上要求極其高的精度。
作為一個有趣的旁註，我想指出當大衞·多伊奇和理查德·費曼在考慮量子計算時，他們都在思考着量子基礎。我的直覺是這很重要。
如果你認同了大衞·梅爾曼版本的哥本哈根解釋——“閉上嘴去算吧”——那麼你就不會去思考量子的古怪性，這樣你可能也就不會去思考量子古怪性的可能用途。
在加州理工，我學了一些物理課程，但主修數學。
我接着去了麻省理工的應用數學研究生院，在那裏研究數學與計算機科學的交叉部分，並最終在貝爾實驗室找了一份數學和計算機科學方面的工作。
我第一次聽説量子信息是在查理·本內特在貝爾實驗室做的一次報告上，他在報告裏講述了BB84量子密鑰分發協議（譯註：該協議由Bennett與Brassard於1984年提出，故名）。我不記得那是哪一年了，不過肯定是在80年代末期。
我記得我對他的報告非常着迷，還思考過一陣查理提出的一個未解難題。這個難題就是你能否嚴格證明BB84協議是安全的。
在思考過程中，我完全不清楚如何將量子力學表述成某種數學形式，以便嚴格證明該協議是安全的。所以我放棄了那個問題。
説起來有點好笑，到了2000年，在我熟知了量子計算、量子信息和量子糾錯碼之後，約翰·普雷斯基爾和我倒是想到了BB84安全的一種簡單證明方式。
這已經是BB84安全性的第三種證明，不過前兩種證明，分別由邁耶斯和比哈姆等人完成，相當複雜。
我仔細讀了邁耶斯的證明並意識到CSS編碼（譯註：即Calderbank-Shor-Steane編碼，後文有詳細介紹）隱含在其中，而如果使用這些編碼，你可以得到一種簡單得多的證明。
在本內特在貝爾實驗室的報告之後，我再也沒想起過量子計算，直到1992年優曼許·沃茲內尼到貝爾實驗室來做報告，講述他和伊桑·伯恩斯坦關於量子圖靈機的文章。
這篇文章後來發表在1993年6月的計算理論研討會（STOC）上，最負盛名的兩個理論計算機科學會議之一。
我對那個報告極為着迷，而且我可能比其他計算機科學家理解得都深一些，因為我在大學時學過一些物理。
伯恩斯坦和沃茲內尼給出了一個精心設計的問題使得量子計算機看起來可以做得更好，但我對那個問題不是太滿意。
於是我開始思考是否可以用量子計算機更有效地解決一個實際問題。
我並沒能真正取得進展，直到我讀到丹·西蒙的文章。
他在文章裏用量子計算機算法解決了一個人為問題，“西蒙問題”，並且比最好的經典算法還要好得多。
我會讀到這篇文章是因為我在1994年STOC會議的項目委員會里，而委員會拒收了那篇文章（儘管我已爭取了）。
我聽説丹·西蒙的出發點是想證明數字計算機不再比量子計算機強大，但他最終找到一個問題顯示了相反的結果。
西蒙用到了一個二進制矢量空間上的傅里葉變換來找出該矢量空間上一個函數的週期。
我知道傅里葉變換對尋找週期有幫助，而且我知道離散對數問題跟週期性有關，所以我開始尋求在量子計算機上解決離散對數問題的方法。
離散對數問題是一個有名的難題，如果你解決了它，就可以破解一些公鑰加密系統。
西蒙算法和離散對數問題中的週期尋找的差異在於，對於西蒙問題，你需要在n-維超立方體上找到一個函數的週期，而對於離散對數問題，你需要在P-1×P-1環面上尋找週期。
如何從一個高維超立方體上的週期尋找轉到一個大的環面上的週期尋找，這是完全不清楚的。對這些你需要不同的量子傅里葉變換。
我最先做到的是在一種特殊情況下解決了離散對數問題，而這種情況已經被經典計算機在多項式時間內解決了。
儘管這並沒有真正給出新東西，但算法跟經典算法是完全不同的，所以給了我很大的鼓舞，讓我去繼續努力並最終解決了一般情況。
我從特殊情況到一般情況的頓悟就是認識到對於一般情況，我並不需要採用模P-1的傅里葉變換；我只需要模一個比P-1稍大一點的數就可以了。
我並沒有告訴任何人我在致力於離散對數問題，因為我覺得實在沒啥把握。
在我1994年4月解決它之後，我告訴了一些認識和合作過的人，包括我的老闆大衞·約翰遜，以及貝爾實驗室的一個同事，傑夫·拉加里亞斯，他驗證了我的算法是對的。事實上，不完全對——傑夫找出了一個小錯誤，很容易就改好了。
之後，大衞·約翰遜建議我在亨利·朗道研討班上就此做一個報告。
亨利·朗道研討班每週二舉行，並且聽眾極其活躍——他們不斷打斷報告人提問，所以有點嚇人。我記得有一次，報告人就沒能翻到第二張幻燈片。
不管怎樣，我就如何在量子計算機上解決離散對數做了一個報告，並且還算順利。
那周晚些時候，我把因數分解問題也解決了。離散對數和因數分解之間有着奇怪的聯繫。並沒有一個公式告訴你，如何將針對其中一個問題的算法應用到另一個上面去。
但是，每次有人發現其中一個問題的改進算法，人們都相當快地想出了另一個問題的相似解法。
這一次也不例外——知道了離散對數算法，很容易就找到了因數分解算法。
那個週末，我得了重感冒在家，優曼許·沃茲內尼打電話給我説“我聽説你可以用量子計算機有效分解因數”。
這有點出人意料，原因有很多。首先，這表明我週二報告的流言已經傳播到優曼許那裏了。其次，報告是關於離散對數的，但等流言到達優曼許那裏時，它們已經變成了因數分解（這有點像電話遊戲，也叫傳話遊戲，其中一個小道消息從一個玩家傳到下一個，並且沿途改變）。
不過幸運的是，我同時也解決了因數分解問題，所以可以向優曼許解釋因數分解算法，而不用告訴他信息有誤。
在那之後，消息像野火一樣蔓延開去。
四月末哥倫比亞大學有一個（關於理論計算機科學的）理論日。查理·本內特、約翰·斯莫林和我約好在那會面，然後我向他們解釋了這個算法。
如果我記得沒錯，本內特給我解釋了他新近的隱形傳態協議，以及新近的伊利澤-威德曼炸彈測試協議。很明顯量子信息這一主題的時代已然來臨。
我被緊急邀請去五月初在康奈爾舉辦的算法數論討論會上做了專題講座。
五月中旬在聖塔菲有個關於量子力學的會議；我去不了，不過優曼許在會上展示了我的算法。阿圖爾·埃克特和大衞·喬薩寫了一篇文章向物理學家們解釋我的算法，並且阿圖爾·埃克特在那年八月科羅拉多州博爾德舉辦的原子物理會議上就此做了報告。
這就是許多物理學家如何得知它的，正如你在這次會議上從大衞·瓦恩蘭的報告裏聽説的那樣。
在此期間，我收到了許多雜誌的採訪請求，以及許多人索要文章副本的請求。（我在文章徹底完成之前就開始寄出去，但這可能是個失誤，因為在我糾正了文章中的錯誤之後很久，還有人問關於早期初稿中錯誤的問題。）
那年八月，美國國家標準技術研究所（NIST）在馬里蘭州蓋瑟斯堡組織了一次會議，是專為因數分解算法的發現而組織的，並且聚焦在量子計算上。
十月，在意大利都靈有一個量子計算的研討會，那其實是一個系列會議裏的第二或第三屆。這個會最初只有幾個人參加，之後與會人數逐年增長，直到超出了瓜裏諾莊園酒店的會議設施容量，於是被終止了。
94年德克薩斯的物理與計算會議是1981年恩迪科特大樓會議的後續（一共舉辦了三屆後續會議，分別在92年、94年和96年），我在那做了報告。
緊接着幾天後，我在新墨西哥聖塔菲的計算機科學基礎（FOCS）會議上講述了我的文章，並且在會議文集裏發表了。
原文鏈接：
The Early Days of Quantum Computation，Peter W. Shor, arxiv:2208.09964, https://arxiv.org/abs/2208.09964
本文經授權轉載自微信公眾號“中國信息協會量子信息分會”。
特 別 提 示
1. 進入『返樸』微信公眾號底部菜單“精品專欄“，可查閲不同主題系列科普文章。
2. 『返樸』提供按月檢索文章功能。關注公眾號，回覆四位數組成的年份+月份，如“1903”，可獲取2019年3月的文章索引，以此類推。