Quantum one-way versus classical two-way communication in XOR games

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