Multiparty Quantum Communication Complexity
| dc.creator | Buhrman, Harry | |
| dc.creator | van Dam, Wim | |
| dc.creator | Hoyer, Peter | |
| dc.creator | Tapp, Alain | |
| dc.date | 1997-10-22 | |
| dc.date | 1999-06-03 | |
| dc.date.accessioned | 2026-07-07T06:14:30Z | |
| dc.date.available | 2026-07-07T06:14:30Z | |
| dc.description | 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. | |
| dc.description | 8 pages, LaTeX2e, no figures; new result and author added | |
| dc.identifier | https://arxiv.org/abs/quant-ph/9710054 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/9710054 | |
| dc.identifier | Phys.Rev. A60 (1999) 2737-2741 | |
| dc.identifier | doi:10.1103/PhysRevA.60.2737 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/93484 | |
| dc.subject | Quantum Physics | |
| dc.title | Multiparty Quantum Communication Complexity | |
| dc.type | text |