BQP ⊆ IP Does Not Relativize
Abstract
We construct an oracle relative to which BQP not⊆ 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 IP and 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 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.
Related
- The inverted pendulum model does not cover natural dynamic balance actions in challenging postures
- Why does CO₂ plasma chamber seasoning favor nanocrystalline silicon growth?
- Polarons in Lead-Halide Perovskites: What the Structural Evidence Does and Does Not Establish
- Bell nonlocality does not imply violation of nonlocal games
- Second largest eigenvalue does not bound stationary entropy production
BibTeX
@misc{bouland2026does,
title = {{$\mathsfBQP \subseteq \mathsfIP$ Does Not Relativize}},
author = {Adam Bouland and Andrew Huang and Anand Natarajan and Itay Shalit and Avishay Tal},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25680},
eprint = {2609.25680},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25680},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - BQP ⊆ IP Does Not Relativize
AU - Adam Bouland
AU - Andrew Huang
AU - Anand Natarajan
AU - Itay Shalit
AU - Avishay Tal
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.25680
UR - https://arxiv.org/abs/2609.25680
AB - We construct an oracle relative to which BQP not⊆ 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 IP and 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 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.
ER -