A team of researchers including Allen School professor Chinmay Nirkhe has resolved one of the biggest open problems in quantum complexity theory of the past 20 years: are quantum proofs computationally more powerful than classical proofs? To prove this, the researchers identified a query complexity problem that can be verified with a short quantum proof but for which “no classical proof can provide the same advantage without requiring exponentially many queries or an exponentially long proof,” Nirkhe explained.
Their results earned the researchers a Best Paper Award at the 58th Annual ACM Symposium on Theory of Computing (STOC 2026) in Salt Lake City, Utah, last month.
The result gives strong evidence that quantum proofs are not just different encodings of classical proofs; they can be fundamentally more powerful computational objects.
The problem that Nirkhe and his collaborators identified is called the spectral forrelation problem, which compares various ways of measuring a quantum state. In this problem, you are given a pair of shadows and must figure out if they could have come from distinct measurements of the same state. The team’s paper titled “Separating QMA from QCMA with a classical oracle” proved that two classes of computation problems — QMA, which includes all problems with quantum proofs, and QMCA, for those with classical proofs that a quantum computer can also check — are different.
To solve the problem, the team introduced a series of new techniques drawing on ideas from physics and other areas of computer science. This includes a novel reduction from verification problems to sampling problems that exploits the unclonability of quantum information. They also developed a new method for analyzing quantum algorithms over random distributions using the mathematics of quantum particles called bosons.
“The result gives strong evidence that quantum proofs are not just different encodings of classical proofs; they can be fundamentally more powerful computational objects,” said Nirkhe, who is part of both the Allen School’s Theory Group and the Quantum Group. “It also points to what I think is the next interesting direction: understanding the computational or cryptographic utility of unclonability — the fact that quantum information cannot be freely copied — and when this uniquely quantum feature can be turned into provable computational utility.”
Additional authors include John Bostanci, researcher at the Simons Institute for the Theory of Computing at the University of California, Berkeley; Jonas Haferkamp, faculty at Ruhr-University Bochum; and Mark Zhandry, faculty at Stanford University.
This paper was one of seven authored by Allen School researchers that were accepted to STOC 2026. Read the full award-winning paper here and a related Quanta Magazine article here.