Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908971833491456 |
|---|---|
| author | Hasegawa, Atsuya Gall, François Le Modanese, Augusto |
| author_facet | Hasegawa, Atsuya Gall, François Le Modanese, Augusto |
| contents | We present relation problems whose input size is $n$ such that they can be solved with no communication for entanglement-assisted quantum communication models, but require $Ω(n)$ qubit communication for $2$-way quantum communication models without prior shared entanglement. This is the maximum separation of quantum communication complexity with and without shared entanglement. To our knowledge, our result even shows the first lower bound on quantum communication complexity without shared entanglement when the upper bound of entanglement-assisted quantum communication models is zero. Our result refutes a quantum analog of Newman's theorem.
The problem we consider is parallel repetition of any non-local game which has a perfect quantum strategy and no perfect classical strategy, and for which a parallel repetition theorem holds with exponential decay. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_16457 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement Hasegawa, Atsuya Gall, François Le Modanese, Augusto Quantum Physics Computational Complexity We present relation problems whose input size is $n$ such that they can be solved with no communication for entanglement-assisted quantum communication models, but require $Ω(n)$ qubit communication for $2$-way quantum communication models without prior shared entanglement. This is the maximum separation of quantum communication complexity with and without shared entanglement. To our knowledge, our result even shows the first lower bound on quantum communication complexity without shared entanglement when the upper bound of entanglement-assisted quantum communication models is zero. Our result refutes a quantum analog of Newman's theorem. The problem we consider is parallel repetition of any non-local game which has a perfect quantum strategy and no perfect classical strategy, and for which a parallel repetition theorem holds with exponential decay. |
| title | Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2505.16457 |