Metraipolis › archive › dc_ea037882ed25

Quantum Advantage of Permutation-Invariant Functions in Communication Complexity — arXiv:2609.40116

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.40116
License (as archived)
CC0-1.0
Archived
2026-10-07T15:22:09.888Z
SHA-256 of the archived text
d9aff3470e01146a745d9acab20ac32b1940761daaf8f8ceb30847adbf1d178c
Stable URL of this page
https://metraipolis.com/documento/dc_ea037882ed25

How to cite

Quantum Advantage of Permutation-Invariant Functions in Communication Complexity — arXiv:2609.40116 — arXiv (en), https://arxiv.org/abs/2609.40116 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ea037882ed25 (Metraipolis archive dc_ea037882ed25, sha256 d9aff3470e01146a745d9acab20ac32b1940761daaf8f8ceb30847adbf1d178c)
BibTeX
@misc{dcea037882ed25,
  title = {Quantum Advantage of Permutation-Invariant Functions in Communication Complexity — arXiv:2609.40116},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.40116},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ea037882ed25; sha256 d9aff3470e01146a745d9acab20ac32b1940761daaf8f8ceb30847adbf1d178c},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.40116. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study how symmetry affects quantum advantage in two-party communication complexity. For any partial function $f$ on length-$n$ strings over a fixed alphabet of size $q$, invariant under simultaneous coordinate permutations, we prove $R^{\mathrm{pub}}(f)=O_q(t\log(2+n/t))$, where $t=\min\{n,Q^{\ast}(f)^2\}$, $R^{\mathrm{pub}}$ denotes public-coin randomized communication complexity, and $Q^{\ast}$ denotes entanglement-assisted quantum communication complexity. This bound is tight for set disjointness and extends the binary-alphabet result of Guan et al. with a smaller logarithmic overhead. The exponent of the logarithmic factor cannot be reduced by any fixed positive amount: for every fixed $\varepsilon\in(0,1)$, there are binary permutation-invariant partial functions with quantum communication complexity $O_\varepsilon(\log\log n)$ and randomized communication complexity $\Omega_\varepsilon((\log n)^{1-\varepsilon})$. We also characterize quantum communication complexity by a combinatorial parameter up to a logarithmic factor. Growing alphabets and graph symmetries admit exponential separations. For every fixed $\varepsilon\in(0,1)$, we exhibit permutation-invariant partial functions on length-$n$ strings over an $n$-symbol alphabet with quantum communication complexity $O_\varepsilon(\log n)$ and randomized communication complexity $\Omega_\varepsilon(n^{1-\varepsilon})$. For graph-invariant partial functions on $v$-vertex graphs, we obtain $O_\varepsilon(\log v)$ quantum versus $\Omega_\varepsilon(v^{2-\varepsilon})$ randomized communication complexity. All separation protocols require no prior entanglement.

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-10-01 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.40116 — 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-07T14:53:56.811Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).