Quantum one way vs. classical two way communication in XOR games

• URL: http://arxiv.org/abs/2003.09747v1
• Date: Sat, 21 Mar 2020 20:30:31 GMT
• Title: Quantum one way vs. classical two way communication in XOR games
• Authors: Abderram\'an Amr and Ignacio Villanueva
• Abstract summary: We show an example of a XOR game for which $O(n)$ bits of two way classical communication are needed. We also find a characterization for the value of a XOR game assisted with a limited amount of two way communication.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work we give an example of exponential separation between quantum and classical resources in the setting of XOR games assisted with communication. Specifically, we show an example of a XOR game for which $O(n)$ bits of two way classical communication are needed in order to achieve the same value as can be attained with $\log n$ qubits of one way communication. We also find a characterization for the value of a XOR game assisted with a limited amount of two way communication in terms of tensor norms of normed spaces.

Related papers

• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover. We establish a quantum soundness result for all compiled two-player nonlocal games.
  arXiv  Detail & Related papers  (2024-08-13T08:11:56Z)
• Photonic implementation of the quantum Morra game [69.65384453064829]
  We study a faithful translation of a two-player quantum Morra game, which builds on previous work by including the classical game as a special case. We propose a natural deformation of the game in the quantum regime in which Alice has a winning advantage, breaking the balance of the classical game. We discuss potential applications of the quantum Morra game to the study of quantum information and communication.
  arXiv  Detail & Related papers  (2023-11-14T19:41:50Z)
• Communication complexity of entanglement assisted multi-party computation [11.820804392113294]
  We consider a multi-party computation problem with $n$ players, where players $2, dots, n$ need to communicate appropriate information to player 1. We exhibit a quantum protocol (with complexity $(n-1) log n$ bits) and a classical protocol (with complexity $(n-1)2 (log n2$) bits) This demonstrates that our quantum protocol is strictly better than classical protocols.
  arXiv  Detail & Related papers  (2023-05-08T03:10:08Z)
• On the power of quantum entanglement in multipartite quantum XOR games [3.655021726150368]
  In particular, quantum entanglement can be a much more powerful resource than local operations and classical communication to play these games. This result shows a strong contrast to the bipartite case, where it was recently proved that the entangled bias is always upper bounded by a universal constant times the one-way classical communication bias.
  arXiv  Detail & Related papers  (2023-02-23T06:26:37Z)
• Connecting XOR and XOR* games [0.0]
  We focus on two classes of games: XOR nonlocal games and XOR* sequential games with monopartite resources. We prove that under certain assumptions these two classes of games can be related via an explicit theorem that connects their optimal strategies.
  arXiv  Detail & Related papers  (2022-10-02T00:11:38Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• Constructive nonlocal games with very small classical values [0.0]
  This paper is devoted to analyzing classical values of the so-called linear games. We employ nontrivial results from graph theory and number theoretic results used earlier in the context of harmonic analysis.
  arXiv  Detail & Related papers  (2021-12-14T20:55:16Z)
• On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
  We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  arXiv  Detail & Related papers  (2021-12-09T21:06:52Z)
• Computation-aided classical-quantum multiple access to boost network communication speeds [61.12008553173672]
  We quantify achievable quantum communication rates of codes with computation property for a two-sender cq-MAC. We show that it achieves the maximum possible communication rate (the single-user capacity), which cannot be achieved with conventional design.
  arXiv  Detail & Related papers  (2021-05-30T11:19:47Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.