Quantum Entanglement and Communication Complexity

Details Quantum Entanglement and Communication Complexity Quantum Entanglement and Communication Complexity

1997-05-18

arxiv.org/abs/quant-ph/9705033v1

SIAM J.Comput. 30 (2001) 1829-1841

Physics

Quantum Physics

10 pages, latex, no figures

Scientific paper

10.1137/S0097539797324886

We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles in an entangled quantum state. We show that, although a prior quantum entanglement cannot be used to simulate a communication channel, it can reduce the communication complexity of functions in some cases. Specifically, we show that, for a particular function among three parties (each of which possesses part of the function's input), a prior quantum entanglement enables them to learn the value of the function with only three bits of communication occurring among the parties, whereas, without quantum entanglement, four bits of communication are necessary. We also show that, for a particular two-party probabilistic communication complexity problem, quantum entanglement results in less communication than is required with only classical random correlations (instead of quantum entanglement). These results are a noteworthy contrast to the well-known fact that quantum entanglement cannot be used to actually simulate communication among remote parties.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-188527