A Relativizing MIP for BQP

Complexity 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} notsubseteq 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.