The communication complexity of non-signaling distributions

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.

23 pages. V2: major modifications, extensions and additions compared to V1. V3 (21 pages): proofs have been updated and simplified, particularly Theorem 10 and Theorem 22. V4 (23 pages): Section 3.1 has been rewritten (in particular Lemma 10 and its proof), and various minor modifications have been made. V5 (24 pages): various modifications in the presentation

References in corpus (11)

• Quantum Communication
• A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
• The Communication Cost of Simulating Bell Correlations
• A generalized no-broadcasting theorem
• Large violation of Bell inequalities with low entanglement
• Operator Space theory: a natural framework for Bell inequalities
• Simulation of partial entanglement with nonsignaling resources
• Simulation of bipartite qudit correlations
• Near-Optimal and Explicit Bell Inequality Violations
• Strengths and Weaknesses of Quantum Fingerprinting
• Classical Interaction Cannot Replace Quantum Nonlocality

Cited by in corpus (18)

• Large violation of Bell inequalities with low entanglement
• Operator Space theory: a natural framework for Bell inequalities
• Unbounded violations of bipartite Bell Inequalities via Operator Space theory
• Lower bounds on information complexity via zero-communication protocols and applications
• Simulating all non-signalling correlations via classical or quantum theory with negative probabilities
• Categorical Probabilistic Theories
• Near-Optimal and Explicit Bell Inequality Violations
• Bell's nonlocality in a general nonsignaling case: quantitatively and conceptually
• Quantum advantages of communication complexity from Bell nonlocality
• Robust Bell inequalities from communication complexity
• Contextuality in composite systems: the role of entanglement in the Kochen-Specker theorem
• Classical and quantum partition bound and detector inefficiency
• On the existence of a local quasi hidden variable (LqHV) model for each N-qudit state and the maximal quantum violation of Bell inequalities
• Information Causality is a Special Point in the Dual of the Gray-Wyner Region
• Better Non-Local Games from Hidden Matching
• Unbounded Bell violations for quantum genuine multipartite non-locality
• The communication complexity of XOR games via summing operators
• Tripartite probability distributions and communication complexity