Classical versus quantum communication in XOR games

Marius Junge, Carlos Palazuelos, Ignacio Villanueva

Research output: Contribution to journalArticle

Abstract

We introduce an intermediate setting between quantum nonlocality and communication complexity problems. More precisely, we study the value of XOR games when Alice and Bob are allowed to use a limited amount (c bits) of one-way classical communication compared to their value when they are allowed to use the same amount of one-way quantum communication (c qubits). The key quantity here is the ratio between the quantum and classical value. We provide a universal way to obtain Bell inequality violations of general Bell functionals from XOR games for which the previous quotient is larger than 1. This allows, in particular, to find (unbounded) Bell inequality violations from communication complexity problems in the same spirit as the recent work by Buhrman et al. (PNAS 113(12):3191–3196, 2016). We also provide an example of a XOR game for which the previous quotient is optimal (up to a logarithmic factor) in terms of the amount of information c. Interestingly, this game has only polynomially many inputs per player. For the related problem of separating the classical versus quantum communication complexity of a function, the known examples attaining exponential separation require exponentially many inputs per party.

Original languageEnglish (US)
Article number117
JournalQuantum Information Processing
Volume17
Issue number5
DOIs
StatePublished - May 1 2018

Keywords

  • Quantum communication
  • Quantum information
  • XOR games

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Statistical and Nonlinear Physics
  • Theoretical Computer Science
  • Signal Processing
  • Modeling and Simulation
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Classical versus quantum communication in XOR games'. Together they form a unique fingerprint.

  • Cite this