{"id":"arxiv/2609.40116","url":"https://arxiv.org/abs/2609.40116","tags":["quant-ph"],"score":0,"title":"Quantum Advantage of Permutation-Invariant Functions in Communication Complexity","domain":"quant-ph","source":"arxiv","authors":["Yunqi Huang","Zekun Ye"],"reviews":0,"subject":"quant-ph","summary":"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.…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}