Exponential quantum enhancement for distributed addition with local nonlinearity
Adam Henry Marblestone, Michel Devoret
Arxiv ID: 0907.3465•Last updated: 2/4/2020
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.
PaperStudio AI Chat
I'm your research assistant! Ask me anything about this paper.