|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Multiplayer XOR games and quantum communication complexity with clique-wise entanglement | | Jop Briet
; Harry Buhrman
; Troy Lee
; Thomas Vidick
; | | Date: |
20 Nov 2009 | | Abstract: | XOR games are a simple computational model with connections to many areas of
complexity theory. Perhaps the earliest use of XOR games was in the study of
quantum correlations. XOR games also have an interesting connection to
Grothendieck’s inequality, a fundamental theorem of analysis, which shows that
two players sharing entanglement can achieve at most a constant factor
advantage over players following classical strategies in an XOR game.
Perez-Garcia et al. show that when the players share GHZ states, this
advantage is bounded by a constant. We use a multilinear generalization of
Grothendieck’s inequality due to Blei and Tonge to simplify the proof of the
second result and extend it to the case of so-called Schmidt states, answering
an open problem of Perez-Garcia et al. Via a reduction given in that paper,
this answers a 35-year-old problem in operator algebras due to Varopoulos,
showing that the space of compact operators on a Hilbert space is a Q-algebra
under Schur product.
A further generalization of Grothendieck’s inequality due to Carne lets us
show that the gap between the entangled and classical value is at most a
constant in any multiplayer XOR game in which the players are allowed to share
combinations of GHZ states and EPR pairs of any dimension.
As an application of our results, we show that the discrepancy method in
communication complexity remains a lower bound in the multiparty model where
the players have quantum communication and the kinds of entanglement discussed
above. This answers an open question of Lee, Schechtman, and Shraibman. | | Source: | arXiv, 0911.4007 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER