Metraipolis › archive › dc_3d68ef323210
On the Limits of Quantum Multiparty Simultaneous Communication — arXiv:2609.10289
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.10289
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T11:18:15.692Z
- SHA-256 of the archived text
009555f9ad031cedc2dabfadafb40f3576f0cdcc06445a30a9e7120b20ff1a68- Stable URL of this page
https://metraipolis.com/documento/dc_3d68ef323210
How to cite
On the Limits of Quantum Multiparty Simultaneous Communication — arXiv:2609.10289 — arXiv (en), https://arxiv.org/abs/2609.10289 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3d68ef323210 (Metraipolis archive dc_3d68ef323210, sha256 009555f9ad031cedc2dabfadafb40f3576f0cdcc06445a30a9e7120b20ff1a68)
BibTeX
@misc{dc3d68ef323210,
title = {On the Limits of Quantum Multiparty Simultaneous Communication — arXiv:2609.10289},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.10289},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3d68ef323210; sha256 009555f9ad031cedc2dabfadafb40f3576f0cdcc06445a30a9e7120b20ff1a68},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.10289. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement. We first introduce XOR Equality, a total Boolean function in which each of $k$ players receives an unrestricted string $x_j\in\{0,1\}^n$, and the referee must decide whether $x_1\oplus\cdots\oplus x_k=0^n$. For $k\ge8$ and worst-case error at most $1/3$, we prove quantum lower bounds of $\Omega(\min\{n,k^2\})$ on total communication and $\Omega(\min\{n/k,k\})$ on maximum message length. A classical public-coin protocol uses two bits per player with error at most $1/4$. For $n=k^2$ and worst-case error at most $1/3$, we prove that quantum protocols require maximum message length $\Omega(\sqrt n)$ qubits, whereas two public-coin bits per player suffice. We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a $k$-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of $\Omega(n^{1-1/k})$ on maximum message length, matched by a classical private-coin protocol. For any fixed error $\varepsilon\in(0,1/8)$, we also prove a bounded-error quantum lower bound of $\Omega(n^{(k-1)/(k+1)})$ while we show that public-coin protocols solve the relation unambiguously with maximum message length $O(\log n)$, giving exponential separations in both regimes. The implicit constants are independent of $k$, and both quantum lower bounds become linear when $k\ge c\log n$ for any fixed $c>0$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-10 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC) ; Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.10289 — 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-16T10:56:42.342Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).