An exact quantum result exposes a limit of black-box verification proofs

A boundary for proofs, not a ban on verification

Can a classical computer check a quantum computation by questioning a computationally unrestricted prover? For polynomial-time quantum decision problems in the ordinary, oracle-free setting, complexity theory already gives a positive answer. Quantum polynomial time sits inside PSPACE, the class solvable with polynomial memory, and PSPACE equals IP, the class admitting classical interactive proofs.

The question in this paper is whether that containment survives when everyone receives access to the same arbitrary black box, called an oracle. A classical machine submits an address and receives a bit. A quantum machine can query the oracle in superposition.

In their November 9 arXiv preprint, Oral and Podder construct an oracle where the containment fails even for exact quantum computation. Their result concerns relativization: whether a theorem continues to hold with every shared oracle. It does not overturn the oracle-free containment or show that practical quantum computations cannot be verified.

What the construction separates

The authors construct a decision problem solvable in quantum polynomial time with certainty, relative to their oracle. This places it in the oracle-relative version of EQP. Yet it lies outside both IP and the polynomial hierarchy, or PH, relative to that same oracle.

An interactive proof pairs a polynomial-time classical verifier with an unrestricted prover. Its guarantees must let an honest prover convince the verifier on yes-instances while preventing any prover from doing so on no-instances, with a fixed gap between acceptance probabilities. The paper allows private verifier randomness and polynomially many messages.

PH describes classical computations with a fixed number of alternating existential and universal choices. Excluding both classes therefore requires more than showing that an ordinary classical query algorithm struggles.

Three queries, with no idealized error

The quantum algorithm uses a variant of Forrelation. Two functions assign either +1 or −1 to each n-bit address. Forrelation measures the normalized overlap of one function with the Fourier transform of the other—a way of detecting a structured relationship spread across their truth tables.

The promise is unusually precise: the overlap must be exactly +1/2 or −1/2.

A standard interference test converts these alternatives into probabilities of 3/4 and 1/4 for a designated outcome. One amplitude-amplification step transforms those probabilities into zero and one. Reading the complementary outcome distinguishes the two cases with certainty.

The full procedure uses three oracle queries and polynomially many other gates. The authors also supply an exact implementation over a fixed finite gate set. This is mathematical exactness in an ideal circuit model, not a claim that noisy hardware will operate without errors. Nor do three queries mean three elementary operations.

Repairing inputs without revealing their answer

The difficult part is constructing inputs that meet the exact promise while remaining hard for classical verifiers to distinguish.

Starting with a distribution whose overlap is merely near the target would not suffice. Simply conditioning it on exact equality could also destroy the features supporting the lower bound.

The authors instead develop a count-repair method. They first obtain a reference distribution in which, once the first function is fixed, the second function’s signs are independent. They group coordinates with equal Fourier-derived integer weights into bins. Within each bin, the overlap depends on how many signs are positive, not on their positions.

They adjust those counts to enforce the exact target, then choose the positive positions uniformly at random. Exceptional samples are replaced with an explicitly constructed valid input.

A small fractional adjustment is not automatically invisible. The repaired distribution can differ substantially from the reference distribution under unrestricted statistical tests. The proof instead bounds what the particular tests arising from interactive verifiers and PH computations can detect. It uses convex-function comparisons for the former and random restrictions that simplify Boolean circuits for the latter.

Building the shared oracle

Those indistinguishability bounds ensure that every resource-bounded classical candidate eventually fails on some promised input. The construction enumerates candidates, finds a failing input by exhaustive search, and fixes enough oracle bits to preserve that failure permanently.

The resulting oracle is recursive: an ordinary algorithm can compute every bit and halt. However, the paper gives no efficient running-time guarantee for constructing or evaluating it. The quantum solver receives oracle access; it does not perform that exhaustive search.

What remains limited

The contribution is a theoretical obstruction to relativizing proofs, strengthening an earlier bounded-error quantum separation to exact computation. It is not an experimental speedup or an oracle-free separation of complexity classes.

This account follows the supplied preprint, not an independent verification of its proofs. The manuscript also discloses substantial ChatGPT assistance with the construction and proofs; the authors state that they checked and developed the work and take responsibility for its correctness.