2000 - 姚期智的量子通訊複雜度（量子計算的理論基礎）#

案件摘要#

2000 年，姚期智（Andrew Chi-Chih Yao，1946–） 因三項奠基性的貢獻獲得圖靈獎—— 首位（且至今唯一）的華人圖靈獎得主：

姚氏的三大理論： 1. 通訊複雜度（communication complexity，1979）： 「兩方通訊需要幾個位元？」——分佈式計算的下界； 2. 姚氏原理（Yao's principle，1977）： 隨機演算法的最壞情況 = 最優確定性演算法的期望——隨機演算法的理論基礎； 3. 量子通訊複雜度（1993）： 量子糾纏能省多少通訊？——量子計算的理論基礎。 2000 年圖靈獎的意義：理論資訊科學的頂峰—— 2004 年起，姚期智在清華大學創辦「姚班」，培育了中國的 AI 世代。

前因 -- 為什麼會有這個案子#

• 姚期智的背景（1946–1981）： 姚期智生於上海，台灣長大（台大物理系）， 哈佛的物理博士（1972）——轉向電腦科學（伊利諾大學）。

• 通訊複雜度的誕生（1979）： 姚期智 1979 年發表《Some Complexity Questions Related to Distributive Computing》：

例子（等值函數 EQ）：兩方各持 \(n\) 位元串，判斷是否相等——

• 量子計算的興起（1980s–1993）：
• Feynman（1982）：「量子系統需要量子電腦模擬」—— 量子計算的構想；
• Deutsch（1985）：量子圖靈機的定義；
• Shor（1994）：量子因數分解——量子計算的「殺手級應用」；
• 姚期智（1993）：量子通訊複雜度——量子計算的理論基礎。

• 2000 年圖靈獎與清華的姚班（2004）： 姚期智 2000 年獲圖靈獎； 2004 年，他放棄普林斯頓的終身職，回清華大學創辦 計算機科學實驗班（姚班）——

姚班的畢業生創辦了多家 AI 公司（曠視科技等）。

線索與推理 -- 數學式、程式、理論#

第一條線索：通訊複雜度（1979）#

模型：Alice 有 \(x\) 、Bob 有 \(y\) （各 \(n\) 位元）， 他們要計算 \(f(x, y)\) ——通訊量最少是多少？

矩陣的視角（姚期智的工具）： 函數 \(f\) 對應一個 \(2^n \times 2^n\) 的矩陣—— 確定性協定的通訊量 = 矩陣的「分割數」的對數：

例子： | 函數 | 確定性通訊量 | 隨機通訊量 | |------|------------|-----------| | 等值 EQ | \(n+1\) | \(O(\log n)\) | | 大於 GT | \(n\) | \(n\) （無法省！） | | 內積 IP | \(n\) | \(\Theta(n)\) |

第二條線索：姚氏原理（1977）#

姚氏原理（Yao's principle）：

• 意義：要證明「隨機演算法幫不上忙」， 只需構造一個「壞分佈」使任何確定性演算法都慢—— 下界證明的標準工具！
• 應用：博弈論的極小極大定理（von Neumann, 1928）的計算版—— 隨機策略的威力被嚴格刻畫。

第三條線索：量子通訊複雜度（1993）與安全多方計算#

量子通訊複雜度：

例子（內積的量子協定）：

安全多方計算（secure multiparty computation，1982）：

• 百萬富翁問題（1982，姚期智）：兩個富翁比誰有錢， 但誰都不透露自己的財富——

• 後代：電子投票、隱私保護的機器學習（federated learning）、 區塊鏈的零知識證明。

Python：通訊複雜度與隨機演算法的驗證#

import numpy as np
np.random.seed(42)

# 1) 通訊複雜度：EQ 函數（等值判斷）
def eq_deterministic(x, y):
    """確定性：傳送全部 n 位元（D = n）"""
    return x == y   # 模擬：需要傳 n 位元才能比較

def eq_randomized(x, y, k=20):
    """隨機：只傳 k 個隨機位元的指紋（R = O(log n)）"""
    # 隨機指紋：選一個隨機質數，比較 mod
    # 簡化：用隨機投影
    for _ in range(k):
        r = np.random.randint(0, 2, len(x))
        fx = (x @ r) % 2
        fy = (y @ r) % 2
        if fx != fy:
            return False   # 發現不同 → 確定不等
    return True   # k 次都相同 → 可能相等（誤差 ≤ 2^-k）

# 測試：n = 100 位元的字串
n = 100
x = np.random.randint(0, 2, n)
y_equal = x.copy()
y_diff = x.copy(); y_diff[50] ^= 1

print("通訊複雜度（EQ 函數，n = 100 位元）：")
print(f"  確定性：需傳 {n} 位元（D = n）")
print(f"  隨機化：只需傳 {20} 次指紋（O(log n)）")
print(f"  x == x：確定性 = True，隨機 = {eq_randomized(x, y_equal)}")
print(f"  x == x⊕一位元：確定性 = False，隨機 = {eq_randomized(x, y_diff)}")
print(f"  → 隨機演算法用 O(log n) 位元完成 n 位元的工作（100 倍省）\n")

# 2) 百萬富翁問題（姚期智 1982）
def millionaire_rich(a, b, max_wealth=100):
    """百萬富翁問題：比較 a 與 b，但不透露具體值（簡化協定）"""
    # 簡化：用「間隔比較」——雙方各自加密，第三方比較
    # 真實協定需要同態加密；這裡模擬「只輸出誰大」
    return "Alice 富" if a > b else "Bob 富"

print("百萬富翁問題（姚期智 1982）：")
print(f"  Alice 有 80 萬，Bob 有 95 萬 → {millionaire_rich(80, 95)}")
print("  → 只輸出「誰大」，不透露 80 或 95（隱私的計算）")
print("  → 後代：電子投票、federated learning、零知識證明\n")

# 3) 姚氏原理：隨機演算法的威力（博弈論的視角）
print("姚氏原理（1977）：")
# 石頭剪刀布：隨機策略 vs 確定性策略
def rps_payoff(my, their):
    """我的收益：贏=1，輸=-1，平=0"""
    if my == their: return 0
    if (my+1) % 3 == their: return 1   # 石頭<剪刀<布<石頭... 簡化
    return -1

# 確定性策略：對手知道你的策略 → 你必輸
# 隨機策略（1/3 均勻）：期望 = 0（不管對手怎麼做）
print("  石頭剪刀布：")
print("    確定性策略：對手預測 → 必輸（期望 < 0）")
print("    隨機策略（1/3 均勻）：期望 = 0（對手無法預測）")
print("  → 姚氏原理：隨機策略的期望 = 最優確定性（對某分佈）的期望")
print("  → 隨機性在對抗環境中是必要的（下界證明的工具）\n")

# 4) 量子通訊的優勢（內積函數）
print("量子通訊複雜度（內積 IP）：")
print("  經典：Q(IP) = Θ(n)（無法省）")
print("  量子：Q(IP) = O(log n) 量子位元（指數級省）")
print("  → 量子糾纏能省通訊（1993 姚期智的理論）")
print("  → 量子計算的理論基礎之一")

通訊複雜度（EQ 函數，n = 100 位元）：
  確定性：需傳 100 位元（D = n）
  隨機化：只需傳 20 次指紋（O(log n)）
  x == x：確定性 = True，隨機 = True
  x == x⊕一位元：確定性 = False，隨機 = False
  → 隨機演算法用 O(log n) 位元完成 n 位元的工作（100 倍省）

百萬富翁問題（姚期智 1982）：
  Alice 有 80 萬，Bob 有 95 萬 → Bob 富
  → 只輸出「誰大」，不透露 80 或 95（隱私的計算）
  → 後代：電子投票、federated learning、零知識證明

姚氏原理（1977）：
  石頭剪刀布：
    確定性策略：對手預測 → 必輸（期望 < 0）
    隨機策略（1/3 均勻）：期望 = 0（對手無法預測）
  → 姚氏原理：隨機策略的期望 = 最優確定性（對某分佈）的期望
  → 隨機性在對抗環境中是必要的（下界證明的工具）

量子通訊複雜度（內積 IP）：
  經典：Q(IP) = Θ(n)（無法省）
  量子：Q(IP) = O(log n) 量子位元（指數級省）
  → 量子糾纏能省通訊（1993 姚期智的理論）
  → 量子計算的理論基礎之一

結案 -- 後果與影響#

• 理論資訊科學的頂峰（2000）：

• 通訊複雜度：分佈式計算的下界——Google、Amazon 的分佈式系統的理論；
• 姚氏原理：隨機演算法的下界證明——隨機演算法（見 隨機算法/）的理論；
• 量子通訊：量子計算的理論——量子電腦（2020s）的基礎。
• 量子計算的世紀（1994–）：

• Shor（1994）：量子因數分解——RSA 的威脅（見「2002-RSA公開金鑰.md」）；
• Grover（1996）：量子搜尋（ \(\sqrt{n}\) 加速）；
• 2019 年 Google 的「量子霸權」：53 量子位的 Sycamore—— 200 秒完成經典電腦 1 萬年的計算（有爭議但里程碑）；
• 後量子密碼學（NIST 標準，2022–2024）：抵禦量子攻擊的新密碼。
• 安全多方計算與隱私（1982–）：

• 零知識證明（Goldwasser–Micali–Rackoff, 1985，2012 圖靈獎）： 「證明我知道答案，但不透露答案」——姚的問題的深化；
• federated learning（2016，Google）：多方的機器學習—— 資料不出本地——姚的「隱私計算」的 AI 版；
• 區塊鏈（2008，中本聰）：零知識證明 + 分佈式共識（Lamport 2013）。
• 姚班與中國的 AI 世代（2004–）：

• 2004 年：姚期智放棄普林斯頓終身職，回清華創辦姚班；
• 2021 年：他放棄美國國籍（2004 年起）——中國科學院院士；
• 姚班的畢業生：曠視科技（Face++）、多家 AI 獨角獸的創辦人；
• 「姚班模式」：本科生的嚴格理論訓練——被多國效仿。
• 隨機演算法的理論（1977–）：

• 偽隨機數產生器（Blum–Micali–Yao，1982）：密碼學安全的隨機；
• 去隨機化（derandomization）：P = BPP？（隨機是否幫不上忙？）—— 與 P vs NP 呼應的未解問題。
• 2000 年圖靈獎的意義： 姚期智的演講主題是「量子計算的展望」—— 他是唯一在圖靈獎演講中談量子計算的得主（當時）—— 20 年後（2020s），量子計算成為主流——遠見的印證。
• 歷史定位：姚期智是「理論的橋樑」——

關鍵人物與文獻#

• A. C.-C. Yao：Some Complexity Questions Related to Distributive Computing（1979）；姚氏原理（1977）；百萬富翁問題（1982）；量子通訊複雜度（1993）；2000 圖靈獎。
• R. Feynman：量子模擬（1982）——量子計算的構想。
• D. Deutsch：量子圖靈機（1985）。
• P. Shor：量子因數分解（1994）——RSA 的威脅。
• S. Goldwasser & S. Micali：零知識證明（1985）；2012 圖靈獎。
• 相關案件：1971-庫克NP完全.md、2002-RSA公開金鑰.md、1982-蘭波特Paxos.md、隨機算法/README.md。