内容来源：https://www.quantamagazine.org/researchers-reveal-the-power-of-quantum-proofs-20260706/

内容总结：

量子证明威力初现：科学家证实存在量子计算机“专属”难题

导语： 三十多年前，科学家发现基于量子物理原理的计算机能迅速攻克复杂数学难题。自此，他们一直在寻找量子计算机超越经典计算机的精确案例。而一个被长期忽视的相关问题也终于有了突破性进展：利用量子物理的“证明”，是否也比经典证明更强大？

核心发现： 近日，四位研究人员在长达100页的论文中，终于解答了困扰量子复杂性理论界超过20年的“QMA与QCMA”核心问题。他们确定了一个特殊的计算问题，该问题必须使用量子证明才能解决，任何经典证明都无法替代。该成果荣获2026年计算机理论研讨会最佳论文奖。

什么是“量子证明”？
在计算机科学中，“证明”并非数学定理的逻辑推导，而是一份确认问题被正确解决的“证书”。例如，填好的数独答案本身就是证明。科学家此前发现，某些问题的验证过程可能需要量子计算机，而针对部分问题，唯一的已知证明形式是极其复杂的“量子态”——一种数学对象，由于叠加效应，其复杂程度远超经典描述能力。

关键突破：模拟“量子物证”
团队聚焦于一个名为“频谱相关性”的问题，将其比作从两个不同角度观察同一量子态所投下的“影子”。给定一对“影子”，判断它们是否来自同一量子态，这本质上是一个“量子物证鉴定”难题。若无额外信息，连量子计算机也难以解决，但若给定一个有效的量子态（即量子证明），问题便迎刃而解。

为何经典证明不行？
研究核心在于利用量子态的“不可重复读取”特性。经典证明如文档，可被反复查阅。团队用反证法证明：假设存在一个经典证明（如生成量子态的程序），则意味着该程序可被反复使用去猜测“影子”形状。而团队最终证明，这种猜测任务极其困难，即使有经典证明也无法完成，从而产生矛盾，最终推翻了经典证明存在的可能性。

重大意义：
该研究严格证明了（虽带有“预言机分离”的前提）两类计算问题确实不同：一类是拥有量子证明的问题（QMA），另一类是拥有经典证明、但可由量子计算机验证的问题（QCMA）。这为“量子证明本质上强于经典证明”提供了20年来最强有力的证据。麻省理工学院量子信息理论家纳塔拉詹评价：“这是一个美丽的结果，其中蕴含了大量新鲜、新颖的想法。”

研究者认为，这一成果不仅对量子复杂性理论意义深远，未来还可能应用于密码学领域，并有助于解答困扰物理学家一个多世纪的深层哲学问题：“为什么量子力学无法用经典方式描述？”

中文翻译：

研究人员揭示“量子证明”的力量

引言

三十多年前，研究人员发现，基于量子物理定律的假想计算机能够快速解决棘手的数学难题。自那时起，他们便一直致力于明确量子计算机在哪些情况下比其普通的“经典”同类更强大。

几乎在同一时期，少数计算机科学家一直在探究一个相关但较少受关注的问题：利用量子物理的证明是否也比经典证明更强大？

在此语境下，“证明”并非数学中导致定理的一连串逻辑陈述，而是一份确认问题已被正确求解的证书。例如，如果你解出一个复杂的数独谜题，你的解答本身就是一个证明。计算机可以轻松扫描网格并验证其正确性。

研究人员已经识别出一些问题，其证明核查过程可能需要量子计算机。对于其中一些问题，证明本身仍然是经典的——即普通的书面文档。但对于其他问题，目前已知的唯一证明是被称为“量子态”的根本不同的数学对象。

研究人员想要理解这种奇特的量子证明是否必要。在那些看似需要量子证明的问题中，是否真的不可能提出一个普通的经典证明？或者是否存在某种巧妙的方法用量子证明替代经典证明，而研究人员只是尚未发现？

二十多年来，这个问题一直是量子复杂性理论领域最大的未解难题之一，该理论研究量子问题固有的难度。现在，在一篇获得2026年6月理论计算研讨会最佳论文奖的100页论文中，四位研究人员终于解决了这个问题——或者至少，他们已经得出了人们期望的全面答案。他们识别出一个特殊的计算问题，确实需要量子证明，任何经典证明都无法奏效。

“这是一个美妙的结果，”麻省理工学院的量子信息理论家阿南德·纳塔拉詹说，“它带来了一系列全新的想法。”

展示，而非告知

假设你想证明一种材料具有某种特定性质——比如说，它具有磁性。除非你能获取该材料的量子态（即指定其电子构型的数学对象），否则这是一个难题。有了该量子态的一份副本，量子计算机就能轻松检查以验证该材料具有磁性。这意味着材料的量子态可以作为这个问题的一个量子证明。许多经典数学问题的量子版本也有类似的量子证明。

问题在于，由于一种称为叠加的现象，量子态可能极其复杂。叠加现象使得一个系统的多种不同构型可以共存于一个单一状态中。即使在一个相对简单的系统中，对量子叠加有贡献的可能构型数量也可能超过宇宙中的原子数量，这使得写出该系统量子态的经典描述变得不可能。

对于某些问题，最自然的证明可能就是这些无法描述的量子态之一。而经典证明（如果存在的话）则必须完全绕过量子世界的内在复杂性。研究人员认为这是不可能的。

为了证实这种直觉，复杂性理论家需要找到一个满足两个条件的具体问题：第一，它必须有一个量子证明。第二，它不能有经典证明。第二步是困难的部分，而且由于存在经典证明的问题仍可能使用量子计算机进行证明核查程序（或算法），这使得问题更加困难。要成功，研究人员必须排除经典证明与量子证明核查算法的每一种潜在组合。

证明适用于所有算法的普遍性陈述是出了名的困难。除非复杂性理论发生革命性的变革，否则不可能得到全面性的结果。相反，研究人员一直在寻找令人信服的证据，证明量子证明与经典证明有本质区别。2006年，他们取得了部分进展，但未能实现最终目标：一种特别令人向往的证据形式，且无需做出非比寻常的假设。

“那看起来就是一个难得多得多的问题，”德克萨斯大学奥斯汀分校的复杂性理论家斯科特·阿伦森说，他与数学家格雷格·库珀伯格合著了2006年的那篇论文。

2025年，四位研究人员终于取得了成功。

量子取证

新成果的故事始于马克·赞德里，一位量子密码学领域的研究员，该领域研究如何利用量子效应保护敏感信息。2024年，他开始怀疑，许多密码方案核心的一个量子物理特性，也可能有助于区分量子证明与经典证明。

“我开始思考这个问题多少有点偶然，”现任教于斯坦福大学的赞德里说。

为了验证他的想法，赞德里需要一个候选问题，该问题要有量子证明但没有经典证明。他最终选定的问题称为“频谱关联问题”，涉及比较测量量子态的两种不同方式。赞德里和他的同事将这两种测量可能产生的结果比作一个物体从两个不同角度照射时投下的阴影。在频谱关联问题中，你会得到一对阴影，你的目标是确定它们是否真的可能来自同一量子态的不同测量结果。

“这是一个取证问题，”华盛顿大学的计算机科学家钦梅·尼尔克说，他与赞德里合作完成了这项新成果，“是否存在一个可能同时投射出这两个阴影的物体？”

没有额外信息，即使是量子计算机也很难解决这个问题。但是，给定一个合适的量子态，量子计算机可以轻松确认它与两个阴影都一致。换句话说，该量子态就是一个有效的量子证明。

现在想象一下，你得到的是一份关于如何生成一个与两个阴影都一致的量子态的书面程序。该程序将被视为频谱关联问题的一个经典证明：要检查它是否有效，你需要首先在量子计算机上运行该程序，然后将生成的量子态与两个阴影进行比较。这听起来不像传统的数学证明，但它仍然是一份简洁的书面文档，而不是复杂到无法写下来的量子态。

赞德里需要证明经典证明不可能存在。他试图用一种称为反证法的策略来做到这一点。首先，他会假设与他想要证明的结论相反的情况：即存在一个针对频谱关联问题的经典证明是可能的。然后，他需要证明这个假设最终会导致矛盾。

他怀疑，这个矛盾将来自经典证明的一个我们通常视为理所当然的特性：即可以多次读取一份证明。

追逐阴影

除了间谍电影，文档在被阅读后很少会自毁——对数学家来说幸运的是，证明也不例外。但在量子世界中，情况有所不同：测量一个量子态可能会不可逆地干扰它，从而改变任何后续测量的结果。这种测量干扰在许多量子密码方案中扮演着核心角色，但研究人员在以往区分量子证明与经典证明的尝试中并未利用它。

然而，拥有密码学背景的赞德里认识到，测量干扰可能具有相关性。频谱关联问题的量子证明是一个易受测量干扰影响的量子态。而假设存在的经典证明则是一份书面文档，例如生成有效量子态的程序。任何人都可以重复运行该程序以不断产生该量子态的新副本。

赞德里想探究这种可重用性的含义，因为他怀疑这好得令人难以置信。

他很快证明，如果存在一个针对频谱关联问题的经典证明，那么任何拥有该证明副本的人都可以重复使用它来完成一项看似困难的任务：在仅获得部分信息的情况下猜测阴影的形状。只剩一步了。如果赞德里能够单独证明，这个猜测任务不仅困难，而且困难到即使是经典证明也无济于事，那么他就会得到一个矛盾。这意味着他的初始假设——经典证明是可能的——必然是假的。

赞德里无法独自完成这最后一步，因此在2024年底，他与约翰·博斯坦奇（现为加州伯克利西蒙斯理论计算研究所的研究员）和约纳斯·哈弗坎普（现为德国波鸿鲁尔大学的计算机科学家）合作。三人很快得到了他们认为已经完成的证明——但最后一步竟然存在一个致命缺陷。如此接近成功，反而让他们更加坚定了成功的决心。

“这就像在我们屁股底下点了一把火，”博斯坦奇说。

多年来一直在独立思考这个问题的尼尔克，于2025年初加入了团队，并提出了一种方法来调整赞德里的思路。他们可以使用相同的总体策略，但几乎每个细节都必须改变。尼尔克的提议开启了一段为期九个月的时期，期间充满了塞得满满的电子邮件以及往返于纽约、华盛顿州、加利福尼亚和德国之间的旅程。

“这基本上占据了我那一整年，”博斯坦奇说，“我基本上没做什么别的事。”

四位研究人员通过借鉴物理学和计算机科学其他领域的思路来攻克这个问题，包括量子学习理论和被称为玻色子的量子粒子的数学。一个关键的突破出现在初秋，当时博斯坦奇正在纽约市中央公园进行20英里的跑步，这是他备战即将到来的马拉松的训练部分。

经过又两个月的紧张工作，团队终于成功了。他们得出了一个矛盾，这意味着他们最初的假设一定是错误的：针对频谱关联问题，不可能存在经典证明。他们于11月中旬在网上发布了他们的成果，就在博斯坦奇成功完成比赛的10天后。

概念验证

正式地说，团队在有一个限定条件的情况下，证明了计算问题的两个类别是不同的。一个类别包括所有具有量子证明的问题，被称为QMA。另一个类别称为QCMA，包括量子计算机可以核查的、有经典证明的问题。（这两个笨拙的首字母缩略词分别代表量子梅林-亚瑟和量子经典梅林-亚瑟，源自一个以中世纪传说中两位角色为主角的虚构思想实验。）

这个限定条件是，团队的成果是QMA和QCMA之间的一个“预言机分离”。这意味着它依赖于某些假设，这些假设限制了需要考虑的可能性空间。但这是量子证明比经典证明更强大的有力证据——正是研究人员二十年来一直在寻找的那种证据。

团队在网上发布论文后不久，麻省理工学院硕士生安德鲁·黄听了博斯坦奇关于该成果的演讲。他意识到该团队证明中的一个方面也可能在基于一个完全不同的计算问题的预言机分离中发挥作用。黄和他的导师维诺德·瓦伊昆塔纳坦与博斯坦奇合作，很快证明了QMA和QCMA之间的第二个预言机分离。这个更新的结果进一步支持了量子证明本质上比经典证明更强大的论点。

证明这些预言机分离所使用的技术有朝一日可能会在密码学中找到应用。但对许多研究人员来说，“QMA与QCMA”问题的魅力并非来自任何潜在的实际应用。它提供了一种方式来探索困扰物理学家一个多世纪的关于量子理论的深层哲学问题。

“我真正的兴趣始终在于，‘为什么量子力学不能用经典方式描述？’”尼尔克说，“我认为计算是我们用来理解这个问题的标尺或度量。”

编者注：斯科特·阿伦森是《量子杂志》顾问委员会成员。

英文来源：

Researchers Reveal the Power of ‘Quantum Proofs’
Introduction
More than 30 years ago, researchers discovered that hypothetical computers based on the laws of quantum physics would be able to rapidly solve difficult math problems. Ever since then, they’ve sought to pinpoint cases where quantum computers are more powerful than their ordinary “classical” cousins.
For nearly as long, a small band of computer scientists has pursued a related question that gets less attention: Are proofs that exploit quantum physics also more powerful than classical proofs?
In this context, a “proof” is not a series of logical statements that leads to a theorem, as it is in math. Instead, it’s a certificate confirming that a problem has been solved correctly. For example, if you solve a tricky sudoku puzzle, your solution itself is a proof. A computer can easily scan the grid and verify that it’s correct.
Researchers have identified problems where this proof-checking process likely requires a quantum computer. For some of these problems, the proofs themselves are still classical — ordinary written documents. But for other problems, the only known proofs are fundamentally different mathematical objects called quantum states.
Researchers want to understand whether such exotic quantum proofs are necessary. In those cases where a problem appears to require a quantum proof, is it really impossible to come up with an ordinary classical proof? Or is there some clever way to replace the quantum proof with a classical one, and researchers just haven’t discovered it?
For over 20 years, this question has ranked among the biggest open problems in the field of quantum complexity theory, which studies the intrinsic hardness of quantum problems. Now, in a 100-page paper that received a best-paper award at the 2026 Symposium on Theory of Computing in June, four researchers have finally resolved it — or at least, they’ve come as close to a comprehensive answer as anyone expects to get. They identified a special computational problem that truly requires a quantum proof. No classical proof will do the trick.
“It’s a beautiful result,” said Anand Natarajan, a quantum information theorist at the Massachusetts Institute of Technology. “There’s a bunch of fresh, new ideas that come out of it.”
Show, Don’t Tell
Suppose you want to prove that a material has a particular property — say, that it’s magnetic. This is a hard problem unless you have access to the material’s quantum state: a mathematical object specifying the configuration of its electrons. Given a copy of that quantum state, a quantum computer can easily check it to verify that the material is magnetic. That means the material’s quantum state can serve as a quantum proof for this problem. Quantum versions of many classic math problems also come with analogous quantum proofs.
The trouble is that quantum states can be extraordinarily complicated, due to a phenomenon called superposition, in which many different configurations of a system can coexist in a single state. Even in a relatively simple system, the number of possible configurations that contribute to a quantum superposition can exceed the number of atoms in the universe, making it impossible to write down a classical description of the system’s quantum state.
For some problems, the natural proof might be one of these impossible-to-describe quantum states. A classical proof, if it existed, would have to bypass the intrinsic complexity of the quantum world completely. Researchers don’t think that’s possible.
To confirm this intuition, complexity theorists need to find a specific problem that checks two boxes: First, it must have a quantum proof. Second, it must not have a classical proof. That second step is the hard part, and it’s made harder still by the fact that problems with classical proofs might still use quantum computers for their proof-checking procedures (or algorithms). To succeed, researchers must rule out every potential combination of classical proof and quantum proof-checking algorithm.
It’s notoriously hard to prove sweeping statements that apply to all algorithms. Short of a revolution in complexity theory, a comprehensive result is out of the question. Instead, researchers have sought compelling evidence that quantum proofs are categorically different from classical ones. In 2006, they made partial progress, but they couldn’t achieve their ultimate goal: a particularly coveted form of evidence that avoids making unusual assumptions.
“That just seemed like a much, much harder problem,” said Scott Aaronson, a complexity theorist at the University of Texas, Austin, who co-authored the 2006 paper with the mathematician Greg Kuperberg.
In 2025, four researchers finally succeeded.
Quantum Forensics
The story of the new result began with Mark Zhandry, a researcher in the field of quantum cryptography, the study of how to harness quantum effects to protect sensitive information. In 2024, he began to suspect that a feature of quantum physics at the heart of many cryptographic schemes could also help distinguish quantum proofs from classical ones.
“It was sort of by accident that I started thinking about it,” said Zhandry, who’s now at Stanford University.
To put his idea to the test, Zhandry needed a candidate for a problem that has a quantum proof but no classical proof. The problem that he settled on, called the spectral forrelation problem, involves comparing two distinct ways of measuring a quantum state. Zhandry and his colleagues liken the possible outcomes of these two measurements to the shadows cast by an object illuminated from two different angles. In the spectral forrelation problem, you’re given a pair of shadows, and your goal is to determine whether they really could have come from different measurements of the same state.
“It’s this forensics problem,” said Chinmay Nirkhe, a computer scientist at the University of Washington who collaborated with Zhandry on the new result. “Is there possibly an object that would have cast both of these shadows?”
Without any extra information, this problem is hard to solve even for a quantum computer. But given an appropriate quantum state, a quantum computer can easily confirm that it’s consistent with both shadows. In other words, that state is a valid quantum proof.
Now imagine you’re instead given a written procedure for how to generate a quantum state consistent with both shadows. That procedure would count as a classical proof for the spectral forrelation problem: To check that it’s valid, you’d first run the procedure on your quantum computer, then compare the resulting state to the two shadows. It doesn’t sound like a traditional mathematical proof, but it would still be a concise written document rather than a quantum state that’s too complex to write down.
Zhandry needed to show that classical proofs can’t exist. He sought to do so with a strategy called a proof by contradiction. First, he’d assume the opposite of what he wanted to prove: that a classical proof for the spectral forrelation problem is possible. Then he’d need to show that this assumption would eventually lead to a contradiction.
That contradiction, he suspected, would come from a property of classical proofs that we usually take for granted: It’s possible to read a proof more than once.
Chasing Shadows
Outside of spy movies, documents rarely self-destruct after they’re read — and fortunately for mathematicians, proofs are no exception. But in the quantum world, things are different: Measuring a quantum state can irreversibly disturb it, altering the results of any subsequent measurements. This kind of measurement disturbance plays a central role in many quantum cryptography schemes, but researchers hadn’t exploited it in previous attempts to distinguish between quantum and classical proofs.
Coming from a background in cryptography, however, Zhandry saw that measurement disturbance could be relevant. A quantum proof for the spectral forrelation problem is a quantum state that’s vulnerable to measurement disturbance. A hypothetical classical proof, on the other hand, would be a written document, such as a procedure for generating a valid quantum state. Anyone could run the procedure repeatedly to churn out fresh copies of that state.
Zhandry wanted to explore the implications of this reusability, because he suspected it was too good to be true.
He quickly showed that if a classical proof for the spectral forrelation problem existed, anyone with a copy of the proof could use it repeatedly to accomplish a seemingly difficult task: guessing the shapes of shadows given only partial information. Only one step remained. If Zhandry could separately prove that this guessing task was not just hard but so hard that even a classical proof couldn’t help, he would have a contradiction. That would mean his starting assumption, that classical proofs were possible, had to be false.
Zhandry couldn’t figure out how to complete that last step alone, so at the end of 2024 he teamed up with John Bostanci, now a researcher at the Simons Institute for the Theory of Computing in Berkeley, California, and Jonas Haferkamp, a computer scientist now at Ruhr University Bochum in Germany. Soon the trio had what they thought was a finished proof — but the final step turned out to have a fatal flaw. Coming so tantalizingly close made them all the more determined to succeed.
“That kind of lit the fire under our butts,” Bostanci said.
Nirkhe, who’d been wrestling with the problem independently for years, joined the team in early 2025 and suggested a way to tweak Zhandry’s approach. They could use the same overall strategy, but almost every detail would have to change. Nirkhe’s proposal kicked off a nine-month period full of overstuffed emails and travel back and forth between New York, Washington state, California, and Germany.
“It really dominated my year,” Bostanci said. “I basically didn’t do much else.”
The four researchers chipped away at the problem by drawing on ideas from other areas of physics and computer science, including quantum learning theory and the math of quantum particles called bosons. One crucial breakthrough came in the early fall while Bostanci was in the middle of a 20-mile run in New York City’s Central Park, part of his training for the upcoming marathon.
After two more months of intense work, the team finally succeeded. They’d reached a contradiction, which meant that their original assumption had to be wrong: A classical proof for the spectral forrelation problem was impossible. They posted their result online in mid-November, 10 days after Bostanci successfully finished his race.
Proof of Concept
Officially, the team proved, with one caveat, that two classes of computational problems are different. One class includes all problems with quantum proofs and is known as QMA. The other, called QCMA, includes problems with classical proofs that a quantum computer can check. (The unwieldy acronyms stand for quantum Merlin-Arthur and quantum-classical Merlin-Arthur, respectively, in reference to a fanciful thought experiment featuring the two characters from medieval legend.)
The caveat is that the team’s result is an “oracle separation” between QMA and QCMA. This means it relies on certain assumptions that restrict the space of possibilities one needs to consider. But it’s strong evidence that quantum proofs are more powerful than classical ones — precisely the kind of evidence that researchers have sought for 20 years.
Soon after the team posted their paper online, an MIT master’s student named Andrew Huang heard Bostanci give a talk about the result. He realized that one aspect of the team’s proof could also play a role in an oracle separation based on a completely different computational problem. Huang and his adviser, Vinod Vaikuntanathan, teamed up with Bostanci and soon proved a second oracle separation between QMA and QCMA. The newer result further bolsters the case that quantum proofs are inherently more powerful than classical ones.
The techniques used to prove these oracle separations could one day find applications in cryptography. But for many researchers, the allure of the “QMA versus QCMA” question doesn’t come from any potential practical application. It offers a way to explore deep philosophical questions about quantum theory that have vexed physicists for over a century.
“My real interest has always been, ‘Why is quantum mechanics not classically describable?’” Nirkhe said. “I think of computation as the yardstick, or the metric, with which we can understand this.”
Editor’s note: Scott Aaronson is a member of Quanta Magazine’s advisory board.