量子物理学定律：如何判断量子计算机是否做出正确计算处理

2017 年春天，Urmila Mahadev 发现自己是少数幸运的研究生之一。她刚刚解决了量子计算中的一个重大问题，探索如何根据如此违反直觉的量子物理定律构建量子计算机。结合早期的论文，Mahadev 提出了所谓的盲计算结果。这“当然意味着她将成为一颗冉冉升起的新星，”德克萨斯大学奥斯汀分校的计算机科学家 Scott Aaronson 说。

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

当时只有 28 岁的 Mahadev 已经在加州大学伯克利分校攻读博士学位的第七年——这是一个绝大多数学生显然无法忍受的漫长学习期。现在，她的伯克利顾问 Umesh Varizani 说，她有这篇“令人羡慕的漂亮博士生”论文。

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

五年多来，她在学习和研究中遇到了另一个重要问题，这就是 Aaronson 所说的“量子计算领域的一个基本问题”，即：如果需要一台量子计算机来执行给定的指令，它应该是你怎么知道它是否真的按照它的指令去做，或者它是否做了任何量子性质的计算？

这个问题可能很快就会被学术界彻底解决。研究人员希望量子计算机很快能够在各种问题中提供指数加速，从模拟黑洞周围的活动到模拟蛋白质大分子如何折叠。

但是，如果某些计算是只有量子计算机可以执行的类型，而不是经典计算机，我们如何判断量子计算机是否进行了正确的计算？如果您不信任传统计算机，那么理论上可以仔细检查计算中的每一步。然而，量子系统天生就无法进行这种审查。首先，它的内部工作很复杂：用数百个量子比特（或“量子比特”）描述计算机的内部状态需要一个能够存储整个可见宇宙的巨大硬盘驱动器。

就算大家都找到了足够的存储空间来记录这段描述，问题依旧没有解决。量子计算机的内部状态通常是大量相互不同的非量子“经典”状态的叠加（如薛定谔的猫理论，既死又活）。然而，在测量这些量子态之一后，它会坍缩成经典态之一。同样，这意味着在 300 量子比特的量子计算机中，我们将只观察到 300 个经典比特——0 或 1。

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

鉴于这些限制，计算机科学家长期以来一直想知道量子计算机是否可以提供现实的保证，即它确实做了它声称要做的事情。“量子世界和经典世界之间的相互作用是否足以进行对话？” 耶路撒冷希伯来大学的计算机科学家 Dorit Aharonov 问道。

在研究的第二阶段，Mahadev 对这个问题着迷，因为她意识到自己无法完全理解问题本身。在接下来的几年里，她尝试了一种又一种方法。“我投入了很多时间，我认为我的方向是正确的，但一年后它仍然是失败的，”她说。

但她不想放弃。Mahadev 表现出 Vazirani 从未见过的坚韧不拔的决心。“从这个角度来看，马哈德夫绝对是一个了不起的学生，”他说。

现在，经过八年的学习，马哈德夫终于成功了。她提出了一种交互协议，没有量子计算能力的用户可以通过该协议在量子计算机上加密部署工具并随时随地驱动它，确保量子计算机遵循其指令。Vazirani 说 Mahadev 的方法帮助用户获得了“一种计算机永远无法摆脱的控制手段”。

Aaronson 指出，对于现在的一名学生来说，单枪匹马取得的成果“相当惊人”。

Mahadev 现在是伯克利的博士后研究员，他在计算机科学基础年度研讨会上展示了他的协议。该研讨会是理论计算机科学领域规模最大的研讨会之一，在巴黎举行。她的工作在会议上获得了“最佳论文”和“最佳学生论文”两个奖项，这对于理论计算机科学家来说都是巨大的荣誉。

与 Mahadev 合作的加州理工学院计算机科学家 Thomas Vidick 在一篇博客文章中指出，她的结果是“近年来量子计算和理论计算机科学家领域出现的最杰出的想法之一”。

量子计算研究人员不仅对 Mahadev 协议的成就感到兴奋，而且还钦佩她解决问题的新方法。Vidick 写道，在量子领域使用经典密码学是“真正新颖的想法。我希望在此基础上，未来会出现更令人兴奋的结果。”

长路

Mahadev出生在洛杉矶的一个医生世家，在考入南加州大学后经历了几次重大转变，希望在继承医生头衔之外找到一条真正适合自己的发展道路。此后，她通过计算机科学家 一、、著名的 RSA 加密算法的创造者 Leonard Adleman 教授的课程对理论计算机科学产生了浓厚的兴趣。她申请了伯克利研究生院，解释说她对理论计算机科学的各个方面都感兴趣——除了量子计算。

“当时，量子计算听起来像是一个完全陌生的东西，我真的不太了解它，”她回忆道。

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

Mahadev 解释说：“协议就像谜题。对我来说，这类问题的进入门槛较低，因为我们可以立即开始考虑我们自己的协议，然后尝试看看它是如何工作的。” 她选择这个方向作为他自己的博士项目，Vazirani 称之为“漫长的道路”。

如果量子计算机可以解决经典计算机无法解决的问题，那并不意味着解决方案一定难以检查。例如，在考虑大数的因式分解时，量子计算机可以有效解决这个经典计算机无法处理的难题，并且其验证非常简单。更具体地说，虽然经典计算机无法计算特定的数字，但它能够将得到的大数乘以一个因子，看看得到的大数是否等于原始的大数——只要它相等，它就有正确的回答 。

然而，计算机科学家认为（我们最近朝着证明迈出了重要一步）量子计算机可以解决的许多问题并不具备这些特征。换句话说，经典计算机不仅不能解决这类问题，甚至无法判断给定的解决方案是否正确。考虑到这一点，安大略省滑铁卢周边理论物理研究所的物理学家 Daniel Gottesman 在 2004 年左右提出了一个问题，即是否有可能建立一个协议，让量子计算机能够证明其声称的计算确实完成了。

四年内，量子计算研究人员已经有了部分答案。两个团队独立提供了证明。与使用纯粹的经典验证计算机相比，在量子计算机内部构建一个小型验证系统有望证明量子计算机的计算过程。研究人员后来改进了该方法，并证明对所有验证器的需求最终归结为测量单个量子比特的能力。

2012 年，包括 Vazirani 在内的一组研究人员证明，如果一台量子计算机由两台无法相互通信的独立量子计算机组成，则可以通过经典验证计算机对其进行检查。但是，本文的结果只适用于这个特定的案例，似乎无法扩展到其他更广泛的应用场景。“我认为有很多人认为这行不通，”戈特斯曼说。

大约在同一时间，Mahadev 遇到了这个重要的验证问题。起初，她希望得出一个“无条件”的结论，即不对量子计算机能做什么或不能做什么做任何假设。但在朝这个方向进行了一段时间的无果探索之后，Vazirani 提出了使用“后量子”方法进行密码学的可能性——换句话说，研究人员认为密码学超出了量子计算机的处理能力。当然，他们也不太确定。（这里需要强调的是，用于在线交易等交易的RSA加密算法不属于后量子密码学，因为大型量子计算机完全可以解决这种依赖大数分解困难的加密方法。）

2016 年，Mahadev 和 Vazirani 在另一个被证明至关重要的问题上取得了进展。现在，旧金山 OpenAI 的计算机科学家 Paul Christiano 正在与他们合作开发一种使用密码学的方法，让量子计算机能够构建所谓的“秘密状态”——一种已经可以验证秘密的经典验证计算机不需要量子计算机本身。状态被描述。

他们提出的程序依赖于所谓的“陷阱门”功能——这些功能很容易执行，但除非你有加密密钥，否则很难逆转。（但研究人员还不知道如何真正构建适合量子计算机的陷阱门功能，这将是未来研究的主题。）该功能还需要“二合一”，即每个输出对应两个不同的输入。可以想象，如果要对一个数字求平方，那么除了数字 0 之外，每个输出结果（如 9） 都有两个对应的输入（3 和 -3）.

使用这个函数，我们可以在量子计算机中创建一个秘密状态，方法是首先要求计算机创建一个叠加所有可能输入的函数（听起来很复杂，但计算机实际上很简单）。之后，计算机被要求将函数应用于这个大叠加，从而建立一个新的状态——函数所有可能输出的叠加集。输入和输出叠加集将相互纠缠，这意味着对一个的测量将立即影响另一个。

接下来，要求计算机测量输出状态并报告结果。这种测量会将输出状态折叠成单个可能的输出，输入状态将立即折叠以匹配输出——因为两者是相互纠缠的。例如，如果使用square函数，那么如果输出状态为9，则输入将折叠为3和-3的叠加。

但是请注意，我们在这里使用了陷门函数。我们有活板门的钥匙，所以我们可以很容易地找出构成输入叠加的两种状态。然而，由于量子计算机没有这个密钥，它不能简单地测量输入叠加来找到它的组成。这主要是因为测量将结果进一步折叠，使得量子计算机只能找到两个输入结果之一。

2017 年，Mahadev 通过使用一种名为 Learning With Errors（简称 LWE）的密码技术发现了秘密状态方法的核心——即构建活板门功能。使用这些陷门函数量子密码学的基础是，她能够创建一个量化版本的盲计算，云计算用户可以使用它来掩盖他们的数据，确保云计算机即使在处理内容时也无法读取内容。不久之后，Mahadev、Vazirani 和 Christiano 开始与 Vidick 和 Zvika Brakerski（以色列魏茨曼科学研究所）合作，进一步完善这些陷阱门功能，旨在为使用秘密状态方法的量子计算机开发一种高度可靠的方法。可证明的随机数生成方法。

Mahadev 本可以以这样的优异成绩毕业，但她决定继续工作，直到验证问题完全解决。“我从没想过毕业，因为我的目标没有毕业的概念，”她说。

虽然目前还不清楚她是否能够解决问题，但她说，“我愿意花时间学习我感兴趣的东西，所以这不是浪费时间。”

不可变

Mahadev 尝试了从秘密状态方法到验证协议的所有方法，但有一段时间，她也陷入了困境。之后，她想了想：研究人员已经证明，如果验证计算机可以测量量子比特，那么验证计算机就可以检查量子计算机。根据定义，经典验证计算机缺乏这种能力。但是，如果经典验证计算机能够以某种方式强制量子计算机自行执行测量并如实报告呢？

Mahadev 意识到，其中最棘手的部分是让量子计算机在询问验证计算机要求测量什么之前承诺了解验证计算机的状态——否则，计算机很容易欺骗验证计算机。这就是秘密状态方法发挥作用的地方：Mahadev 的协议要求量子计算机首先创建一个秘密状态量子密码学的基础是，然后将其与它应该测量的状态纠缠在一起。只有这样，计算机才能确定要执行哪种类型的测量。

由于计算机不知道什么构成了秘密状态，但验证计算机知道，Mahadev 强调，量子计算机不能在不留下明显对偶痕迹的情况下作弊。本质上，维迪克写道，计算机测量的量子比特已经“一成不变”。这样，只要测量看起来是正确的，验证计算机就可以确信它是正确的。

维迪克写道：“这是一个非常好的主意！每次马哈德夫解释它时我都感到震惊！”

Mahadev 的验证协议——连同随机数生成器和盲加密方法——基于量子计算机无法破解 LWE 的假设。目前被广泛认为是后量子密码学领域的领先候选者，LWE 可能很快就会被美国国家标准与技术研究院采用作为一种新的加密标准，以取代现有的量子计算机可以破解的标准。但 Gottesman 警告说，这并不能保证量子计算机的处理能力。“然而，到目前为止，解决方案是可靠的，没有人发现它可以被破解的证据，”他说。

无论如何，Vidick 写道，该协议对 LWE 的高度依赖使 Mahadev 的结果具有双赢的潜力。量子计算机欺骗协议的唯一方法是让量子计算世界中的某个人弄清楚如何破解 LWE——这本身就是一项了不起的成就。

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

Aaronson 表示，Mahadev 的协议在未来五年内可能不可行，但“这并不完全只是幻想。在量子计算机发展的下一阶段，如果一切顺利，每个人都可以开始思考。”

考虑到技术发展的惊人速度，相信下一阶段应该很快就会到来。毕竟，就在五年前，维迪克提到研究人员认为量子计算机距离真正解决传统计算机无法解决的问题还需要几年的时间。“目前，人们认为这种能力将在未来一到两年内可用。”

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

但理论计算机科学家认为，马哈德夫对量子计算和密码学的统一并不是终点，而是希望证明更丰富思想的探索者的新起点。

Aharonov 说，“我认为未来会有很多后续发展，我期待 Mahadev 做出更多令人兴奋的贡献。”