Exponential quantum enhancement for distributed addition with local nonlinearity

Adam Henry Marblestone, Michel Devoret
Arxiv ID: 0907.3465Last 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.

Related papers

Commercial Disclosure
© 2023 Paper Studio™. All Rights Reserved.