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

发布时间：2019-09-24 13:08

【摘要】：假设多个用户分别根据各自持有的函数对共享数据进行计算,用户之间采用互相通信的方式完成一个共同的目标任务。本文基于一个通用的判别函数模型,给出对于上述任务,采用经典最优算法下的经典通信复杂度。然后,以数据库算法为基础,文中构造了适用于前述任务的量子分布式算法,并给出相应的量子通信复杂度。研究表明,量子算法的性能取决于函数定义域与用户数的无穷大阶的差距。量子通信复杂度较之经典情形最多将会有二次级别的降低。
【图文】：

序列,通信过程,量子态

第12期余文斌等:多方计算任务的量子通信复杂度x＞g1(x)＞g2(x)＞…gK－1(x)＞由以上结果，我们可以定义量子态序列{φk＞1≤k≤K}和{yk＞1≤k≤K}。其中φk＞和yk＞分别为n+(k－1)m位量子比特和n+(K－k)m位量子比特，并且满足以下条件:Uk(φk＞0＞鄃m)=φk+1＞，U－1K－kyk＞=yk+1＞0＞鄃m，OracleφK＞=y1＞在k=1和k=K的特殊情况下，φ1＞和yK＞均为n位量子比特，其分别为DOO算法的输入与输出量子态。图1DOO的通信过程Fig．1ThecommunicationprocessofDOO如图1所示，我们把DOO算法分为三个阶段。第一阶段的前向通信操作是按用户1到用户K的顺序进行。在此阶段，，每个用户按顺序对序列{φk＞1≤k≤K}中的量子态应用{Uk1≤k≤K－1}中的幺正算符，因此，每个用户计算后的信息将被传输到用户K。在第二阶段，用户K于量子态φK＞上执行Oracle算符以得到量子态y1＞。同时，MPC问题的“解”所对应的量子态都会获得一个相位翻转，使得“解”可以被标记出来。第三阶段的后向通信操作是按用户K到用户1的顺序进行。每个用户按顺序对序列{yk＞1≤k≤K}中的量子态应用{U－1k1≤k≤K－1}中的幺正算符，以便承载“解”的标志信息的量子态被传输到用户1。完整的DOO算法如下所述:(1)从用户1到用户K的前向通信阶段Step1初始输入为用户1接受到得量子态φ1＞。Step2当前用户接受到量子态φk＞，在其后添加m量子比特0＞鄃m作为辅助量子态。Step3当前用户对上述结果应用算符Uk，得到量子态φk+1＞。Step4当前用户将量子态φk+1＞发送给下一个用户。Step5下一个用户跳转到Step2开始操作。重复这个过程直到量

次数,Grover算法,迭代次数,函数定义域

鸥丛?度将处于以下两者之间，即O(i酜NlogN)≤量子通信复杂度＜O(KNm)4性能分析4．1量子分布式算法的性能分析QD算法是一种基于Grover算法的量子搜索算法。这说明，QD算法本质上属于随机算法，而它的成功概率将取决于迭代次数［8，9，16］。假设S是函数定义域N中“解”的数目，令Ｒ表示迭代次数，Pe代表平均差错概率。根据Grover算法的性能特性，我们可以得到QD算法的迭代次数的上界，即Ｒ≤p4Ni酳当算法执行Ｒ次迭代后，QD算法的性能将达到最优。此时的平均差错概率为Pe=S/N=2－K图2N/S下的QD算法迭代次数Fig．2QDalgorithmiterationnumberwithN/S图3N/S下的QD算法平均成功率Fig．3TheaveragesuccessprobabilityofQDalgorithmwithN/S从图2可以看出，函数定义域N与解的数目的比值从1增加到1000，迭代次数增加的较为缓慢。1476
【作者单位】：南京邮电大学信号处理与传输研究所;
【基金】：国家自然科学基金(61271238) 教育部博士点专项科研基金(20060293003)
【分类号】：TN918;O413

【参考文献】