A Relativizing MIP for BQP
Ági Villányi | MIT
Complexity class containments involving interactive proof classes are famously nonrelativizing: although 𝖨𝖯=𝖯𝖲𝖯𝖠𝖢𝖤, Fortnow and Sipser showed that that there exists an oracle relative to which 𝖼𝗈𝖭𝖯⊈𝖨𝖯. In contrast, the question of whether the containment 𝖡𝖰𝖯⊆𝖨𝖯 is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment 𝖡𝖰𝖯⊆𝖬𝖨𝖯 holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle O, a 𝖯𝖢𝖯 proof system for 𝖡𝖰𝖯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 𝖨𝖯 for 𝖡𝖰𝖯 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.
Location
- QNC 1201
- Online on Zoom
-
Meeting ID: 912 8146 6256
Passcode: 494237
-