I'm currently on the look out for some good reference material relating non-local games with beneficial aspects in quantum communication. For instance, I am aware that non-local games are good at lower bounding communication complexity as well as ensuring the security of QKD protocols.

What I'd like to know is, what are some of the big papers in regard to non-local games in quantum communication? Have there been any recent advancements in this field that have been exceptionally important? Are there any good video abstracts/lectures/presentations on the web that parallel this material?

Specifically finding some material that relates quantum communication and the CHSH game would be of specific interest to myself as well.

Any feedback on this for any one of my questions would be very much appreciated. Thanks!


There was a talk at last year's AQIS'10 (Asian Quantum Information Science Conference) by Harry Buhrman, which dealt exactly on what your asking. The title was Quantum Non-locality, Communication Complexity, and Grothendieck Inequalities. I have the proceedings with me, and sadly there is only a 1-page abstract of his talk. However, the references give a good account of what you should check. I'll transcribe it below:

  1. Job Briet, Harry Buhrman, Troy Lee, and Thomas Vidick. Multi-player xor games with clique-wise entanglement.
  2. Jop Briet, Harry Buhrman, and Ben Toner. A generalized grothendieck inequality and entanglement in xor games. link
  3. R. Cleve, P. Hoyer, B. Toner, and J. Watrous. Same as the link given in Marcin Kotowski's answer.
  4. B.S. Tsirelson. Some results and problems on quantum Bell-type inequalities. Hadronic J. Suppl. 8(4):329-345, 1993.

Luckily, there is a video of a lecture given by Troy Lee about exactly the same subject. Grothendieck Inequalities, XOR Games, and Communication Complexity, presented at the Institute of Advance Study in 2009. This was a great talk!


What about "Consequences and Limits of Nonlocal Strategies" by Cleve, Hoyer, Toner and Watrous? It gives a pretty good introduction and then you can check e.g. other paper by Watrous

  • $\begingroup$ Hi Aaron. Yes, I've read this paper before and found it to be a terrific introduction to nonlocal games. However, I was wondering if there was something in the literature that focused more on increasing the efficiency of quantum communication protocols via nonlocal games. $\endgroup$ – Vincent Russo Jun 23 '11 at 23:31
  • $\begingroup$ @Vincent: The answer was actually provided by Marcin K. I just added a hyperlink to the article he suggested. You can see this by clicking on the edit history. $\endgroup$ – Aaron Sterling Jun 24 '11 at 14:47
  • $\begingroup$ Ah, sorry for the confusion Aaron, and thanks for the addition of the link. $\endgroup$ – Vincent Russo Jun 25 '11 at 13:55

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.