量子验证问题被这位女博士生破解

2017年春季，Urmila Mahadev发现自己成为少数极为幸运的研究生之一。她刚刚解决了量子计算中的一个主要问题，即探索如何立足与直觉严重相悖的量子物理学定律构建起量子计算机。结合早期论文，Mahadev得出了所谓盲计算成果。德克萨斯大学奥斯汀分校的计算机科学家Scott Aaronson表示，这“无疑代表着她将成为一颗冉冉升起的新星。”

Urmila Mahadev最近在加州大学伯克利分校举办了计算机科学研讨会

当时刚刚28岁的Mahadev已经在加州大学伯克利分校进行第七年博士生学习——绝大多数学生显然都忍受不了如此漫长的学习时间。她在伯克利的导师Umesh Varizani表示，如今，她拥有了这一“漂亮得令人羡慕的博士生”论文。

然而，Mahadev并没有在那年毕业——她甚至没有考虑过毕业，因为她认为自己的工作还没有完成。

五年多以来，她在学习与研究当中遇到了另一个重要问题，也就是Aaronson所提到的“量子计算领域中的一大根本性问题”，即：如果要求量子计算机执行下达的指令，应如何判断其是否真的按照指示进行，或者是否进行了任何量子性质的计算？

这个问题可能很快就会被学术界彻底解决。研究人员们希望能够尽快让量子计算机在各类问题当中提供指数级加速能力，包括模拟黑洞周边活动到模拟蛋白质大分子的折叠方式等等。

然而，如果说某些计算属于只有量子计算机能够执行、而经典计算机无法处理的类型，我们该如何判断量子计算机是否做出了正确的计算处理？如果大家不信任传统计算机，那么在理论上我们完全可以对计算中的每个步骤进行复查。然而，量子系统从本质上无法被这种复查。首先，其内部工作原理非常复杂：对拥有数百个量子比特（或者称「量子位」）的计算机进行内部状态描述，就需要一块能够存储下整个可见宇宙的巨大硬盘。

即使大家通过某种方式找到了记录这一描述的充足存储空间，问题仍然没有得到解决。量子计算机的内部状态通常由大量彼此不同的非量子“经典”态叠加而成（正如薛定谔的猫理论，其处于既死又生的状态）。然而，在测量了其中某一量子态之后，其就会坍缩为经典状态中的一种。同样的，这意味着在300量子比特的量子计算机当中，我们观察到的结果将仅仅只是300个经典比特——0或者1。

Vazirani解释称，“量子计算机非常强大，但同时也非常神秘。”

考虑到这些限制因素，计算机科学家们长期以来一直弄不清楚量子计算机是否能够提供切实可信的运行保证，即证明其确实已经完成了声称的计算功能。耶路撒冷希伯来大学计算机科学家Dorit Aharonov提问道，“量子与经典世界之间的相互作用是否强大到足以进行对话？”

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

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

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

Aaronson指出，对于一位在读学生而言，这样以一己之力完成的成果可谓“非常惊人”。

Mahadev如今已经成为伯克利大学的博士后研究员，并在日前召开的计算机科学基础年度研讨会上公布了自己的协议。该研讨会是理论计算机科学领域规模最大的盛会之一，本届会议于巴黎举行。她的成果在会上被授予“最佳论文”与“最佳学生论文”奖，这一切即使是对理论计算机科学家们而言都堪称巨大的荣誉。

在一篇博文中，曾与Mahadev进行过合作的加州理工学院计算机科学家Thomas Vidick指出，她的成果是“最近几年以来，量子计算与理论计算机科学家领域出现的、最为杰出的思想之一。”

量子计算研究者们不仅对Mahadev协议所取得的成就感到兴奋，同时亦赞叹她给这个问题带来的全新处理方法。Vidick写道，在量子领域使用经典密码学手段是一种“真正新颖的思维。我希望以此为基础，未来能够出现更多振奋人心的成果。”

漫长的道路

Mahadev出生于洛杉矶的一个医生家庭，并在考入南加州大学之后进行过多次专业转换，希望能够在继承医生头衔之外找到真正适合自己的发展道路。此后，由著名RSA加密算法创造者之一、计算机科学家Leonard Adleman教授的课程让她对理论计算机科学建立起浓厚兴趣。她向伯克利研究生院提交了申请，解释称她对理论计算机科学中的各个方面都很感兴趣——除了量子计算。

她回忆道，“当时，量子计算听起来是种完全陌生的事物，我对此确实不太了解。”

她在进入伯克利之后，Vazirani轻松易懂的解释很快改变了她的想法。Vazirani指出，他曾得这位优秀的学生介绍一个经典问题，即思考如何找到对量子计算进行验证的协议。这个问题“彻底激发出了她的想象力。”

Mahadev解释称，“协议就像是谜题。对我来说，这类问题的切入门槛更低，因为我们可以立即开始构思自己的协议，而后进行尝试以观察其如何工作。”她选择了这个方向作为自己的博士生课题，而Vazirani则将此称为一条“漫长的道路。”

如果量子计算机能够解决经典计算机无法解决的问题，这并不代表着相关解决方案必然难以检查。举例来说，在考虑大数因子分解问题时，量子计算机能够有效解决这一经典计算机所无法处理的难题，而其验证工作却非常简单。更具体地讲，尽管经典计算机无法计算出具体数字，但其能够将得出的因子相乘以观察得出的大数是否与原始大数相等——只要相等，即代表得出了正确的答案。

然而，计算机科学家们认为（最近我们亦在证明层面迈出了重要一步），量子计算机能够解决的众多问题并不存在上述特征。换言之，经典计算机不仅无法解决这类问题，甚至无法判断给出的解决方案是否正确。有鉴于此，安大略省滑铁卢周界理论物理研究所的物理学家Daniel Gottesman于2004年左右提出了一个问题，即是否有可能建立起一种协议，从而由量子计算机向某非量子观察方证明其确实完成了宣称的计算。

在四年之内，量子计算研究人员们已经得出了部分答案。已经有两个团队各自独立给出证明，相较于利用纯粹的经典验证计算机，在量子计算机之内建立一个小型验证系统有望对该量子计算机的计算过程进行证明。研究人员们之后对此种方法做出了改进，并证明对所有验证方的需求，最终都可归结于对单一量子比特的测量能力。

2012年，包括Vazirani在内的一组研究人员们证明，如果一套量子计算机是由两台独立且无法相互通信的量子计算机所构成，那么经典的验证计算机即可检查其量子计算结果。然而，这篇论文的结果只适用于这一特定情况，而且似乎无法被扩展至其它更为广泛的应用场景。Gottesman表示，“我认为有不少人认为这条道路恐怕走不通。”

大致就在同一时间，Mahadev接触到了这一重要的验证问题。起初，她希望提出一个“无条件”性结论，即不对量子计算机能做什么或不能做什么做出假设。但在这个方向探索一段时间并发现无果之后，Vazirani提出了使用“后量子”密码学方法的可能性——换言之，研究人员们认为密码学超出了量子计算机的处理能力。当然，他们对此也不太确定。（这里需要强调，用于在线交易等事务的RSA加密算法不属于后量子密码学，因为大型量子计算机完全可以解决这类将安全性建立在大数分解难度的加密方法。）

2016年，Mahadev与Vazirani在处理另一个不同问题方面取得了进展，而这一进展被证明极为关键。如今，旧金山OpenAI公司的计算机科学家Paul Christiano正与他们通力合作，开发出一种利用密码学方法让量子计算机构建起所谓“秘密状态”的方法——无需量子计算机本身，经典验证计算机已经能够对秘密状态做出描述。

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

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

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

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

2017年，Mahadev通过使用一种名为Learning With Errors（简称LWE）的加密技术，发现了实现秘密状态方法的核心——即构建陷阱门函数。利用这些陷阱门函数，她能够创建盲计算的量化版本，云计算用户可以通过这种计算方式屏蔽自己的数据，从而确保云计算机即使在处理的过程中也无法对内容进行读取。不久之后，Mahadev、Vazirani以及与Christiano开始同Vidick与Zvika Brakerski（来自以色列Weizmann科学研究所）合作，大家共同进一步完善这些陷阱门函数，旨在利用秘密状态方法为量子计算机开发出一种高度可靠的可证明随机数生成方法。

Mahadev完全可以凭借这一出色成果顺利毕业，但她决定继续工作直到彻底解决这个验证问题。她表示，“我从未想过毕业，因为我的目标不存在毕业这一概念。”

虽然并不清楚她到底是否能够解决这个问题，但她表示，“我愿意花时间学习我感兴趣的事情，所以这并不算是在浪费时间。”

一成不变

Mahadev尝试了从秘密状态方法到验证协议的多种方法，但有一段时间，她也陷入了困境。在此之后，她考虑了一下：研究人员们已经证明，如果验证计算机能够测量量子比特，由验证计算机即可检查量子计算机。根据定义，经典验证计算机缺乏这种能力。但如果经典验证计算机能够以某种方式迫使量子计算机自行执行测量并如实报告，结果又会如何？

Mahadev意识到，其中最棘手的部分是让量子计算机在了解验证计算机提出测量对象要求之前，就承诺了解对应的状态——否则，计算机很容易欺骗验证计算机。这正是秘密状态方法发挥作用的地方：Mahadev的协议要求量子计算机首先创建一个秘密状态，而后将其与应当测量的状态纠缠起来。只有这样，计算机才能找出要执行的测量类型。

由于计算机不知道秘密状态的构成，但验证计算机却知道，因此Mahadev强调量子计算机无法在不留下明显双重性痕迹的前提下作弊。从本质上讲，Vidick写道，计算机测量的量子比特已经“设置为一成不变”的形式。如此一来，只要测量结果看起来是正确的，则验证计算机即可确信其正确无误。

Vidick写道，“这是个非常好的主意！每当Mahadev做出解释时，我都对此感到震惊！”

Mahadev的验证协议——以及随机数发生器与盲加密方法——立足于量子计算机无法破解LWE这一假设。目前，LWE被广泛视为后量子密码学领域的主要候选方案，亦可能很快被美国国家标准与技术研究所作为新的加密标准，用以取代量子计算机可能破解的现有标准。但Gottesman告诫称，这并不能保证其真正应对量子计算机的强大处理能力。他表示，“不过到目前为止，这种解决方案还很稳固，没有人发现其可能被破解的证据。”

Vidick写道，无论如何，该协议对于LWE的高度依赖性使得Mahadev的成果具有双赢潜力。量子计算机欺骗该协议的唯一方法，就是量子计算世界中有人想到如何破解LWE——而这本身也将成为一项了不起的成就。

Mahadev的协议不太可能在不久的未来在真正的量子计算机中实现。目前，该协议需要大量算力才能付诸实用。但随着量子计算机规模的扩大以及研究人员对协议的简化，这一情况未来几年可能发生变化。

Aaronson表示，Mahadev的协议可能在未来五年内恐怕还不可行，但“其并非完全只是一种幻想。在量子计算机发展的下一阶段，如果一切顺利的话，大家就可以开始思考这个问题了。”

考虑到技术发展的速度极为可观，相信下一阶段应该会很快到来。毕竟就在五年之前，Vidick提到研究人员们还认为量子计算机尚需要多年才能真正解决传统计算机所无法解决的问题。“现在，人们认为这种能力在未来一到两年后即会实现。”

至于Mahadev，解决她最喜欢的问题让她感觉有点像漂泊在大海之上。她提到，她希望自己能够尽快找到那些最适合自己的研究方向。“现在我需要找个新的问题了，我对这一切充满期待。”

不过理论计算机科学家们认为，Mahadev的量子计算与密码学统一并不是结束，而将成为希望证明更多丰富思想的探索者们的新起点。

Aharonov表示，“我认为未来还将有很多后续发展，我期待着Mahadev能够带来更多激动人心的贡献。”