Zusammenfassung
We study multiprover interactive proof systems. The power of classical
multiprover interactive proof systems, in which the provers do not share
entanglement, was characterized in a famous work by Babai, Fortnow, and Lund
(Computational Complexity 1991), whose main result was the equality MIP = NEXP.
The power of quantum multiprover interactive proof systems, in which the
provers are allowed to share entanglement, has proven to be much more difficult
to characterize. The best known lower-bound on MIP* is NEXP, due to Ito and
Vidick (FOCS 2012). As for upper bounds, MIP* could be as large as RE, the
class of recursively enumerable languages.
The main result of this work is the inclusion of NEEXP (nondeterministic
doubly epxonential time) in MIP*. This is an exponential improvement over the
prior lower bound and shows that proof systems with entangled provers are at
least exponentially more powerful than classical provers. In our protocol the
verifier delegates a classical, exponentially large MIP protocol for NEEXP to
two entangled provers: the provers obtain their exponentially large questions
by measuring their shared state, and use a classical PCP to certify the
correctness of their exponentially-long answers. For the soundness of our
protocol, it is crucial that each player should not only sample its own
question correctly but also avoid performing measurements that would reveal the
other player's sampled question. We ensure this by commanding the players to
perform a complementary measurement, relying on the Heisenberg uncertainty
principle to prevent the forbidden measurements from being performed.
Beschreibung
[1904.05870] NEEXP in MIP*
Links und Ressourcen
Tags
Community