ECCC-Report TR24-144https://eccc.weizmann.ac.il/report/2024/144Comments and Revisions published for TR24-144en-usWed, 25 Sep 2024 22:49:27 +0300
Paper TR24-144
| Consumable Data via Quantum Communication |
Siddhartha Jain,
Dar Gilboa,
Jarrod McClean
https://eccc.weizmann.ac.il/report/2024/144Classical 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.Wed, 25 Sep 2024 22:49:27 +0300https://eccc.weizmann.ac.il/report/2024/144