Trade-offs between Entanglement and Communication
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909935109931008 |
|---|---|
| author | Arunachalam, Srinivasan Girish, Uma |
| author_facet | Arunachalam, Srinivasan Girish, Uma |
| contents | We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on $n$ bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every $k\ge 1$:
$Q\|^*$ versus $R2^*$: We show that quantum simultaneous protocols with $\tildeΘ(k^5 \log^3 n)$ qubits of entanglement can exponentially outperform two-way randomized protocols with $O(k)$ qubits of entanglement. This resolves an open problem from [Gav08] and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement [Gav19, GRT22].
$R\|^*$ versus $Q\|^*$: We show that classical simultaneous protocols with $\tildeΘ(k \log n)$ qubits of entanglement can exponentially outperform quantum simultaneous protocols with $O(k)$ qubits of entanglement, resolving an open question from [GKRW06, Gav19]. The best result prior to our work was a relational separation against protocols without entanglement [GKRW06].
$R\|^*$ versus $R1^*$: We show that classical simultaneous protocols with $\tildeΘ(k\log n)$ qubits of entanglement can exponentially outperform randomized one-way protocols with $O(k)$ qubits of entanglement. Prior to our work, only a relational separation was known [Gav08].
Our techniques can also be used to show advantages of quantum communication models over hybrid classical-quantum models, i.e., models that have a large amount of both classical communication and quantum simultaneous communication. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_01233 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Trade-offs between Entanglement and Communication Arunachalam, Srinivasan Girish, Uma Quantum Physics Computational Complexity We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on $n$ bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every $k\ge 1$: $Q\|^*$ versus $R2^*$: We show that quantum simultaneous protocols with $\tildeΘ(k^5 \log^3 n)$ qubits of entanglement can exponentially outperform two-way randomized protocols with $O(k)$ qubits of entanglement. This resolves an open problem from [Gav08] and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement [Gav19, GRT22]. $R\|^*$ versus $Q\|^*$: We show that classical simultaneous protocols with $\tildeΘ(k \log n)$ qubits of entanglement can exponentially outperform quantum simultaneous protocols with $O(k)$ qubits of entanglement, resolving an open question from [GKRW06, Gav19]. The best result prior to our work was a relational separation against protocols without entanglement [GKRW06]. $R\|^*$ versus $R1^*$: We show that classical simultaneous protocols with $\tildeΘ(k\log n)$ qubits of entanglement can exponentially outperform randomized one-way protocols with $O(k)$ qubits of entanglement. Prior to our work, only a relational separation was known [Gav08]. Our techniques can also be used to show advantages of quantum communication models over hybrid classical-quantum models, i.e., models that have a large amount of both classical communication and quantum simultaneous communication. |
| title | Trade-offs between Entanglement and Communication |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2306.01233 |