两位中国量子信息领军人物荣获FOCS 2021“时间检验奖”

光子盒研究院出品

2021年12月24日，第62届IEEE计算机科学基础年度研讨会(FOCS 2021)各奖项揭晓！FOCS由IEEE计算机学会的计算机数学基础专委会提供资助，是计算机科学领域最顶级的国际会议，与ACM计算理论年会(STOC)并称理论计算机科学两大顶会。

FOCS 2021奖项包括最佳论文奖、最佳学生论文奖和时间检验奖。中国科学院院士、清华大学交叉信息研究院院长、清华大学量子信息中心主任姚期智和阿里巴巴达摩院量子实验室负责人施尧耘，与其他两位作者凭借2001年发表的论文《Informationl Complexity and the Direct Sum Problem for Simultaneous Message Complexity》，获得时间检验奖。

作为中国量子信息领军人物，姚期智和施尧耘分别领导的清华大学交叉研究院和达摩院量子实验室，是国内领先的量子信息科研机构。

我们简要回顾一下这篇论文。

论文摘要：

给定同一问题的m个副本，解决这m个问题是否需要m倍的资源？这就是直和问题(direct sum problem)——一个在许多计算模型中已经研究过的基本问题。研究人员在姚期智先前提出的同步消息(SM)通信模型中研究了这个问题。众所周知，n位字符串的相等问题具有SM复杂度Θ(√n）。他们证明了求解问题的m个副本具有复杂度Ω(m√n)；使用先前已知的技术可以证明的最佳下界是Ω(√mn)。他们还证明了等式函数的多个副本的某些布尔组合的类似下界。这些结果可以推广到更广泛的函数类。他们引入了一个与SM复杂度相关的新的信息复杂性概念，并且具有良好的直和性质。这一概念被用作证明上述结果的工具；它似乎相当强大，可能具有独立的利益。

论文链接：

https://www.cs.dartmouth.edu/~ac/Pubs/focs01-infocomplex.pdf

此外，麻省理工学院(MIT)工程硕士在读的毛啸凭借论文《Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance》获得FOCS 2021最佳学生论文奖。据了解，毛啸曾就读于长沙雅礼中学，是2017年国际奥林匹克信息学竞赛银牌得主，本科获得MIT数学与计算机双学位。

关于姚期智

1946年出生于中国上海，计算机科学家，2000年获得图灵奖，中国科学院院士、美国科学院外籍院士，清华大学交叉信息研究院院长。研究方向包括：计算理论及其在密码学和量子计算中的应用，最先提出量子通信复杂性，提出分布式量子计算模式，后来成为分布式量子算法和量子通信协议安全性的基础。

2021年，清华大学交叉信息学院正式成立量子信息班，由姚期智院士担任首席教授。这是清华大学首个量子信息方向的本科人才培养项目，也是继计算机科学实验班“姚班”、人工智能班“智班”之后，姚期智院士创办的第三个拔尖创新人才培养项目。

关于施尧耘

1997年本科毕业于北京大学，后在普林斯顿大学取得计算机科学博士学位，是姚期智院士的学生。研究方向包括：量子算法和复杂性，量子通信复杂性，量子系统和量子计算的经典模拟，量子信息学和量子密码学。回国前是密西根大学安娜堡分校终身教授。2017年加入阿里巴巴，目前是达摩院量子实验室负责人。

时间检验奖名单：

https://focs2021.cs.colorado.edu/test-of-time-awards/