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.\mathrm{}$ 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\mathrm{}$ bits of communication when the parties share prior entanglement. We then show that without entangled particles, the one-round communication complexity of $G$ is $\mathrm{}(3/2)n+1.\mathrm{}$ Next we generalize this function to a function $F.\mathrm{}$ We show that if the parties share prior quantum entanglement, then the communication complexity of $F$ is exactly $k.\mathrm{}$ We also show that, if no entangled particles are provided, then the communication complexity of $F$ is roughly $k{\log }_{2}k.\mathrm{}$ These two results prove communication complexity separations better than a constant number of bits.