6
$\begingroup$

The traditional definition of a nonlocal game is restricted to having two players and one round (e.g., here), but it is natural to consider a more general class of games that may have more than two players and more than one round of questions. While there has been a lot of work dealing with games with more than two players, I have found very little on multi-round games. For instance, there is a recent preprent of Crépeau and Yang that gives a definition of a multi-party, multi-round non-signaling distribution and seems to describe a multi-round game (although the paper is written in the language of commitment schemes rather than games, so I'm not entirely sure my interpretation is correct).

Has there been any other work dealing with multi-round games? And is there a reason so much of the literature has focused on single-round games? Are multi-round games inherently "no more interesting" than single-round games from the perspective of understanding nonlocality?

$\endgroup$
  • $\begingroup$ I think Debbie Leung might be able to give you some useful information about this, but I have not seen her here. You may like to ask her colleague @John Watrous since he does come here sometimes. $\endgroup$ – user1271772 Jul 3 '18 at 0:52
  • $\begingroup$ Hi and welcome to Quantum Computing Stack Exchange, Evan! Since you created the nonlocal-games, please consider writing the tag excerpt for it. Go here. Thank you. $\endgroup$ – Sanchayan Dutta Jul 5 '18 at 8:40
3
$\begingroup$

It seems that using more rounds will not be such helpful for us to get something more powerful from complexity perspectives. There are a few comments about the number of rounds and the number of players for $\mathsf{MIP}^*$ in Thomas Vidick's lecture note regarding quantum mutli-prover interactive proofs. Note that the non-local games are $\mathsf{MIP^*}$ protocols.

  • If we allow an extra prover and quantum messages (i.e. a $\mathsf{QMIP^*}$ protocol), then non-local games with polynomially many rounds can be parallelized to one round, which it proved by Kempe-Kobayashi-Matsumoto-Vidick. But as @John Watrous mentioned, we don't know how to do that for non-local games with classical messages, i.e. $\mathsf{MIP^*}$ protocol.

More details see section 6.3.2 in Watrous-Vidick's survey about quantum proofs, or the KKMV paper mentioned above.

  • But we did not know something similar for the number of provers, even the following could be true $\mathsf{MIP^*}(2,\mathrm{poly}) \subsetneq \mathsf{MIP^*}(3,\mathrm{poly}) \subsetneq \cdots$, where $\mathsf{MIP^*}(r,k)$ denote $r$-round $k$-prover non-local games. Namely, we may get something more powerful by adding new provers.
$\endgroup$
  • 2
    $\begingroup$ The essence of the answer, which is that multi-round versions of nonlocal games have been analyzed in the study of interactive proofs with entangled provers, is right on track. If it were my answer, though, I would not have led off with the suggestion that more rounds doesn't change anything: my reading of the question is that it is asking about something analogous to $\text{MIP}^{\ast}$ not $\text{QMIP}^{\ast}$, and as the answer points out it is not known if it is possible to parallelize $\text{MIP}^{\ast}$. $\endgroup$ – John Watrous Jul 3 '18 at 17:57
  • 1
    $\begingroup$ In fact, because the OP expresses an interest in nonlocality rather than complexity, a modified answer that just lists some pointers to work on multi-round interactive proofs with entangled provers might be enough. $\endgroup$ – John Watrous Jul 3 '18 at 17:59
  • $\begingroup$ @JohnWatrous Thanks for corrections! It is a little confusing for me... $\endgroup$ – Yupan Liu Jul 3 '18 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.