機(jī)器之心編輯部

一年一度的 ACM 博士論文獎(jiǎng)出爐了！

6 月 10 日，美國(guó)計(jì)算機(jī)協(xié)會(huì) ACM 宣布了最新一屆的博士論文獎(jiǎng)。

該獎(jiǎng)項(xiàng)于 1978 年設(shè)立，每年頒發(fā)給計(jì)算機(jī)科學(xué)與工程領(lǐng)域最佳博士論文的作者，獎(jiǎng)金為 20000 美元，榮譽(yù)提名獎(jiǎng)獎(jiǎng)金為 10000 美元。獲獎(jiǎng)?wù)撐膶⒆鳛?ACM 圖書系列的一部分，在 ACM 數(shù)字圖書館出版。

今年頒發(fā)的是 2025 年的獎(jiǎng)項(xiàng)，包括一個(gè)博士論文獎(jiǎng)和兩個(gè)博士論文獎(jiǎng)榮譽(yù)提名。

其中，MIT 博士、現(xiàn)紐約大學(xué)庫(kù)朗數(shù)學(xué)、計(jì)算與數(shù)據(jù)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)助理教授 Allen Liu（劉書亮）憑借博士論文《Learning Theoretic Foundations for Understanding Quantum Systems》摘得本屆 ACM 博士論文獎(jiǎng)。

劉書亮的研究方向較為廣泛，主要涉及算法和機(jī)器學(xué)習(xí)理論。目前，他最關(guān)注的是機(jī)器學(xué)習(xí)和語(yǔ)言模型的基礎(chǔ)理論。他也曾研究過多個(gè)方向，從計(jì)算和統(tǒng)計(jì)中的基礎(chǔ)問題，到科學(xué)領(lǐng)域中的反問題，尤其是量子信息中的相關(guān)問題。

此前，他于 2025 年秋季在加州大學(xué)伯克利分校擔(dān)任 Miller 博士后研究員。他本科同樣就讀于 MIT，專業(yè)為數(shù)學(xué)。博士專業(yè)為計(jì)算機(jī)科學(xué)。

值得一提的是 2014 年到 2016 年，劉書亮代表美國(guó)奧數(shù)代表隊(duì)連續(xù)三屆拿到過 IMO 金牌，其中 2016 年拿到滿分。在 2020 年，他還參加過阿里巴巴數(shù)學(xué)競(jìng)賽決賽。

ACM 博士論文獎(jiǎng)榮譽(yù)提名授予以下兩位學(xué)者：

• 博科尼大學(xué)博士后研究員 Gal Arnon，博士論文題為《New Advancements in Interactive Oracle Proofs: Theory, Practice, and Limitations》，他在魏茨曼科學(xué)研究所獲得博士學(xué)位；
• MIT 助理教授 Rachit Nigam，博士論文題為《Modular Abstractions for Efficient Hardware Desi》，他在康奈爾大學(xué)獲得博士學(xué)位。

ACM 博士論文獎(jiǎng)

• 論文名稱：《Learning Theoretic Foundations for Understanding Quantum Systems》
• 論文鏈接：https://dspace.mit.edu/entities/publication/86bf5543-05b9-45e0-9cfc-2cc342559582

理解并駕馭量子系統(tǒng)的力量，有望改變科學(xué)與技術(shù)的許多領(lǐng)域。然而，在實(shí)現(xiàn)這些愿景之前，首先必須更深入地理解量子系統(tǒng)的基本行為方式。

在這篇論文中，作者從學(xué)習(xí)理論的視角切入這一問題，發(fā)展出理解量子系統(tǒng)、認(rèn)識(shí)其結(jié)構(gòu)性質(zhì)的新范式。論文給出了一系列出人意料的結(jié)果：它們推翻了人們過去對(duì)一些基本規(guī)律的認(rèn)識(shí)，并在一些此前被認(rèn)為難以處理的情形中，給出了可證明高效的量子系統(tǒng)學(xué)習(xí)算法。

在典型的量子多體系統(tǒng)中，系統(tǒng)內(nèi)的粒子會(huì)依據(jù)某種幾何結(jié)構(gòu)發(fā)生局域相互作用，這通常由局域哈密頓量來描述。這里有兩個(gè)關(guān)鍵問題：其一，是理解一個(gè)給定哈密頓量系統(tǒng)的平衡性質(zhì)；其二，是從系統(tǒng)性質(zhì)的測(cè)量結(jié)果中反推出這個(gè)哈密頓量。

針對(duì)第一個(gè)問題，論文證明了一條普適規(guī)律：在一個(gè)只取決于幾何結(jié)構(gòu)、與系統(tǒng)規(guī)模無關(guān)的臨界溫度上，糾纏會(huì)發(fā)生「驟然消亡」。針對(duì)第二個(gè)問題，論文提出了第一個(gè)能夠在任意溫度下恢復(fù)哈密頓量的高效算法，突破了此前人們認(rèn)為在低溫下難以跨越的障礙。

除了局域相互作用系統(tǒng)之外，論文還研究了一般量子態(tài)性質(zhì)的學(xué)習(xí)與檢驗(yàn)問題，重點(diǎn)關(guān)注統(tǒng)計(jì)復(fù)雜性與近期量子設(shè)備限制之間的關(guān)系。在這些設(shè)備限制下，研究只允許對(duì)量子態(tài)的有限個(gè)副本進(jìn)行糾纏測(cè)量。針對(duì)許多與近期量子設(shè)備相關(guān)的情形，論文刻畫了單副本測(cè)量以及多副本測(cè)量下，學(xué)習(xí)與檢驗(yàn)問題所能達(dá)到的最優(yōu)速率。

ACM 博士論文獎(jiǎng)榮譽(yù)提名

• 論文 1：New Advancements in Interactive Oracle Proofs: Theory, Practice, and Limitations
• 論文鏈接：https://galarnon42.github.io/gal_thesis.pdf

概率證明系統(tǒng)允許一個(gè)強(qiáng)大的證明者，說服計(jì)算能力較弱的驗(yàn)證者相信某個(gè)大規(guī)模、復(fù)雜計(jì)算的正確性。這類看似神奇的對(duì)象，在理論和實(shí)踐中都發(fā)揮了極其重要的作用。在理論上，它們推動(dòng)了 PCP 定理、零知識(shí)證明以及近似難度等領(lǐng)域的突破；在實(shí)踐中，它們是提升云計(jì)算和區(qū)塊鏈技術(shù)可擴(kuò)展性的關(guān)鍵組成部分，并已被廣泛部署，用于保護(hù)價(jià)值數(shù)十億美元的交易。

本文聚焦于交互式預(yù)言機(jī)證明（interactive oracle proofs，IOPs）。這是一種概率證明模型：證明者與驗(yàn)證者進(jìn)行多輪交互；交互結(jié)束后，驗(yàn)證者以概率方式從每條證明者消息中讀取少量比特，并根據(jù)讀取到的位置決定接受或拒絕。IOP 是一種極其強(qiáng)大的工具。

從理論上看，它能夠?qū)崿F(xiàn)其他概率證明系統(tǒng)尚未達(dá)到的效率參數(shù)；從實(shí)踐上看，高效的 IOP 可以被編譯成速度極快、規(guī)模極小的密碼學(xué)證明，并已被廣泛用于保障真實(shí)世界系統(tǒng)的安全。

在這篇論文中，作者從理論、實(shí)踐和局限性三個(gè)層面，進(jìn)一步推進(jìn)了對(duì) IOP 及相關(guān)證明系統(tǒng)的理解。

具體而言，本文的貢獻(xiàn)包括：（1）通過證明小查詢復(fù)雜度的 IOP 與交互式證明具有同等計(jì)算能力，為 IOP 建立了類似 PCP 定理的結(jié)果；（2）構(gòu)造了新的 NP 問題 IOP，具備較小的可靠性誤差和較低的查詢復(fù)雜度；（3）為 Reed–Solomon 碼開發(fā)了新的、具體效率更高的鄰近性 IOP；（4）揭示了構(gòu)造高效 IOP 和 PCP 所面臨的障礙。

• 論文 2：Modular Abstractions for Efficient Hardware Desi
• 論文鏈接：https://people.csail.mit.edu/rachit/files/pubs/dissertation.pdf

硬件設(shè)計(jì)最核心的目標(biāo)是效率：用盡可能少的資源和功耗，實(shí)現(xiàn)速度最快的電路。與此同時(shí)，硬件的設(shè)計(jì)、制造和部署本身需要投入巨量資源，因此，優(yōu)化決策幾乎貫穿了硬件設(shè)計(jì)工具的整個(gè)設(shè)計(jì)過程。

模塊化，也就是關(guān)注點(diǎn)分離，使可復(fù)用組件的設(shè)計(jì)成為可能，也是軟件革命的重要驅(qū)動(dòng)力。但在硬件設(shè)計(jì)中，模塊化長(zhǎng)期處于次要位置。原因在于，模塊化設(shè)計(jì)往往會(huì)遮蔽電路的一些關(guān)鍵屬性，進(jìn)而導(dǎo)致低效實(shí)現(xiàn)。在專用化時(shí)代，性能提升越來越依賴于為特定計(jì)算任務(wù)設(shè)計(jì)專門硬件，因此，硬件設(shè)計(jì)迫切需要既模塊化又高效的抽象。

這篇論文指出，對(duì)「時(shí)間」進(jìn)行顯式推理，是設(shè)計(jì)這類抽象的關(guān)鍵，并通過三個(gè)系統(tǒng)體現(xiàn)了這一思想。

第一個(gè)系統(tǒng)是 Dahlia。這是一種可編譯到硬件的命令式語(yǔ)言，它利用對(duì)時(shí)間敏感的推理，確保上層程序能夠被編譯成高效硬件。

第二個(gè)系統(tǒng)是 Calyx。它既是一個(gè)編譯器，也是一種中間語(yǔ)言，用于將類似 Dahlia 的語(yǔ)言轉(zhuǎn)換為硬件描述。Calyx 通過一種新的中間語(yǔ)言，彌合了計(jì)算描述與電路實(shí)現(xiàn)之間的差距。這種中間語(yǔ)言同時(shí)融合了類似軟件的控制流，以及類似硬件的結(jié)構(gòu)化構(gòu)造。Calyx 還利用一個(gè)觀察結(jié)果，緩解了周期級(jí)時(shí)間精確建模與可擴(kuò)展編譯器優(yōu)化之間的張力：對(duì)時(shí)間敏感的執(zhí)行調(diào)度，可以看作是對(duì)時(shí)間無關(guān)調(diào)度的進(jìn)一步細(xì)化。

第三個(gè)系統(tǒng)是 Filament。這是一種新的硬件描述語(yǔ)言，能夠在模塊接口中直接建模周期級(jí)約束，并在編譯期確保設(shè)計(jì)中不存在結(jié)構(gòu)沖突。

這三個(gè)系統(tǒng)共同表明，在每一層抽象中恰當(dāng)?shù)亟r(shí)間，對(duì)于構(gòu)建兼具模塊化和效率的硬件設(shè)計(jì)工具至關(guān)重要。這項(xiàng)工作也為專用加速器時(shí)代進(jìn)一步擴(kuò)大硬件設(shè)計(jì)規(guī)模奠定了基礎(chǔ)。

https://x.com/TheOfficialACM/status/2064724518325670060

https://www.acm.org/media-center/2026/june/dissertation-award-2025