Exponential quantum enhancement for distributed addition with local nonlinearity
arXiv:0907.3465 · doi:10.1007/s11128-009-0126-9
Abstract
We consider classical and entanglement-assisted versions of a distributed computation scheme that computes nonlinear Boolean functions of a set of input bits supplied by separated parties. Communication between the parties is restricted to take place through a specific apparatus which enforces the constraints that all nonlinear, nonlocal classical logic is performed by a single receiver, and that all communication occurs through a limited number of one-bit channels. In the entanglement-assisted version, the number of channels required to compute a Boolean function of fixed nonlinearity can become exponentially smaller than in the classical version. We demonstrate this exponential enhancement for the problem of distributed integer addition.
arXiv commentTo appear in Quantum Information Processing
References in corpus (9)
- Quantum Information and Relativity Theory
- Non-local correlations as an information theoretic resource
- A limit on nonlocality in any world in which communication complexity is not trivial
- Quantum protocols for anonymous voting and surveying
- Quantum Pseudo-Telepathy
- Towards quantum-based privacy and voting
- Multiparty Quantum Communication Complexity
- Combinatorics and Quantum Nonlocality
- A quantum secret ballot