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.

arXiv:2609.40116 [quant-ph]

(or arXiv:2609.40116v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.40116 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.