Unbounded-Error Classical and Quantum Communication Complexity
Unbounded-Error Classical and Quantum Communication Complexity
复制标题
DOI：
10.1007/978-3-540-77120-3_11
复制
发表时间：
2007-09
期刊：
影响因子：
--
通讯作者：
K. Iwama;H. Nishimura;Raymond H. Putra;S. Yamashita
中科院分区：
文献类型：
--
作者：
K. Iwama;H. Nishimura;Raymond H. Putra;S. Yamashita
自Paturi和Simon[26，FOCS‘84&Jcss’86]的开创性工作以来，基于点和超平面的排列，研究了布尔函数的无界误差经典通信复杂性。最近，[14，ICALP‘07]发现单向通信模型中的无界误差量子通信复杂性也可以用这种安排来研究，并证明它恰好是经典单向通信复杂性的一半(甚至没有一个量子比特的差别)。在本文中，我们将安排变元推广到双向和同时消息传递(SMP)模型。结果，我们给出了任意部分/全布尔函数的无界误差双向/单向/SMP量子/经典通信复杂性的类似紧界，这意味着它们都等价于乘法常数4。此外，排列引理还被用来证明弱无界误差量子通信复杂性与经典通信复杂性之间的差距至多是三倍。
Since the seminal work of Paturi and Simon [26,FOCS’84 & JCSS’86], the unbounded-error classical communication complexity of a Boolean function has been studied based on the arrangement of points and hyperplanes. Recently, [14, ICALP’07] found that the unbounded-errorquantumcommunication complexity in theone-way communicationmodel can also be investigated using the arrangement, and showed that it is exactly (without a difference of even one qubit) half of the classical one-way communication complexity. In this paper, we extend the arrangement argument to thetwo-wayandsimultaneous message passing(SMP) models. As a result, we show similarly tight bounds of the unbounded-error two-way/one-way/SMP quantum/classical communication complexities foranypartial/total Boolean function, implying that all of them are equivalent up to a multiplicative constant of four. Moreover, the arrangement argument is also used to show that the gap betweenweaklyunbounded-error quantum and classical communication complexities is at most a factor of three.