二十年来，计算机科学家一直在与一个看似简单的问题作斗争：量子计算机能否验证经典计算机甚至无法描述的问题的解决方案？
答案是可以，而这项证明长达96页。
由四名研究人员组成的团队，，John Bostanci（西蒙斯研究所/哥伦比亚大学）、Jonas Haferkamp（波鸿鲁尔大学）、Chinmay Nirkhe（华盛顿大学）和Mark Zhandry（斯坦福大学），，已经证明，对于至少一个计算问题，量子证明在类别上比经典证明更强大。该论文在理论计算机科学顶级会议STOC 2026上获得了最佳论文奖。
“这是一个美丽的结果，”未参与该工作的麻省理工学院量子信息理论家Anand Natarajan表示。”它带来了许多新鲜、新颖的想法。”
证明实际展示的内容
该问题属于理论计算机科学的一个分支，，复杂性理论，它研究解决问题所需的资源如何随问题规模扩大而变化。其核心是QMA（量子梅林-阿瑟）和QCMA（量子-经典梅林-阿瑟）类。
可以这样理解：想象一名学生（梅林）试图让一位老师（阿瑟）相信某个数学陈述是正确的。在QMA场景中，梅林可以提交一个量子态（一组脆弱的量子比特）作为证据。在QCMA场景中，梅林只能提交一串经典比特。这个问题由Dorit Aharonov和Tomer Naveh于2002年首次提出，即量子版本是否严格更强大。
该团队通过构建一个称为”谱关联问题”的问题证明的确如此。对于该问题，量子证据有效而经典证据无效。这个问题是一种取证谜题：给定两组测量数据，判断它们来自同一个底层量子对象还是两个不同的对象。量子证据可以直接编码两组数据之间的关系，而经典证据根本携带不了足够的信息。
该证明采用了一种称为”反证法”的策略。研究人员首先假设该问题存在经典证明。然后他们证明，这样的证明是可重用的，，你可以用同一个经典证据来回答许多不同的查询。但他们证明了这种可重用性将允许解决一项被证明不可能完成的困难猜测任务。这一矛盾意味着最初的假设是错误的：不存在任何经典证明。
“我开始思考这个问题多少有点偶然，”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问题的研究人员来说，答案终于揭晓了。
婷 翻译
来源
- 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月）.