TY - GEN

T1 - Amortized communication complexity of distributions

AU - Roland, Jérémie

AU - Szegedy, Mario

PY - 2009

Y1 - 2009

N2 - Consider the following general communication problem: Alice and Bob have to simulate a probabilistic function p, that with every associates a probability distribution on . The two parties, upon receiving inputs x and y, need to output , in such a manner that the (a,b) pair is distributed according to p(x,y). They share randomness, and have access to a channel that allows two-way communication. Our main focus is an instance of the above problem coming from the well known EPR experiment in quantum physics. In this paper, we are concerned with the amount of communication required to simulate the EPR experiment when it is repeated in parallel a large number of times, giving rise to a notion of amortized communication complexity. In the 3-dimensional case, Toner and Bacon showed that this problem could be solved using on average 0.85 bits of communication per repetition [1]. We show that their approach cannot go below 0.414 bits, and we give a fundamentally different technique, relying on the reverse Shannon theorem, which allows us to reduce the amortized communication to 0.28 bits for dimension 3, and 0.410 bits for arbitrary dimension. We also give a lower bound of 0.13 bits for this problem (valid for one-way protocols), and conjecture that this could be improved to match the upper bounds. In our investigation we find interesting connections to a number of different problems in communication complexity, in particular to [2]. The results contained herein are entirely classical and no knowledge of the quantum phenomenon is assumed.

AB - Consider the following general communication problem: Alice and Bob have to simulate a probabilistic function p, that with every associates a probability distribution on . The two parties, upon receiving inputs x and y, need to output , in such a manner that the (a,b) pair is distributed according to p(x,y). They share randomness, and have access to a channel that allows two-way communication. Our main focus is an instance of the above problem coming from the well known EPR experiment in quantum physics. In this paper, we are concerned with the amount of communication required to simulate the EPR experiment when it is repeated in parallel a large number of times, giving rise to a notion of amortized communication complexity. In the 3-dimensional case, Toner and Bacon showed that this problem could be solved using on average 0.85 bits of communication per repetition [1]. We show that their approach cannot go below 0.414 bits, and we give a fundamentally different technique, relying on the reverse Shannon theorem, which allows us to reduce the amortized communication to 0.28 bits for dimension 3, and 0.410 bits for arbitrary dimension. We also give a lower bound of 0.13 bits for this problem (valid for one-way protocols), and conjecture that this could be improved to match the upper bounds. In our investigation we find interesting connections to a number of different problems in communication complexity, in particular to [2]. The results contained herein are entirely classical and no knowledge of the quantum phenomenon is assumed.

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

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

U2 - 10.1007/978-3-642-02927-1_61

DO - 10.1007/978-3-642-02927-1_61

M3 - Conference contribution

AN - SCOPUS:70449122801

SN - 3642029264

SN - 9783642029264

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 738

EP - 749

BT - Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings

T2 - 36th International Colloquium on Automata, Languages and Programming, ICALP 2009

Y2 - 5 July 2009 through 12 July 2009

ER -