乌尔米拉·马哈德夫（Urmila Mahadev）在治安法院工作了八年，以寻求对量子计算最基本问题之一的答案：我们如何知道量子计算机至少在量子水平上做了什么？
从大多数研究生的角度来看，2017年春天，乌尔米拉·马哈德夫（Urmila Mahadev）处于良好状态。 她刚刚解决了量子计算的关键问题-计算机科学领域，并从量子物理学的奇异定律中汲取了它的功能。 结合她的早期作品，马哈德夫（Mahadev）的新成果描述了所谓的 得克萨斯大学奥斯汀分校的IT专家
Scott Aaronson说：“瞎眼的计算使她显然是后起之秀。”
当时28岁的马哈德夫（Mahadev）已经在加州大学伯克利分校的研究生院就读了七年级，这比大多数学生失去耐心并想完成学业所需的时间要长得多。 然后，她终于得以写出“出色的博士论文”，她在伯克利的策展人
Umesh Vazirani说。
但是马哈德夫还没有完成那一年的学习。 她甚至不考虑这个问题。 还没完成
五年多来，她从事另一项研究任务，亚伦森称其为“量子计算领域最基本的问题之一”。 即：如果您要求一台量子计算机为您进行计算，您如何知道它是否遵循您的指令，实际上，它是否在量子水平上做某事？
这个问题可能很快将不再纯粹是学术性的。 研究人员希望，不会过去很多年，量子计算机将能够在解决许多问题上提供指数加速，从模拟黑洞附近的情况到模拟大蛋白质的折叠。
但是，一旦一台量子计算机能够执行传统计算机无法执行的计算，我们如何知道它能够正确执行这些计算呢？ 如果您不相信普通计算机，理论上您可以自己仔细研究其计算的每个步骤。 但是量子计算机天生就抵制这种检查。 首先，它们的工作非常复杂：要记录仅由几百个量子位或qubit组成的计算机内部状态的描述，您将需要一个比观察到的宇宙还要大的硬盘。
即使您有地方可以撰写此说明，也无法将其拆分。 量子计算机的内部状态通常是许多不是量子而是经典状态（例如活着和死掉的薛定ding猫）的叠加。 但是，一旦您测量了量子态，它就会立即崩溃为经典态之一。 看看具有300个量子比特的量子计算机，您将只看到300个经典比特，零和一，礼貌地对您微笑。
瓦兹拉尼说：“量子计算机功能强大，但却神秘莫测。”
鉴于这些限制，计算机科学家长期以来一直在思考量子计算机是否可以提供绝对可靠的保证，确保它确实做到了自己声称的那样。 “量子世界和古典世界之间的相互作用是否足够强大，从而使这种对话成为可能？” 耶路撒冷希伯来大学的计算机科学家
Dorit Akharonova问。
在治安官第二年，马哈德夫被这项任务抓获，她甚至不完全理解为什么。 在随后的几年中，她尝试对她使用一种方法，然后再对另一种方法使用。 她说：“我有很多这样的时刻，我觉得自己做对了一切，然后一切都崩溃了，要么很快，要么一年后。”
但是她拒绝放弃。 Mahadev表现出了坚定的决心，以至于Vazirani从未见过。 他说：“从这个意义上说，乌尔米拉绝对是非凡的。”
而现在，经过八年的研究生学习，马哈德夫成功了。 她创建了一个交互式协议，不具备量子功能的用户仍然可以使用密码学来限制量子计算机并将其定向到任何地方，完全有信心量子计算机遵守命令。 瓦兹拉尼说，马哈德夫的方法给用户“计算机无法摆脱的压力杠杆”。
亚伦森说：“绝对令人惊讶的是，一个研究生仅凭这一成绩就可以实现。”
Mahadev现在是伯克利的一名研究博士后，于2018年10月在年度
计算机科学研讨会上提出了她的协议，这是今年在巴黎举行的最大规模的计算机会议之一。 观众给她的作品颁发了“最佳作品”和“最佳学生作品”奖，这是理论计算机科学领域专家的罕见奖项。
加利福尼亚理工学院的IT专家
托马斯·维迪克 （
Thomas Widick ）过去曾与Mahadev一起工作，他在博客中
称其结果为“近年来在量子计算和理论信息学的交汇中出现的最杰出的思想之一。”
计算机科学领域的研究人员不仅对Mahadev协议的功能感到满意，而且对帮助解决这一问题的全新方法感到高兴。 Vidik写道，在量子领域使用经典密码学是“一个真正的创新想法”。 “我认为这些想法还会带来许多其他结果。”
很长的路
马哈德夫在洛杉矶一个医生家庭长大，并在南加州大学学习，在那里她从一个地区搬到了另一个地区，最初只是说服了她自己不想当医生。 然后，她对理论计算机科学课程非常感兴趣，这是著名的RSA加密算法的创建者之一伦纳德·艾德曼（Leonard Aidleman）教授的课程。 她进入了伯克利的研究生院，并在一份解释性说明中指出，她对理论计算机科学的所有方面都感兴趣，但量子计算除外。
她说：“这是我最不知道的完全陌生的东西。”
但是，一旦来到伯克利，她很快就改变了主意，受到了瓦兹拉尼的解释。 Vazirani说，他向她介绍了寻找确认量子计算的协议的方法，这项任务“确实使她的想象力发挥了作用”。
“协议就像难题一样，”马哈德夫解释说。 “对我来说，比其他问题要容易得多，因为在这里您可以立即开始思考协议，将它们分解成碎片，然后观察它们的工作原理。” 正如Vazirani所说，她为自己的博士学位选择了这项任务，走了“很长的路要走”。
如果量子计算机可以解决经典计算机无法解决的问题，那么这并不意味着解决方案将难以验证。 以分解为大数的问题为例-人们认为大型量子计算机可以有效地解决它，但与此同时，它仍然超出了任何经典计算机的能力。 但是，即使经典计算机无法分解该数字，它也可以轻松地检查量子结果是否正确-它只需要乘以所有因子，看看它们是否给出正确的答案。
但是，计算机科学家认为（并且最近已朝证明方向迈出了一步）量子计算机可以解决的许多任务都没有这种功能。 换句话说，经典计算机不仅无法解决它们，甚至无法识别所提出的解决方案是否正确。 结果，在2004年，滑铁卢周边研究所的理论物理学家
丹尼尔·戈茨曼 （
Daniel Gottsman）询问是否有可能提出任何允许量子计算机向非量子观察者证明他确实完成了他声称的内容的协议。
四年来，量子计算研究人员找到了部分答案。 两个不同的小组
表明 ，一台量子计算机可以证明其计算，但不能证明是纯粹的经典验证者，而是可以使用另一台非常小的量子计算机。 研究人员后来通过证明测试仪仅需要一次测量一个qubit的状态的能力来改进了这种方法。
在2012年，包括瓦兹拉尼（Vazirani）在内的一组研究人员表明，如果一个完全经典的验证程序是由一对彼此不通信的量子计算机执行的，则它们可以验证量子计算。 然而，戈茨曼说，他们的方法是专门为这种情况设计的，任务似乎陷入了僵局。 “我认为可能有人认为没有进一步的方法。”
大约在这个时候，马哈德夫面临确认的问题。 最初，她试图产生“无条件”结果，但没有说明量子计算机可以做什么和不能做什么。 但是，在她完成这项任务一段时间后没有成功，瓦齐拉尼提出使用“后量子”密码学的可能性-也就是说，密码学，据研究人员称，即使是肯定的，黑客攻击也超出了量子计算机的能力。他们不知道。 （诸如用于加密在线传输的RSA算法之类的方法不是后量子的-大型量子计算机可以破解它们，因为它们的安全性是基于分解大量数字的难度）。
2016年，马哈德夫（Mahadevv）和瓦济拉尼（Vazirani）在完成另一项任务时取得了突破，这将在未来发挥决定性作用。 他们与旧金山OpenAI公司的IT专家
Paul Cristiano一起，设计了一种使用加密技术使量子计算机进入“秘密状态”的方法，这种状态由传统的验证程序描述，而不是由量子计算机本身描述。
他们的过程基于“陷阱”功能，该功能易于执行，但很难逆转，除非您拥有秘密的加密密钥。 （当时，研究人员还不知道如何制作合适的陷阱-后来出现了）。 该函数还必须具有“二合一”属性，这意味着对于每组输出数据，都有两组不同的输入数据。 例如，我们可以想象一个函数对数字进行平方-除了数字0，对于每个结果（例如9），还有两个对应的输入数字（3和-3）。
拥有类似的功能，您可以使量子计算机进入秘密状态，如下所示。 首先，您要求计算机构造功能的所有可能输入数据的叠加的任务（这对计算机来说似乎是一项艰巨的任务，但实际上很简单）。 然后，您告诉计算机将该功能应用于该巨大的叠加，从而创建一个新状态，该状态是该功能所有可能输出的叠加。 输入和输出的叠加将被混淆，这意味着测量其中的一个会立即影响另一个。
然后，您命令计算机测量最终状态并报告结果。 度量会将状态折叠为一组可能的输出数据，并且输入状态也会折叠为与之对应，因为它们很困惑-例如，如果我们使用平方函数，则如果输出状态为9，则输入将折叠为叠加3并-3。
但是请记住，我们使用了陷阱函数。 我们有陷阱的秘密密钥，因此我们可以很容易地找出组成输入叠加的两个状态。 量子计算机不能。 而且他不能简单地测量输入叠加来找出它的组成部分，因为这样的测量将使输入叠加更进一步，从而使计算机成为两个选项中的一个，而无法计算另一个。
2017年，马哈德夫（Mahadev）了解了如何使用称为
学习错误的密码
学 （LWE）创建基于秘密状态方法的陷阱函数。 使用这些陷阱功能，她能够创建“盲”计算的量子版本，云计算系统的用户可以使用该版本隐藏数据，以便云计算机即使使用它们执行计算也无法读取它们。 此后不久，马哈德夫（Mahadev），瓦兹拉尼（Wazirani）和克里斯蒂亚诺（Cristiano）与Vidik和
Zwika Brackerski （来自以色列魏兹曼研究所（Weizmann Institute））合作，进一步提高了这些功能的质量，并使用秘密状态方法来开发一种有保证的方式，使量子计算机可以生成
可证明的随机数 。
Mahadev可以根据这样的结果获得学位，但是她打算继续工作直到解决确认问题。 她说：“我从未考虑过发布，因为我的目标根本不是发布。”
有时候，解决这个问题的能力的不确定性给她带来了压力。 但是，她说：“我花时间学习了我感兴趣的事情，因此，这种消遣不能称为浪费。”
刻在石头上
Mahadev尝试对秘密状态方法使用不同的方法来组织确认协议，但是一段时间以来，这没有产生任何结果。 然后一个想法浮现在脑海：研究人员已经表明，测试人员可以检查量子计算机是否具有测量量子位的能力。 根据定义，经典验证程序没有这样的机会。 但是，如果经典的测试人员能够以某种方式使量子计算机自行进行测量并诚实地报告其结果呢？
难题将是马哈德夫（Mahadevv）如何理解让量子计算机承诺在检查员要求他进行哪种测量之前进行一些特定的测量-否则，计算机将很容易欺骗他。 这就是秘密状态方法起作用的地方。 Mahadev协议要求量子计算机首先创建一个秘密状态，然后将其与它必须测量的状态混淆。 然后计算机才知道需要进行哪些测量。
由于计算机不了解检查员已知的秘密状态的内部细节，因此马哈德夫（Mahadev）证明了量子计算机无法以任何方式作弊，对此毫无疑问。 Vidik写道，实际上，计算机需要测量的量子位“刻在密码石上”。 因此，如果测量结果看起来像正确的证明，那么检查员可以确定它是正确的。
“这真是个好主意！ -Vidik写道。 “每次Urmila向她解释时，她都会打我。”
Mahadev的确认协议以及随机数生成器和盲加密功能取决于量子计算机无法破解LWE的假设。 到目前为止，LWE被普遍认为是后量子密码技术的领先候选者，不久，美国国家标准技术研究院就可以将其批准为新的密码标准，以取代那些容易被量子计算机破解的密码标准。 戈茨曼警告说，但这不能保证它实际上对量子计算机是安全的。 他说：“但是到目前为止，一切都还清楚。” “还没有人发现破坏它的可能性的证据。”
Vidik写道，无论如何，该协议对LWE的信心使Mahadev在任何情况下都是制胜法宝。 量子计算机欺骗协议的唯一方法是，如果量子计算领域的某人想出了如何破解LWE，这本身就是一个了不起的成就。
在可预见的将来，Mahadev协议不太可能在真实的量子计算机上实现。
到目前为止，从实际角度来看，他需要太多的计算能力。但是将来随着量子计算机的发展，这可能会改变，研究人员可以简化该协议。该协议不太可能在未来五年内出现，但“这不是科幻小说，”亚伦森说。 “关于这一主题，在量子计算机的下一阶段中，如果一切按预期进行，将已经有可能开始思考。”并且，鉴于该领域的发展速度，这一阶段可能比预期的要早开始。毕竟，仅仅五年前，研究人员认为，直到量子计算机无法解决传统计算机无法解决的任何问题之前，这将需要更多年。他说：“现在，人们相信这将在一两年内发生。”马克哈杰夫（Makhadev）解决了她最喜欢的问题，但仍处于混乱状态。Mahadev说，她想了解到底是什么使这个问题如此适合她。“现在我需要寻找其他问题，所以很高兴找出来。” 但是理论信息学专家认为，量子计算和密码学的结合是马哈德夫成功的，而不是历史的终结，而仅仅是对可能成为新思想的丰富来源的研究的开始。“在我看来，很多派生的想法都会随之而来，”亚伦森说。“我期待Urmila的新成果。”