Nick Spooner, University of Southern California, Berkeley
Understanding the computational power of multi-prover interactive proofs where the provers may share entanglement -- the complexity class MIP* -- is a central question in quantum computation. In 2012, Ito and Vidick showed that this model is at least as powerful as MIP, i.e. NEXP is contained in MIP*. The original motivation for the introduction of multi-prover interactive proofs, however, was studying unconditional zero knowledge: while single-prover interactive proofs with unconditional zero knowledge are limited to the complexity class SZK, which is not believed to contain NP, with non-communicating provers unconditional zero knowledge is 'for free': ZK-MIP = NEXP. A natural question, then, is: what is the power of ZK-MIP*? This is not immediately clear from the other results, because the techniques used to obtain them seem to be incompatible. In this work, we show that ZK-MIP* contains NEXP, developing new algebraic tools for zero knowledge which are compatible with the Ito-Vidick framework.