Metraipolis › archive › dc_ace092478bb6
Non-local games and communication complexity with noisy entanglement — arXiv:2609.05122
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.05122
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T00:01:42.892Z
- SHA-256 of the archived text
bdb7a690b51552eda55604d56189178a1f68f66d912153add29fa4eedd6068a2- Stable URL of this page
https://metraipolis.com/documento/dc_ace092478bb6
How to cite
Non-local games and communication complexity with noisy entanglement — arXiv:2609.05122 — arXiv (en), https://arxiv.org/abs/2609.05122 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ace092478bb6 (Metraipolis archive dc_ace092478bb6, sha256 bdb7a690b51552eda55604d56189178a1f68f66d912153add29fa4eedd6068a2)
BibTeX
@misc{dcace092478bb6,
title = {Non-local games and communication complexity with noisy entanglement — arXiv:2609.05122},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.05122},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ace092478bb6; sha256 bdb7a690b51552eda55604d56189178a1f68f66d912153add29fa4eedd6068a2},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.05122. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the impact of noise on the theories of quantum nonlocality and entanglement-assisted communication complexity. We consider non-local games and entanglement-assisted communication complexity in a model where Alice and Bob may share arbitrarily many noisy EPR pairs. We study four noise models: depolarizing noise, unital noise, biased reset noise, and erasure noise. Our results are as follows: 1. We upper bound the value of the CHSH game under all these noise models in terms of the noise parameter, without any assumptions on the measurements used in the strategy. 2. We prove a parallel repetition theorem for general non-local games under all noise models except biased reset noise; we prove an improved parallel repetition theorem for unique games. Our parallel repetition rate is smaller than the quantum parallel repetition rate for CHSH in a nontrivial noise regime. 3. Using our unique-game parallel repetition theorem and a relation defined by the CHSH game, we prove a separation between communication complexity with noisy vs noiseless entanglement. This implies an $\Omega(n)$ two-way communication lower bound for distilling $n$ EPR pairs from noisy EPR pairs, in the same nontrivial noise regime. 4. We show that any interactive entanglement-assisted communication protocol can be simulated by an SMP communication protocol with noisy shared randomness, with an exponential blowup in communication. This generalizes a known result on the simulation of noiseless shared randomness with noisy shared randomness. 5. We show a polynomial lower bound on the number of copies of noisy EPR pairs required to compute the Equality function with constant communication, under all four noise models. The previous result gives a matching upper bound, and moreover, this answers an open question in the literature on whether logarithmically many noisy shared bits suffice for communication. Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-09-07 in quant-ph). Categorie arXiv: Quantum Physics (quant-ph). Pagina del lavoro: https://arxiv.org/abs/2609.05122 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T23:41:14.311Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).