Skip to content

BQP ⊆ IP Does Not Relativize

Sep 2026 · arXiv.org · Vol abs/2609.25680 · 1 citation · ⚡ 1 influential · 22 references
Physics Computer Science

TL;DR

It is shown that any prover-efficient classical interactive protocol for the BQP must rely on non-relativizing techniques, which might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.

Abstract

We construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between $\mathsf{IP}$ and $\mathsf{MIP}$, answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions $f$ and $g$, the goal is to determine if $f$ is correlated with the Fourier spectrum of $g$. While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier. Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions. Our results imply that any prover-efficient classical interactive protocol for $\mathsf{BQP}$ must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.

View source

Similar papers

Preprint Sep 2026

Oracle Separations in the Fourier Hierarchy

The Fourier hierarchy $\mathrm{FH}_0\subseteq\mathrm{FH}_1\subseteq\mathrm{FH}_2\subseteq\cdots$, introduced by Shi (TCS 2005), measures a quantum computation by the number of Hadamard layers it uses. Between two layers the circuit may permute basis states and attach phases, but it may not create superposition; the lay...

A. Mantri · 0 citations
Preprint Nov 2026

$\mathsf{RCA}_0$ Proves the Collapse of the Intersection Principles Hierarchy

This paper shows that the pairwise intersection principle ($2\mathrm{IP}$) implies, over $\mathsf{RCA}_0$, the existence of a Cohen $1$-generic real relative to every given set. Together with the known implications, this yields the equivalence over $\mathsf{RCA}_0$ of the finite intersection principle (FIP), $2\mathrm{...

Patrizio Cintioli · 1 citation
Preprint Oct 2026

Unitary complexity in polynomial space

We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or $\mathsf{BPP} \neq \mathsf{NEXP}$. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. W...

William Kretschmer, Ewin Tang · 1 citation
Sep 2026

Constant-Probability Witness Isolation Implies NP in P/poly

It is shown that every positive constant already implies the collapse: if a randomized nonuniform polynomial-size pruning procedure succeeds with probability $\epsilon$ on affine circuit inputs with at most $2^{\lfloor 2/\epsilon\rfloor}$ satisfying assignments, then $\mathrm{NP}\subseteq\mathrm{P/poly}$.

Sebastian Ben Daniel · 1 citation
Preprint Sep 2026

Maltsev Constraint Satisfaction Problems and Deterministic Logspace With Counting

In this article, we prove that the problem of solving $\operatorname{CSP}(\mathbf{A})$, where $\mathbf{A}$ is a finite relational template which admits a Maltsev polymorphism is in a specific complexity class DET, which is related to the complexity of computing the determinant of a matrix with integer entries. Such a c...

D. Delic, Ali Syed · 1 citation
Preprint Oct 2026

$\exists \mathbb{R} \subseteq \textsf{CH}$

The existential theory of the reals asks whether polynomial constraints with integer coefficients have a real solution. We give a proof placing this problem in the counting hierarchy. The first argument is intended to expose the essential steps, and a separate analysis lowers the bound to $\exists \mathbb{R}\subseteq\t...

Alex Meiburg · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.