TR24-144 Authors: Dar Gilboa, Siddhartha Jain, Jarrod McClean

Publication: 25th September 2024 22:49

Downloads: 69

Keywords:

Classical data can be copied and re-used for computation, with adverse consequences economically and in terms of data privacy. Motivated by this, we formulate problems in one-way communication complexity where Alice holds some data and Bob holds $m$ inputs, and he wants to compute $m$ instances of a bipartite relation on Alice's data and each of his inputs. We call this the asymmetric direct sum question for one-way communication. We give a number of examples where the quantum communication complexity of such problems scales polynomially with $m$, while the classical communication complexity depends at most logarithmically on $m$.

For these examples, data behaves like a consumable resource when the owner stores and transmits it as quantum states.

We show an application to a strategic data-selling game, and discuss other potential economic implications.