{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihgt3bpjb3jx23ldu347omerxdkv3h3yxqjvkffdp6ycqee34hg2q",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mjj5oedyz4s2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.11952v1",
  "publishedAt": "2026-04-15T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Scott Aaronson",
    "Anand Natarajan",
    "Avishay Tal",
    "Agi Villanyi"
  ],
  "textContent": "**Authors:** Scott Aaronson, Anand Natarajan, Avishay Tal, Agi Villanyi\n\nComplexity class containments involving interactive proof classes are famously nonrelativizing: although $\\mathsf{IP} = \\mathsf{PSPACE}$, Fortnow and Sipser showed that that there exists an oracle relative to which $\\mathsf{coNP} \\not\\subseteq \\mathsf{IP}$. In contrast, the question of whether the containment $\\mathsf{BQP} \\subseteq \\mathsf{IP}$ is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment $\\mathsf{BQP} \\subseteq \\mathsf{MIP}$ holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle $O$, a $\\mathsf{PCP}$ proof system for $\\mathsf{BQP}^{O}$ where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle $O$. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the \"exponential PCP\" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an $\\mathsf{IP}$ for $\\mathsf{BQP}$ in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory.",
  "title": "A Relativizing MIP for BQP"
}