Quantum Entanglement and the Communication Complexity of the Inner Product Function
arXiv:quant-ph/9708019
Abstract
We consider the communication complexity of the binary inner product function in a variation of the two-party scenario where the parties have an a priori supply of particles in an entangled quantum state. We prove linear lower bounds for both exact protocols, as well as for protocols that determine the answer with bounded-error probability. Our proofs employ a novel kind of "quantum" reduction from a quantum information theory problem to the problem of computing the inner product. The communication required for the former problem can then be bounded by an application of Holevo's theorem. We also give a specific example of a probabilistic scenario where entanglement reduces the communication complexity of the inner product function by one bit.
14 pages, LaTeX w/ llncs style, no figures, made changes in notation in order to be consistent with other papers. To appear in Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communications (Springer-Verlag)
References in corpus (4)
Cited by in corpus (16)
- Non-locality and Communication Complexity
- On the Theory of Quantum Secret Sharing
- Foundations of quantum theory and quantum information applications
- Renyi-entropic bounds on quantum communication
- Interferometric computation beyond quantum theory
- Quantum Communication Complexity (A Survey)
- Practical Quantum Appointment Scheduling
- Recasting Mermin's multi-player game into the framework of pseudo-telepathy
- The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting
- Constant communication complexity protocols for multiparty accumulative boolean functions
- A quantum Goldreich-Levin theorem with cryptographic applications
- Interactive Leakage Chain Rule for Quantum Min-entropy
- Quantum Communication-Query Tradeoffs
- Proceedings of the 7th International Workshop on Physics and Computation
- Classical lower bounds from quantum upper bounds
- Three-qubit exact Grover within the blind oracular quantum computation scheme