Unbounded-Error Classical and Quantum Communication Complexity - Quantum PhysicsReport as inadecuate

Unbounded-Error Classical and Quantum Communication Complexity - Quantum Physics - Download this document for free, or read online. Document in PDF available to download.

Abstract: Since the seminal work of Paturi and Simon \citeFOCS-84 and JCSS-86{PS86},the unbounded-error classical communication complexity of a Boolean functionhas been studied based on the arrangement of points and hyperplanes. Recently,\citeICALP-07{INRY07} found that the unbounded-error {\em quantum}communication complexity in the {\em one-way communication} model can also beinvestigated using the arrangement, and showed that it is exactly without adifference of even one qubit half of the classical one-way communicationcomplexity. In this paper, we extend the arrangement argument to the {\emtwo-way} and {\em simultaneous message passing} SMP models. As a result, weshow similarly tight bounds of the unbounded-error two-way-one-way-SMPquantum-classical communication complexities for {\em any} partial-totalBoolean function, implying that all of them are equivalent up to amultiplicative constant of four. Moreover, the arrangement argument is alsoused to show that the gap between {\em weakly} unbounded-error quantum andclassical communication complexities is at most a factor of three.

Author: Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita

Source: https://arxiv.org/

Related documents