Multi-party quantum communication complexity with prior entanglements
There exist some results showing that quantum communications are more powerful than classical communications. Moreover, although quantum entangled states do not give extra information, by using prior entanglement the quantum communication complexity of some functions is less than the classical communication complexity. The communications with prior entanglement can be regarded as a type of public coin models. In this paper, we investigate quantum communications for multi-party with prior entanglement, and show that there exists a generalized inner product function for k-party such that the quantum communication complexity is at most k bits, but the classical communication complexity needs at least [3k/2] bits. Moreover, we also provide a generalized form of prior entanglements that is effective in order to compute some type of Boolean functions.
quantum communication complexity prior entanglement public coin model multi-party communication