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.
Quantum computing resources have been known to provide speed-ups in computational complexity in many algorithms. The impact of these resources in communication, however, has not attracted much attention. We investigate the impact of \nquantum entanglement on communication complexity. We provide a positive result, \nby presenting a class of multi-party communication problems wherein the presence of \na suitable quantum entanglement lowers the classical communication complexity. We \nshow that, in evaluating certains function whose parameters are distributed among \nvarious parties, the presence of prior entanglement can help in reducing the required \ncommunication. We also present an outline of realizing the required entanglement \nthrough optical photon quantum computing. We also suggest the possible impact of \nour results on network information flow problems, by showing an instance of a lower \nbound which can be broken by adding limited power to the communication model.