Quantum Proofs Reveal the Inescapable Complexity of the Quantum World

When verifying the correctness of solutions to certain computational problems, it has become evident that researchers cannot bypass the inherent complexity of the quantum world. For more than three decades, the scientific community has been aware that hypothetical computers operating on the laws of quantum physics possess the ability to solve difficult mathematical problems with unprecedented speed. Since that initial discovery, researchers have diligently sought to pinpoint specific cases where quantum computers demonstrate superior power compared to their ordinary "classical" counterparts.

For nearly as long, a specialized group of computer scientists has pursued a related, yet less scrutinized, question: Are proofs that exploit quantum physics also more powerful than classical proofs? In this specific context, a "proof" does not refer to the series of logical statements that leads to a theorem in traditional mathematics. Instead, it functions as a certificate confirming that a problem has been solved correctly. For instance, if one solves a complex Sudoku puzzle, the completed grid itself serves as a proof. A computer can easily scan the grid and verify its correctness through standard classical algorithms.

Researchers have identified specific problems where this proof-checking process likely requires a quantum computer. For some of these challenges, the proofs themselves remain classical—ordinary written documents that can be read by humans. However, for other problems, the only known proofs are fundamentally different mathematical objects known as quantum states. A primary objective of current research is to understand whether such exotic quantum proofs are strictly necessary. In cases where a problem appears to require a quantum proof, is it truly impossible to devise an ordinary classical proof? Or is there some clever, undiscovered method to replace the quantum proof with a classical one?

For over twenty years, this question has ranked among the most significant open problems in quantum complexity theory, a field that studies the intrinsic hardness of quantum problems. Now, a 100-page paper, which received a best-paper award at the 2026 Symposium on Theory of Computing in June, presents a resolution. Four researchers have finally addressed this issue, coming as close to a comprehensive answer as expected. They identified a special computational problem that genuinely requires a quantum proof, demonstrating that no classical proof will suffice.

To illustrate the concept, suppose one wishes to prove that a material possesses a particular property, such as magnetism. This is an extremely difficult task unless one has access to the material’s quantum state—a mathematical object that specifies 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 indeed magnetic. Consequently, the material’s quantum state serves as a valid quantum proof for this problem. Many classic math problems have analogous quantum proofs.

The difficulty arises because quantum states are 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 contributing to a quantum superposition can exceed the number of atoms in the universe. This makes it impossible to write down a complete classical description of the system’s quantum state. For some problems, the natural proof is 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 entirely. Researchers generally believe this is not possible.

To confirm this intuition, complexity theorists needed to find a specific problem that satisfied two conditions: first, it must have a quantum proof; second, it must not have a classical proof. The second condition is exceptionally difficult to prove, especially because problems with classical proofs might still use quantum computers for their proof-checking procedures. To succeed, researchers had to rule out every potential combination of classical proof and quantum proof-checking algorithm.

It is notoriously difficult to prove sweeping statements that apply to all possible algorithms. Without a revolution in complexity theory, a comprehensive result was previously out of reach. Instead, researchers sought compelling evidence that quantum proofs are categorically different from classical ones. In 2006, they made partial progress but could not achieve the 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 at Austin, who co-authored the 2006 paper with mathematician Greg Kuperberg. In 2025, four researchers finally succeeded in overcoming these barriers.

The story of the new result began with Mark Zhandry, a researcher in quantum cryptography, the study of harnessing quantum effects to protect sensitive information. In 2024, he began to suspect that a feature of quantum physics central to 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 was then at Stanford University. To test his idea, Zhandry needed a candidate problem with a quantum proof but no classical proof. He settled on the spectral forrelation problem, which involves comparing two distinct ways of measuring a quantum state. Zhandry and his colleagues likened the possible outcomes of these measurements to shadows cast by an object illuminated from two different angles. In this problem, one is given a pair of shadows and must determine whether they 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. "Is there possibly an object that would have cast both of these shadows?"

Without extra information, solving this problem is hard even for a quantum computer. However, given an appropriate quantum state, a quantum computer can easily confirm that it is consistent with both shadows, validating the state as a proof. Now, imagine being given a written procedure for how to generate such a state. This procedure would count as a classical proof. To check its validity, one would run the procedure on a quantum computer and compare the resulting state to the shadows. While not a traditional mathematical proof, it is a concise written document rather than an unwriteable quantum state.

Zhandry needed to show that classical proofs cannot exist. He employed a strategy called proof by contradiction. He assumed the opposite: that a classical proof for the spectral forrelation problem was possible. He then sought to show that this assumption would lead to a logical contradiction. He suspected this contradiction would arise from a property of classical proofs that is usually taken for granted: the ability to read a proof more than once.

In the classical world, documents rarely self-destruct after being read. Proofs are similarly reusable. In the quantum world, however, things are different: measuring a quantum state can irreversibly disturb it, altering the results of any subsequent measurements. This measurement disturbance is central to quantum cryptography but had not been exploited in previous attempts to distinguish between proof types.

Coming from a cryptography background, Zhandry recognized the relevance of measurement disturbance. A quantum proof for the spectral forrelation problem is a quantum state vulnerable to disturbance. A hypothetical classical proof, by contrast, would be a written procedure. Anyone could run this procedure repeatedly to generate fresh copies of the quantum state.

Zhandry explored the implications of this reusability, suspecting it was "too good to be true." He showed that if a classical proof existed, anyone with a copy could use it repeatedly to accomplish a seemingly difficult task: guessing the shapes of shadows given only partial information. One step remained. If Zhandry could prove that this guessing task was not just hard, but so hard that even a classical proof couldn’t help, he would achieve a contradiction. This would mean the initial assumption—that classical proofs were possible—was false.

Zhandry could not complete the final step alone. At the end of 2024, he teamed up with John Bostanci of the Simons Institute for the Theory of Computing and Jonas Haferkamp of Ruhr University Bochum. The trio believed they had a finished proof, but the final step contained a fatal flaw. This proximity to success fueled their determination.

"That kind of lit the fire under our butts," Bostanci said. Chinmay Nirkhe, who had been wrestling with the problem independently for years, joined the team in early 2025 and suggested tweaking Zhandry’s approach. The group employed the same strategy but altered almost every detail. This began a nine-month period of intense collaboration across New York, Washington state, California, and Germany.

"It really dominated my year," Bostanci said. "I basically didn’t do much else." The researchers drew on ideas from quantum learning theory and the mathematics of bosons. A crucial breakthrough occurred in early fall while Bostanci was running in Central Park. After two more months of intense work, the team succeeded. They reached a contradiction, proving that a classical proof for the spectral forrelation problem was impossible. They posted their result online in mid-November, ten days after Bostanci completed a marathon.

Officially, the team proved, with one caveat, that two classes of computational problems are distinct. One class, known as QMA (quantum Merlin-Arthur), includes all problems with quantum proofs. The other, called QCMA (quantum-classical Merlin-Arthur), includes problems with classical proofs that a quantum computer can check. The caveat is that the result is an "oracle separation," meaning it relies on assumptions that restrict the space of possibilities considered. Nevertheless, it provides strong evidence that quantum proofs are more powerful than classical ones—the exact evidence researchers have sought for two decades.

Soon after the paper’s release, MIT master’s student Andrew Huang heard Bostanci speak about the result. He realized one aspect of the proof could apply to a completely different computational problem. Huang, his adviser Vinod Vaikuntanathan, and Bostanci proved a second oracle separation between QMA and QCMA. This newer result further bolsters the case for the inherent superiority of quantum proofs.

While these techniques may eventually find applications in cryptography, the allure of the "QMA versus QCMA" question lies in deeper philosophical inquiries. It offers a way to explore why quantum mechanics resists classical description.

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