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

References in corpus (5)

• The Communication Cost of Simulating Bell Correlations
• Further results on the cross norm criterion for separability
• On the capacities of bipartite Hamiltonians and unitary gates
• Bell Inequalities with Auxiliary Communication
• Lower bounds on the complexity of simulating quantum gates

Cited by in corpus (9)

• The communication complexity of non-signaling distributions
• Non-classicality of temporal correlations
• Local tests of global entanglement and a counterexample to the generalized area law
• Non-signaling deterministic models for non-local correlations have to be uncomputable
• On Dimension Bounds for Auxiliary Quantum Systems
• Quantum Blackjack or Can MIT Bring Down the House Again?
• Remote Sampling with Applications to General Entanglement Simulation
• Optical quantum communication complexity in the simultaneous message passing model
• Impossibility of memory in hidden-signaling models for quantum correlations