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 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 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 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)).
Given x,y∈{0,1}n , Set Disjointness consists in deciding whether xi=yi=1 for some index i∈[n] . We study the problem of computing this function in a distributed computing scenario in which the inputs x and y are given to the processors at the two extremities of a path of length d . Each vertex of the path has a quantum processor that can communicate with each of its neighbours by exchanging O(logn) qubits per round. We are interested in the number of rounds required for computing Set Disjointness with constant probability bounded away from 1/2 . We call this problem “Set Disjointness on a Line”. Set Disjointness on a Line was introduced by Le Gall and Magniez [ 14 ] for proving lower bounds on the quantum distributed complexity of computing the diameter of an arbitrary network in the CONGEST model. However, they were only able to provide a lower bound when the local memory used by the processors on the intermediate vertices of the path is severely limited. More precisely, their bound applies only when the local memory of each intermediate processor consists of O(logn) qubits. In this work, we prove an unconditional lower bound of Ω(3nd2+n) rounds for Set Disjointness on a Line with d+1 processors. This is the first non-trivial lower bound when there is no restriction on the memory used by the processors. The result gives us a new lower bound of Ω(3nδ2+n) on the number of rounds required for computing the diameter δ of any n -node network with quantum messages of size O(logn) in the CONGEST model. We draw a connection between the distributed computing scenario above and a new model of query complexity. In this model, an algorithm computing a bi-variate function f (such as Set Disjointness) has access to the inputs x and y through two separate oracles Ox and Oy , respectively. The restriction is that the algorithm is required to alternately make d queries to Ox and d queries to Oy , with input-independent computation in between queries. The model reflects a “switching delay” of d queries between a “round” of queries to x and the following “round” of queries to y . The information-theoretic technique we use for deriving the round lower bound for Set Disjointness on a Line also applies to the number of rounds in this query model. We provide an algorithm for Set Disjointness in this query model with round complexity that matches the round lower bound stated above, up to a polylogarithmic factor. This presents a barrier for obtaining a better round lower bound for Set Disjointness on the Line. At the same time, it hints at the possibility of better communication protocols for the problem.
In this paper, we focus on the quantum communication complexity of functions of the form f∘G=f(G(X1,Y1),…,G(Xn,Yn)) where $f: \Bset^n \to \Bset$ is a symmetric function, $G: \Bset^j \times \Bset^k \to \Bset$ is any function and Alice (resp. Bob) is given (Xi)i∈[n] (resp. (Yi)i∈[n]). Recently, Chakraborty et al. [STACS 2022] showed that the quantum communication complexity of f∘G is $O(Q(f)\QCCEX(G))$ when the parties are allowed to use shared entanglement, where Q(f) is the query complexity of f and $\QCCEX(G)$ is the exact communication complexity of G. }{In this paper, we first show that the same statement holds \emph{without both shared entanglement and shared randomness}, which generalizes their result. Based on the improved result, we next show tight upper bounds on f∘AND2 for any symmetric function f (where $\textrm{AND}_2 : \Bset \times \Bset \to \Bset$ denotes the 2-bit AND function) in both models: with shared entanglement and without shared entanglement. This matches the well-known lower bound by Razborov~[Izv. Math. 67(1) 145, 2003] when shared entanglement is allowed and improves Razborov's bound when shared entanglement is not allowed.
We study the set disjointness problem in the most powerful model of bounded-error communication, the k -party randomized number-on-the-forehead model. We show that set disjointness requires Ω(√n/2 k k ) bits of communication, where n is the size of the universe. Our lower bound generalizes to quantum communication, where it is essentially optimal. Proving this bound was a longstanding open problem even in restricted settings, such as one-way classical protocols with k =4 parties [Wigderson 1997]. The proof contributes a novel technique for lower bounds on multiparty communication, based on directional derivatives of protocols over the reals.