Multiparty Quantum Communication Complexity

Details Multiparty Quantum Communication Complexity Multiparty Quantum Communication Complexity

1997-10-22

arxiv.org/abs/quant-ph/9710054v2

Phys.Rev. A60 (1999) 2737-2741

Physics

Quantum Physics

8 pages, LaTeX2e, no figures; new result and author added

Scientific paper

10.1103/PhysRevA.60.2737

Quantum entanglement cannot be used to achieve direct communication between remote parties, but it can reduce the communication needed for some problems. Let each of k parties hold some partial input data to some fixed k-variable function f. The communication complexity of f is the minimum number of classical bits required to be broadcasted for every party to know the value of f on their inputs. We construct a function G such that for the one-round communication model and three parties, G can be computed with n+1 bits of communication when the parties share prior entanglement. We then show that without entangled particles, the one-round communication complexity of G is (3/2)n + 1. Next we generalize this function to a function F. We show that if the parties share prior quantum entanglement, then the communication complexity of F is exactly k. We also show that if no entangled particles are provided, then the communication complexity of F is roughly k*log(k). These two results prove for the first time communication complexity separations better than a constant number of bits.

Affiliated with

Also associated with

No associations

Rating

Multiparty 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 Multiparty Quantum Communication Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiparty Quantum Communication Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-615158