This paper describes a general quantum lower bounding technique for the communication complexity of a function that depends on the inputs given to two parties connected via paths, which may be shared with other parties, on a network of any topology. The technique can also be employed to obtain a lower-bound of the quantum communication complexity of some functions that depend on the inputs distributed over all parties on the network. As a typical application, we apply our technique to the distinctness problem of deciding whether there are a pair of parties with identical inputs, on a k-party ring; almost matching upper bounds are also given.
This paper describes a general quantum lower bounding technique for the communication complexity of a function that depends on the inputs given to two parties connected via paths, which may be shared with other parties, on a network of any topology. The technique can also be employed to obtain a lower-bound of the quantum communication complexity of some functions that depend on the inputs distributed over all parties on the network. As a typical application, we apply our technique to the distinctness problem of deciding whether there are a pair of parties with identical inputs, on a k-party ring; almost matching upper bounds are also given.
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 study the communication complexity of a number of graph properties where the edges of the graph G are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: * An Omega(n) lower bound on the quantum communication complexity of deciding whether an n-vertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. * A deterministic upper bound of O(n^{3/2}log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. * A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for the quantum communication complexity of this problem. The first two quantum lower bounds are obtained by exhibiting a reduction from the n-bit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if G is triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix.
The focus of this paper is on {\em quantum distributed} computation, where we investigate whether quantum communication can help in {\em speeding up} distributed network algorithms. Our main result is that for certain fundamental network problems such as minimum spanning tree, minimum cut, and shortest paths, quantum communication {\em does not} help in substantially speeding up distributed algorithms for these problems compared to the classical setting. In order to obtain this result, we extend the technique of Das Sarma et al. [SICOMP 2012] to obtain a uniform approach to prove non-trivial lower bounds for quantum distributed algorithms for several graph optimization (both exact and approximate versions) as well as verification problems, some of which are new even in the classical setting, e.g. tight randomized lower bounds for Hamiltonian cycle and spanning tree verification, answering an open problem of Das Sarma et al., and a lower bound in terms of the weight aspect ratio, matching the upper bounds of Elkin [STOC 2004]. Our approach introduces the {\em Server model} and {\em Quantum Simulation Theorem} which together provide a connection between distributed algorithms and communication complexity. The Server model is the standard two-party communication complexity model augmented with additional power; yet, most of the hardness in the two-party model is carried over to this new model. The Quantum Simulation Theorem carries this hardness further to quantum distributed computing. Our techniques, except the proof of the hardness in the Server model, require very little knowledge in quantum computing, and this can help overcoming a usual impediment in proving bounds on quantum distributed algorithms.
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.
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.
Quantum entanglement cannot be used to achieve direct communication between remote parties, but it can reduce the communication needed for some problems. Let each of k parties hold some partial input data to some fixed k-variable function f. The communication complexity of f is the minimum number of classical bits required to be broadcasted for every party to know the value of f on their inputs. We construct a function G such that for the one-round communication model and three parties, G can be computed with n+1 bits of communication when the parties share prior entanglement. We then show that without entangled particles, the one-round communication complexity of G is (3/2)n+1. Next we generalize this function to a function F. We show that if the parties share prior quantum entanglement, then the communication complexity of F is exactly k. We also show that, if no entangled particles are provided, then the communication complexity of F is roughly klog2k. These two results prove communication complexity separations better than a constant number of bits.