We study the two-party communication complexity of functions with large outputs, and show that the communication complexity can greatly vary depending on what output model is considered. We study a variety of output models, ranging from the open model, in which an external observer can compute the outcome, to the XOR model, in which the outcome of the protocol should be the bitwise XOR of the players' local outputs. This model is inspired by XOR games, which are widely studied two-player quantum games. We focus on the question of error-reduction in these new output models. For functions of output size k, applying standard error reduction techniques in the XOR model would introduce an additional cost linear in k. We show that no dependency on k is necessary. Similarly, standard randomness removal techniques, incur a multiplicative cost of
2k in the XOR model. We show how to reduce this factor to O(k). In addition, we prove analogous error reduction and randomness removal results in the other models, separate all models from each other, and show that some natural problems, including Set Intersection and Find the First Difference, separate the models when the Hamming weights of their inputs is bounded. Finally, we show how to use the rank lower bound technique for our weak output models.
In this work we introduce an intermediate setting between quantum nonlocality and communication complexity problems. More precisely, we study the value of XOR games
G when Alice and Bob are allowed to use a limited amount of one-way classical communication
ωo.w.−c(G) (resp. one-way quantum communication
ωo.w.−c∗(G)), where
c denotes the number of bits (resp. qubits). The key quantity here is the quotient
ωo.w.−c∗(G)/ωo.w.−c(G). We provide a universal way to obtain Bell inequality violations of general Bell functionals from XOR games for which the quotient
ωo.w.−c∗(G)/ωo.w.−2c(G) is larger than 1. This allows, in particular, to find (unbounded) Bell inequality violations from communication complexity problems in the same spirit as the recent work by Buhrman et al. (2016). We also provide an example of a XOR game for which the previous quotient is optimal (up to a logarithmic factor) in terms of the amount of information
c. Interestingly, this game has only polynomially many inputs per player. For the related problem of separating the classical vs quantum communication complexity of a function, the known examples attaining exponential separation require exponentially many inputs per party.
XOR games are a simple computational model with connections to many areas of complexity theory. Perhaps the earliest use of XOR games was in the study of quantum correlations. XOR games also have an interesting connection to Grothendieck's inequality, a fundamental theorem of analysis, which shows that two players sharing entanglement can achieve at most a constant factor advantage over players following classical strategies in an XOR game. Perez-Garcia et al. show that when the players share GHZ states, this advantage is bounded by a constant. We use a multilinear generalization of Grothendieck's inequality due to Blei and Tonge to simplify the proof of the second result and extend it to the case of so-called Schmidt states, answering an open problem of Perez-Garcia et al. Via a reduction given in that paper, this answers a 35-year-old problem in operator algebras due to Varopoulos, showing that the space of compact operators on a Hilbert space is a Q-algebra under Schur product. A further generalization of Grothendieck's inequality due to Carne lets us show that the gap between the entangled and classical value is at most a constant in any multiplayer XOR game in which the players are allowed to share combinations of GHZ states and EPR pairs of any dimension. As an application of our results, we show that the discrepancy method in communication complexity remains a lower bound in the multiparty model where the players have quantum communication and the kinds of entanglement discussed above. This answers an open question of Lee, Schechtman, and Shraibman.
We study the complexity of computing the commuting-operator value
ω∗ of entangled XOR games with any number of players. We introduce necessary and sufficient criteria for an XOR game to have
ω∗=1, and use these criteria to derive the following results: 1. An algorithm for symmetric games that decides in polynomial time whether
ω∗=1 or
ω∗<1, a task that was not previously known to be decidable, together with a simple tensor-product strategy that achieves value 1 in the former case. The only previous candidate algorithm for this problem was the Navascués-Pironio-Acín (also known as noncommutative Sum of Squares or ncSoS) hierarchy, but no convergence bounds were known. 2. A family of games with three players and with
ω∗<1, where it takes doubly exponential time for the ncSoS algorithm to witness this (in contrast with our algorithm which runs in polynomial time). 3. A family of games achieving a bias difference
2(ω∗−ω) arbitrarily close to the maximum possible value of
1 (and as a consequence, achieving an unbounded bias ratio), answering an open question of Briët and Vidick. 4. Existence of an unsatisfiable phase for random (non-symmetric) XOR games: that is, we show that there exists a constant
Ckunsat depending only on the number
k of players, such that a random
k-XOR game over an alphabet of size
n has
ω∗<1 with high probability when the number of clauses is above
Ckunsatn. 5. A lower bound of
Ω(nlog(n)/loglog(n)) on the number of levels in the ncSoS hierarchy required to detect unsatisfiability for most random 3-XOR games. This is in contrast with the classical case where the
n-th level of the sum-of-squares hierarchy is equivalent to brute-force enumeration of all possible solutions.
We show that for any Boolean function f : {0,1}n → {0,1}, the bounded-error quantum communication complexity Q∊(f ○ ⊕) of XOR functions f(x ⊕ y) satisfies that where d = deg2(f) is the ℱ2-degree of f, and ‖ ‖1,∊ = ming:‖f–g‖∞≤∊ ‖ĝ‖1. This implies that the previous lower bound Q∊(f ○ ⊕) = Ω(log ‖ ‖1,∊) by Lee and Shraibman [LS09] is tight for f with low 2-degree. The result also confirms the quantum version of the Log-rank Conjecture for low-degree XOR functions. In addition, we show that the exact quantum communication complexity satisfies where ‖ ‖0 is the number of nonzero Fourier coefficients of f. This matches the previous lower bound QE(f(x, y)) = Ω(logrank(Mf)) by Buhrman and de Wolf [BdW01] for low-degree XOR functions.
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). Our results apply to any non-signaling distribution, that is, those where Alice's marginal distribution does not depend on Bob's input, and vice versa.~~~By taking a geometric view of the non-signaling distributions, we introduce a simple new technique based on affine combinations of lower-complexity distributions, and we give the first general technique to apply to all these settings, with elementary proofs and very intuitive interpretations. 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. Despite their apparent simplicity, 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 as in the case of Boolean functions, 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. It also allows us to show that for some distributions, information theoretic methods are necessary to prove strong lower bounds. ~~~ 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 of this is a simple proof that any quantum distribution can be approximated with a constant number of bits of communication.