Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement

DOI10.1137/050644768MaRDI QIDQ3631890zbMATH OpenOpenAlexFDO

Authors Yaoyun Shi, Yufan Zhu

Publication date 22 June 2009

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0511071

zbMATH Keywords

Bell inequalityclassical simulationcommunication complexityquantum entanglementtensor norms

Mathematics Subject Classification ID

Tensor products in functional analysis (46M05) Tensor products of linear operators (47A80) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

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.

Recommendations

• The communication complexity of non-signaling distributions
• Information-based measure of nonlocality
• The Communication Complexity of Non-signaling Distributions
• Simulating quantum correlations with finite communication
• Quantum entanglement and communication complexity

Cited in

(9)

• Multipartite quantum correlation and communication complexities
• The communication complexity of non-signaling distributions
• The Communication Complexity of Non-signaling Distributions
• Simulating quantum correlations with finite communication
• scientific article; zbMATH DE number 7559121 (Why is no real title available?)
• A Communication-Efficient Nonlocal Measurement With Application to Communication Complexity and Bipartite Gate Capacities
• ON CLASSICAL TELEPORTATION AND CLASSICAL NON-LOCALITY
• Efficient protocols for generating bipartite classical distributions and quantum states
• Information-based measure of nonlocality

This page was built for publication: Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3631890)