2025 年 ACM 博士论文奖揭晓：Allen Liu 夺冠，两学者获荣誉提名！
ACM 博士论文奖揭晓！Allen Liu（刘书亮）夺冠，另有两学者获荣誉提名
6 月 10 日，美国计算机协会 ACM 宣布了最新一届的博士论文奖。该奖项于 1978 年设立，每年颁发给计算机科学与工程领域最佳博士论文的作者，奖金为 20000 美元，荣誉提名奖奖金为 10000 美元。获奖论文将作为 ACM 图书系列的一部分，在 ACM 数字图书馆出版。今年颁发的是 2025 年的奖项，包括一个博士论文奖和两个博士论文奖荣誉提名。
其中，MIT 博士、现纽约大学库朗数学、计算与数据科学学院计算机科学助理教授 Allen Liu（刘书亮）凭借博士论文《Learning Theoretic Foundations for Understanding Quantum Systems》摘得本届 ACM 博士论文奖。
刘书亮的研究方向较为广泛，主要涉及算法和机器学习理论。目前，他最关注的是机器学习和语言模型的基础理论。他也曾研究过多个方向，从计算和统计中的基础问题，到科学领域中的反问题，尤其是量子信息中的相关问题。
此前，他于 2025 年秋季在加州大学伯克利分校担任 Miller 博士后研究员。他本科同样就读于 MIT，专业为数学。博士专业为计算机科学。值得一提的是，2014 年到 2016 年，刘书亮代表美国奥数代表队连续三届拿到过 IMO 金牌，其中 2016 年拿到满分。在 2020 年，他还参加过阿里巴巴数学竞赛决赛。
ACM 博士论文奖荣誉提名授予以下两位学者：
- 博科尼大学博士后研究员 Gal Arnon，博士论文题为《New Advancements in Interactive Oracle Proofs: Theory, Practice, and Limitations》，他在魏茨曼科学研究所获得博士学位。
- MIT 助理教授 Rachit Nigam，博士论文题为《Modular Abstractions for Efficient Hardware Desi》，他在康奈尔大学获得博士学位。
ACM 博士论文奖
- 论文名称：《Learning Theoretic Foundations for Understanding Quantum Systems》
- 论文链接：https://dspace.mit.edu/entities/publication/86bf5543-05b9-45e0-9cfc-2cc342559582
理解并驾驭量子系统的力量，有望改变科学与技术的许多领域。然而，在实现这些愿景之前，首先必须更深入地理解量子系统的基本行为方式。
在这篇论文中，作者从学习理论的视角切入这一问题，发展出理解量子系统、认识其结构性质的新范式。论文给出了一系列出人意料的结果：它们推翻了人们过去对一些基本规律的认识，并在一些此前被认为难以处理的情形中，给出了可证明高效的量子系统学习算法。
在典型的量子多体系统中，系统内的粒子会依据某种几何结构发生局域相互作用，这通常由局域哈密顿量来描述。这里有两个关键问题：其一，是理解一个给定哈密顿量系统的平衡性质；其二，是从系统性质的测量结果中反推出这个哈密顿量。
针对第一个问题，论文证明了一条普适规律：在一个只取决于几何结构、与系统规模无关的临界温度上，纠缠会发生「骤然消亡」。针对第二个问题，论文提出了第一个能够在任意温度下恢复哈密顿量的高效算法，突破了此前人们认为在低温下难以跨越的障碍。
除了局域相互作用系统之外，论文还研究了一般量子态性质的学习与检验问题，重点关注统计复杂性与近期量子设备限制之间的关系。在这些设备限制下，研究只允许对量子态的有限个副本进行纠缠测量。针对许多与近期量子设备相关的情形，论文刻画了单副本测量以及多副本测量下，学习与检验问题所能达到的最优速率。
ACM 博士论文奖荣誉提名
论文 1
- 论文名称：New Advancements in Interactive Oracle Proofs: Theory, Practice, and Limitations
- 论文链接：https://galarnon42.github.io/gal_thesis.pdf
概率证明系统允许一个强大的证明者，说服计算能力较弱的验证者相信某个大规模、复杂计算的正确性。这类看似神奇的对象，在理论和实践中都发挥了极其重要的作用。在理论上，它们推动了 PCP 定理、零知识证明以及近似难度等领域的突破；在实践中，它们是提升云计算和区块链技术可扩展性的关键组成部分，并已被广泛部署，用于保护价值数十亿美元的交易。
本文聚焦于交互式预言机证明（interactive oracle proofs，IOPs）。这是一种概率证明模型：证明者与验证者进行多轮交互；交互结束后，验证者以概率方式从每条证明者消息中读取少量比特，并根据读取到的位置决定接受或拒绝。IOP 是一种极其强大的工具。从理论上看，它能够实现其他概率证明系统尚未达到的效率参数；从实践上看，高效的 IOP 可以被编译成速度极快、规模极小的密码学证明，并已被广泛用于保障真实世界系统的安全。
在这篇论文中，作者从理论、实践和局限性三个层面，进一步推进了对 IOP 及相关证明系统的理解。具体而言，本文的贡献包括：
- 通过证明小查询复杂度的 IOP 与交互式证明具有同等计算能力，为 IOP 建立了类似 PCP 定理的结果。
- 构造了新的 NP 问题 IOP，具备较小的可靠性误差和较低的查询复杂度。
- 为 Reed–Solomon 码开发了新的、具体效率更高的邻近性 IOP。
- 揭示了构造高效 IOP 和 PCP 所面临的障碍。
论文 2
- 论文名称：Modular Abstractions for Efficient Hardware Desi
- 论文链接：https://people.csail.mit.edu/rachit/files/pubs/dissertation.pdf
硬件设计最核心的目标是效率：用尽可能少的资源和功耗，实现速度最快的电路。与此同时，硬件的设计、制造和部署本身需要投入巨量资源，因此，优化决策几乎贯穿了硬件设计工具的整个设计过程。
模块化，也就是关注点分离，使可复用组件的设计成为可能，也是软件革命的重要驱动力。但在硬件设计中，模块化长期处于次要位置。原因在于，模块化设计往往会遮蔽电路的一些关键属性，进而导致低效实现。在专用化时代，性能提升越来越依赖于为特定计算任务设计专门硬件，因此，硬件设计迫切需要既模块化又高效的抽象。
这篇论文指出，对「时间」进行显式推理，是设计这类抽象的关键，并通过三个系统体现了这一思想。
- 第一个系统是 Dahlia。这是一种可编译到硬件的命令式语言，它利用对时间敏感的推理，确保上层程序能够被编译成高效硬件。
- 第二个系统是 Calyx。它既是一个编译器，也是一种中间语言，用于将类似 Dahlia 的语言转换为硬件描述。Calyx 通过一种新的中间语言，弥合了计算描述与电路实现之间的差距。这种中间语言同时融合了类似软件的控制流，以及类似硬件的结构化构造。Calyx 还利用一个观察结果，缓解了周期级时间精确建模与可扩展编译器优化之间的张力：对时间敏感的执行调度，可以看作是对时间无关调度的进一步细化。
- 第三个系统是 Filament。这是一种新的硬件描述语言，能够在模块接口中直接建模周期级约束，并在编译期确保设计中不存在结构冲突。
这三个系统共同表明，在每一层抽象中恰当地建模时间，对于构建兼具模块化和效率的硬件设计工具至关重要。这项工作也为专用加速器时代进一步扩大硬件设计规模奠定了基础。