We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles in an entangled quantum state. We show that, although a prior quantum entanglement cannot be used to simulate a communication channel, it can reduce the communication complexity of functions in some cases. Specifically, we show that, for a particular function among three parties (each of which possesses part of the function's input), a prior quantum entanglement enables them to learn the value of the function with only three bits of communication occurring among the parties, whereas, without quantum entanglement, four bits of communication are necessary. We also show that, for a particular two-party probabilistic communication complexity problem, quantum entanglement results in less communication than is required with only classical random correlations (instead of quantum entanglement). These results are a noteworthy contrast to the well-known fact that quantum entanglement cannot be used to actually simulate communication among remote parties.
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.