Quantum Advantage of Permutation-Invariant Functions in Communication Complexity

We study how symmetry constrains quantum advantage in two-party communication complexity. For partial functions over any fixed alphabet of size $q$ that are invariant under simultaneous coordinate permutations, we prove that public-coin randomized and entanglement-assisted quantum communication complexities satisfy $R^{\mathrm{p}\mathrm{u}\mathrm{b}}(f)=O_q(Q^{\ast }(f{)}^2\log n)$, where $n$ is the input length. We also characterize quantum communication complexity by a combinatorial parameter up to a logarithmic factor. These results extend the binary-alphabet result of Guan et al. and improve its logarithmic overhead. Input-length dependence is necessary: for every fixed $\epsilon \in (0,1)$, binary permutation-invariant partial functions can have quantum complexity $O_{\epsilon }(\log \log n)$ and randomized complexity ${\mathrm{\Omega }}_{\epsilon }((\log n{)}^{1-\epsilon })$. Growing alphabets and graph symmetries permit exponential separations. For every fixed $\epsilon \in (0,1)$, we construct permutation-invariant partial functions on length-$n$ strings over an $n$-symbol alphabet with quantum complexity $O_{\epsilon }(\log n)$ and randomized complexity ${\mathrm{\Omega }}_{\epsilon }(n^{1-\epsilon })$. We also construct graph-invariant partial functions on $v$-vertex graphs with quantum complexity $O_{\epsilon }(\log v)$ and randomized complexity ${\mathrm{\Omega }}_{\epsilon }(v^{2-\epsilon })$. All separation protocols use neither prior entanglement nor shared randomness.