Andrew Yao（姚期智）：通信复杂性与量子计算的开拓者，首位华人图灵奖得主，从普林斯顿到清华的育人之路

图灵奖第三十五届（2000）| Andrew Yao（姚期智）：通信复杂性与量子计算的开拓者，首位华人图灵奖得主，从普林斯顿到清华的育人之路

一句话概括：他创立了通信复杂性理论，奠定了量子计算的理论基础，开创了安全多方计算，是首位获得图灵奖的华人科学家，放弃普林斯顿终身教职回国创建清华”姚班”，培养了一代又一代顶尖计算机人才。

🏆 获奖简介

Andrew Chi-Chih Yao（姚期智，1946-）是美籍华裔计算机科学家，量子计算和密码学理论家，中国科学院院士。

出生时间：1946年12月24日
出生地点：中国上海
主要成就：通信复杂性理论创始人，安全多方计算开创者，量子计算复杂性理论奠基人
获奖年份：2000年
获奖原因：在计算理论方面的贡献，包括伪随机数生成、密码学和通信复杂性

为什么他是第三十五位？ 1970-1980年代，当计算机科学家们关注单机算法时，姚期智提出了一个全新的问题：当计算分布在多台机器上时，它们之间需要交换多少信息？这个看似简单的问题开创了”通信复杂性”这一全新领域，成为理解分布式计算、大数据处理、区块链的理论基础。他提出的”百万富翁问题”更是开创了安全多方计算，让隐私保护的协作成为可能——今天的联邦学习、区块链零知识证明都源自这一思想。在量子计算刚刚起步时，姚期智建立了量子电路模型，为量子算法提供了标准框架。2000年，他成为首位获得图灵奖的华人，这不仅是个人荣誉，更是华人在计算机科学领域的历史性突破。更令人敬佩的是，2004年他放弃普林斯顿终身教授职位回国，创办清华”姚班”，培养出楼天城、胡渊鸣等世界级人才，让中国计算机教育走向世界前沿。

🚀 重大贡献详解

1. 通信复杂性理论：分布式计算的理论基石

历史背景（1970年代末）：

传统计算复杂性理论研究的是：

时间复杂性：算法需要多少步？
空间复杂性：算法需要多少内存？

但随着分布式系统的出现，一个新问题浮现：

通信复杂性：多台机器协作时，需要交换多少信息？

Yao的开创性工作（1979年论文）：

1.1 Alice和Bob模型

问题设定：

Alice有输入 x ∈ {0,1}^n
Bob有输入 y ∈ {0,1}^n
目标：共同计算函数 f(x,y)
约束：最小化通信位数

例子：判断相等

任务：判断 x = y 是否成立？

朴素方法：
Alice发送整个x给Bob → n位通信
Bob本地比较 → 返回1位结果
总通信：n+1位

Yao的问题：能否更少？

Yao的证明技术：

分割引理（Partition Lemma）
信息论下界
对抗性输入

结论：对于某些函数（如相等判断），任何协议都需要Ω(n)位通信，朴素方法已经最优！

1.2 通信复杂性的数学框架

确定性协议：

协议树（Protocol Tree）：
- 每个节点：一方发送一位
- 叶子节点：输出结果

通信复杂性 = 树的深度

随机化协议：

允许抛硬币
只需要大概率正确（如99%）
有时能显著减少通信

例子：相等判断的随机化协议

Alice选择随机质数p
Alice计算 a = x mod p，发送 (p, a) 给Bob
Bob计算 b = y mod p
Bob判断：a = b 则"可能相等"，否则"一定不等"

通信量：O(log n)位  （远小于确定性的Ω(n)位！）
错误率：可以任意小（多选几个质数）

1.3 经典结果与应用

不相交性问题（Disjointness）：

Alice有集合 A ⊆ {1,...,n}
Bob有集合 B ⊆ {1,...,n}
问题：A ∩ B = ∅ 吗？

Yao证明：任何确定性协议需要 Ω(n) 位通信
后续研究：即使随机化，也需要 Ω(n) 位

意义：这个简单问题的难度，解释了为什么分布式系统中某些任务本质上就是昂贵的。

对分布式算法的影响：

MapReduce的极限：理解哪些任务适合分布式
数据库查询：join操作的通信代价
传感器网络：节点间通信的优化

对数据流算法的影响：

流计算模型：单次扫描数据的限制
近似算法：通过放松精度要求降低复杂性
Sketch算法：用小空间存储大数据的摘要

2. 百万富翁问题与安全多方计算

1982年论文：Yao’s Millionaires’ Problem

2.1 问题描述

场景：

Alice的财富：a 百万美元
Bob的财富：b 百万美元

目标：他们想知道 a > b 还是 a ≤ b
约束：都不想透露具体的 a 和 b

形式化：

输入隐私：对方学不到自己的输入
输出正确性：结果必须正确
无需可信第三方：只有Alice和Bob参与

为什么重要？ 这个看似简单的问题，抽象了无数现实场景：

竞标：谁出价最高，但不透露具体金额
医疗数据分析：合作研究但不共享病人信息
机器学习：联合训练但不共享数据

2.2 Yao的解决方案：混淆电路（Garbled Circuit）

核心思想：

步骤1：将问题转化为布尔电路

比较 a > b 可以用逻辑门电路实现：
输入：a的二进制位，b的二进制位
电路：由AND、OR、NOT门组成
输出：1位（1表示a>b，0表示a≤b）

步骤2：Alice”混淆”电路

对于每根电线，Alice生成两个随机密钥：
- k_0 代表"0"
- k_1 代表"1"

对于每个门，Alice创建"加密真值表"：
例如AND门，输入线A、B，输出线C
  Enc_{k_A0, k_B0}(k_C0)  // 0 AND 0 = 0
  Enc_{k_A0, k_B1}(k_C0)  // 0 AND 1 = 0
  Enc_{k_A1, k_B0}(k_C0)  // 1 AND 0 = 0
  Enc_{k_A1, k_B1}(k_C1)  // 1 AND 1 = 1
打乱顺序，Bob看不出哪行对应哪个输入

步骤3：Alice发送混淆电路给Bob

Bob收到：
- 所有门的加密真值表
- Alice输入对应的密钥（如a=5，Alice发送a的每一位对应的密钥）

步骤4：不经意传输（Oblivious Transfer）

Bob需要获得自己输入b对应的密钥，但不能让Alice知道b

协议：
- Bob想要第b位对应的密钥
- Alice有两个密钥 k_0 和 k_1
- 不经意传输让Bob得到 k_b，但Alice不知道Bob选了哪个

步骤5：Bob评估电路

Bob有了所有输入线的密钥，逐门计算：
- 用手上的密钥解密对应的真值表条目
- 得到输出线的密钥
- 最终得到结果对应的密钥

Alice告诉Bob：输出密钥与结果的对应关系
Bob得知结果，但不知道a的具体值

安全性保证：

Alice的隐私：Bob只能解密正确输入对应的路径，看不到其他可能性
Bob的隐私：通过不经意传输，Alice不知道Bob的输入
结果正确性：密码学保证Bob无法篡改

2.3 影响与应用

理论影响：

证明了任何可计算函数都可以安全地多方计算（在密码学假设下）
开创了**MPC（Multi-Party Computation）**整个领域

现代应用：

联邦学习（Federated Learning）：

场景：多家医院联合训练AI模型
挑战：不能共享病人数据（隐私法规）
MPC解法：
- 各医院本地计算梯度
- 安全聚合（不泄露各家数据）
- 更新全局模型

区块链与零知识证明：

场景：证明"我知道某个秘密"但不透露秘密本身
应用：
- Zcash等隐私币
- 身份验证但不泄露身份
- 合规性证明但不泄露数据

隐私保护的数据分析：

场景：政府统计、广告分析
挑战：保护个人隐私
MPC解法：差分隐私 + 安全计算

实际系统：

Google的Privacy Sandbox：广告归因但保护用户隐私
金融风控：多银行协作但不共享客户数据
基因数据研究：联合分析但保护个人基因信息

3. 量子计算复杂性理论

背景（1980-1990年代）：

1982年：Feynman提出量子计算的想法
1985年：Deutsch定义量子图灵机
但缺乏实用的量子算法框架

Yao的量子电路模型（1993）：

3.1 量子电路的定义

经典电路回顾：

输入：n个比特
门：AND、OR、NOT
输出：m个比特

量子电路：

输入：n个量子比特（|0⟩ 或 |1⟩ 或叠加态）
门：Hadamard、CNOT、相位门等
输出：测量得到 m 个经典比特

量子门举例：

Hadamard门（制造叠加态）：

H|0⟩ = (|0⟩ + |1⟩)/√2
H|1⟩ = (|0⟩ - |1⟩)/√2

CNOT门（受控非门，制造纠缠）：

|00⟩ → |00⟩
|01⟩ → |01⟩
|10⟩ → |11⟩
|11⟩ → |10⟩

3.2 Yao定理：量子电路的普遍性

定理内容：

任何量子算法都可以表示为量子电路，其中门来自一个有限的通用门集。

意义：

就像经典计算可以用AND/OR/NOT实现一切
量子计算可以用少数几个门实现一切
为量子算法设计提供标准框架

通用门集：

单比特门：Hadamard、T门、Pauli-X/Y/Z
双比特门：CNOT

影响：

Shor因子分解算法（1994）用这个框架
Grover搜索算法（1996）用这个框架
今天所有量子算法都用量子电路描述

3.3 量子通信复杂性

问题：量子纠缠能否减少通信？

Yao的开创性工作：

定义了量子通信复杂性模型
Alice和Bob可以共享纠缠态
还可以发送量子比特（不仅仅是经典比特）

惊人发现：某些问题，量子通信可以指数级减少通信量！

例子：分布式Deutsch-Jozsa问题

经典通信：需要 n 位
量子通信：只需 O(1) 个量子比特 + 纠缠

但也有限制：对于很多问题（如不相交性），量子通信并没有显著优势。

影响：

理解量子通信协议的能力与限制
量子互联网的理论基础
量子密码学（如量子密钥分发BB84）

4. 伪随机数生成器的理论基础

背景：密码学需要随机数，但真随机数难以获得，能否用确定性算法生成”看起来随机”的数？

Yao定理（1982）：

4.1 定义：计算不可区分性

什么是”看起来随机”？

Yao的定义：

如果任何多项式时间算法都无法区分”真随机串”和”伪随机串”，则伪随机数生成器是安全的。

形式化：

真随机：从 {0,1}^n 均匀随机抽取
伪随机：从种子 s ∈ {0,1}^k 生成 G(s) ∈ {0,1}^n （n >> k）

安全性：
对任何多项式时间算法 A，
|Pr[A(真随机) = 1] - Pr[A(G(种子)) = 1]| < 可忽略量

4.2 Yao定理内容

定理：

如果存在单向函数（易于计算，难以反演），则存在密码学安全的伪随机数生成器。

单向函数例子：

大数分解：n = p × q 容易算，但从 n 分解出 p、q 困难
离散对数：g^x mod p 容易算，但从结果算出 x 困难

构造思路：

种子 s
→ 应用单向函数 f
→ 提取"硬核位"（hard-core bit）
→ 得到1位伪随机输出
→ 迭代这个过程
→ 生成任意长的伪随机串

影响：

所有现代密码学的随机数生成器基于此理论
TLS/SSL、比特币、密码学库（OpenSSL等）都依赖伪随机数
没有这个理论，密码学无法实用化

5. 其他重要贡献

5.1 Byzantine Agreement（拜占庭将军问题）

贡献： Yao改进了拜占庭协议的通信复杂性，从指数级降到多项式级。

应用：

区块链共识（如PBFT）
分布式数据库的一致性

5.2 并行算法复杂性

Yao的定理：关于并行随机算法（PRAM模型）的下界。

影响：理解并行计算的极限。

5.3 计算几何

贡献：最近邻搜索、凸包等问题的通信复杂性。

应用：地理信息系统、计算机视觉。

🌍 对世界的深远影响

1. 理论计算机科学的多个支柱

通信复杂性：

成为独立的研究领域，数千篇论文
理解分布式计算、大数据、量子通信的理论基础

安全多方计算：

MPC成为密码学的核心方向
从理论走向实践（如MPC公司Sharemind、Unbound Security）

量子计算理论：

量子电路模型成为标准
量子算法设计的基础

2. 实际系统的理论支撑

分布式系统：

云计算（AWS、Azure、GCP）的资源调度
微服务架构的通信优化
边缘计算的任务分配

大数据处理：

MapReduce、Spark的算法设计
数据流处理（Flink、Storm）的理论极限

隐私计算：

联邦学习（Google、微软）
隐私保护的广告归因（Apple、Google）
合规数据分析（金融、医疗）

区块链：

共识算法（PBFT、HotStuff）
零知识证明（Zcash、StarkWare）
Layer 2扩容（状态通道、Rollups）

3. 中国计算机科学教育的革命

清华姚班（2005年创办）：

3.1 姚班的创新模式

招生：

从全国高考生中选拔
后来也接受转系、国际学生

培养方案：

小班教学：每届30人左右
国际标准：对标MIT、斯坦福
理论与实践并重：既有数学严谨性，又有编程能力
个性化培养：根据学生兴趣定制课程

课程特色：

大一：数学基础（线性代数、微积分、离散数学）
大二：算法、数据结构、计算理论
大三：专业方向（AI、系统、理论）
大四：科研项目

师资：

姚期智亲自授课
邀请世界顶级学者（图灵奖得主、国际知名教授）

3.2 姚班的杰出校友

楼天城（楼教主）：

三届IOI金牌（国际信息学奥林匹克）
Google无人车早期核心工程师
小马智行联合创始人

胡渊鸣：

Taichi（太极）图形库创始人
SIGGRAPH论文多篇
MIT博士

吴佳俊：

计算机视觉专家
南京大学教授，入选国家青年人才

其他：

众多进入MIT、Stanford、CMU等顶尖学府
许多加入Google、Facebook、Microsoft等科技巨头
多人创业成功（AI、区块链、自动驾驶）

3.3 姚班的影响

对中国高等教育：

证明了中国可以培养世界级人才
其他高校纷纷效仿（北大图灵班、上交ACM班）
提升了计算机科学教育的国际地位

对全球竞赛：

ACM-ICPC：清华多次夺冠
IOI、IMO：中国学生表现优异
顶会论文：姚班学生贡献显著

对科技产业：

姚班校友成为中国AI、自动驾驶、区块链等领域的领军人物
促进了学术与产业的结合

4. 华人在计算机科学界的地位

首位华人图灵奖：

打破了”玻璃天花板”
证明华人可以在理论计算机科学达到最高水平

示范效应：

激励了无数华人学生投身计算机科学
促进了中美学术交流

后续华人图灵奖得主：

虽然至今姚期智仍是唯一在美国本土培养的华人图灵奖得主
但华人学者在计算机科学各领域都有杰出贡献

🏆 获奖理由（ACM官方表述）

ACM图灵奖委员会的颁奖词：

“For his contributions to the theory of computation, including the complexity-based theory of pseudorandom number generation, cryptography, and communication complexity.” （表彰他对计算理论的贡献，包括基于复杂性的伪随机数生成理论、密码学和通信复杂性。）

三大贡献的解读：

通信复杂性：开创性地定义了这个领域，奠定了分布式计算理论基础
密码学（安全多方计算）：百万富翁问题和混淆电路，实现隐私保护的协作
伪随机数生成：连接了计算复杂性与密码学，使密码学可实用化

为什么2000年授奖？

1980-1990年代的工作经过10多年验证，影响已充分显现
量子计算开始从理论走向实验，Yao的量子电路模型价值凸显
互联网时代，通信复杂性和密码学的实际意义更加明显

👤 个人生平与传奇

早年经历（1946-1975）

家庭背景：

1946年12月24日：出生于上海
父亲：姚文琮，著名经济学家
1949年：随家人迁往台湾

教育经历：

1963-1967年：台湾大学物理学学士
1967-1972年：哈佛大学物理学博士
- 导师：与量子场论相关
- 但发现自己更喜欢数学和逻辑

转向计算机科学：

1972-1975年：在伊利诺伊大学香槟分校重读博士
- 导师：C.C. Cheng（华裔计算机科学家）
- 1975年：计算机科学博士学位

为什么转专业？

“物理学需要实验验证，但我更喜欢用纯粹的逻辑和数学解决问题。计算机科学恰好结合了数学的严谨和工程的实用。“

学术生涯（1975-2004）

MIT时期（1975-1976）：

博士后研究员
开始研究计算复杂性

斯坦福大学（1976-1986）：

助理教授、副教授
发表通信复杂性的开创性论文（1979）
提出百万富翁问题（1982）

加州大学伯克利分校（1986-2004，兼职）：

访问教授、兼职教授
与密码学小组合作

普林斯顿大学（1986-2004）：

William and Edna Macaleer工程学教授
终身教授
领导理论计算机科学小组
培养了多位优秀博士生

研究风格：

深刻而广泛：从通信复杂性到量子计算，横跨多个领域
数学之美：追求证明的优雅，不满足于繁琐的技术细节
前瞻性：总是在新领域兴起时就布局

回国之路（2004-至今）

回国的决定（2004年）：

动机：

“中国的发展速度令人惊叹，但在计算机科学教育上还有差距。我希望用普林斯顿的经验，帮助中国培养世界级人才。”

清华大学的邀请：

全职回国，担任高等研究中心教授
给予充分的自主权和资源
承诺支持创办实验班

家人的支持：

妻子Frances Yao（姚储枫）也是知名计算机科学家
夫妇一同回国，在清华任教

创办姚班（2005年）：

初衷：

“中国有最聪明的学生，只要给他们世界一流的教育，他们就能成为世界一流的科学家。”

挑战：

国内教育体系习惯大班授课，如何小班精英化？
如何吸引国际顶级师资？
如何平衡理论与实践？
如何让学生既有深度又有广度？

解决方案：

小班模式：严格控制规模
国际课程：采用MIT、Stanford的教材
双语教学：逐步过渡到全英文
灵活培养：允许学生探索兴趣
科研导向：大三开始进实验室

姚班的成功：

2010年：第一届学生毕业，大部分进入世界顶尖学府深造
2015年：姚班校友开始在学术界和产业界崭露头角
2020年：姚班成为清华乃至中国高等教育的金字招牌

创办交叉信息研究院（2011年）：

整合姚班资源，扩大规模
研究方向：量子计算、AI、密码学、网络科学
吸引了大批海外学者回国

放弃美国国籍（2017年）：

成为中国科学院院士
需要中国国籍
2017年2月：正式加入中国国籍，放弃美国国籍

媒体评价：

“这是对中国最好的背书。一位图灵奖得主，放弃美国的一切，全心投入中国教育。“

荣誉与奖项

学术荣誉：

2000年：ACM图灵奖
1996年：Knuth奖（理论计算机科学）
2021年：京都奖（基础科学）
院士身份：
- 中国科学院院士
- 美国科学院外籍院士
- 美国艺术与科学院院士

荣誉学位：

香港中文大学
香港科技大学
台湾交通大学

其他：

清华大学荣誉教授
清华大学交叉信息研究院院长

家庭生活

妻子Frances Yao（姚储枫）：

斯坦福大学计算机科学博士
专长：算法、在线算法
City University of Hong Kong荣休教授
夫妇是学术伙伴，常合作发表论文

子女：

保护隐私，很少公开信息
据悉也在学术或科技领域

兴趣爱好：

围棋：业余高手
中国文化：书法、古诗词
音乐：喜欢古典音乐

性格特点：

严谨：对学生要求高，但也关怀备至
谦逊：从不自夸，总说”我只是做了些小工作”
坚持：回国后全心投入教育，十几年如一日
远见：总是布局长远，不追逐短期热点

教学风格与学生评价

学生眼中的姚先生：

“姚老师的课，每一句话都值得记笔记。他能用最简洁的语言解释最复杂的概念。” —— 姚班2008级学生

“姚老师对我们很严格，但你能感受到他真心希望我们成为最好的自己。” —— 姚班2012级学生

“见到姚老师，你会明白什么是’大师风范’。他从不居高临下，总是鼓励我们挑战权威，包括他自己。” —— 姚班2015级学生

授课风格：

板书：工整清晰，逻辑严密
互动：鼓励学生提问，常说”问题问得好”
深度：不满足于表面，追求本质理解
激励：相信学生能做到最好，给予充分信任

💭 为什么他值得纪念？

1. 他开创了多个研究领域

通信复杂性：

从零开始，定义了整个领域
今天有数千篇论文、数十本教科书

安全多方计算：

百万富翁问题是起点
今天MPC已成为密码学核心

量子计算复杂性：

量子电路模型成为标准
为量子计算机的发展奠定理论基础

2. 他是理论与实践的桥梁

理论深度：

数学证明严谨、优雅
复杂性理论的核心贡献

实践影响：

通信复杂性指导分布式系统设计
MPC应用于隐私计算
伪随机数生成器支撑所有密码学

3. 他是华人科学家的骄傲

首位华人图灵奖：

历史性突破
证明华人可以在理论计算机科学达到巅峰

回国育人：

放弃普林斯顿的舒适生活
全身心投入中国教育
培养了一代世界级人才

文化桥梁：

连接中美学术界
促进东西方交流

4. 他是教育家的典范

姚班的奇迹：

从零开始，建立世界一流的本科教育
证明中国可以培养顶尖人才

育人理念：

“教育不是填鸭，而是点燃火焰。”

影响力：

姚班模式被其他高校学习
提升了整个中国计算机教育水平

5. 他是跨时代的先知

1979年：提出通信复杂性 → 今天大数据时代的理论基础 1982年：提出MPC → 今天隐私计算的起点 1993年：量子电路模型 → 今天量子计算机的标准框架

每一个贡献：都超前了几十年，今天才显现全部价值。

🔍 技术深度：深入理解核心概念

1. 通信复杂性的证明技术

1.1 分割引理（Partition Lemma）

思想：通过分析协议如何将输入空间分割，得出通信下界。

例子：相等判断

输入空间：{0,1}^n × {0,1}^n
输出：x = y 还是 x ≠ y

关键观察：
- 如果通信了 k 位，协议将输入分成 2^k 个矩形
- 每个矩形内，输出必须一致
- 但"x=y"的对角线与任何矩形都有交集
- 因此需要至少 n 个矩形 → k ≥ log n

1.2 信息论下界

思想：用信息论量化”必须传递多少信息”。

例子：不相交性

Alice有集合A，Bob有集合B
判断 A ∩ B = ∅ 吗？

信息论论证：
- Alice的输入有 2^n 种可能
- Bob需要知道"哪些A会与自己的B相交"
- 这需要Ω(n)位信息

2. 混淆电路的密码学细节

2.1 加密方案

对称加密：

用途：加密真值表
方案：AES、ChaCha20等
关键：每个密钥只用一次（一次性密码本风格）

哈希函数：

用途：从输入密钥派生加密密钥
方案：SHA-256、BLAKE2
关键：抗碰撞性，保证不同输入生成不同密钥

2.2 不经意传输（Oblivious Transfer）

协议（简化版）：

Alice有两个秘密 m_0, m_1
Bob想要 m_b （b ∈ {0,1}），但不让Alice知道b

步骤：
1. Alice生成RSA密钥对 (pk, sk)
2. Alice生成两个随机数 r_0, r_1，发送 pk, r_0, r_1 给Bob
3. Bob选择 b，生成随机 k，计算 v = Enc_pk(k) + r_b，发送v给Bob
4. Alice计算：
   m'_0 = m_0 ⊕ H(Dec_sk(v - r_0))
   m'_1 = m_1 ⊕ H(Dec_sk(v - r_1))
   发送 m'_0, m'_1 给Bob
5. Bob计算 m_b = m'_b ⊕ H(k)

结果：Bob得到 m_b，但Alice不知道b

3. 量子电路的数学基础

3.1 量子态

单比特量子态：

|ψ⟩ = α|0⟩ + β|1⟩
其中 |α|^2 + |β|^2 = 1

测量后：
- 得到0的概率：|α|^2
- 得到1的概率：|β|^2

多比特量子态：

|ψ⟩ = Σ α_i |i⟩  （i ∈ {0,1}^n）
满足 Σ |α_i|^2 = 1

3.2 量子门的矩阵表示

Hadamard门：

H = 1/√2 [ 1   1 ]
           [ 1  -1 ]

作用：H|0⟩ = (|0⟩ + |1⟩)/√2 （均匀叠加）

CNOT门（controlled-NOT）：

CNOT = [ 1 0 0 0 ]
       [ 0 1 0 0 ]
       [ 0 0 0 1 ]
       [ 0 0 1 0 ]

作用：|控制,目标⟩ → |控制, 控制⊕目标⟩

3.3 Yao的普遍性定理

定理：任何 n 比特量子门都可以用 O(n^2) 个单比特门和CNOT门实现。

意义：量子计算机只需要实现少数几种基本门，就能实现任何量子算法。

🧪 实践意义：今天如何应用Yao的理论

1. 分布式系统设计

应用通信复杂性：

评估算法是否适合分布式：如果通信复杂性是Ω(n)，可能不适合
选择通信高效的协议：如使用Sketch算法
权衡计算与通信：有时本地多算一些，可以减少通信

2. 隐私保护的机器学习

联邦学习中的MPC：

场景：多家医院联合训练AI模型
步骤：
1. 各医院本地计算梯度（本地隐私）
2. 使用MPC安全聚合梯度（Yao的混淆电路或其优化版本）
3. 更新全局模型
4. 分发给各医院

保证：各医院看不到彼此的数据

工具：

PySyft（Python库）
TensorFlow Federated
PaddleFL

3. 量子算法开发

使用Yao的量子电路模型：

步骤：
1. 将问题转化为量子电路
2. 使用Hadamard、CNOT等基本门
3. 测量得到结果

工具：
- Qiskit（IBM）
- Cirq（Google）
- Q#（Microsoft）

4. 密码学系统

伪随机数生成器：

应用：TLS/SSL、区块链、数字签名
实现：基于AES、SHA-256等单向函数
理论保证：Yao定理

📚 延伸阅读

核心论文

“Some Complexity Questions Related to Distributive Computing” (1979)
- 通信复杂性的开创性论文
- 定义了Alice-Bob模型
“Protocols for Secure Computations” (1982)
- 百万富翁问题
- 混淆电路
“Quantum Circuit Complexity” (1993)
- 量子电路模型
- 普遍性定理
“Theory and Applications of Trapdoor Functions” (1982)
- 伪随机数生成器
- Yao定理

教科书

《Communication Complexity》- Eyal Kushilevitz & Noam Nisan
- 通信复杂性的权威教材
- 详细介绍Yao的贡献
《A Graduate Course in Applied Cryptography》- Dan Boneh & Victor Shoup
- 现代密码学教材
- 包含MPC章节
《Quantum Computation and Quantum Information》- Nielsen & Chuang
- 量子计算的圣经
- 介绍Yao的量子电路模型

关于姚班

清华大学交叉信息研究院官网
- 姚班的课程设置
- 学生成就
纪录片《姚班十年》
- 姚班的创办历程
- 学生访谈

🌟 精神遗产

Yao的三大品质

1. 跨界思维

“从物理到计算机，从理论到实践，不拘泥于单一领域。”

意义：

通信复杂性结合了复杂性理论与信息论
MPC结合了密码学与算法设计
量子计算结合了物理与计算

2. 教育情怀

“再多的论文，不如培养一个改变世界的学生。”

意义：

回国创办姚班，全心投入教育
用普林斯顿的标准培养中国学生
姚班校友正在改变世界

3. 民族自豪

“中国有最聪明的学生，只要给他们机会，他们能成为最好的。”

意义：

首位华人图灵奖，打破刻板印象
证明华人可以在理论计算机科学达到巅峰
姚班证明中国可以培养世界级人才

对年轻人的启示

追求本质：不要满足于表面的技术，追问”为什么”。

跨界学习：最好的创新往往在交叉领域。

回馈社会：有了成就，要想着如何帮助他人。

坚持理想：姚期智放弃普林斯顿的舒适，回国育人，这需要巨大的勇气和理想。

总结语：姚期智是理论计算机科学的巨匠，用数学的严谨和优雅解决了通信、安全、量子计算的根本问题。他开创了通信复杂性理论，让我们理解分布式计算的极限；他提出百万富翁问题，开创了安全多方计算，让隐私保护的协作成为可能；他建立了量子电路模型，为量子计算提供了标准框架；他证明了伪随机数生成器的存在性，支撑了整个现代密码学。

更难能可贵的是，他作为首位华人图灵奖得主，不仅是个人荣耀，更是华人在计算机科学界的历史性突破。他本可以在普林斯顿安享晚年，却选择回国，创办清华姚班，用世界一流的标准培养中国学生。十几年过去，姚班已成为中国乃至世界计算机教育的典范，校友遍布学术界和产业界，正在改变世界。

从通信复杂性到量子计算，从普林斯顿到清华，从理论贡献到育人成就，姚期智用一生诠释了什么是”学者的风范”、“教育家的情怀”、“民族的脊梁”。他的遗产不仅是一篇篇经典论文，更是一个个改变世界的学生，一个个推动人类进步的理论。

最后更新：2024年12月 本文为图灵奖系列文章，旨在以通俗方式介绍计算机科学先驱的贡献