Consumable Data via Quantum Communication
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912491459575808 |
|---|---|
| author | Gilboa, Dar Jain, Siddhartha McClean, Jarrod R. |
| author_facet | Gilboa, Dar Jain, Siddhartha McClean, Jarrod R. |
| contents | 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 $x$ and Bob holds $m$ inputs $y_1,... , y_m$. They want to compute $m$ instances of a bipartite relation $R$ on every pair $(x, y_1),\ldots, (x, y_m)$. 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$. Thus, for such problems, data behaves like a consumable resource that is effectively destroyed upon use when the owner stores and transmits it as quantum states, but not when transmitted classically. We show an application to a strategic data-selling game, and discuss other potential economic implications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_08495 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Consumable Data via Quantum Communication Gilboa, Dar Jain, Siddhartha McClean, Jarrod R. Quantum Physics Computational Complexity Computer Science and Game Theory 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 $x$ and Bob holds $m$ inputs $y_1,... , y_m$. They want to compute $m$ instances of a bipartite relation $R$ on every pair $(x, y_1),\ldots, (x, y_m)$. 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$. Thus, for such problems, data behaves like a consumable resource that is effectively destroyed upon use when the owner stores and transmits it as quantum states, but not when transmitted classically. We show an application to a strategic data-selling game, and discuss other potential economic implications. |
| title | Consumable Data via Quantum Communication |
| topic | Quantum Physics Computational Complexity Computer Science and Game Theory |
| url | https://arxiv.org/abs/2409.08495 |