IQIM Postdoctoral and Graduate Student Seminar

Abstract: One of the most basic questions about quantum proof systems is whether quantum information is genuinely necessary in a proof, or whether a classical description would suffice. In complexity-theoretic terms, this asks whether allowing a verifier to receive a quantum witness (as in QMA) is strictly more powerful than restricting it to a classical witness (as in QCMA). While these classes remain unresolved in the unrelativized world, oracle separations offer a way to probe the structure of this question and isolate the source of any potential advantage. In this work, we show that quantum witnesses can indeed be strictly more powerful—even when the oracle itself is entirely classical. 

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 whether 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.

In this talk, I will outline the proof techniques for showing the oracle separation. The lower bound is derived 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.

A joint work with John Bostanci, Jonas Haferkamp, and Mark Zhandry.

Following the talk, lunch will be provided on the lawn outside East Bridge.