This paper describes a general quantum lower bounding technique for the communication complexity of a function that depends on the inputs given to two parties connected via paths, which may be shared with other parties, on a network of any topology. The technique can also be employed to obtain a lower-bound of the quantum communication complexity of some functions that depend on the inputs distributed over all parties on the network. As a typical application, we apply our technique to the distinctness problem of deciding whether there are a pair of parties with identical inputs, on a k-party ring; almost matching upper bounds are also given.

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.