### 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 language | English (US) |
---|---|

Article number | 117 |

Journal | Quantum Information Processing |

Volume | 17 |

Issue number | 5 |

DOIs | |

State | Published - May 1 2018 |

### Fingerprint

### 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

*Quantum Information Processing*,

*17*(5), [117]. https://doi.org/10.1007/s11128-018-1883-0

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

Research output: Contribution to journal › Article

*Quantum Information Processing*, vol. 17, no. 5, 117. https://doi.org/10.1007/s11128-018-1883-0

}

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

AN - SCOPUS:85045049773

VL - 17

JO - Quantum Information Processing

JF - Quantum Information Processing

SN - 1570-0755

IS - 5

M1 - 117

ER -