Multiparty Quantum Communication Complexity

Quantum entanglement cannot be used to simulate communication among remote parties, but it can reduce the communication needed for some problems. Let each out 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 show that, for a particular function $F$, if the parties share prior quantum entanglement, then the communication complexity of $F$ is exactly $k$. On the other hand, we also show that, if no entangled particles are provided, then the classical communication complexity of $F$ is roughly $k \log_2 k$. In terms of the number of parties, this proves for the first time a communication complexity separation better than a constant number of bits.