女博士7年不肯毕业，终一战成名！获理论计算机界至高荣誉，她破解了“量子计算最基础问题”

在今年于巴黎举行的理论计算机科学领域的最顶级会议——计算机科学年度基础论坛（FOCS）上，一位来自加州大学伯克利分校的博士后“一战成名”：乌尔米拉·马哈德（Urmila Mahadev）的成果被会议授予“最佳论文”和“最佳学生论文”奖。这是理论计算机科学家梦寐以求的殊荣。

曾经与马哈德合作的加州理工计算机科学家托马斯·温迪克（Thomas Vidick）在博文中表示，“这是近年来理论计算机科学和量子计算交叉领域中最杰出的成果。”

如此成果的背后，是这位女科学家“顽固”的 7 年博士生涯：到了马哈德 28 岁的时候，她已经在加州伯克利研究生院度过 7 个年头——大多数研究生根本无法承受如此枯燥而“没有盼头的人生”。知道2017年春季，马哈德发现自己成为少数极为幸运的研究生之一。她刚刚解决了量子计算中的一个主要问题，即探索如何立足与直觉严重相悖的量子物理学定律构建起量子计算机。结合早期论文，马哈德得出了所谓盲计算成果。然而，马哈德并没有考虑毕业，因为她认为自己的工作还没完成。

量子计算领域最基础的问题

马哈德花了 5 年时间研究被阿伦森称为“量子计算领域最基础的问题”：如果要求量子计算机执行下达的指令，应如何判断其是否真的按照指示进行，或者是否进行了任何量子性质的计算？

这个问题可绝不仅仅是一个象牙塔学术问题。如果不能证明量子计算机的输出结果确实对应于用户指令，那么不管是仿真黑洞行为还是计算蛋白质构型，结果都不可信。量子计算机的速度确实令经典计算机望尘莫及，但是，经典计算机能忠实执行用户指令，量子计算机可以么？

马哈德在伯克利的导师瓦斯拉米表示，量子计算机非常强大，但是其运算结果的可靠性难以核查。

计算机科学家一直以来都在寻找对量子计算结果进行检验的方法。

在研二阶段，Mahadev被这个问题所深深迷住，因为她意识到自己无法完全理解问题本身。在接下来的几年中，她尝试了一种又一种实现方法。她表示，“我投入了很多时间，我认为自己找到了正确的方向，但很快在一年之后仍然宣告失败。”

但她不愿就此放弃。马哈德表现出一种坚韧的决心，这是瓦斯拉米此前从未见过的。他表示，“从这个角度来讲，Mahadev绝对是一位了不起的学生。”

8 年之后，马哈德成功了。她提出一种交互式协议，通过该协议，不具备量子计算能力的用户可以利用密码方法将工具部署在量子计算机之上并随时随地加以驱动，从而确保量子计算机遵循其指令。Vazirani表示，Mahadev的方法帮助用户们获得了“计算机永远无法摆脱的控制手段。”

德克萨斯大学奥斯汀分校的计算机科学家阿伦森表示，对于一位在读学生而言，这样以一己之力完成的成果可谓“非常惊人”。

漫长的道路

马哈德出生于洛杉矶的的一个医生家庭，在南加州大学读本科。除了确定自己不想成为医生，马哈德换个很多个专业。不过，在听过计算机科学家，RAS 公钥加密算法发明人勒纳德·阿德曼（Leonard Adleman）的课之后，对于理论计算机科学产生了浓厚的兴趣。她在提交给伯克利的研究生申请中表示，她对理论计算机科学的任何方向都感兴趣，“除了量子计算”，因为这听上去太过遥远，她不怎么了解。

然而，在伯克利，导师瓦斯拉米的教导很快使马哈德改变了主意。瓦斯拉米说：“我引导马哈德接触了量子计算可靠性问题，这个问题激发了她无穷的想象。”

马哈德说：“协议就像猜谜。我觉得它比其他的问题简单一些，因为你可以立即在脑子里思考和分析协议，并搞清协议的工作原理。”马哈德将量子计算可靠性作为博士课题，瓦斯拉米导师称“这是一条非常漫长的路。”

起初，她试图直接做出一个终极结果，即“对量子计算机能做什么和不能做什么不加任何假定”。然而，碰壁之后，瓦斯拉尼建议，尝试一下“后量子”密码学方法。计算机科学家猜测（尚未严格证明），“后量子”密码算法甚至能在量子计算机的破解下保持足够的安全性。

2016 年，马哈德和瓦斯拉尼在另一个问题上取得了突破，这个成果在日后被证明是通向最终答案的关键。两人与 OpenAI 公司的的计算机科学家保罗·克里斯塔诺（Paul Christiano）合作，发明了一种利用密码学来让量子计算机创造“秘密状态”的方法。“秘密状态”对于经典计算机是不可知的，但是对于量子计算机本身是可知的的。

他们的核心工具是“陷门函数”——该函数很容易正向计算，但是反向计算几乎不可能，除非拥有密钥。此外，陷门函数还必须是 2 对 1 的映射，即每 1 个输出对应于 2 个不同的输入。类似于 4 等于 2 的平方和-2 的平方。研究团队成功构建了陷门函数。

陷门函数是一种易于执行的函数，但除非拥有加密密钥，否则将难以逆向执行。（但目前研究人员们并不知道要如何实际构建起适合量子计算机的陷阱门函数，这将成为接下来的研究课题。）该函数亦需要“二合一”，即每项输出都对应两条不同的输入。可以想象，假如要对数字进行平方计算，那么除了数字0之外，每条输出结果（例如9）都拥有两个对应的输入项（3与－3）。

利用这一函数，我们可以在量子计算机当中建立秘密状态，具体方法如下所示：首先要求计算机建立一项函数，将其所有可能的输入内容进行叠加（听起来很复杂，但计算机执行起来其实非常容易）。在此之后，要求计算机将该函数应用于此大型叠加，从而建立起新状态——该状态为函数所有可能输出的叠加集。输入与输出叠加集将彼此纠缠，意味着对其中一者的测量将立即对另一个产生影响。

接下来，要求计算机测量输出状态并报告结果。此测量将把输出状态折叠为单一可能输出，且输入状态也将立即折叠从而与该输出结果匹配——这是因为二者彼此纠缠。举例来说，如果使用平方函数，那么如果输出状态为9，则输入将折叠为3与－3的叠加。

不过请注意，这里我们使用的是陷阱门函数。我们拥有陷阱门的密钥，因此能够很容易地找出构成输入叠加的两个状态。然而，量子计算机由于没有这一密钥，所以无法简单地通过测量输入叠加以找出其构成。这主要是因为测量会使结果进一步折叠，从而导致量子计算机只能找到两个输入结果中的一个。

2017 年，马哈德提出，用一种被称为“试错方法”的加密方法构建陷门函数，是“秘密状态”方法的核心。“试错方法”作为一种加密方法被广泛应用于云计算领域，可以令云端服务器无法读取用户未授权的数据，即使它正在处理用户的数据。不久，马哈德、瓦斯拉尼、克里斯塔诺、温迪克和以色列魏茨曼科学研究所的斯维卡·布拉克斯基（Zvika Brakerski）进一步推动了陷门函数的研究，成功利用“秘密状态”方法构建了一种能证明量子计算机输出的随机数确实是随机数的方法。

马哈德此时完全可以毕业，但是她决心继续工作，直到彻底解决量子计算可靠性问题。“我根本没考虑过何时毕业，因为我的目标从来不是拿学位。”

她承认，探索未知领域有很大压力。不过，“我想通了，花时间学习我感兴趣的东西不算浪费时间。”

一个有望通向更多丰硕研究成果的起点

马哈德尝试了各种办法，希望基于“秘密状态”方法设计出可靠性证明协议，但是很长时间没有进展。

直到某天她想到：研究人员已经证明，如果检查者可以测量量子比特，那么就可以检验量子计算结果；经典计算机无法测量量子比特，因此无法利用这个方法检验计算结果。然而，如果检查者能强迫量子计算机自己来测量量子比特，然后报告自查结果呢？

这个思路的核心前提在于：在检验者发出测量指令之前，量子计算机不能知道检验者要做什么测量，否则计算机很容易愚弄检验者。“秘密状态”方法简直就是解决该问题的天赐工具：马哈德令量子计算机首先创立一个“秘密状态”，然后将该秘密状态和待测状态耦合。只有在这个时候，量子计算机才会知道，要执行什么测量。计算机不知道秘密状态的内容，而检验者知道。马哈德证明，量子计算机不可能欺骗检验者而不留下痕迹。温迪克进一步解释，待测量子比特是“整个方法的基石”。最终，如果检验结果看上去是正确的，那么检查者就大可放心。

温迪克：“这个点子太惊人了，每次乌尔米拉解释的时候，我都会被震惊。”

马哈德的检验协议，以及随机数生成器和盲加密算法，都依赖于这样一个假定：量子计算机无法破解“试错方法”。目前，“试错方法”被认为是首屈一指的后量子加密方法，有望被美国国家标准和技术研究所认定为新的加密标准，来取代那些面对量子计算机不堪一击的加密方法。古斯曼表示，目前还不能说“试错方法”可以万无一失地克制量子计算机的解密，但是至少现在它足够可靠，没有谁发现这个算法有什么弱点可利用。

反过来，如果要愚弄马哈德提出的检验协议，那么就必须找出破解“试错方法”的办法，这同样会是一个惊人的成就。

当然，马哈德的协议不太可能马上被应用，原因之一是执行该协议需要的计算量大得惊人。不过，当量子计算机更加强大，算法得以优化之后，该协议仍有很大的应用希望。

虽然马哈德的协议不大可能在 5 年内得以应用。但是阿伦森表示，如果一切顺利，这将是量子计算下一轮技术革命的起点。

温迪克还补充，5 年前，计算机科学家普遍认为，量子计算机想要解决任何经典计算机解决不了的问题还要很多年。现在，科研界普遍认为：“只要 1-2 年就够了”。因此马哈德协议的应用可能比想象的要快。

对于马哈德，她承认自己的成就令自己有点迷茫，她个人希望找到一个新的问题来研究。

不过，在理论计算机科学圈看来，马哈德一统量子计算和加密算法的工作远远不是终点，而是一个有望通向更多丰硕研究成果的起点。

编辑：郝梦夷
责任编辑：许琦敏

来源：综合自网络