读研八年不毕业，她解决了量子计算的一个根本性问题
马哈德夫出席 10 月上旬在加州大学伯克利分校举办的计算机科学研讨会；之后，她在巴黎举行的计算机科学基础学术报告会上发表了演讲。
2017 年春天，乌尔米拉·马哈德夫（Urmila Mahadev）让大多数研究生都很羡慕。她刚刚解决了量子计算领域的一个重大问题。所谓量子计算，研究的是量子计算机，它的算力来自于量子物理学的奇异法则。德州大学奥斯汀分校的计算机科学家斯科特·阿伦森（Scott Aaronson）指出，马哈德夫的新研究成果（称为“盲计算”），加之她早先发表的论文，让所有人看到，“她是一颗冉冉升起的新星”。
当时，28 岁的马哈德夫已经在加州大学伯克利分校念了七年的研究生，早就过了大多数学生迫不及待想要毕业的阶段。现在，她终于具备了完成一篇“漂亮博士论文”的条件，马哈德夫在伯克利的博士生导师优曼许·瓦齐雷尼（Umesh Vazirani）如是说。
不过，马哈德夫没有在那一年毕业，她甚至没有考虑过毕业的问题。她的研究还没有完成。
量子计算领域的最基本问题之一
五年多来，马哈德夫一直还在研究另一个问题，阿伦森称之为“你能在量子计算领域提出的最基本问题之一”，即：如果我们让量子计算机执行一次计算任务，我们如何知道它真的遵照了指令，它究竟有没有做任何与量子计算有关的事情？
这个问题可能很快就会超越学术的范畴。研究人员希望，量子计算机能够在相对较短的时间内，在一系列问题上实现指数级的计算加速，包括对黑洞周围的天体行为进行建模、模拟大分子蛋白质的折叠方式，等等。
不过，一旦量子计算机能够执行传统计算机无法完成的任务，我们如何才能知道它的计算过程是对的呢？
如果我们不信任一台传统计算机，理论上说，我们可以亲自对每一个计算步骤进行检验。然而，量子系统从根本上是抵制这种检验的。首先，它们的内部机制极其复杂：即便是一台只有数百个量子比特（即量子位）的计算机，如果我们要把描述其内部状态的信息全部记录下来，我们将需要一个比整个可观测宇宙还要大的硬盘，才能把这些信息存储下来。
而且，即使有足够的空间来存储这些信息，我们也无法去理解它。量子计算机的内部状态，通常是许多非量子“经典”状态的叠加，这就像薛定谔的猫，同时处于既死又活的状态。但是，一旦你对一个量子态进行测量，它就会坍缩成其中一个经典态。如果观察一台 300 量子比特计算机的内部，其实你只会看到 300 个经典比特（0 和1）对着我们笑。
“量子计算机非常强大，但它同样非常神秘。”瓦齐雷尼说道。
考虑到这些限制因素，计算机科学家一直以来就想知道，是否有可能让量子计算机提供某种万无一失的保证，即它确实做了自己宣称做过的那些事情。“量子世界与经典世界之间的相互作用是否强大到足以实现彼此之间的对话？”耶路撒冷希伯来大学的计算机科学家多瑞特·阿哈罗诺夫（Dorit Aharonov）这样问道。
八年，终于成功！
在念研究生的第二年，马哈德夫被这个问题迷住了，而且她自己也不完全明白其中的原因。随后几年，她尝试了一个又一个方法。“很多时候，我都觉得自己做对了，然后它们却崩溃了，有的耗时很短，有的则要花上一年。”她说。
但马哈德夫没有放弃，反而表现出一种持之以恒的决心，这是瓦齐雷尼在其他人身上不曾见过的，他说，“从这个方面讲，乌尔米拉绝对与众不同。”
如今，念了八年研究生后，马哈德夫成功了。她构想出一种交互协议，通过这种协议，那些自身不具备量子能力的用户可以使用加密技术，给量子计算机套上“挽具”，驾驭它去往任何想去的地方，并且能够确定量子计算机是在遵循指令行事。瓦齐雷尼表示，马哈德夫的方法向用户提供了“计算机无法挣脱的手段”。
阿伦森说，一名研究生能够单枪匹马取得这样的成果，这“非常惊人”。
马哈德夫现在是加州大学伯克利分校的博士后研究员，她最近在计算机科学基础学术报告会上展示了自己的协议——该会议是理论计算机科学领域规模最大的会议之一，今年在巴黎举行。马哈德夫的研究成果被授予大会“最佳论文”和“最佳学生论文”。对一名理论计算机科学家来说，这是难得的殊荣。
加州理工学院的计算机科学家托马斯·维迪克（Thomas Vidick）曾与马哈德夫共事，他在一篇博客文章中，把后者的研究成果称为“近些年在量子计算和理论计算机科学交叉领域出现的最杰出成果之一”。
让研究人员感到兴奋的，不仅是马哈德夫的协议所取得的效果，更在于她为解决这个问题而提出的全新方法。在量子领域使用经典加密技术是一个“真正新颖的想法”，维迪克写道，“我认为这种想法将催生更多的研究成果。”
“我的目标从来不是为了毕业”
马哈德夫在洛杉矶的一个医生家庭长大，她本科就读于南加州大学，在那里辗转于多个研究领域。起初，她只是确信自己不想当一名医生。后来，RSA 加密算法的创造者之一、计算机科学家伦纳德·阿德曼（Leonard Adleman）教授的一门课程，让她对理论计算机科学产生了浓厚的兴趣。她向加州大学伯克利分校的研究生院提出了申请，并在申请书中表示，自己对理论计算机科学的各个方面都感兴趣——量子计算除外。
“当时，它听起来像是我最不熟悉、最不了解的东西。”马哈德夫说。
不过，她来到伯克利分校后，瓦齐雷尼通俗易懂的解释很快改变了她的想法。瓦齐雷尼给她布置了一项任务，让她找出一种能够验证量子计算的协议。瓦齐雷尼说，这个问题“真正激发了她的想象力”。
“协议就像谜题。”马哈德夫解释道，“对我来说，它们似乎比其他问题更容易切入，因为我可以立刻开始思考那些协议，然后打破它们，这可以让我看到它们是如何发挥作用的。”马哈德夫把这个问题作为了博士研究的课题，从而踏上了瓦齐雷尼所谓的“漫漫长路”。
如果量子计算机可以解决传统计算机无法解决的问题，并不一定意味着我们难以检验量子计算机给出的解决方案。
以大数的因数分解为例，大型量子计算机能够高效地加以解决，而传统计算机在这方面则被认为力有不逮。尽管传统计算机无法分解出一个大数的因数，但它能够轻易检验量子计算机得出的结果是否正确——它只需把所有因数相乘，看看结果是否与大数相等就行了。
然而，计算机科学家认为，量子计算机能够解决的很多问题并不具备这个特性。换句话说，传统计算机不但无法解决这些问题，而且也无法确认量子计算机给出的解决方案是否正确。
有鉴于此，2004 年左右，加拿大圆周理论物理研究所的物理学家丹尼尔·戈特斯曼（Daniel Gottesman）提出了一个问题：我们是否有可能构想出一种协议，让量子计算机可以借此向一个非量子观察者证明，它确实做了自己宣称做过的那些事情？
在四年的时间里，量子计算研究人员找到了部分答案。两支不同的研究团队证明，量子计算机有可能证明自己的计算，但对象并非一个纯粹的传统计算验证者，而是一个能够访问小型量子计算机的验证者。研究人员后来改进了这种方法，表明验证者需要的只是一次对单个量子比特进行测量的能力。
2012 年，一支包括瓦齐雷尼在内的研究团队证明，如果量子计算是由两台无法相互通信的量子计算机来执行，那么一台纯粹的传统计算机是能够对量子计算结果进行检验的。
但是，那篇论文描述的方法是为特定情况量身定制的，而问题似乎在这里走到了死胡同，戈特斯曼说，“当时可能有人觉得，我们没法再前进一步了。”
大约在此时，马哈德夫也遇到了这个验证问题。起初，她试图得出一个“无条件限制”的结果，也就是不对关于量子计算机能做什么、不能做什么提出任何假设。而后，在马哈德夫研究这个问题一段时间却没有丝毫进展的情况下，瓦齐雷尼提出，也许可以试试“后量子”加密技术。所谓“后量子”加密技术，就是量子计算机也无力破解的加密术。（用于为在线交易加密的 RSA 算法并不属于后量子加密术，大型量子计算机可以破解这些算法，因为它们的安全性取决于分解大数因数的难易程度。）
2016 年，在与计算机科学家保罗·克里斯蒂亚诺（Paul Christiano）合作另一个课题的研究时，马哈德夫和瓦齐雷尼取得了一项后来被证明至关重要的进展。他们开发出一种方法，可以利用加密术让量子计算机生成所谓的“秘密状态”——对于这种状态的描述，传统计算验证者能够知道，而量子计算机本身无法知道。
他们的程序依赖于所谓的“陷门”函数，该函数易于执行，但难于逆转，除非你拥有私密的加密密钥。（当时，研究人员还不知道如何创建一个合适的陷门函数，后来才知道。）此外，陷门函数还需要是“二对一”，这意味着，每个输出值都对应着两个不同的输入值。比如说平方数函数，除了数字 0 之外，每个输出值（例如9）都有两个相应的输入值（3 和-3）。
有了这样的函数之后，我们便能让量子计算机按照如下步骤生成一个秘密状态：首先，我们让计算机建立一个包含函数所有潜在输入值的叠加态。然后，我们让计算机把函数应用在这个巨型叠加态上，从而生成一个新状态，它是函数所有潜在输出值的叠加态。输入值和输出值的叠加态将被纠缠在一起，这意味着，对其中一个进行测量会立刻影响到另一个。
接下来，我们让计算机测量输出状态，并得到结果。这种测量会让输出值叠加态坍缩为一个确定的潜在输出值，然后，输入值叠加态也会立刻坍缩来进行匹配——例如，当我们使用平方数函数时，如果输出值是9，那么输入值将坍缩为 3 和-3 的叠加态。
但不要忘了，我们使用的是陷门函数。我们有陷门的密钥，所以，我们可以很容易找出构成输入值叠加态的两个状态。但量子计算机不行，而且量子计算机也不能通过简单地测量输入值叠加态，来弄清它由什么构成，因为这种测量会让它进一步坍缩，使计算机只能得到两个输入值中的一个，而无法得到另一个。
2017 年，马哈德夫利用一种名为“容错学习”（LWE）的加密技术，想出了如何在秘密状态的核心方法中构建陷门函数。利用这些陷门函数，她得以创建量子版本的“盲”计算——在盲计算中，云计算用户可以屏蔽数据，使云计算机无法读取，即便云计算机在使用数据进行计算。不久之后，马哈德夫、瓦齐雷尼、克里斯蒂亚诺联手维迪克和以色列魏茨曼科学研究所的兹维卡·布拉克斯基（Zvika Brakerski），希望进一步完善这些陷门函数。
他们顺着秘密状态的思路，开发出了一种让量子计算机生成“可证明随机数”的简单方法。
马哈德夫本可以凭借这些成果顺利毕业，但她决心继续研究，直至解决验证问题为止。“我从未想过毕业的问题，因为我的目标从来不是为了毕业。”她说道。
有时，由于不知道自己能否解决这个问题，马哈德夫会感受到压力。但她说，“我是在花时间学习自己感兴趣的事情，所以这真的不算是浪费时间。”
如何判定量子计算机在“作弊”？
马哈德夫尝试了多种途径，想要通过秘密状态方法，得出一种验证协议，但有一段时间，她一无所获。后来，她有了一个想法：研究人员已经证明，如果验证者能够对量子比特进行测量，那么该验证者便能检验量子计算机。显然，传统计算验证者缺乏这种能力。但如果传统验证者能够以某种方式迫使量子计算机自己进行测量，并如实地报告，结果会怎样呢？
马哈德夫意识到，棘手的地方在于，要让量子计算机在知道验证者要求进行哪种测量之前，就确定它要测量的状态——否则，计算机很容易欺骗验证者。这就是秘密状态方法的用武之地了：按照马哈德夫的协议，量子计算机会先创建一个秘密状态，然后将其与它应该测量的状态纠缠在一起。只有这样，计算机才能知道要执行哪种测量。
由于计算机不知道秘密状态的构成而验证者知道，马哈德夫证明，如果量子计算机大肆“作弊”，一定会留下明显的欺骗痕迹。维迪克认为，从本质上说，计算机要测量的量子比特已经被“钉在加密术的板子上”。因此，如果测量结果看起来像是一个正确的证明，那么验证者就可以确信，它们确实如此。
“这个想法真是太棒了！”维迪克写道，“每次乌尔米拉进行解释，我都会感到惊艳。”
马哈德夫的验证协议——连同随机数生成器和盲加密方法——取决于一个前提假设，即量子计算机无法破解 LWE。目前，LWE 被广泛认为是后量子加密术的主要候选者，它可能很快会被美国国家标准与技术研究所选为新的加密标准，以取代那些可以被量子计算机破解的技术。
戈特斯曼提醒说，这并不能保证 LWE 就一定不会被量子计算机破解。“但到目前为止，它还是稳固的。”他说，“还没有人发现它有可能被破解的证据。”
维迪克表示，无论如何，协议对 LWE 的依赖让马哈德夫的研究成果具有了双赢属性。量子计算机能够“欺骗”该协议的唯一方法，是量子计算领域中，有人想到了如何破解 LWE，而这本身就将是一项了不起的成就。
“现在，我需要找到一个新的问题来研究”
马哈德夫的协议不太可能很快就在真正的量子计算机中实现。目前来说，该协议要成为现实，还需要太多的算力才行。但未来几年，随着量子计算机的规模不断扩大以及研究人员继续对协议进行简化，情况是有可能发生改变的。
也许，这份协议在未来五年内都不具有可行性，但“它也并不完全是幻想中的事物”，阿伦森说道，“如果一切顺利，在量子计算机发展的下一个阶段，我们就可以开始思考这个问题了。”
而考虑到该领域的发展之快，这个阶段或许很快就会到来。维迪克说，毕竟，就在五年前，研究人员还认为，量子计算机还需要很多年才能解决传统计算机无法解决的问题，“而现在，人们觉得只需要一两年就可以了。”
至于马哈德夫，解决了自己最喜欢的问题后，她觉得有点茫然。她说，她想知道这个问题究竟有何魔力，让自己如此着迷。“现在，我需要找到一个新的问题来研究，如果能知道，就太好了。”
