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 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 klog₂k. These two results prove communication complexity separations better than a constant number of bits.