Quantum Advantage of Permutation-Invariant Functions in Communication Complexity
Abstract
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 Rpub(f)=Oq(tlog(2+n/t)), where t=min{n,Q∗(f)2}, Rpub denotes public-coin randomized communication complexity, and Q∗ 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 ε∈(0,1), there are binary permutation-invariant partial functions with quantum communication complexity Oε(loglog n) and randomized communication complexity Ωε((log n)1−ε). 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 ε∈(0,1), we exhibit permutation-invariant partial functions on length-n strings over an n-symbol alphabet with quantum communication complexity Oε(log n) and randomized communication complexity Ωε(n1−ε). For graph-invariant partial functions on v-vertex graphs, we obtain Oε(log v) quantum versus Ωε(v2−ε) randomized communication complexity. All separation protocols require no prior entanglement.
Related
- Constant-round quantum advantage in communication complexity for total functions
- Asymptotic advantage of quantum one-way and SMP communication for total functions
- On the quantum communication complexity of total functions
- Improved Separations between Quantum and Classical Communication Complexity of Total Functions
- The equivalence of quantum deletion and insertion errors on permutation-invariant codes
BibTeX
@misc{huang2026quantum,
title = {{Quantum Advantage of Permutation-Invariant Functions in Communication Complexity}},
author = {Yunqi Huang and Zekun Ye},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.40116},
eprint = {2609.40116},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40116},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Advantage of Permutation-Invariant Functions in Communication Complexity
AU - Yunqi Huang
AU - Zekun Ye
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2609.40116
UR - https://arxiv.org/abs/2609.40116
AB - 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^pub(f)=O_q(tlog(2+n/t)), where t=min{n,Q^∗(f)^2}, R^pub denotes public-coin randomized communication complexity, and Q^∗ 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 ε∈(0,1), there are binary permutation-invariant partial functions with quantum communication complexity O_ε(loglog n) and randomized communication complexity Ω_ε((log n)^1−ε). 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 ε∈(0,1), we exhibit permutation-invariant partial functions on length-n strings over an n-symbol alphabet with quantum communication complexity O_ε(log n) and randomized communication complexity Ω_ε(n^1−ε). For graph-invariant partial functions on v-vertex graphs, we obtain O_ε(log v) quantum versus Ω_ε(v^2−ε) randomized communication complexity. All separation protocols require no prior entanglement.
ER -