在量子計算發展最初的階段作出重要貢獻的三位先驅科學家（從左至右）：保羅·貝尼奧夫（Paul Benioff）、戴維·多伊齊（David Deutsch）和彼得·秀爾（Peter Shor）

編者按

2021年10月25日，中國科學技術大學潘建偉團隊在物理學期刊《物理評論快報》（Physical Review Letters）上同時報告了兩個關於量子計算的新進展。其中一個，是66位元可程式設計超導量子計算原型機 “祖沖之2.0” 的工作 ，研究人員透過操控其上的56個量子位元，在隨機線路取樣任務上實現了量子計算優越性；另一篇論文是升級版的光量子計算原型機 “九章2.0”：對於高斯玻色取樣問題，“九章2.0” 具有了部分可程式設計的能力，其一分鐘完成的任務，世界上最強大的超級計算機需要花費億年時間。

量子計算在一些特定問題上的巨大優勢，令人期待其在幫助解決一些實際問題上發揮出自己的能量。那麼，量子計算的概念是怎樣提出來的？量子計算的實質是什麼？我們如何證明量子計算理論上的優越性？

以下這篇文章，就以上問題進行了解答，並介紹了在量子計算發展最初的階段作出重要貢獻的三位先驅科學家。

撰文｜揍蘇 江流

責編｜Melody

● 　● 　●

量子計算概念的提出

提及量子計算，人們大抵會想到1981年在麻省理工學院舉辦的第一屆計算中的物理大會（First conference on the Physics of Computation）上，理查德·費曼（Richard Feynman）做出的關於量子計算的演講。但實際上，保羅·貝尼奧夫（Paul Benioff）也參加了那次大會。與費曼討論能否在經典計算機中有效模擬量子系統不同的是，貝尼奧夫主要討論了是否能構造出沒有耗散，且遵循量子力學進行操作和運算的計算機模型。

貝尼奧夫的這次報告主要基於他在1980年發表的學術雜誌文章中的工作。在當時關於計算機的模型形式就有很多討論，大部分的計算機模型都是考慮的開放耗散系統，一個很自然的問題就是，計算機模型是否能透過封閉且能量守恆的系統構造？如果存在，就可以減少很多計算機處理資訊和運算過程中的能量損耗問題。貝尼奧夫在他1980年的論文當中，構造出這樣無能量耗散的計算模型。

在介紹貝尼奧夫的工作之前，首先需要簡單瞭解一下圖靈機。圖靈機是計算機科學中常用的一個理論模型，它的主要組成部分有無限長的紙帶、讀寫頭、一套控制規則和狀態暫存器。紙帶被分隔成了一個接著一個的小格子，每個格子上要麼是0要麼是1或者別的符號。計算過程就是讓機器讀入紙帶，根據當前機器所處的狀態和當前讀寫頭所指的格子上的符號，透過控制規則，更改狀態暫存器的數值。重複以上的過程，直到暫存器中儲存的狀態為某個特殊狀態，觸發圖靈機停止運算。

在貝尼奧夫的工作中，他將圖靈機中的每個組成部分和操作，在他構造出的基於量子系統的計算機模型中找到了對應。在他的構造中，一維自旋晶格構成了圖靈機的紙帶，在晶格中一個固定位置的粒子構成了暫存器，而所有可能的圖靈機的狀態都由所有可能的自旋投影結果構成，而讀寫頭則是由一個沿著晶格移動的無自旋粒子構成。他證明了對於每一個圖靈機和任意數量的問題規模，都存在一個對應的哈密頓量和一類合適的初態，讓圖靈機的每一步的計算對應到純態的演化過程中。需要注意的是，這樣的模型並不是完全沒有能量的損耗，其能量的損耗會出現在諸如檢查計算是否結束、讓圖靈機恢復到初態的過程中。毫無疑問，貝尼奧夫的這些理論工作都給量子計算機的發展奠定了堅實的理論基礎。

圖1 保羅·貝尼奧夫 | 圖源：wikipedia.org

貝尼奧夫於1930年5月1日出生於美國加州的帕薩迪納市。他的父母都是知識分子，父親是美國加州理工學院的教授，母親則從加州大學伯克利分校拿到了碩士學位。貝尼奧夫在1951年在加州大學伯克利分校拿到了植物學的本科學士學位。隨後的兩年，他在Tracerlab主要從事和核化學相關的工作。之後他又回到了加州大學伯克利分校，並於1959年獲得了核化學的博士學位。

1960年，貝尼奧夫進入了以色列的魏茨曼科學研究院做博後。此後他獲得了尼爾斯·玻爾研究所的福特研究員獎金，並在所裡從事了六個月的科研工作。從1961年開始，他開始了他在美國阿貢國家實驗室的漫長工作生涯，並於1995年退休。如今他以退休後的名譽科學家的身份，繼續參與實驗室裡的科研工作。

除此之外，1979年，貝尼奧夫還作為客座教授在以色列的特拉維夫大學教授量子力學基礎課程。同時，他還在1979年和1982年擔任法國國家科學研究中心（CNRS Marseilles）的客座科學家。

貝尼奧夫在2000年獲得了國際量子通訊、計算和測量組織的量子通訊獎，以及日本玉川大學的量子計算和通訊獎。他於2001年成為了美國物理學會（APS）會士。在2002年，他又被授予了芝加哥大學阿貢國家實驗室傑出表現特別獎。2016年，阿貢實驗室舉辦了一次會議，以紀念貝尼奧夫在量子計算領域的傑出貢獻。

“自然可以被有效模擬嗎？”

戴維·多伊齊（David Deutsch）於 1953 年 5 月 18 日出生於以色列海法的一個猶太家庭，在劍橋克萊爾學院進行自然科學的本科學習，在牛津沃爾夫森學院進行理論物理學方向的深造，博士學位論文的研究方向是彎曲時空的量子場論。

圖2 戴維·多伊齊 | 圖源：wikipedia.org

作為量子計算領域的先驅者之一，使多伊齊名聲大噪的是他發表於 1985 年的影響深遠的論文 Quantum theory, the Church–Turing principle and the universal quantum computer。

在這篇開創性的工作中，多伊齊用發人深省的語言風格闡述了物理學視角下 “計算” 的含義。多伊齊對圖靈表述的 Church-Turing 猜想—— “任意 ‘被自然地認為可計算的函式’ 均可被圖靈機計算” 中關於 “自然地” 概念的模糊表述提出了不滿，並給出了物理學意義下的表述—— “任意物理上可有限實現的系統均能被一個通用計算機在有限資源下完美模擬”。多伊齊稱此為 strong form of Church–Turing principle，並指出經典圖靈機不能滿足這一猜想。

基於此，多伊齊給出了他對 “量子圖靈機” 的構想，與其他同時代的量子計算先驅提出的概念相比較，貝尼奧夫在1982年提出的 “量子計算機” 雖按照量子力學執行，本質上卻仍舊是一種經典計算，每一個計算環節的最終結果中並不包含量子干涉、糾纏等量子力學特性，可以被經典圖靈機完美模擬的；費曼構想的 “量子模擬機” 具備了充分的量子力學特性，可以模擬經典圖靈機無法完美模擬的量子物理系統，但並沒有進一步考慮賦予其通用性。

多伊齊指出量子圖靈機可以滿足 strong form of Church–Turing principle，並且討論了量子圖靈機的若干特性，如量子隨機性，量子關聯，量子並行性，量子演算法優勢，並非常富有遠見地指出了量子計算複雜度理論的研究意義，這些概念都極大地指導了後來量子計算科學的研究。

1992 年，多伊齊與 理查德·喬薩（Richard Jozsa）拓展了先前的研究，提出了 Deutsch–Jozsa 演算法，這是最早的量子演算法之一，能夠相對任何可能的確定性經典演算法帶來指數級的加速。多伊齊在量子邏輯閘理論，量子計算網路，量子糾錯方案上均做出過貢獻。此外，多伊齊還曾建議使用糾纏態和貝爾定理進行量子金鑰分配，後來提出了量子密碼學中重要的E91協議的阿圖爾·埃克特（Artur Ekert）正是他的博士生。多伊齊是量子力學的多世界詮釋的支持者，在理解其哲學含義方面開展了大量研究，並撰寫著作將之傳播給公眾，他的作品《現實的結構》曾於1998年入圍 Rhone-Poulenc 科學圖書獎。

自 2012 年以來，多伊齊致力於發展 constructor theory，試圖將計算的量子理論推廣到不僅涵蓋計算，而且涵蓋所有物理過程的 “萬物理論”。

多伊齊於 1998 年獲得物理研究所頒發的狄拉克獎，在2008年被評選為英國皇家學會會士，2017年獲得國際理論物理中心（ICTP）頒發的狄拉克獎章， 2018年獲得了墨子量子獎。

詩人Shor和他的演算法

作為國際奧林匹克數學競賽獎牌得主，彼得·秀爾（Peter Shor）在學生生涯期間就展示了在數學上的驚人天賦。他於1981年獲得了加州理工的數學學士學位，並在此期間參加曾普特南數學競賽獲 “Putnam Fellow”。1985年秀爾在麻省理工學院取得應用數學的博士學位，後於加州大學伯克利分校從事博士後研究。而後秀爾接受了貝爾實驗室的研究職位，並在那裡開發出了大名鼎鼎的Shor演算法。

圖3 彼得·秀爾 | 圖源：nature.com

Shor演算法展示了量子計算可以在質因數分解問題上實現比經典計算機近乎指數級別的加速，這是第一個讓人們相信量子計算機可以在模擬量子物理系統之外得到廣泛應用的演算法，引發了物理學界之外廣泛的討論，開啟了量子計算研究的熱潮。

秀爾對於質因數分解演算法的工作部分建立在計算機科學家丹尼爾·西蒙（Daniel Simon）的工作之上，秀爾曾在1994年4月在貝爾實驗室內部做了一個關於該選題的報告，當時他還只是得到了部分結果，尚未真正解決質因數分解的問題。然而會後訊息不脛而走，在人們口口相傳之下變成了成功進行質因數分解，於是在那個週末，計算機科學家烏梅什·瓦茲拉尼（Umesh Vazirani）就曾給秀爾打電話詢問他是怎麼做到的。神奇而幸運的是，報告結束的五天內，秀爾確實與奔走相告的人們同期開展研究得到了完備的結果，解決了質因數分解的問題。

秀爾的發現一出，立刻帶來了兩個顯著的效應，一方面人們首次看到量子計算機在物理系統模擬之外的應用潛力，極大地促進了量子計算方向的研究；另一方面，對密碼學界的研究造成了不小的衝擊，因為它可以用於破解在網際網路上廣泛使用的公鑰加密方案如RSA協議，給資訊保安提出了新的挑戰。這些都極大地引起了學界和社會對量子計算、量子通訊的重視和投入。

然而，儘管Shor演算法的橫空出世彷彿讓量子計算研究步入快車道，一些同期的頂尖實驗物理學家卻對建造出一臺實際的量子計算機提出了懷疑。

這種懷疑來自於遵循量子力學的任何物理系統的基本特性之一——退相干，任何量子系統只要存在與環境的相互作用，就不可避免地與環境產生量子關聯，這等效於一種噪聲使得處於量子態的系統迅速退化為經典狀態。這一特性部分地解釋了為什麼我們在日常生活中從來不能直接觀察到任何物理系統處於量子態——即使構成我們生活中方方面面事物的微觀粒子均服從於量子力學描述。退一步講，即使實驗物理學家真的能夠建造一個與環境完美隔絕的量子系統，為了實現量子計算的過程，外界仍需要對其進行製備、控制、讀取等過程，在實際建造裝置的意義上來說這無法使系統與環境噪聲真正隔絕。

另一個讓問題變得更加棘手的困難是，在經典計算中噪聲問題可以透過比較直觀的糾錯技術手段實現，相關技術在通訊和經典計算機中已經被證明成功而且獲得了普遍的應用，但對於量子計算機中的量子位元，任何涉及直接觀測的糾錯手段都會導致量子態受到破壞而失去量子計算本身的意義。

面對以上挑戰，秀爾再次挺身而出，構造了第一個量子糾錯碼方案，隨後在其他多位研究者的努力之下，科學家們最終完成了量子容錯計算的理論框架，使得脆弱的量子位元不再與噪聲水火不容。

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

值得一提的是，秀爾也是一位出版過詩集的詩人，在中國科學家成功構建 “九章” 量子計算原型機實現 “量子計算優越性里程碑” 之時，他曾賦詩一首：

Variation on a Theme of von Neumann

馮·諾伊曼主題變奏詩

(Theme: Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.)

（主題：任何考慮用算術手段來產生隨機數的人自然都是有原罪的）

Is it not blasphemous of us to hope

That all of Nature, in her boundless scope,

Can be reduced to voltage on a chip?

大自然無邊無界，

若希望一塊小小晶片就可將她的萬物歸結，

這難道不是一種瀆褻？

If God's great handiwork does not have more computing power

Than do our jury-rigged contraptions, how are

We to believe that it could be His finest workmanship?

若上帝的妙手算力

不及我們粗製濫造的裝置，

我們又如何相信那是上帝之神工？