二十年来，计算机科学家一直纠结于一个看似简单的问题：量子计算机能否验证那些经典计算机甚至无法描述的问题的解决方案？
事实证明，答案是肯定的，而证明长达96页。
由四名研究人员组成的团队，John Bostanci（西蒙斯研究所/哥伦比亚大学）、Jonas Haferkamp（波鸿鲁尔大学）、Chinmay Nirkhe（华盛顿大学）和Mark Zhandry（斯坦福大学），证明了量子证明在至少一个计算问题上绝对比经典证明更强大。该论文在理论计算机科学顶级会议STOC 2026上获得了最佳论文奖。
“这是一个美妙的结果，”未参与此项工作的麻省理工学院量子信息理论家Anand Natarajan表示。”其中涌现出许多新鲜的想法。”
证明实际揭示了什么
该问题属于理论计算机科学的一个分支，称为复杂性理论，它研究解决问题所需资源如何随问题规模增长而变化。其核心是QMA（Quantum Merlin-Arthur）类和QCMA（Quantum-Classical Merlin-Arthur）类。
可以这样理解：想象一名学生（Merlin）试图说服老师（Arthur）某个数学命题为真。在QMA场景中，Merlin可以提交一个量子态（一组脆弱的量子比特）作为证据。在QCMA场景中，Merlin只能提交经典的比特串。这个问题由Dorit Aharonov和Tomer Naveh于2002年首次提出，核心是量子版本是否严格更强大。
该团队通过构建一个称为”频谱相合问题”（spectral forrelation problem）的问题证明了这一点。在该问题中，量子证人可以工作，而经典证人则不能。这个问题类似于一种法医谜题：给定两组测量数据，判断它们来自同一量子对象还是两个不同的对象。量子证人可以直接编码两个数据集之间的关系，而经典证人根本无法携带足够的信息。
证明采用了一种称为”反证法”的策略。研究人员首先假设存在该问题的经典证明。然后他们表明，这样的证明将是可重复使用的，可以用同一个经典证人来回答许多不同的查询。但他们证明，这种可重用性将允许解决一个被证明是不可能完成的困难的猜测任务。这个矛盾意味着最初的假设是错误的：不存在任何经典证明。
“我几乎是偶然开始思考这个问题，”Zhandry告诉Quanta Magazine。他2024年11月的个人研究解决了一半的问题，但未能完成。四人聚在一起，经过九个月的紧张工作，”它完全主导了我的一年。我基本上没怎么做其他事情，”Bostanci说，他们完成了完整的证明。
第二个独立证明
值得注意的是，第二个团队使用完全不同的方法独立得出了相同的结论。麻省理工学院的Andrew Huang和Vinod Vaikuntanathan与Bostanci一起，于2026年2月提出了第二个预言机分离结果（arXiv:2602.09385）。这一结果在概念上更简单，并且首次实现了BQP/qpoly类与BQP/poly类之间的分离（后者是关于量子建议的相关领域）。
两个独立的证明，一个巧妙但复杂，另一个更简单且更具扩展性，加强了结果的可靠性。
预言机的局限性说明
两个证明都是”预言机分离”：它们表明QMA和QCMA相对于一个黑箱函数（预言机）是不同的，计算机可以查询该函数但无法看到其内部运作。没有预言机的无条件证明将需要复杂性理论的革命性进步，相当于证明P不等于PSPACE。
尽管如此，预言机分离仍被视为非常有力的证据。主要复杂性类之间的每一个已知分离最初都是作为预言机结果出现的，随后才被完善。该领域的历史表明，当两个类相对于预言机不同时，它们在现实中几乎也总是不同的。
“我们拥有迄今为止最有力的证据表明答案是肯定的，量子证明更强大，”研究人员在论文中指出。
为何重要
对于在职的量子计算机物理学家来说，这一结果可能不会改变日常工作。将这两个类别区分开来的问题（频谱相合问题）是精心构造的人为问题。但证明中开发的技术，特别是将问题视为玻色子处理的”二次量子化”压缩预言机方法，有望在密码学和量子算法设计中找到应用。
该结果还解决了量子复杂性理论中的一个主要开放性问题。量子复杂性理论研究的是用量子资源可以计算什么、不能计算什么的根本性问题。对于二十年来一直致力于攻克QMA与QCMA问题的研究人员来说，答案终于揭晓了。
婷 翻译
Sources
- Quanta Magazine: “Researchers Reveal the Power of ‘Quantum Proofs'”（2026年7月6日）。https://www.quantamagazine.org/researchers-reveal-the-power-of-quantum-proofs-20260706/
- Bostanci, J., Haferkamp, J., Nirkhe, C., Zhandry, M. “Separating QMA from QCMA with a Classical Oracle.” arXiv:2511.09551. STOC 2026 Best Paper.
- Bostanci, J., Huang, A., Vaikuntanathan, V. “Separating Quantum and Classical Advice with Good Codes.” arXiv:2602.09385（2026年2月）。