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)状态，爱因斯坦说这种状态允许“幽灵般的超距作用”。量子相关性可以用来证明更有力的陈述吗?

没有找到条目

登录阅读全文