多方计算任务的量子通信复杂度

摘要

Assume multi parties want to calculate a shared data according to their own function,they have to communi-cate with each other to achieve the common computation task.This paper first presented the classical communication com-plexity 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 de-pends on the infinite order gap of 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.%假设多个用户分别根据各自持有的函数对共享数据进行计算，用户之间采用互相通信的方式完成一个共同的目标任务。本文基于一个通用的判别函数模型，给出对于上述任务，采用经典最优算法下的经典通信复杂度。然后，以数据库算法为基础，文中构造了适用于前述任务的量子分布式算法，并给出相应的量子通信复杂度。研究表明，量子算法的性能取决于函数定义域与用户数的无穷大阶的差距。量子通信复杂度较之经典情形最多将会有二次级别的降低。