LWE（在读博士的第八年）

Urmila Mahadev（厄米拉·马哈德夫）花了八年时间在研究生院解决了量子计算领域最基本的问题之一：怎么知道量子计算机是否做了量子计算呢？

○ Urmila Mahadev在研讨会上。 | 图片来源：Jana Ašenbrennerová/Quanta Magazine

2017年春天，Urmila Mahadev发现自己处于大多数研究生都会认为相当不错的一个位置。她刚刚解决了量子计算领域的一个主要问题。量子计算是研究计算机的科学，它从量子物理学的奇怪定律中获得强大的计算力。

德州大学奥斯汀分校的计算机科学家Scott Aaronson认为，Mahadev关于“盲计算”的新成果与她之前的论文结合起来，显然让她成为“一颗冉冉升起的新星”

当时28岁的Mahadev已经在加州大学伯克利分校读了七年研究生——远远超过了大多数学生迫切想要毕业的阶段。现在，正如她的博士导师Umesh Vazirani所说的，她终于有了一篇“非常漂亮的博士论文”。

但是那一年，Mahadev并没有毕业，她甚至没有考虑要毕业，因为事情还没有完成呢。

量子计算+密码学

在五年多的时间里，她还有另一个不同的研究目标。她想解决的这个问题被Aaronson称为“量子计算领域最基本的问题之一”，那就是：如果让一台量子计算机做计算，怎么知道它是否真的遵循了你的指令，或者它是否真的执行了任何量子计算呢？

研究人员希望，过不了许多年，量子计算机就能指数级地加速为我们解答许多问题，比如模拟黑洞周围的行为、蛋白质如何折叠等等。但是，一旦量子计算机能够完成经典计算机无法完成的计算，我们将如何知道它的计算是否正确呢？

如果你不信任一台普通的计算机，理论上，你可以亲自检查它的每一个计算步骤。但是，量子系统从根本上抵制这种检查。

首先，量子计算机的内部工作机制极其复杂：对于几百个量子比特的计算机，要写出关于其内部状态的描述将需要比整个可见宇宙还要大的一个硬盘。此外，即使有足够的空间写下这个描述，也没有办法得到它。通常，量子计算机的内部状态是许多不同的非量子的“经典”态的叠加。（就像是薛定谔的猫，同时处于“死”和“活”的状态）但是，一旦测量一个量子态，它就会坍缩为其中一个经典态。凝视一台300个量子比特的量子计算机，本质上，你看到的只会是300个经典比特，也就是0和1。

Vazirani说：“量子计算机非常强大，但是也非常神秘。”

考虑到这些限制，长久以来，计算机科学家一直好奇，是否有可能让量子计算机提供任何严格的保证，证明它确实做了自己宣称的事情。耶路撒冷希伯来大学的计算机科学家Dorit Aharonov问道：“量子和经典世界之间的相互作用是否足够强大，以至于能够进行对话呢？”

在研究生二年级的时候，Mahadev被这个问题迷住了，其中的原因连她自己都不完全明白。在随后的几年里，她尝试了一种又一种方法。她说：“有很多次，我觉得自己做着正确的事情，但是接着就出错了，有时很快，有时过了一年才出现。”

但是，Mahadev拒绝放弃。她表现出了Vazirani从未见过的持久的决心，Vazirani说：“从这个意义上说，Mahadev绝对是与众不同的。”

现在，经过八年的研究生学习，Mahadev终于成功了！她提出了一种交互式协议，通过这种协议，没有量子计算能力的用户也可以使用经典的密码学让量子计算机做任何他们想做的事情，并确信量子计算机正在遵循他们的命令，就像是牵着马具任意驰骋一样。Vazirani说，Mahadev的方法给用户提供了“让计算机无法摆脱的手段“。

○ Mahadev提出的协议。 | 图片来源：https://arxiv.org/pdf/1804.01082.pdf

Aaronson说，一个研究生能够独自完成这样一个任务”非常令人震惊“。

Mahadev现在是伯克利大学的博士后研究员。近日，她在计算机科学基金会的年度研讨会——理论计算机领域最大型的会议之一——上提交了自己的方案。她的作品获得了这次会议的”最佳论文“和”最佳学生论文“奖，这对一位理论计算机科学家来说是罕见的荣誉。

加州理工学院的计算机科学家Thomas Vidick过去曾与Mahadev合作过，他在博客文章中写道，Mahadev的研究成果是”近年来量子计算和理论计算机科学的交叉处出现的最杰出的思想之一“。

量子计算领域的研究人员之所以兴奋，不仅是因为Mahadev的协议能够解决问题，还因为她为解决这个问题所采取的全新方法。Vidick写道，在量子计算领域使用经典的密码学真的是非常新颖的想法，”我希望，在这些想法的基础上，会继续产生更多成果。“

漫长的证明之路

Mahadev在洛杉矶的一个医生家庭长大，她就读于南加州大学，在那里，她从一个研究领域漂流到另一个。起初，她只确信一点，那就是自己不想成为一名医生。后来，计算机科学家Leonard Adleman——RSA加密算法的三位创造者中的A——讲授的一门课程让她对理论计算机科学产生了兴趣。之后，她申请成为加州大学伯克利分校的研究生，并在申请材料中解释说，自己对理论计算机科学的所有方面都感兴趣，除了量子计算。因为量子计算“听起来像是非常古怪的事情，是我知道得最少的事情”。

然而，一到伯克利，Vazirani深入浅出的解释很快改变了她的想法。他向她介绍了一个问题——如何找到一个验证量子计算的协议？而这个问题“激发了她的想象力”，Vazirani说道。

Mahadev解释说：“协议就像是谜题。对我来说，这种问题似乎比其他问题更容易，因为你可以自己立即开始思考协议，然后破解它们，这样你就会发现它们是如何运作的。” 她选择这个问题作为自己的博士研究课题，开始了Vazirani所说的“漫漫长路”。

○ Urmila Mahadev。 | 图片来源：Quanta Magazine

如果一台量子计算机可以解决经典计算机无法解决的问题，那并不必然意味着解决方案将难以检验。以大数的因数分解为例，一台大型量子计算机可以高效解决这个问题，但经典计算机被认为无法完成这个任务。

虽然一个经典计算机不能对一个大的数字进行因数分解，但它却能够检验量子计算机的因数分解是否正确——只需要将这些因数相乘，看看它们是否得出正确答案。

然而，计算机科学家相信（并且最近已经向证明迈出了一步），量子计算机能够解决的许多问题并没有这个特性。也就是说，一台经典计算机不仅不能解决这些问题，甚至也不能判断一个提出的解决方案是否正确。

鉴于这一点，大约在2004年，圆周理论物理研究所的物理学家Daniel Gottesman提出一个问题：是否有可能提出任何一种协议，通过这个协议，一台量子计算机可以向非量子观察者证明自己确实完成了声称的那些事情？

在四年内，量子计算的研究人员已经得到了部分答案。两个不同的团队证明，一台量子计算机有可能证明它的计算，但是不是向一台纯粹经典的验证设备，而是向一个能够进入自己内部非常小的量子计算机的验证设备。研究人员后来改进了这种方法，并证明，验证设备所需要的只是每一次测量单个量子比特的能力。

2012年，包括Vazirani在内的一组研究人员证明，如果量子计算是由一对无法相互通信的量子计算机进行的，那么，一台完全经典的验证设备就能够检查量子计算。Gottesman表示，那篇论文的方法是针对这种特定情形设计的，这个问题似乎陷入了死胡同，一些人认为不能再往前走了。

大约就在这个时候，Mahadev遇到了这个验证问题。起初，她试图得到一个“无条件”的结果，一个并不假定量子计算机能做什么或不能做什么的结果。

在她研究这个问题一段时间，且并没有取得任何进展后，Vazirani建议了一种不同的可能性——用“后量子”加密（post-quantum cryptography）。研究人员认为，这是一种即使量子计算机也无法破解的加密方法，虽然他们还不确定。

像RSA加密算法之类用于加密在线交易等信息的方法不是后量子的，也就是说，一台量子计算机能够破解这种加密方法，因为它们的安全性取决于对大数做因数分解的难度。

2016年，Mahadev和Vazirani在解决另一个问题的时候取得了进展，这在后来被证明是至关重要的。

他们与如今在OpenAI公司工作的计算机科学家Paul Christiano合作，开发了一种方法，使用密码学让量子计算机构建所谓的“加密态（secret state）”，这个加密态的描述对于经典的验证设备是已知的，但是对于量子计算机本身却是未知的。

他们的程序依赖于所谓的“暗门”函数（trapdoor function），这个函数很容易执行，但是要逆转则非常困难，除非知道密钥。（研究人员还不知道如何真正构建一个合适的暗门函数，之后将会提出。）另外，还要求这个函数是“二对应一”的，这意味着，每一个输出对应着两个不同的输入。比如说，对于平方函数y=x²，除了数字0之外的每一个输出（例如9）都有两个对应的输入（3和−3）。

有了这样一个函数，就可以让量子计算机按照下面的步骤构建一个加密态：

输入的叠加和输出的叠加会产生纠缠，这意味着，测量其中一个会立即影响另一个。

接下来，要求计算机测量输出态，并告诉我们结果。这个测量会导致输出态坍缩为所有可能输出中的一个，而输入态也会立即坍缩以与之匹配，因为它们彼此纠缠。例如，对于平方方程，如果测量得到的输出态是9，那么输入态会坍缩为3和−3的叠加态。

但是，如果使用的是暗门函数，那么我们就有暗门的秘钥，因此可以很容易地找出构成输入态的两种叠加态。然而，量子计算机不能。量子计算机不能简单地测量输入的叠加来求出它的构成，因为测量会进一步让输入的叠加坍缩，让计算机只剩下其中一个输入态，而无法求出另一个。

2017年，Mahadev使用一种名为“错误学习（Learning With Errors，LWE）”的加密技术，找到了在加密态方法的核心构建暗门函数的方法。利用暗门函数，她就能够创建一个量子版本的“盲”计算，使得云计算用户可以屏蔽他们的数据，这样云计算机即使在计算时也无法读取数据。

不久之后，Mahadev、Vazirani 、Christiano与Vidick、Zvika Brakerski（以色列魏茨曼科学研究所的科学家）合作，进一步改进这些暗门函数，利用加密态方法发展出一种让量子计算机产生可证实的真随机数的安全方法。

Mahadev 本可以凭借这些结果毕业，但她决心继续工作，直到解决验证问题。她说：“我从来没有想毕业的事情，因为我的目标从来就不是毕业。”

不知道能否解决这个问题有时会让人感到压力，但是，她说：“我花时间学习自己感兴趣的东西，因此，这也就不是真的在浪费时间。”

如何加密？

Mahadev尝试了各种方法，试图从加密态方法抵达一种验证协议，但是有一段时间，她一无所获。然后，她有了一个想法：研究人员已经证明，如果验证设备能够测量量子比特，它就能够检验量子计算机。根据定义，一个经典的验证设备缺乏这种能力。但是，如果这个经典的验证设备能够以某种方式强迫量子计算机自己进行测量，然后诚实地报告测量结果呢？

Mahadev意识到，最棘手的部分是，在量子计算机知道验证设备会要求哪种测量之前，就让量子计算机确定它将要测量的状态。否则，量子计算机很容易欺骗验证设备。这正是加密态方法发挥作用的地方：Mahadev的协议要求量子计算机首先创建一个加密态，然后将它与应该测量的状态纠缠在一起。只有到那时，计算机才会知道要进行何种测量。

由于量子计算机不知道加密态的构成，但验证设备知道，Mahadev证明，量子计算机不可能在不留下明显的欺骗痕迹的情况下做出严重的欺骗。

Vidick写道，本质上，计算机要测量的量子比特被“设置为密码石”。正因为如此，如果测量结果看起来像是一个正确的证明，验证设备就能确信它们真的是。“真是个好主意！每一次Urmila解释它的时候，我都惊呆了。”

量子计算机不能破解的密码？

Mahadev的验证协议，连同随机数生成器和盲加密方法，都取决于量子计算机不能破解LWE的假设。目前，LWE被广泛认为是后量子密码学的优先候选对象，而且，它或许很快会被美国国家标准与技术研究所（NIST）采用作为其新的加密标准，取代那些量子计算机可能破解的方法。

Gottesman警告说，这并不能确保这种加密方法真的能抵御量子计算机，“但是到目前为止，这种方法是可靠的，还没有人找到证据，证明这种方法有可能被破解。”

Vidick写道，无论如何，协议对LWE的依赖给Mahadev的作品带来了双赢的意味。量子计算机可能欺骗协议的唯一方法是，量子计算领域的某个人找到了破解LWE的方法，而这本身将会是一项了不起的成就。

Mahadev的协议不太可能在不久的将来就在真正的量子计算机上实现。目前，这个协议需要太多的计算能力，因而不太有实用性。但在未来几年，随着量子计算机越来越大，以及研究人员对协议进行简化，情况可能会改变。

Aaronson说，Mahadev的协议可能在未来五年内都没有可行性，但是，“在假想世界里也不是完全不可行。如果一切顺利，在量子计算机演化的下一个阶段，就可以开始思考这个问题。“

考虑到这个领域现在的发展速度有多快，这个阶段可能会更早到来。Vidick说，毕竟，就在五年前，研究人员还认为量子计算机要想解决经典计算机无法解决的任意问题还需要很多年。现在，人们认为这将在一两年内发生。

至于Mahadev，解决了自己最喜欢的问题让她有点茫然。她希望自己能明白，是什么让这个问题适合自己去研究。“我现在必须找到一个新问题，所以很希望能知道这个答案。”

然而，理论计算机科学家更多地是将Mahadev统一量子计算与密码学一事视为对那些丰富多彩的思想脉络的初步探索，而不是故事的结束。

译：乌鸦少年

原文链接：

https://www.quantamagazine.org/graduate-student-solves-quantum-verification-problem-20181008/