{"id":"arxiv/2609.25680","url":"https://arxiv.org/abs/2609.25680","tags":["quant-ph","cs.CC"],"score":0,"title":"$\\mathsf{BQP} \\subseteq \\mathsf{IP}$ Does Not Relativize","domain":"quant-ph","source":"arxiv","authors":["Adam Bouland","Andrew Huang","Anand Natarajan","Itay Shalit","Avishay Tal"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-22","reactions":{}}