At this year’s ACM Symposium on Theory of Computing (STOC) in Salt Lake City, Utah (USA), Jonas Haferkamp received a Best Paper Award. The conference took place from June 22 to 27, 2026, and is considered one of the most prestigious international conferences in the field of theoretical computer science. The award recognized the paper “Separating QMA from QCMA with a Classical Oracle”, which Haferkamp co-authored with John Bostanci (Columbia University), Chinmay Nirkhe (University of Washington), and Mark Zhandry (NTT Research & Stanford University)
Abstract:
We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decidable with access only to a classical witness (QCMA). The separating classical oracle we construct is for a decision problem we coin spectral Forrelation – the oracle describes two subsets of the boolean hypercube, and the computational task is to decide if there exists a quantum state whose standard basis measurement distribution is well supported on one subset while its Fourier basis measurement distribution is well supported on the other subset. This is equivalent to estimating the spectral norm of a “Forrelation” matrix between two sets that are accessible through membership queries.
Our lower bound derives from a simple observation that a query algorithm with a classical witness can be run multiple times to generate many samples from a distribution, while a quantum witness is a “use once” object. This observation allows us to reduce proving a QCMA lower bound to proving a sampling hardness result which does not simultaneously prove a QMA lower bound. To prove said sampling hardness result for QCMA, we observe that quantum access to the oracle can be compressed by expressing the problem in terms of bosons – a novel “second quantization” perspective on compressed oracle techniques, which may be of independent interest. Using this compressed perspective on the sampling problem, we prove the sampling hardness result, completing the proof.
General note: In case of using gender-assigning attributes we include all those who consider themselves in this gender regardless of their own biological sex.