Tensor norms and the classical communication complexity of nonlocal quantum measurement

We initiate the study of quantifying nonlocality of a bipartite measurement by the minimum amount of classical communication required to simulate the measurement. We derive general upper bounds in terms of some tensor norms of the measurement operator. As applications, we show that (a) if the amount of communication is a constant, then quantum and classical communication protocols with an unlimited amount of shared entanglement or shared randomness compute the same class of functions; and (b) it requires only a constant amount of communication to classically generate an approximation of the output distribution resulting from local measurements on an entangled quantum state, as long as the number of measurement outcomes is a constant.