姚期智到底有多牛？細數中國唯一圖靈獎得主在三大領域的學術造詣

提起姚期智，大部分人的第一反應會想到圖靈獎。如今作為國內第一名也是唯一一名圖靈獎獲得者，姚期智自 2011 年起擔任清華交叉資訊研究院院長，為培養國內優秀人才做出了巨大貢獻。今天，雷鋒網AI科技評論就和大家一起細數姚期智院士的學術造詣，「數風流人物，還看今朝」。

姚期智這個名字總與「圖靈獎」掛鉤，而如果你瞭解他的學術造詣，也會知道這一獎項也是實至名歸。

生於上海，遷居香港，又移民臺灣，姚期智在臺灣大學完成了物理學學士學位後，赴哈佛大學就讀物理學碩士及博士，師從 1979 年諾貝爾物理學獲得者 Sheldon Glashow。隨後，他只花了兩年時間就拿下了伊利諾大學的電腦科學博士學位，師從劉炯朗。

自1975年畢業之後，姚期智分別在 MIT、斯坦福、加州大學伯克利分校等世界頂級名校從事教學及研究。他的主要貢獻主要包括了三大領域，也大致可以分為三大階段：

第一階段：演算法理論創新

早在博士就讀期間，姚期智提出了隨機化演算法複雜度的論證，而如今已經成為研究者無人不知的重要工具。

在 1977 年的論文中，姚期智提出了 Yao's min-max principle，這一原理成為了推理隨即演算法與複雜度的基本技術，也已經應用於屬性測試與學習理論等領域。

在 1978 年，姚期智對資料結構的創新做出了根本性的創新。在《Should tables be sorted?》論文中，他介紹了一種名為 cell-probe model 的資料結構抽象模型，目前已經被廣泛應用於創建演算法的下限證明。

在這一階段，姚期智最重要的貢獻在於提出了理論電腦科學的重要次領域：通訊複雜性和偽亂數產生計算理論。

第二階段：奠定密碼學基礎

1982 年，姚期智從加州大學伯克利分校的電腦科學系重回斯坦福大學任教，研究的重心從原來的演算法理論逐漸轉移到密碼學、電腦安全及隨機計算領域。而其中最為出名的一個問題，當數姚氏百萬富翁問題。這到底是何方難題，且聽雷鋒網 AI 科技評論道來。

話說西晉時期，石崇與王愷爭豪。壓倒王愷的最後一根稻草，不是「並窮綺麗，以飾輿服」，而是他視若珍寶的二尺珊瑚樹卻被石崇用鐵如意擊碎，更碾壓的是，石崇還拿出了「條幹絕世」的珊瑚樹，讓王愷惘然自失。

一葉知秋，只從小小的珊瑚樹，就可一窺雙方家底深淺。然而如果難度再升一級，連珊瑚樹也不讓比，土豪們要如何炫富才能不著痕跡地一比高下？

而在千年之後的 20 世紀，姚期智也以「比壕」為主題，提出了馳名的「姚氏百萬富翁問題」：兩個百萬富翁如何在不向對方透露任何身家資訊的前提下比較各自的財富？

這一問題後來也衍生為安全多方計算問題的起源：如何在一個互不新任的多使用者系統中，各使用者能通過網路協同完成計算任務，但又能保證各自資料的安全性？

安全多方計算問題一經提出，吸引了不少學者研究，後來也成為了密碼學協定研究的基礎問題之一，目前已經被廣泛應用於解決資料採擷、資料庫查詢、科學計算等許多計算領域的問題。而姚期智自然也成為了現代密碼學基礎的奠基人。在 1982 年，姚期智給出了一種解決方案：通過生成亂數，加上公開金鑰與私有金鑰的加密再進行比較，避免了實數域的有序性和加減的可逆性帶來多餘資訊的暴露。

而除了姚氏百萬富翁問題外，姚期智在加密和安全計算方面也做出了開創性的貢獻，「Dolev-Yao 模型」已經成為了大多數符號安全工作的起點，而《陷門函數的理論和應用》（Theory and applications of trapdoor functions）及《安全計算的協定》（Protocols for secure computations）等著作也成為了安全計算領域的重要著作。此外，還有去隨機化領域的基本技術 XOR-lemma 及解決安全多方計算的亂碼電路技術，也同樣由姚期智提出。

第三階段：量子計算領域

在 20 世紀 90 年代後，在普林斯頓大學 William and Edna Macaleer 工程與應用科學任教期間，姚期智開始著手開展量子計算、通信及資訊理論方面的工作。在 1993 年的論文《Quantum circuit complexity》中，姚期智就將通信封複雜度擴展到量子計算領域，完成了量子電腦的理論基礎。在線路複雜性、計算幾何、資料結構及量子計算領域，姚教授提出了不少開放性問題，並開拓了不少富有建設性的創見。

在 1995 年，姚期智提出了分散式量子計算模式，後來成為了分散式量子演算法和量子通訊協定安全性的基礎。

憑藉姚期智在計算理論的基本貢獻，包括基於複雜性的偽亂數產生，密碼學和通信複雜性的理論，美國電腦協會 ACM 於 2000 年授予其圖靈獎及百萬美元獎金，以表彰姚期智在電腦界做出的巨大貢獻。

著作等身，名利雙收，如果一直在美國高校繼續教書育人，完善理論創新，姚期智誠然會是眾多華人學者中最為頂尖的一個，這樣的人生軌跡也算得上圓滿。但他在 57 歲時做出了一個決定：回到中國擔任清華教授。

「落葉歸根」，助力演算法理論及交叉學科發展

在 2004 年，姚期智回國擔任清華大學高等研究中心教授，原本計畫的是構建培養博士生的機制，並打造一支研究團隊。但隨即姚教授意識到，國內傳統比較重視電腦工程方面的學習，而為了更好地提升學生的國際視野，姚期智開設了國內首門電腦理論課程，從根本上夯實了電腦本科課程的理論基礎。

隔年，姚期智開設了鼎鼎有名的「姚班」，桃李滿天下。曠視科技三巨頭、中國大學生電腦程式設計第一人「樓教主」、鄒昊等人都是「姚班」的得意門生，具體介紹可查看 AI 科技評論撰寫的《中國唯一的圖靈獎獲得者姚期智，在清華開設的「姚班」有哪些 AI 名徒？》。

據不完全統計，僅截至 2014 年，電腦科學實驗班學生本科期間共發表論文 110 篇，其中以學生為論文通訊作者或主要完成人的共 84 篇，有些文章甚至達到了博士畢業的水準。而截至 2016 年 12 月，姚班學生為論文通訊作者或主要完成人的已發表論文達 121 篇，並有 42 位優秀姚班學生被選派參加國際會議並作論文宣講。

2010 年 12 月，姚期智牽頭成立清華大學交叉資訊研究院並擔任院長，這是全國首個針對電腦科學與技術和物理學兩大學科方向的交叉建設學院，而這兩個領域正是姚期智在過去 20 年的科研歷程中所潛心鑽研的。

如果一定要總結姚教授回國後的最大貢獻，非百年樹人莫屬。不論是豐富了演算法理論的研究多樣性，或是帶動了電腦科學與物理學之間的聯繫，姚教授對國內頂尖學術人才的培育功不可沒。而近日雷鋒網也曾報導姚期智已放棄外國國籍，從中國科學院外籍院士轉為中國科學院院士，這一消息也坐實了姚教授將繼續留在國內繼續科研及教育事業的想法，相信在未來，會有更多的姚班學生在工業界與學術界發光發熱。