A Quantum Algorithm That Provably Escapes the Classical Proof System — And the Oracle Trick That Makes It Work

EQP ⊄ IP relative to a recursive oracle. Three queries, zero error, and a clean separation that prior work only achieved for BQP.

Imagine you have a locked room with two envelopes. One contains a coin that always lands heads exactly half the time; the other lands tails exactly half the time. A classical detective can interrogate witnesses (the interactive proof system), run forensic labs (the polynomial hierarchy), and still never tell the envelopes apart — every test looks identical. But a quantum detective walks in, performs exactly three measurements, and announces the answer with certainty. That is the structural picture of this paper. The committed claim: there exists a recursive oracle O and a unary language L decidable by an exact quantum polynomial-time machine (EQP^O) that no interactive proof system (IP^O) and no level of the polynomial hierarchy (PH^O) can recognize. This strengthens Bouland, Fefferman, Nirkhe, and Vazirani's 2019 result, which proved the same separation for BQP (bounded-error quantum polynomial time). The upgrade from bounded error to exact — zero probability of being wrong — is the headline move. The technical engine is a variant of the Forrelation problem. Forrelation asks whether the normalized correlation between a Boolean function and the Fourier transform of another is close to +1/2 or −1/2. The original version tolerates slack: the promise gap is approximate. Oral and Podder need the promise to be exact — the correlation is precisely +1/2 or precisely −1/2 — because EQP demands certainty, not high probability. The central difficulty is that random Boolean function pairs almost never land on these exact values. The paper's main technical contribution is a "repair method": a procedure that surgically modifies distributions over Boolean function pairs so they are supported exactly on the ±1/2 levels, while preserving the statistical indistinguishability properties that make the IP and PH lower bounds go through. This is a relativization barrier result. It tells you that any proof of EQP ⊆ IP — if such a containment is even true in the unrelativized world — cannot work by techniques that relativize (i.e., that go through unchanged when you add an oracle). That is a structural constraint on proof strategy, not a direct complexity separation. The practical read: you now know that a whole category of proof attempts is dead on arrival for this question. The oracle is recursive (computable), which is a stronger statement than a random oracle separation — it rules out more proof strategies. The ladder here starts with Bouland et al. (2019), who separated BQP from IP relative to a random oracle. Raz and Tal (2019) separated BQP from PH relative to a random oracle using Forrelation. This paper unifies and strengthens both: EQP (a subset of BQP) separates from both IP and PH, relative to a single recursive oracle. The quantum algorithm uses only three queries and has zero error. Classical systems — even IP, which by Shamir's theorem equals PSPACE in the unrelativized world — cannot detect the difference under this oracle. Integrity is strong for a theory paper. The result is a mathematical proof, not a simulation or experiment. The key claim — correctness of the repair method — is a 50-page construction with explicit lemmas. There are no benchmarks to cherry-pick, no hyperparameters to tune. The validation regime is the proof itself, reviewable by any complexity theorist who can follow the measure-theoretic arguments. The attack surface is subtle errors in the indistinguishability analysis, which is where 50-page oracle constructions historically break. The obvious next experiment is extending the separation to promise problems or to quantum complexity classes with advice (EQP/poly). The authors explicitly note that their repair technique is tailored to unary languages. The harder prize — and likely the reason it's not in this paper — is an oracle separation of exact quantum computation from counting classes like PP or #P, which would require fundamentally different machinery. My read: the authors executed the natural strengthening of Bouland et al. cleanly and are probably exploring the counting-class boundary next, but that problem is genuinely harder, not just a compute limitation.