We introduce the communication problem QNDISJ, short for Quantum (Unique) Non-Disjointness, and study its complexity under different modes of communication complexity. The main motivation for the problem is that it is a candidate for the separation of the quantum communication complexity classes QMA and QCMA. The problem generalizes the Vector-in-Subspace and Non-Disjointness problems. We give tight bounds for the QMA, quantum, randomized communication complexities of the problem. We show polynomially related upper and lower bounds for the MA complexity. We also show an upper bound for QCMA protocols, and show that the bound is tight for a natural class of QCMA protocols for the problem. The latter lower bound is based on a geometric lemma, that states that every subset of the n-dimensional sphere of measure 2^-p must contain an ortho-normal set of points of size Omega(n/p). We also study a "small-spaces" version of the problem, and give upper and lower bounds for its randomized complexity that show that the QNDISJ problem is harder than Non-disjointness for randomized protocols. Interestingly, for quantum modes the complexity depends only on the dimension of the smaller space, whereas for classical modes the dimension of the larger space matters.
We introduce the communication problem QNDISJ, short for Quantum (Unique) Non-Disjointness, and study its complexity under different modes of communication complexity. The main motivation for the problem is that it is a candidate for the separation of the quantum communication complexity classes QMA and QCMA. The problem generalizes the Vector-in-Subspace and Non-Disjointness problems. We give tight bounds for the QMA, quantum, randomized communication complexities of the problem. We show polynomially related upper and lower bounds for the MA complexity. We also show an upper bound for QCMA protocols, and show that the bound is tight for a natural class of QCMA protocols for the problem. The latter lower bound is based on a geometric lemma, that states that every subset of the n-dimensional sphere of measure 2^-p must contain an ortho-normal set of points of size Omega(n/p). We also study a "small-spaces" version of the problem, and give upper and lower bounds for its randomized complexity that show that the QNDISJ problem is harder than Non-disjointness for randomized protocols. Interestingly, for quantum modes the complexity depends only on the dimension of the smaller space, whereas for classical modes the dimension of the larger space matters.
We study the power of quantum proofs, or more precisely, the power of Quantum Merlin-Arthur (QMA) protocols, in two well studied models of quantum computation: the black box model and the communication complexity model. Our main results are obtained for the communication complexity model. For this model, we identify a complete promise problem for QMA protocols, the Linear Subspaces Distance problem. The problem is of geometrical nature: Each player gets a linear subspace of R m and considers the sphere of unit vectors in that subspace. Their goal is to output 1 if the distance between the two spheres is very small (say, smaller than 0.1 · √ 2) and 0 if the distance is very large (say, larger than 0.9 · √ 2). We show that: 1. The QMA communication complexity of the problem is O(log m). 2. The (classical) MA communication complexity of the problem is Ω(m ɛ) (for some ɛ> 0). 3. The (standard) quantum communication complexity of the problem is Ω ( √ m). In particular, this gives an exponential separation between QMA communication complexity and MA communication complexity.
A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.
We study the power of quantum proofs, or more precisely, the power of quantum Merlin-Arthur (QMA) protocols, in two well studied models of quantum computation: the black box model and the communication complexity model. Our main results are obtained for the communication complexity model. For this model, we identify a complete promise problem for QMA protocols, the linear sub-spaces distance problem. The problem is of geometrical nature: each player gets a linear subspace of R/sup m/ and considers the sphere of unit vectors in that subspace. Their goal is to output 1 if the distance between the two spheres is very small (say, smaller than 0.1 /spl middot/ /spl radic/2) and 0 if the distance is very large (say, larger than 0.9 /spl middot/ /spl radic/2). We show that: 1. The QMA communication complexity of the problem is O(logm). 2. The (classical) MA communication complexity of the problem is /spl Omega/(m/sup /spl epsi//) (for some /spl epsi/ > 0). 3. The (standard) quantum communication complexity of the problem is /spl Omega/(/spl radic/m). In particular, this gives an exponential separation between QMA communication complexity and MA communication complexity. For the black box model we give several observations. First, we observe that the block sensitivity method, as well as the polynomial method for proving lower bounds for the number of queries, can both be extended to QMA protocols. We use these methods to obtain lower bounds for the QMA black box complexity of functions. In particular, we obtain a tight lower bound of /spl Omega/(N) for the QMA black box complexity of a random function, and a tight lower bound of /spl Omega/(/spl radic/N) for the QMA black box query complexity of NOR(X/sub 1/,..., X/sub n/). In particular, this shows that any attempt to give short quantum proofs for the class of languages Co - NP have to go beyond black box arguments. We also observe that for any Boolean function G(X/sub 1/,..., X/sub n/), if for both G and 7minus;G there are QMA black box protocols that make at most T queries to the black box, then there is a classical deterministic black box protocol for G that makes 0(T/sup 6/) queries to the black box. In particular, this shows that in the black box model QMA /spl cap/ Co - QMA = P. On the positive side, we observe that any (total or partial) Boolean function G(X/sub 1/,..., X/sub n/) has a QMA black box protocol with proofs of length N that makes only 0(/spl radic/N) queries to the black box. Finally, we observe a very simple proof for the exponential separation (for promise problems) between QMA black box complexity and (classical) MA black box complexity (first obtained by Watrous).
We prove that the randomized communication complexity of Vector-in-Subspace in Rn with error at most 1/3 is Θ(n). Alice holds a unit vector u and Bob holds an n/2-dimensional subspace H; they must distinguish u∈H from u∈H⊥. An exact one-way quantum protocol uses O(logn) qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's O(n) upper bound, improves the Ω(n1/3) lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's Ω(n) result.
The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.
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 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.)