We show lower bounds in the multi-party quantum communication complexity model. In this model, there are t parties where the ith party has input X/sub i/ /spl sube/ [n]. These parties communicate with each other by transmitting qubits to determine with high probability the value of some function F of their combined input (X/sub 1/,...,X/sub t/). We consider the class of Boolean valued functions whose value depends only on X/sub 1/ /spl cap/.../spl cap/ X/sub t/; that is, for each F in this class there is an f/sub F/ : 2/sup [n]/ /spl rarr/ {0,1}, such that F(X/sub 1/,...,X/sub t/) = f/sub F/(X/sub 1/ /spl cap/.../spl cap/ X/sub t/). We show that the t-party k-round communication complexity of F is /spl Omega/(s/sub m/(f/sub F/)/(k/sup 2/)), where s/sub m/(f/sub F/) stands for the monotone sensitivity of f/sub F/' and is defined by s/sub m/(f/sub F/) = /sup /spl utri// max/sub S/spl sube//[n] |{i : f/sub F/(S /spl cup/ {i}) /spl ne/ f/sub F/(S)}|. For two-party quantum communication protocols for the set disjointness problem, this implies that the two parties must exchange /spl Omega/(n/k/sup 2/) qubits. An upper bound of O(n/k) can be derived from the O(/spl radic/n) upper bound due to S. Aaronson and A. Ambainis (2003). For k = 1, our lower bound matches the /spl Omega/(n) lower bound observed by H. Buhrman and R. de Wolf (2001) (based on a result of A. Nayak (1999)), and for 2 /spl les/ k /spl Lt/ n/sup 1/4 /, improves the lower bound of /spl Omega/(/spl radic/n) shown by A. Razborov (2002). For protocols with no restrictions on the number of rounds, we can conclude that the two parties must exchange /spl Omega/(n/sup 1/3/) qubits. This, however, falls short of the optimal /spl Omega/ (/spl radic/n) lower bound shown by A. Razborov (2002). Our result is obtained by adapting to the quantum setting the elegant information-theoretic arguments of Z. Bar-Yossef et al. (2002). Using this method we can show similar lower bounds for the L/sub /spl infin// function considered in Z. Bar-Yossef et al. (2002).
We show lower bounds in the multi-party quantum communication complexity model. In this model, there are t parties where the ith party has input X/sub i/ /spl sube/ [n]. These parties communicate with each other by transmitting qubits to determine with high probability the value of some function F of their combined input (X/sub 1/,...,X/sub t/). We consider the class of Boolean valued functions whose value depends only on X/sub 1/ /spl cap/.../spl cap/ X/sub t/; that is, for each F in this class there is an f/sub F/ : 2/sup [n]/ /spl rarr/ {0,1}, such that F(X/sub 1/,...,X/sub t/) = f/sub F/(X/sub 1/ /spl cap/.../spl cap/ X/sub t/). We show that the t-party k-round communication complexity of F is /spl Omega/(s/sub m/(f/sub F/)/(k/sup 2/)), where s/sub m/(f/sub F/) stands for the monotone sensitivity of f/sub F/' and is defined by s/sub m/(f/sub F/) = /sup /spl utri// max/sub S/spl sube//[n] |{i : f/sub F/(S /spl cup/ {i}) /spl ne/ f/sub F/(S)}|. For two-party quantum communication protocols for the set disjointness problem, this implies that the two parties must exchange /spl Omega/(n/k/sup 2/) qubits. An upper bound of O(n/k) can be derived from the O(/spl radic/n) upper bound due to S. Aaronson and A. Ambainis (2003). For k = 1, our lower bound matches the /spl Omega/(n) lower bound observed by H. Buhrman and R. de Wolf (2001) (based on a result of A. Nayak (1999)), and for 2 /spl les/ k /spl Lt/ n/sup 1/4 /, improves the lower bound of /spl Omega/(/spl radic/n) shown by A. Razborov (2002). For protocols with no restrictions on the number of rounds, we can conclude that the two parties must exchange /spl Omega/(n/sup 1/3/) qubits. This, however, falls short of the optimal /spl Omega/ (/spl radic/n) lower bound shown by A. Razborov (2002). Our result is obtained by adapting to the quantum setting the elegant information-theoretic arguments of Z. Bar-Yossef et al. (2002). Using this method we can show similar lower bounds for the L/sub /spl infin// function considered in Z. Bar-Yossef et al. (2002).
We consider the class of functions whose value depends only on the intersection of the input X_1,X_2, ..., X_t; that is, for each F in this class there is an f_F: 2^{[n]} \to {0,1}, such that F(X_1,X_2, ..., X_t) = f_F(X_1 \cap X_2 \cap ... \cap X_t). We show that the t-party k-round communication complexity of F is Omega(s_m(f_F)/(k^2)), where s_m(f_F) stands for the `monotone sensitivity of f_F' and is defined by s_m(f_F) \defeq max_{S\subseteq [n]} |{i: f_F(S \cup {i}) \neq f_F(S)|. For two-party quantum communication protocols for the set disjointness problem, this implies that the two parties must exchange Omega(n/k^2) qubits. For k=1, our lower bound matches the Omega(n) lower bound observed by Buhrman and de Wolf (based on a result of Nayak, and for 2 <= k <= n^{1/4}, improves the lower bound of Omega(sqrt{n}) shown by Razborov. (For protocols with no restrictions on the number of rounds, we can conclude that the two parties must exchange Omega(n^{1/3}) qubits. This, however, falls short of the optimal Omega(sqrt{n}) lower bound shown by Razborov.)
We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with r rounds, we prove a lower bound of Omega(n/r) on the communication required for computing disjointness of input size n, which is optimal up to logarithmic factors. The previous best lower bound was Omega(n/r̂2) due to Jain, Radhakrishnan and Sen. Along the way, we develop several tools for quantum information complexity, one of which is a lower bound for quantum information complexity in terms of the generalized discrepancy method. As a corollary, we get that the quantum communication complexity of any boolean function f is at most 2 ̂O(QIC(f)), where QIC(f) is the prior-free quantum information complexity of f (with error 1/3).
Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function f:{-1,1}ⁿ → {-1,1} and •:{-1,1}² → {-1,1} the two-party bounded-error quantum communication complexity of (f ∘ •) is O(Q(f) log n), where Q(f) is the bounded-error quantum query complexity of f. Note that the bounded-error randomized communication complexity of (f ∘ •) is bounded by O(R(f)), where R(f) denotes the bounded-error randomized query complexity of f. Thus, the BCW simulation has an extra O(log n) factor appearing that is absent in classical simulation. A natural question is if this factor can be avoided. Razborov (IZV MATH'03) showed that the bounded-error quantum communication complexity of Set-Disjointness is Ω(√n). The BCW simulation yields an upper bound of O(√n log n). Høyer and de Wolf (STACS'02) showed that this can be reduced to c^(log^* n) for some constant c, and subsequently Aaronson and Ambainis (FOCS'03) showed that this factor can be made a constant. That is, the quantum communication complexity of the Set-Disjointness function (which is NOR_n ∘ ∧) is O(Q(NOR_n)). Perhaps somewhat surprisingly, we show that when • = ⊕, then the extra log n factor in the BCW simulation is unavoidable. In other words, we exhibit a total function F:{-1,1}ⁿ → {-1,1} such that Q^{cc}(F ∘ ⊕) = Θ(Q(F) log n). To the best of our knowledge, it was not even known prior to this work whether there existed a total function F and 2-bit function •, such that Q^{cc}(F ∘ •) = ω(Q(F)).
We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least α(n) on yes-inputs and at most β(n) on no-inputs, for some functions α(n) > β(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions α and β, and a near-complete characterization for public-coin protocols. In particular, we obtain a simple proof of a theorem of Braverman and Moitra (STOC 2013), who studied the case where α = 1/2+ (n) and β = 1/2− (n). The following contributions play a crucial role in our characterization and are interesting in their own right. (1) We introduce two communication analogues of the classical complexity class that captures small bounded-error computations: we define a “restricted” class SBP (which lies between MA and AM) and an “unrestricted” class USBP. The distinction between them is analogous to the distinction between the well-known communication classes PP and UPP. (2) We show that the SBP communication complexity is precisely captured by the classical corruption lower bound method. This sharpens a theorem of Klauck (CCC 2003). (3) We use information complexity arguments to prove a linear lower bound on the USBP complexity of set-disjointness.
We obtain a lower bound of n^Omega(1) on the k-party randomized communication complexity of the Disjointness function in the `Number on the Forehead' model of multiparty communication when k is a constant. For k=o(loglog n), the bounds remain super-polylogarithmic i.e. (log n)^omega(1). The previous best lower bound for three players until recently was Omega(log n). Our bound separates the communication complexity classes NP^{CC}_k and BPP^{CC}_k for k=o(loglog n). Furthermore, by the results of Beame, Pitassi and Segerlind \cite{BPS07}, our bound implies proof size lower bounds for tree-like, degree k-1 threshold systems and superpolynomial size lower bounds for Lovasz-Schrijver proofs. Sherstov \cite{She07b} recently developed a novel technique to obtain lower bounds on two-party communication using the approximate polynomial degree of boolean functions. We obtain our results by extending his technique to the multi-party setting using ideas from Chattopadhyay \cite{Cha07}. A similar bound for Disjointness has been recently and independently obtained by Lee and Shraibman.
A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical ones for computing a {\em total} Boolean function in the two-party interactive model. Razborov's result ({\em Izvestiya: Mathematics}, 67(1):145--159, 2002) implies the conjectured negative answer for functions F of the following form: F(x,y)=fn(x1⋅y1,x2⋅y2,...,xn⋅yn), where fn is a {\em symmetric} Boolean function on n Boolean inputs, and xi, yi are the i'th bit of x and y, respectively. His proof critically depends on the symmetry of fn. We develop a lower-bound method that does not require symmetry and prove the conjecture for a broader class of functions. Each of those functions F is the ``block-composition'' of a ``building block'' gk:{0,1}k×{0,1}k→{0,1}, and an fn:{0,1}n→{0,1}, such that F(x,y)=fn(gk(x1,y1),gk(x2,y2),...,gk(xn,yn)), where xi and yi are the i'th k-bit block of x,y∈{0,1}nk, respectively. We show that as long as g_k itself is "hard'' enough, its block-composition with an arbitrary f_n has polynomially related quantum and classical communication complexities. For example, when g_k is the Inner Product function with k=\Omega(\log n), the deterministic communication complexity of its block-composition with any f_n is asymptotically at most the quantum complexity to the power of 7.