Yaoyun Shi

Tensor norms and the classical communication complexity of nonlocal quantum measurement

Nonlocality is at the heart of quantum information processing. In this work we investigate the minimum classical communication cost required to simulate a nonlocal quantum measurement. We give general upper bounds, which in turn translate to systematic classical simulations of quantum communication protocols.

Besides other concrete applications, we prove that if the cost of communication is constant, quantum and classical protocols, with shared entanglement and shared coins, respectively, compute the same class of functions. Our upper bounds are expressed in the forms of {\em tensor norms}, which capture the nonlocality of bipartite measurements in their own way and may be of independent interest and further applications.