Quantum Communication Complexity of Multi-Party Computation Task

Assume multi parties want to calculate a shared data according to their own function, they have to communicate with each other to achieve the common computation task. This paper first presented the classical communication complexity of the classical optimal algorithm to achieve this task based on a general discriminant function. Furthermore, a quantum distributed algorithm is proposed for the computation task based on the Grover database search algorithm, and the quantum communication complexity is presented. Our research shows that the performance of this quantum algorithm depends on the infinite order gap between the function domain and the users number. It is proved that the quantum algorithm can get a quadratic reduction at most on the performance of communication complexity than the classical algorithm.