Chinmay Nirkhe is part of both the Allen School’s Theory Group and the Quantum Group.
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.Chinmay NirkheAllen School professor
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.
