计算机检查任务的范围已经扩大。 由于发生了什么秘密因素？ 由于量子纠缠。
想象一下有人来找你，说他有一个可以揭示宇宙秘密的神谕。 您可能对此感兴趣，但是很难相信。 您想提出一种方法来确认预言家说的是实话。
这是计算机科学的主要问题。 有些任务太难在合理的时间内解决。 但是他们的决定很容易验证。 鉴于此，计算机科学家想知道：一项任务有多复杂，其解决方案仍可得到验证？
事实证明，这个问题的答案是：几乎难以想象的复杂。
在2019年4月发表的
一篇论文中，两位计算机科学专家从根本上增加了属于“难以解决，易于验证”类别的任务数量。 他们描述了一种方法，该方法可以验证几乎难以理解的问题的解决方案。 加州理工学院的IT专家Thomas Widick说：“这听起来很疯狂。”
该研究适用于根据量子力学的非直观规则进行计算的量子计算机。 量子计算机几乎没有出现，但在未来，它们有可能彻底改变计算。
实际上，这项新工作使我们可以利用那个全能的神谕。 即使甲骨文承诺为您提供现成的解决方案，以解决其解决方案的可能性远远超出您的能力，但仍有一种方法可以检查甲骨文是否在说真话。
到宇宙的尽头
当问题难以解决但易于验证时，查找解决方案会花费很长时间，而检查特定解决方案的正确性则不需要。 例如，假设某人向您显示一个图形-用线（边）连接的一组点（顶点）。 一个人问是否有可能用三种颜色为图形的顶点着色，以使没有两个相连的顶点具有相同的颜色。
三种颜色的任务很难解决。 在一般情况下，搜索顶点着色（或确定不存在这种着色）所需的时间随着图形尺寸的增加而呈指数增长。 例如，如果搜索具有20个顶点的图的解需要3
20 ns（即几秒钟），那么对于具有60个顶点的图的搜索将花费3
60 ns，这是当前宇宙年龄的100倍。
但是，假设有人声称用三种颜色画了伯爵。 验证此应用程序不会花费很多时间。 您只需要一个一个地遍历所有顶点，研究与它们关联的顶点。 随着图的大小增加，此检查的时间缓慢增加-为
多项式 。 因此，计算机检查60个顶点的颜色不会比检查20个顶点的颜色花费更多的时间。
麻省理工学院的物理学家
约翰·赖特 （
John Wright）与加州理工学院的
阿南德·纳塔拉让 （
Anand Natarajan）共同撰写了这篇文章，他说：“使用三种正确的颜色，可以很容易地测试其性能。”
在1970年代，计算机科学家确定了一类易于验证的任务，即使其中一些任务难以解决。 他们称此类为NP，
是不确定的多项式时间 。 从那时起，在计算机科学领域，对NP类的研究比以往更多。 特别是，计算机科学家想知道当测试算法收到验证解决方案正确性的新方法时，此类如何变化。
正确的问题
在纳塔拉让和赖特工作之前，检查的力量有了两次大的提高。
要理解第一个，请想象您不区分颜色。 有人将两个立方体放在您面前的桌子上，并询问它们是相同颜色还是不同颜色。 您无法完成此任务。 此外，您无法确认其他人对该问题的解决方案的正确性。
但是，您可以问这个证明人问题。 假设证明者告诉您多维数据集具有不同的颜色。 您将其中一个称为“多维数据集A”，将另一个称为“多维数据集B”。 然后，您将它们隐藏在背后，并意外地在它们之间交换位置。 然后，您打开多维数据集，并要求证明者找到模具A。
如果多维数据集具有不同的颜色，这是一个非常简单的问题。 证明者将识别多维数据集A（如果这是一个红色多维数据集），并将每次正确地确定它。
但是，如果多维数据集具有相同的颜色-证明者错误地称其为不同-证明者只能猜测哪个是哪个。 因此，他只能在50％的情况下正确确定多维数据集A。 通过不断询问证明者关于他的决定的信息，您可以确认它是否正确。
阿南德·纳塔拉詹（Anand Natarajan）和约翰·赖特（John Wright）赖特说：“审查员可以向证明人发送问题，也许在谈话结束时，审查员会更加确信答案。”
1985年，三位计算机科学家证明了这种交互式证据可用于确认比NP问题更复杂的问题的解决方案。 他们的工作创造了新的任务类别，即IP，“交互式多项式时间”。 用于确认立方体颜色的方法可用于确认对更复杂问题的答案。
第二个突破发生在同一十年。 这看起来像是警方调查的逻辑。 如果您认为有两名犯罪嫌疑人犯罪，则不会一起审问。 您将在不同的房间中询问它们，并将一个答案与另一个答案进行比较。 通过单独采访他们，您可以揭示出比拥有一个嫌疑人更多的真相。
赖特说：“这两名犯罪嫌疑人将无法建立一个分布一致的故事，因为他们不知道其他答案是什么。”
1988年，四位计算机科学家证明，如果让两台计算机分别解决同一问题，然后分别对它们进行提问，则可以确认一类甚至比IP大的问题：MIP类，具有大量证据的交互式证据。
使用此方法，例如，对于大小比NP中的图形快得多的图形序列，可以确认为三种颜色着色图形的正确性。 在NP中，图形大小线性增加-顶点数量可以从1增加到2，最多增加3，最多增加4，依此类推-这样图形的大小不会成比例地大于检查着色所需的时间。 但是在MIP中，图顶点的数量从2
1到2 2，2
3，2 4呈指数增长。
结果，这些图形变得太大，甚至无法容纳计算机的内存，该内存必须遍历顶点列表并检查颜色。 但是，仍然可以通过询问两个证明者不同但相关的问题来检查颜色。
在MIP中，测试人员有足够的内存来运行程序，该程序使我们能够确定图形的两个顶点是否通过边连接-并且他可以验证测试人员的答案以确保着色正确。
从经典计算机到NP到IP和MIP，扩展了难以解决但易于验证的任务列表。 但是量子计算机的工作方式却大不相同。 几十年来，还不清楚他们的使用方式如何改变这种状况-在他们的帮助下验证解决方案更容易或更困难？
Natarajan和Wright的新著作为这个问题提供了答案。
量子技巧
量子计算机执行使用量子位或量子位的计算。 它们具有
相互缠结的特性。 当两个量子比特甚至大型量子比特系统混淆时，这意味着它们的物理特性以某种方式相互影响。
Natarajan和Wright在他们的新著作中考虑了一个场景，其中包括两个不同的量子计算机，其中一个的量子位与另一个的量子位相混淆。
这样的设置似乎会降低响应验证的质量。 具有许多证明者的交互式证据的全部力量正好来自您可以分别采访两名证明者并验证其答案的事实。 如果证明者的答案相同，则很可能是正确的。 但是，如果两个证明者的量子态混淆了，他们似乎会有更多机会一贯坚持错误答案的正确性。
确实，当具有两个纠缠量子计算机的场景于2003年首次
揭晓时，计算机科学家建议纠缠将减少验证的可能性。 维迪克说：“包括我在内的每个人的明显反应是，这种情况下的证明者有更多机会。” “他们可以使用混淆来链接他们的答案。”
但是，尽管最初有悲观情绪，但维迪克还是花了几年时间试图证明相反的观点。 在2012年，他和
伊藤刚（Tsuyoshi Ito） 证明了使用缠结的量子计算机测试MIP中所有任务的能力。
现在，纳塔拉让和赖特已经证明了情况甚至更好：在错综复杂的帮助下，人们所面临的问题比没有错的情况更大。 可以使纠缠的量子计算机之间的连接反向，从而使验证者受益。
要了解如何执行此操作，请从MIP调用该过程以检查大小呈指数增长的图形的着色。 测试者没有足够的内存来存储整个图形，但是他有足够的内存来确定两个相连的顶点，并向测试者询问有关这些顶点颜色的问题。
在Natarajan和Wright考虑的一类问题中，称为NEEXP，这是不确定的两次指数时间，其图的增长速度甚至比MIP还要快。 NEEXP中的图形以“双指数速率”增长。 图中的顶点数不是以2-2
1，2 2，2
3，2 4等的角度增长，而是以2-2 2
1，2 2
2，2 2
3 3，2的角度增长。
2 4 ，依此类推。 结果，这些图形很快变得非常庞大，以至于检查人员甚至无法找到一对相连的顶点。
Natarajan说：“要识别顶点，需要2
n位，这比验证程序在内存中的位数还要大。” 但是，Nataarajan和Wright证明即使没有确定需要询问哪些顶点的证据的能力，也可以检查三种颜色的双指数图的着色。 事实是，您可以让证明者自己选择正确的问题。
让计算机对自己的决定进行审问的想法对计算机科学家来说听起来像要求可疑犯罪分子审问自己一样合理，这绝对是一个愚蠢的主张。 那只是Natarajan，Wright证明事实并非如此。 原因是混乱。
赖特说：“纠缠的国家是共享资源。” “我们的整个协议是了解如何使用此共享资源来创建相互关联的问题。”
如果量子计算机感到困惑，那么它们对顶点的选择将相互关联，并给出正确的问题集以检查三种颜色的颜色。
同时，检查人员不需要将两个量子计算机交织在一起，从而使他们对这些问题的答案相互关联（这类似于两个可疑犯罪分子如何将其假借口关联起来）。 另一个奇怪的量子特征解决了这个问题。 在量子力学中，
不确定性原理禁止我们同时知道粒子的确切位置和动量-如果您测量一个属性，则会破坏有关另一个属性的信息。 不确定性原理严重限制了您对量子系统的任何两个“互补”性质的了解。
Natarajan和Wright在他们的工作中使用了它。 为了计算顶点的颜色，他们迫使两个量子计算机进行互补测量。 每台计算机都会计算自己顶点的颜色，从而破坏有关另一台计算机的所有信息。 换句话说，混乱使计算机能够提出相关问题，但不确定性原则禁止它们合谋回答问题。
Vidik说：“我们需要让证明者忘记，这是Natarajan和Wright在他们的工作中所做的主要事情。” “他们迫使证明者通过测量擦除信息。”
他们工作的结果几乎可以说是存在的。 在发表作品之前，我们可以完全放心获得的知识的限制要少得多。 如果从NEEXP集合中得到问题的答案，我们只需要凭信心接受即可。 但是Natarajan和Wright突破了这些界限，从而有可能从更大范围的计算问题中确认答案。
现在他们已经做到了，现在还不清楚下一个可验证性边界在哪里。 佐治亚理工学院的IT专家Lance Fortnau说：“可能还有更多。” “他们为下一步行动提供了机会。”