Consider a function where its entries are distributed among many parties. Suppose each party is allowed to send only a limited amount of information to a referee. The referee can use a classical protocol to compute the value of the global function. Is there a quantum protocol improving the results of all classical protocols? In a recent work Brukner et al. showed the deep connection between such problems and the theory of Bell inequalities. Here we generalize the theory to trits. There, the best classical protocol fails whereas the quantum protocol yields the correct answer.
Communication complexity problems (CCPs) are tasks in which separated parties attempt to compute a function whose inputs are distributed among the parties. Their communication is limited so that not all inputs can be sent. We show that broad classes of Bell inequalities can be mapped to CCPs and that a quantum violation of a Bell inequality is a necessary and sufficient condition for an enhancement of the related CCP beyond its classical limitation. However, one can implement CCPs by transmitting a quantum system, encoding no more information than is allowed in the CCP, and extracting information by performing measurements. We show that for a large class of Bell inequalities, the improvement of the CCP associated with a quantum violation of a Bell inequality can be no greater than the improvement obtained from quantum prepare-transmit-measure strategies.
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.
We consider a quantum and a classical version of a multi-party function computation problem with n players, where players 2,…,n need to communicate appropriate information to player 1 so that a “generalized” inner product function with an appropriate promise can be calculated. In the quantum version of the protocol, the players have access to entangled qudits but the communication is still classical. The communication complexity of a given protocol is the total number of classical bits that need to be communicated. When n is prime, and for our chosen function, we exhibit a quantum protocol (with complexity (n−1)(logn) bits) and a classical protocol (with complexity ((n−1)2(logn2) bits)). Furthermore, we present an integer linear programming formulation for determining a lower bound on the classical communication complexity. This demonstrates that our quantum protocol is strictly better than classical protocols.