Multiparty quantum communication complexity

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 kappa parties hold some partial input data to some fixed kappa-variable function f. The communication complexity off is the minimum number of classical bits required to be broadcasted for every party to know the value off 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+l 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 k log, k. These two results prove communication complexity separations better than a constant number of bits. [S1050-2947(99)05209-9].