On Removing Interaction from Quantum Proofs
本文提供了正式证据，证明通用的类 Fiat-Shamir 编译程序无法在量子随机预言机模型中将量子交互式证明（特别是针对 QMA 的 -协议）转化为非交互式零知识论证，因为这类编译程序的存在将意味着 QMA 向 BQP 的坍缩。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
在密码学领域，人们一直渴望创造出既是非交互式又具有公开可验证性的证明系统。想象这样一个场景：一台计算机需要向一个陌生人证明它已经解开了一个难题，但它只能通过发送一条消息来完成证明。这个陌生人（验证者）必须能够在不需要任何密钥或预设条件的情况下检查答案，且该证明不能泄露关于解法的任何信息。对于经典问题，数学家们已经找到了将交互式对话转化为这种单次证明的方法，这种技术就像是一个数字锁，迫使证明者在看到验证者的提问之前就必须对自己的答案做出承诺。然而，当问题涉及量子力学时——即信息以脆弱的、叠加态的形式存在时——这种标准方法便碰壁了。核心难点在于，量子信息无法被复制或测量，否则可能会破坏其本身，这使得通常用于消除交互的技巧似乎无法应用。
这种不确定性留下了我们对量子安全理解中的一个重大空白。研究人员已经开发出了交互式协议，其中量子证明者可以向验证者证明一个解法，但这些协议需要往返通信。一个大问题是，是否存在一种通用方法可以剥离这种往返过程，并为这些量子问题创建单消息证明，类似于经典做法？如果这种方法存在，它将彻底改变我们验证量子计算的方式。如果不存在，则表明量子信息进行压缩和验证时存在一个根本性的限制。
康奈尔大学的一个研究小组现在提供了强有力的证据，表明这种通用方法并不存在。他们并非仅仅是猜测或模拟失败，而是构建了一个正式证明，表明如果这种用于消除交互的编译器是可能的，那么它会导致两个主要计算问题类之间的区别发生坍塌，从而导致逻辑矛盾。具体而言，他们证明了，如果一个“直线型”编译器（即一种利用单次通信将交互式量子协议转换为非交互式协议的编译器）能够以高可靠性工作，那么一类对量子计算机而言极其困难的问题将突然变得容易解决。这将意味着量子计算机比目前认为的要强大得多，而这种情形在大多数专家看来是极不可能的。
为了得出这一结论，作者设计了一个巧妙的反例。他们构想了一组量子证明协议，其中证明者的第一条消息使用一种特殊的量子锁进行了加密。在正常的交互中，验证者会解密这条消息以进行检查。然而，研究人员表明，任何试图将这种交互过程转换为单消息的过程，都会迫使编译器去测量加密的量子态。由于测量量子态会扰动它，编译器要么会破坏证明的有效性，要么会允许作弊者伪造证明。研究人员证明，如果编译器能够以某种方式绕过这种扰动并仍然产生有效的单消息证明，这本质上意味着编译器已经找到了一种在不被察觉的情况下窥探秘密解法的方法。
他们论证的核心依赖于量子加密中的一个属性，称为“追溯安全性”（retrospective security）。这一概念确保了即使攻击者看到了加密的最终结果，也无法判断该消息是真实的，还是事后创建的模拟占位符。研究人员表明，在一个成功的非交互式证明中，编译器必须表现得好像它在挑战发出之前就已经知道了消息，但量子力学的定律阻止了这一点，除非破坏消息。通过将这些概念交织在一起，他们构建了一个逻辑陷阱：如果编译器有效，它必须能够以一种破坏加密安全性的方式来区分真实消息和模拟消息。这种破坏反过来又使得编译器能够高效地解决一个难题。
这项研究并未排除创造非交互式证明的所有可能途径。它专门针对的是“直线型”编译器，这些编译器是目前用于经典方法的、最直接的类比。它也为更复杂、多步骤的策略是否可行，或者是否能为特定的问题子集创建证明留下了余地。然而，对于在经典计算机上运作良好的那种广义、通用的方法，本文提出了一个硬性的停止信号。研究结果暗示，量子信息的独特本质——其脆弱性和不可复制性——为像处理经典数据那样消除交互创造了一个根本性的障碍。这一结果理清了量子密码学的格局，告诉我们，实现公开可验证量子证明的路径可能需要全新的思想，而非仅仅是对旧思想的简单改编。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。