姚期智2021年京都獎演講全文：計算機科學之旅

京都獎是由稻盛和夫創辦的國際獎項，被認爲是亞洲諾貝爾獎。

每年，該獎項會頒發給爲科學進步、文明發展以及人類精神的豐富和提升做出卓越貢獻的個人。京都獎分爲先進技術、基礎科學、藝術與哲學三個類別，每個類別包括四個領域，共計 12 個領域。三個類別各頒發一個獎項，每個類別的獎金爲 1 億日元。

今年早些時候，清華大學交叉信息研究院院長姚期智獲得了 2021 年京都獎，以表彰他對計算和通信新理論及其安全基礎理論做出了開創性貢獻。

姚期智開創了計算機科學的新趨勢，通過建立具有創新性的計算和通信基礎理論，爲各個領域的前沿研究做出了巨大貢獻，特別是在安全、安全計算和量子計算方面。他的成就持續影響着當前的現實世界問題，例如安全、安全計算和大數據處理。

姚期智和其他兩位 2021 年京都獎得主在 2021 年京都獎特別網站上都有相關介紹，包括作品、簡介和三分鐘的介紹視頻。今年的京都獎還授予了洛克菲勒大學生物化學和分子生物學領域的教授 Robert G。 Roeder（基礎科學類）；巴黎政治學院名譽教授 Bruno Latou（藝術與哲學類）。

近日， 2021 年京都獎官網發佈了姚期智爲本次獎項進行的英文報告——“計算機科學之旅”。出於科學傳播的目的，《學術頭條》將該報告整理成文，以饗讀者。

在這份報告中，姚期智分享了他年輕時和學術生活中的故事，以及他從物理學和計算機科學的成就中所獲得的見解。回顧了自己的研究生涯，他說道：“在科學中，範式是尋求真理。在這個過程中，我們有時會發現可以昇華人類精神的樣式和美感。它也追求創新以改善人類境況，讓我們爲未來人類需要面對的挑戰做好準備。”

以下爲報告全文：

女士們，先生們，我很高興來到這裏。首先我要說，獲得京都獎是一種莫大的榮幸。瞭解了歷屆獲獎者和他們的輝煌成就後，我爲自己被認爲值得與他們齊名而深感謙卑，也很高興和榮幸在這裏發言。

今天，我想談談我的成長經歷，如何進入計算機科學領域，以及一路走來的旅程。

更詳細地，我將從我的背景開始，講一講我小時候對物理學的癡迷，這後來促成了我選擇了第一個職業，然後，我會講到我是如何偶然轉換領域併成爲一名計算機科學家的。之後我會簡單介紹我的研究工作、我所思考的問題以及它們爲什麼有趣。結束之前，我還要向幾位對我的生活和工作產生重大影響的人致敬。

1946 年，我出生在中國上海。不久後，我的家人搬到了香港，然後又搬到了臺灣。我在一個幸福的中產階級家庭長大，有慈愛的雙親和兩個非常親密的兄弟/姐妹。

我從小深受中國傳統價值觀薰陶，特別是對文化和學習非常重視。令我和我父母欣慰的是，我是一名優秀的學生，學生時期一直是名列前茅。

我記得我小時候喜歡數學、科學和歷史。

對歷史人物着迷，是因爲他們表現出不同尋常的勇敢和智慧。像伽利略和牛頓這樣的科學家，他們也是我心目中的英雄，因爲他們的才華以及爲自己的信仰挺身而出的勇氣，讓我大爲震撼。我夢想有一天自己也會成爲這樣的人。

高中三年級，我偶然發現了亞瑟·愛丁頓爵士關於相對論的筆記副本，其中給出了相對論最生動、最簡單的推導。

大致如下：實驗中，我們已經知道光具有恆定的速度。從這一事實，我們可以巧妙地推導出我們熟悉的時間概念不可能是一個絕對普遍的概念。而長期以來，這一點是每個人都認爲理所當然的事情。

這個論點給我留下了深刻的印象。我發現，物理學可以像偵探故事一樣吸引人，而且比“福爾摩斯”中任何聰明的情節都更具想象力。這令我深受鼓舞。於是在1963年，我在大學選擇了主修物理。

不久之後，理查德·費曼的物理學講義發表了。

傳說加州理工學院想從根本上重組他們的物理學大一課程，費曼同意這樣做，條件是他只教一次。由此誕生了傳奇的三卷本物理學講義《費曼物理學講義》。

這個系列講義讓我大開眼界。難以解釋的高級概念，結果其證明只用初級數學就可以解釋和推導出來。這真是令人印象深刻，讓我看到了物理學的深度和美妙。

事實上，這是我第一次覺得自己真正理解了量子力學的原理。30 年後，當我開始從事量子計算領域的工作時，費曼對量子現象的解釋在我看來仍然是最有啓發性和最有用的解釋。

這讓我堅定下來，決定在大學畢業後繼續在物理學深造。1967年，我大學畢業後服了一年兵役，之後前往哈佛大學攻讀物理學研究生。1972 年，我在 Sheldon Glashow 教授的指導下獲得了物理學博士學位。

最終我成爲了真正的物理學家，但這並沒有持續多久。1973 年，當時我在麻省理工學院攻讀博士學位的妻子 Frances 向我介紹了“算法”。

算法這個詞今天已頻繁出現在日常生活中，但在當時，對大多數人來說，這是一個非常陌生的詞彙。當時，我接觸到高德納教授編寫的《計算機程序設計藝術》的早期草稿。這是一本很有名的關於算法的書，一個多麼了不起的傑作，它介紹了一門引人入勝的新科學。

閱讀後，我開始不斷思考書中提出的研究問題，深陷其中而無法自拔，以至於我很快就辭去了物理學博士後的工作，轉而全職攻讀計算機科學研究生。

我記得我母親當時很擔心我，因爲我似乎放棄了這麼多年的物理工作，但我的妻子非常支持我。所以我成爲了伊利諾伊大學的計算機科學研究生。非常感謝 CL Liu 教授願意接受我。

接下來，我將講述我的工作。最初，我專注於解決算法中現有的開放問題，例如最小生成樹、B 樹等。但畢業後不久，我開始對開發計算機科學的新框架和新理論產生興趣。

幾十年來，我有機會在幾所一流大學工作。我在伯克利、斯坦福度過了 10 年，隨後在普林斯頓度過了 18 年。2004 年，我加入了清華大學，直至今日。

在每個時期，我都在做一些不同的事情。很有趣的是，我在不同時期關注的主題，它們與時代的變化和計算機科學作爲一門學科的發展，以及身處的大學環境都有很大關係。

接下來，我想要介紹三個主題，極大極小算法（min max complexity），通信複雜度（communication complexity），以及密碼學和 MPC。

我發現做研究最好的方法是提出深刻、大膽和關鍵性的問題。如果你能提出好問題，那麼就一定會做好研究，得出對學術界來說實用且有重大意義的結論。現在我將對每個主題的主要問題及其重要性進行討論。

第一個是 1977 年提出的極大極小算法問題。它在我心中有很特殊的位置，因爲這是我第一次提出了自己的研究問題，並找到了很好的解決方法。我們知道，算法本質上和食譜很像。例如在烹飪中，食譜會告訴你每步的步驟，例如放 3 盎司鹽或幾克肉。

20 世紀 70 年代中期，一種新的算法引起了人們的注意，即“隨機化算法”（Randomized algorithm）。這種新算法結合了隨機移動（stochastic moves）。如果用烹飪來比喻的話就是，不明確告訴你有放兩勺鹽的步驟，而是讓你用扔硬幣決定是放兩勺鹽，還是放一杯紅酒。

因此，對於傳統的思維方式來說，這看起來是一種瘋狂的做事方式。但在 20世紀70年代，人們已經證明以這種方式執行算法是有優勢的，在某些情況下，它們會產生一些令人驚歎的結果。但人們還無法理解這些算法的侷限性。

因此，這讓我產生了一個問題。到底哪算法個更好？是當時剛剛提出的隨機化方法，還是用傳統的方法觀察數據分佈，並在執行過程中調整呢？

一旦用這種方式提出了這個問題，那麼就出現了一種令人驚喜的聯繫，讓人們可以對隨機化算法有了很多的瞭解。

當把隨機化算法與傳統分佈方法進行比較時，可以將其視爲隨機化算法和數據之間的博弈。算法（可以根據數據）選擇如何隨機移動，而數據（對手）可以選擇分佈方式，從而使算法的運行變得更加困難。在博弈論極大極小原理（馮·紐曼）的作用下下這兩種方法恰好達到了它們的極限。這個聯繫給出了我們想要證明的定理，也就是說事實上這兩種方法是相同的。這爲理解隨機化算法提供了新途徑。在現在，這種在當時還算新穎的算法已經成爲許多密碼技術和人工智能算法的默認模式。

人們想了解隨機化算法的侷限性是有原因的。因此，在 40 多年的時間裏，我發現的算法仍然被許多研究人員用來來解決他們的問題。第二個主題是我在 1979 年提出的通信複雜性。

讓我先解釋一下這個數學問題，愛麗絲和鮑勃是兩個在不同地點的人，他們各自持有一條 n 個比特的數據，比如 x 和 y。我們想要解決的問題是，假設它們想要聯合計算某個量 f，它們之間需要通信多少比特，這就是這個函數的通信複雜度。

當然，這取決於你在計算什麼函數，例如，要計算這兩個整數的和是奇數還是偶數只需要兩個比特的通信。每個人只需告訴對方它是偶數還是奇數，然後他們就可以知道答案了。

另一方面，如果你想計算 x 是否大於 y，那麼它將需要 n 比特。你需要把整個字符串從一個人發送給另一個人才能解決這個問題。更深一層的是，你必須意識到並證明，沒有比這種方式來解決這個問題更好的方法了。一般來說，這是一個相當困難的問題。如果我給你一個關於F的計算複雜性，那需要相當深入的數學分析才能完成。

考慮通信複雜度的原因是，計算模式在 20 世紀 70 年代末發生了很明顯的變化。從之前大家都熟悉的大型計算機，逐漸轉向我們現在熟悉的計算機網絡。人們對以分佈式方式解決問題感興趣，許多人願意協作解決問題。

因此，這意味着我們必須把過去的計算模型調整爲網絡模型。在這個新的世界裏，通信成本通常是很高的，因爲我們必須移動數據。因此，我剛剛向你們的介紹的通信複雜度的概念就是爲了模擬和反映這種變化。

自從該模型被提出和分析以來，通信複雜性在從芯片設計到數據流的各個領域都得到了廣泛的應用。我要討論的最後一個話題是關於密碼學和 MPC。

1982 年，我寫了三篇論文，這些論文對現代密碼學做出了重大貢獻。這三篇論文涉及 Dolev-Yao 威脅模型、僞隨機數生成算法（pseudo random number generation）和安全多方計算（MPC）。今天我只談最後一個問題。

MPC 是一個加密概念，使我們可以對加密數據進行計算。如果您使用 MPC，就有可能讓多個數據庫在不泄露它們自己的數據的情況下進行聯合計算。

也就是說，我們可以在看不到數據的情況下共享數據。讓我用一個例子來解釋一下這一點。我將引用在論文中提到的著名的億萬富翁的例子。

兩個百萬富翁，愛麗絲和鮑勃，他們希望在不透露任何數據信息的情況下知道誰更有錢。所以愛麗絲有 X 百萬，鮑勃有 Y 百萬。所以數學問題是，他們想要彼此交流來知道 X 是否小於 Y。問題是，是否有可能進行一次對話，讓雙方在不知道對方數據的情況下又知道誰更富有呢？

直覺上來說你會認爲這是不可能的。我怎樣才能在不透露任何一方任何信息的情況下找出誰更富有呢？如果你想幾分鐘你就會意識到，如果採用 1982 年的信息安全定義，也就是香農的信息論（ Shannon‘s information theory），那確實是不可能的，你可以證明在那個模型下是不可能的。

但我認爲，需求是所有發明之母。如果真的有需要的話你肯定會想盡一切辦法。所以，如果你跳出框框去思考，事實證明這是可能的。說到跳出框框，我們的意思是需要丟棄香農在這種情況下規定的非常死板的條條框框，然後把艾倫·圖靈納入其中，我不會對此說太多。但事實證明，如果你把安全定義放寬一些，讓它變成一個務實且足夠好的標準，那麼這個問題事實上是有解的。具體地說，我用“亂碼電路” （garble circuit）實現瞭解決方案。

在過去近 40 年的發展中，它在硬件和算法方面取得了進步，現在幾乎是可行的。而這方面的研究工作也很多，準備在金融科技、數據交易、藥物研發等方面開展工作。

目前我還有一些其他的研究課題，就不一一詳述了。我的課題包括：革命性、有望實現指數級增長的量子計算技術；可以用博弈論來解決經濟問題的拍賣理論；人工智能，這項技術見證了 AlphaGo 等機器學習算法取得的令人難以置信的壯舉，但成功的原因仍然是個謎。

所有這些都是非常有趣的新領域，而且還在持續發展中。如你所見，我研究過很多不同的課題。這些豐富多彩的課題，實際上不僅反映了我個人的喜好，也反映了半個世紀以來信息科學的蓬勃發展，以及我們今天所看到的日益增長的跨學科聯繫。

最後，我想對我人生中遇到的人說幾句話。

在這些年裏，作爲一名計算機科學家，我有幸遇到了許多才華橫溢的人。我非常幸運地遇到了兩位給我巨大靈感的導師，Glashow 教授和 Knuth 教授。