Researchers Reveal the Power of ‘Quantum Proofs’

Ada Zejun Shen/ Quanta Magazine

沉泽君/广达杂志

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.

30 多年前，研究人员发现基于量子物理定律的假设计算机能够快速解决困难的数学问题。

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.

20多年来，这个问题一直是量子复杂性理论领域最大的开放问题之一，该理论研究量子问题的内在难度。

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.

现在，在 6 月份的 2026 年计算理论研讨会上获得最佳论文奖的 100 页论文中，四位研究人员终于解决了这个问题——或者至少，他们已经接近了所有人期望的全面答案。

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.

“这是一个美妙的结果，”麻省理工学院的量子信息理论家阿南德·纳塔拉詹 (Anand Natarajan) 说。

“There’s a bunch of fresh, new ideas that come out of it.”

“其中产生了很多新鲜的、新的想法。”

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.

即使在相对简单的系统中，促成量子叠加的可能配置数量也可能超过宇宙中原子的数量，从而无法写出系统量子态的经典描述。

Outside of spy movies, documents rarely self-destruct after they’re read — and fortunately for mathematicians, proofs are no exception.

除了间谍电影之外，文件很少会在阅读后自毁——幸运的是，对于数学家来说，证明也不例外。

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.

2006年，他们取得了部分进展，但未能实现最终目标：一种特别令人垂涎的证据形式，可以避免做出不寻常的假设。

“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 .

“这似乎是一个非常非常困难的问题，”德克萨斯大学奥斯汀分校的复杂性理论家斯科特·阿伦森 (Scott Aaronson) 说，他与数学家格雷格·库珀伯格 (Greg Kuperberg) 共同撰写了 2006 年这篇论文。

In 2025, four researchers finally succeeded.

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

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.

这一新结果的故事始于量子密码学领域的研究员马克·詹德里(Mark Zhandry)，该领域研究如何利用量子效应来保护敏感信息。

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.

2024 年，他开始怀疑作为许多密码方案核心的量子物理学的一个特征也可以帮助区分量子证明和经典证明。

“It was sort of by accident that I started thinking about it,” said Zhandry, who’s now at Stanford University.

“我开始思考这个问题有点偶然，”现在斯坦福大学的詹德里说。

Clockwise from top left: Chinmay Nirkhe, Mark Zhandry, Jonas Haferkamp, and John Bostanci blended ideas from cryptography, statistical physics, and other far-flung fields to show that quantum proofs are more powerful than classical ones.

从左上角顺时针方向：Chinmay Nirkhe、Mark Zhandry、Jonas Haferkamp 和 John Bostanci 融合了密码学、统计物理学和其他广泛领域的思想，证明量子证明比经典证明更强大。

Clockwise from top left: From left: Patricia Rossi; Matt Hagen; Michael Schwettmann; Kristy (Sungmin) Hong

从左上角顺时针方向：左起：Patricia Rossi；马特·哈根；迈克尔·施韦特曼；洪克里斯蒂（晟敏）

From left: Chinmay Nirkhe, Mark Zhandry, John Bostanci, and Jonas Haferkamp blended ideas from cryptography, statistical physics, and other far-flung fields to show that quantum proofs are more powerful than classical ones.

从左至右：Chinmay Nirkhe、Mark Zhandry、John Bostanci 和 Jonas Haferkamp 融合了密码学、统计物理学和其他广泛领域的思想，证明量子证明比经典证明更强大。

From left: Patricia Rossi; Matt Hagen; Kristy (Sungmin) Hong; Michael Schwettmann

左起：帕特里夏·罗西；马特·哈根；洪克里斯蒂（Sungmin）；迈克尔·施韦特曼

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.

“这就是取证问题，”与 Zhandry 合作研究新结果的华盛顿大学计算机科学家 Chinmay Nirkhe 说道。

“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.

他怀疑，这种矛盾可能来自于我们通常认为理所当然的经典证明的一个属性：可以多次阅读一个证明。

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.

这种测量干扰在许多量子密码方案中发挥着核心作用，但研究人员在之前区分量子证明和经典证明的尝试中并未利用它。

The final step turned out to have a fatal flaw.

结果最后一步出现了致命的缺陷。

Coming so tantalizingly close made them all the more determined to succeed.

如此接近让他们更加坚定了成功的决心。

Coming from a background in cryptography, however, Zhandry saw that measurement disturbance could be relevant.

然而，来自密码学背景的 Zhandry 发现测量干扰可能是相关的。

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.

Zhandry 无法弄清楚如何独自完成最后一步，因此在 2024 年底，他与 John Bostanci（现任加州伯克利西蒙斯计算理论研究所研究员）和 Jonas Haferkamp（现任德国波鸿鲁尔大学计算机科学家）合作。

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.

Nirkhe 多年来一直独立解决这个问题，于 2025 年初加入该团队，并提出了一种调整 Zhandry 方法的方法。

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.

初秋时，博斯坦奇在纽约中央公园进行 20 英里跑步，这是他为即将到来的马拉松训练的一部分，他取得了一项重大突破。

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.

11 月中旬，即 Bostanci 成功完成比赛 10 天后，他们在网上发布了结果。

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.

一类包括量子证明的所有问题，称为 QMA。

The other, called QCMA, includes problems with classical proofs that a quantum computer can check.

另一个称为 QCMA，包括量子计算机可以检查的经典证明问题。

(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.

需要注意的是，该团队的结果是 QMA 和 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.

但这是强有力的证据，表明量子证明比经典证明更强大——这正是研究人员 20 年来一直在寻找的证据。

Soon after the team posted their paper online, an MIT master’s student named Andrew Huang heard Bostanci give a talk about the result.

该团队将论文发布到网上后不久，麻省理工学院的硕士生安德鲁·黄（Andrew Huang）听到了博斯坦奇关于结果的演讲。

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.

Huang 和他的顾问 Vinod Vaikuntanathan 与 Bostanci 合作，很快证明了 QMA 和 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.

但对于许多研究人员来说，“QMA 与 QCMA”问题的吸引力并非来自任何潜在的实际应用。

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.

编者注：斯科特·阿伦森 (Scott Aaronson) 是《Quanta》杂志顾问委员会的成员。

Get highlights of the most important news delivered to your email inbox

获取发送到您的电子邮件收件箱的最重要新闻的摘要

Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation.

《Quanta》杂志对评论进行审核，以促进知情、实质性、文明的对话。

Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected.

辱骂、亵渎、自我推销、误导、语无伦次或偏离主题的评论将被拒绝。

Moderators are staffed during regular business hours (New York time) and can only accept comments written in English.

版主在正常工作时间（纽约时间）有工作人员，并且只能接受英文评论。