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

Fingerprint

Quantum communication
Quantum Communication
quantum communication
games
Communication Complexity
bells
Game
Bell's Inequality
quotients
communication
Communication
Quotient
Nonlocality
Qubit
functionals
Logarithmic

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

Cite this

Classical versus quantum communication in XOR games. / Junge, Marius; Palazuelos, Carlos; Villanueva, Ignacio.

In: Quantum Information Processing, Vol. 17, No. 5, 117, 01.05.2018.

Research output: Contribution to journalArticle

Junge, Marius ; Palazuelos, Carlos ; Villanueva, Ignacio. / Classical versus quantum communication in XOR games. In: Quantum Information Processing. 2018 ; Vol. 17, No. 5.
@article{b76be9920b134cecbde0abf074384fd1,
title = "Classical versus quantum communication in XOR games",
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.",
keywords = "Quantum communication, Quantum information, XOR games",
author = "Marius Junge and Carlos Palazuelos and Ignacio Villanueva",
year = "2018",
month = "5",
day = "1",
doi = "10.1007/s11128-018-1883-0",
language = "English (US)",
volume = "17",
journal = "Quantum Information Processing",
issn = "1570-0755",
publisher = "Springer New York",
number = "5",

}

TY - JOUR

T1 - Classical versus quantum communication in XOR games

AU - Junge, Marius

AU - Palazuelos, Carlos

AU - Villanueva, Ignacio

PY - 2018/5/1

Y1 - 2018/5/1

N2 - 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.

AB - 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.

KW - Quantum communication

KW - Quantum information

KW - XOR games

UR - http://www.scopus.com/inward/record.url?scp=85045049773&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045049773&partnerID=8YFLogxK

U2 - 10.1007/s11128-018-1883-0

DO - 10.1007/s11128-018-1883-0

M3 - Article

VL - 17

JO - Quantum Information Processing

JF - Quantum Information Processing

SN - 1570-0755

IS - 5

M1 - 117

ER -