1 Replies - 353 Views - Last Post: 14 April 2019 - 10:16 AM

#1 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12556
  • View blog
  • Posts: 45,683
  • Joined: 27-December 08

[News] Quantum Multiprover IP Contains NEEXP

Post icon  Posted 12 April 2019 - 07:16 PM

The following paper was posted to the arXiv last night. It is not peer reviewed. If true, this result would be a very big deal.

I spoke with our complexity theorist today. The intuition he provided for why MIP* is difficult to study, is that in the quantum setting, the provers can work in Hilbert spaces of arbitrary dimension. Given that, in the quantum setting, we are working over the complex numbers for a Hilbert space (as opposed to vector spaces over Z/2Z in the classical setting), there is a lot more room for the provers to work.

https://arxiv.org/abs/1904.05870

Quote

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.

This post has been edited by macosxnerd101: 12 April 2019 - 07:19 PM


Is This A Good Question/Topic? 0
  • +

Replies To: [News] Quantum Multiprover IP Contains NEEXP

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12556
  • View blog
  • Posts: 45,683
  • Joined: 27-December 08

Re: [News] Quantum Multiprover IP Contains NEEXP

Posted 14 April 2019 - 10:16 AM

One of the folks who showed that NEXP is contained in MIP* wrote a blog post about this new result that NEEXP is contained in MIP*. This is a more accessible summary of the key ideas in this new paper.

https://mycqstate.wo...t-ups-the-game/

This post has been edited by macosxnerd101: 14 April 2019 - 10:16 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1