Four Researchers Prove Quantum Proofs Beat Classical Ones in 20-Year Complexity Problem
Updated
Updated · Quanta Magazine · Jul 6
Four Researchers Prove Quantum Proofs Beat Classical Ones in 20-Year Complexity Problem
3 articles · Updated · Quanta Magazine · Jul 6
Summary
A 100-page paper by Chinmay Nirkhe, Mark Zhandry, Jonas Haferkamp and John Bostanci identifies a computational problem that requires a quantum proof, delivering the strongest answer yet to a 20-year question in quantum complexity theory.
The team used the spectral forrelation problem, showing a quantum state can certify the answer while any reusable classical proof would imply an impossible shadow-guessing method, yielding a contradiction.
The result establishes an oracle separation between QMA and QCMA—the classes for problems with quantum proofs and classical proofs checked by quantum computers—and won a best-paper award at the 2026 Symposium on Theory of Computing.
A second oracle separation, developed soon after with MIT student Andrew Huang and adviser Vinod Vaikuntanathan, reinforced the conclusion and may eventually inform quantum cryptography.
On July 6, 2026, four leading researchers achieved a major breakthrough by proving that quantum proofs (QMA) are fundamentally more powerful than classical proofs (QCMA) for certain computational problems. Their work showed that quantum proofs can convince a quantum verifier much more efficiently, or even in cases where classical proofs fail. This result marks a significant milestone in understanding quantum information, providing a definitive answer to a long-standing question about the differences between quantum and classical computation. The proof also deepens our knowledge of how quantum mechanics offers unique computational advantages beyond just faster processing.