Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-144 | 16th September 2024 20:28

Consumable Data via Quantum Communication

RSS-Feed




TR24-144
Authors: Dar Gilboa, Siddhartha Jain, Jarrod McClean
Publication: 25th September 2024 22:49
Downloads: 98
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint