Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement

Abstract

We initiate the study of quantifying nonlocalness of a bipartite measurement by the minimum amount of classical communication required to simulate the measurement. We derive general upper bounds, which are expressed in terms of certain tensor norms of the measurement operator. As applications, we show that (a) If the amount of communication is constant, quantum and classical communication protocols with unlimited amount of shared entanglement or shared randomness compute the same set of functions; (b) A local hidden variable model needs only a constant amount of communication to create, within an arbitrarily small statistical distance, a distribution resulted from local measurements of an entangled quantum state, as long as the number of measurement outcomes is constant.

A preliminary version of this paper appears as part of an article in Proceedings of the the 37th ACM Symposium on Theory of Computing (STOC 2005), 460--467, 2005