For twenty years, computer scientists have wrestled with a deceptively simple question: can a quantum computer verify solutions to problems that a classical computer cannot even describe?
The answer, it turns out, is yes, and the proof is 96 pages long.
A team of four researchers, John Bostanci (Simons Institute / Columbia), Jonas Haferkamp (Ruhr University Bochum), Chinmay Nirkhe (University of Washington), and Mark Zhandry (Stanford), has proven that quantum proofs are categorically more powerful than classical proofs for at least one computational problem. The paper won the Best Paper Award at STOC 2026, the premier conference in theoretical computer science.
“This is a beautiful result,” said Anand Natarajan, a quantum information theorist at MIT who was not involved in the work. “There’s a bunch of fresh, new ideas that come out of it.”
What the proof actually shows
The problem belongs to a branch of theoretical computer science called complexity theory, which asks how the resources needed to solve a problem scale as the problem grows larger. At its heart are the classes QMA (Quantum Merlin-Arthur) and QCMA (Quantum-Classical Merlin-Arthur).
Think of it this way: imagine a student (Merlin) trying to convince a teacher (Arthur) that a certain mathematical statement is true. In the QMA scenario, Merlin can submit a quantum state, a fragile collection of qubits, as evidence. In the QCMA scenario, Merlin can only submit a classical string of bits. The question, first posed by Dorit Aharonov and Tomer Naveh in 2002, was whether the quantum version is strictly more powerful.
The team proved it is, by constructing a problem called the spectral forrelation problem for which a quantum witness works but a classical one cannot. The problem is a kind of forensic puzzle: given two sets of measurement data, determine whether they came from the same underlying quantum object or from two different ones. A quantum witness can encode the relationship between the two datasets directly; a classical witness simply cannot carry enough information.
The proof uses a strategy called a “proof by contradiction.” The researchers first assumed that a classical proof for the problem existed. Then they showed that such a proof would be reusable, you could use the same classical witness to answer many different queries. But this reusability, they demonstrated, would allow solving a hard guessing task that is provably impossible. The contradiction means the original assumption was false: no classical proof can exist.
“It was sort of by accident that I started thinking about it,” Zhandry told Quanta Magazine. His solo work in November 2024 cracked half the problem but couldn’t finish it. The four came together, and after nine months of intense work, “It really dominated my year. I basically didn’t do much else,” Bostanci said, they produced the complete proof.
A second, independent proof
Remarkably, a second team independently reached the same conclusion using a completely different method. Andrew Huang and Vinod Vaikuntanathan of MIT, together with Bostanci, produced a second oracle separation in February 2026 (arXiv:2602.09385) that is conceptually simpler and also yields the first separation between the classes BQP/qpoly and BQP/poly, a related area about quantum advice.
Having two independent proofs, one that is ingenious but intricate, the other simpler and more extensible, strengthens the case that the result is solid.
The oracle caveat
Both proofs are “oracle separations”: they show that QMA and QCMA differ relative to a black-box function (an oracle) that the computer can query but whose inner workings it cannot see. An unconditional proof, without an oracle, would require revolutionary advances in complexity theory, equivalent to proving P does not equal PSPACE.
Nevertheless, oracle separations are considered very strong evidence. Every known separation between major complexity classes started as an oracle result before being refined. The history of the field shows that when two classes differ relative to an oracle, they almost always differ in reality.
“What we have is the strongest evidence to date that the answer is yes, quantum proofs are more powerful,” the researchers note in their paper.
Why it matters
For the working quantum computer physicist, this result may not change day-to-day operations. The problem that separates the two classes, the spectral forrelation problem, is carefully constructed and artificial. But the techniques developed in the proof, particularly “second quantization” compressed oracle methods that treat the problem in terms of bosons, are expected to find applications in cryptography and quantum algorithm design.
The result also closes one of the major open questions in quantum complexity theory, a field that asks fundamental questions about what can and cannot be computed with quantum resources. For researchers who have spent two decades chipping away at the QMA vs QCMA problem, the answer is finally in.
Sources
- Quanta Magazine: “Researchers Reveal the Power of ‘Quantum Proofs'” (July 6, 2026). 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 (February 2026).