ACM通信
研究突出了
技术视角:关于证明、纠缠和对策
什么是证明?哲学家和数学家几个世纪以来一直在思考这个问题。理论计算机科学对这个深刻的问题提供了一个严谨的处理方法。我们可以将证明看作是一个双人游戏:一个全能但不受信任的证明者提供命题的证明，以及一个计算能力较弱的验证者只需要验证它。事实上，NP问题完全可以用这种验证者-证明者语言来表示。把证明看作是博弈是非常有成效的。例如，发明了互动证明，类似于苏格拉底对话录;在这些游戏中，证明者和验证者交换消息(可能是随机的)。为什么只有一个证明呢?在多证明交互式证明(MIP)中，涉及到多个非通信证明。 This gave birth to beautiful concepts such as zero knowledge and probabilistically checkable proofs (PCPs) with immense impact not only theoretically but also in practice, for example, in digital currency.
本文研究了量子相互作用的证明。在这里，证明者被允许共享一个纠缠量子态;这类似于共享一个随机比特串，只不过量子态具有那些有趣的、强于经典的相关性;一个典型的例子是爱因斯坦-波多尔斯基-罗森(EPR)状态，爱因斯坦说这种状态允许“幽灵般的超距离作用”。量子相关性能用来证明更有力的说法吗?
多证明子量子交互证明可解决的一类问题记为MIP＊．它的计算能力已经开放了超过15年。在接下来的旅行强制文件中，一个卓越的系列作品的顶点，这个问题最终得到了解决。虽然一开始人们认为MIP＊等于它的经典对应MIP，结果是MIP＊包含停止问题!结果不仅解决了顽固的MIP＊问题，但同时也解决了数学领域几十年来悬而未决的几个主要问题。是什么想法使这个结果如此深远?
最好开始我们进入MIP的旅程＊兔子洞的1991年的里程碑式的结果，表明MIP等于NEXP，一个放大版的NP，其中验证者需要检查指数级长的证明。在MIP中，验证者只与证明者交换多项式多的位——它如何在不完全读取证明的情况下验证证明呢?关键的工具是低次测试，它利用低次多项式的鲁棒性，允许验证者检查，使用很少的通信，两个证明保持一致的多项式。2011年，该协议被证明是安全的，即使对纠缠证明。米兰理工大学管理学院＊因此，它至少和经典版本一样强大。
但这篇论文的重点是MIP＊可证明比MIP大得多。纠缠有什么帮助呢?我们可以从2019年的一篇论文中得出见解，该论文首次表明，MIP＊严格大于MIP。本文证明了MIP＊包含一类需要双指数长证明(NEEXP)的问题。验证者如何检查这样的证明，即使在证明中指定一个位置也需要指数级的多位?
“纠缠”来拯救我们了。更准确地说，是纠缠态的一个显著特性，叫做自我测试。1964年，Bell设计了一款游戏，在该游戏中，两名处于EPR状态的玩家获胜的概率要比传统情况下的概率大得多。玩家最优策略的唯一性意味着获得最大成功概率作为他们的状态和测量是唯一最优的证明。这是量子力学刚性的一种显著形式。这就好像验证者可以窥见证明者的秘密量子实验室!此外，低次测试的量子版本支持仅使用多项式通信来验证指数级长纠缠态的自检。现在出现了一个令人难以置信的想法:尽管验证者的消息太短，无法指定双指数级长证明的指数级长问题，但它可以使用量子自我测试，有效地迫使证明者共享一个指数级大的纠缠态，然后自己正确地抽样他们的问题。
这个结果只是故事的开始;要解决停顿问题，就需要修改“纠缠压缩”的思想，这样它就可以递归地应用。大量的新障碍出现了，其解决方案是本文的力作。
令人兴奋的应用包括构建在任何有限维度都无法近似的无限代数，以及分离以前推测为相等的量子相关模型。自我测试与群体稳定性有关，这给群论中的主要问题带来了进展的希望。
如何解释这一计算机科学理论成果对纯数学的强烈影响?这里应用了pcp和其他强大的计算复杂性概念，但另一个方面可能是协议在结果中所扮演的角色。这些依赖于时间的独立步骤序列，构成了一种直观的方式来思考高度复杂的数学对象，这种方法似乎为物理和数学问题提供了一种新的视角。
数字图书馆是由计算机协会出版的。版权所有©2021 ACM, Inc.
没有找到条目