The Communication Complexity of Non-signaling Distributions

DOI10.1007/978-3-642-03816-7_24MaRDI QIDQ3182931zbMATH OpenOpenAlexFDO

Authors Julien Degorre, Sophie Laplante, Jérémie Roland, Marc Kaplan

Publication date 16 October 2009

Published in Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0804.4859

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: We study a model of communication complexity that encompasses many well-studied problems, including classical and quantum communication complexity, the complexity of simulating distributions arising from bipartite measurements of shared quantum states, and XOR games. In this model, Alice gets an input x, Bob gets an input y, and their goal is to each produce an output a,b distributed according to some pre-specified joint distribution p(a,b|x,y). We introduce a new technique based on affine combinations of lower-complexity distributions. Specifically, we introduce two complexity measures, one which gives lower bounds on classical communication, and one for quantum communication. These measures can be expressed as convex optimization problems. We show that the dual formulations have a striking interpretation, since they coincide with maximum violations of Bell and Tsirelson inequalities. The dual expressions are closely related to the winning probability of XOR games. These lower bounds subsume many known communication complexity lower bound methods, most notably the recent lower bounds of Linial and Shraibman for the special case of Boolean functions. We show that the gap between the quantum and classical lower bounds is at most linear in the size of the support of the distribution, and does not depend on the size of the inputs. This translates into a bound on the gap between maximal Bell and Tsirelson inequality violations, which was previously known only for the case of distributions with Boolean outcomes and uniform marginals. Finally, we give an exponential upper bound on quantum and classical communication complexity in the simultaneous messages model, for any non-signaling distribution. One consequence is a simple proof that any quantum distribution can be approximated with a constant number of bits of communication.

Recommendations

• The communication complexity of non-signaling distributions
• Communication complexity under product and nonproduct distributions
• Amortized Communication Complexity of Distributions
• Non-deterministic communication complexity with few witnesses
• Communication complexity of secure distributed computation in the presence of noise
• Probabilistic communication complexity
• A note on non-deterministic communication complexity with few witnesses
• Communication Complexity and Quasi Randomness
• Probabilistic communication complexity over the reals
• The communication complexity of private simultaneous messages, revisited

Cites work

• Approximating the Cut-Norm via Grothendieck's Inequality
• Bell inequalities with auxiliary communication
• Communication Complexity
• Complexity measures of sign matrices
• Lower bounds in communication complexity based on factorization norms
• On the power of quantum fingerprinting
• Simulating quantum correlations with finite communication
• Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement
• Tensor products and probability weights
• Tensor products in generalized measure theory
• Towards quantifying non-local information transfer: finite-bit non-locality

Cited in

(18)

• Non-deterministic communication complexity with few witnesses
• Bell's nonlocality in a general nonsignaling case: Quantitatively and conceptually
• Optimal non-signalling violations via tensor norms
• On the existence of a local quasi hidden variable (LqHV) model for each n-qudit state and the maximal quantum violation of Bell inequalities
• Classical and quantum partition bound and detector inefficiency
• Bell scenarios with communication
• The communication complexity of non-signaling distributions
• Categorical probabilistic theories
• Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement
• Amortized Communication Complexity of Distributions
• Communication complexity of secure distributed computation in the presence of noise
• Testing linearity against non-signaling strategies
• Unbounded Bell violations for quantum genuine multipartite non-locality
• scientific article; zbMATH DE number 7250157 (Why is no real title available?)
• The Hilbertian tensor norm and entangled two-prover games
• Robust Bell inequalities from communication complexity
• Unbounded violations of bipartite Bell inequalities via operator space theory
• Large violation of Bell inequalities with low entanglement

This page was built for publication: The Communication Complexity of Non-signaling Distributions

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