$\mathsf{BQP} \subseteq \mathsf{IP}$ Does Not Relativize
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.25680
curl -X POST /api/v1/records/arxiv/2609.25680/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.25680/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'