CAJ | 학술논문

假设多个用户分别根据各自持有的函数对共享数据进行计算，用户之间采用互相通信的方式完成一个共同的目标任务。本文基于一个通用的判别函数模型，给出对于上述任务，采用经典最优算法下的经典通信复杂度。然后，以数据库算法为基础，文中构造了适用于前述任务的量子分布式算法，并给出相应的量子通信复杂度。研究表明，量子算法的性能取决于函数定义域与用户数的无穷大阶的差距。量子通信复杂度较之经典情形最多将会有二次级别的降低。
가설다개용호분별근거각자지유적함수대공향수거진행계산，용호지간채용호상통신적방식완성일개공동적목표임무。본문기우일개통용적판별함수모형，급출대우상술임무，채용경전최우산법하적경전통신복잡도。연후，이수거고산법위기출，문중구조료괄용우전술임무적양자분포식산법，병급출상응적양자통신복잡도。연구표명，양자산법적성능취결우함수정의역여용호수적무궁대계적차거。양자통신복잡도교지경전정형최다장회유이차급별적강저。
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.