Unbounded-Error Classical and Quantum Communication Complexity

Details Unbounded-Error Classical and Quantum Communication Complexity Unbounded-Error Classical and Quantum Communication Complexity

2007-09-18

arxiv.org/abs/0709.2761v1

Physics

Quantum Physics

11 pages. To appear at Proc. ISAAC 2007

Scientific paper

Since the seminal work of Paturi and Simon \cite[FOCS'84 & JCSS'86]{PS86}, the unbounded-error classical communication complexity of a Boolean function has been studied based on the arrangement of points and hyperplanes. Recently, \cite[ICALP'07]{INRY07} found that the unbounded-error {\em quantum} communication complexity in the {\em one-way communication} model 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 the {\em two-way} and {\em simultaneous 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 for {\em any} partial/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 between {\em weakly} unbounded-error quantum and classical communication complexities is at most a factor of three.

Affiliated with

Also associated with

No associations

Rating

Unbounded-Error Classical and Quantum Communication Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Unbounded-Error Classical and Quantum Communication Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unbounded-Error Classical and Quantum Communication Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-456540