Quantum Advantage of Permutation-Invariant Functions in Communication Complexity

Abstract

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{pub}}(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 $\varepsilon\in(0,1)$, binary permutation-invariant partial functions can have quantum complexity $O_\varepsilon(\log\log n)$ and randomized complexity $\Omega_\varepsilon((\log n)^{1-\varepsilon})$. Growing alphabets and graph symmetries permit exponential separations. For every fixed $\varepsilon\in(0,1)$, we construct permutation-invariant partial functions on length-$n$ strings over an $n$-symbol alphabet with quantum complexity $O_\varepsilon(\log n)$ and randomized complexity $\Omega_\varepsilon(n^{1-\varepsilon})$. We also construct graph-invariant partial functions on $v$-vertex graphs with quantum complexity $O_\varepsilon(\log v)$ and randomized complexity $\Omega_\varepsilon(v^{2-\varepsilon})$. All separation protocols use neither prior entanglement nor shared randomness.