In this paper, we focus on the quantum communication complexity of functions of the form $f \circ G = f(G(X_1, Y_1), \ldots, G(X_n, Y_n))$ where $f: \{0, 1\}^n \to \{0, 1\}$ is a symmetric function, $G: \{0, 1\}^j \times \{0, 1\}^k \to \{0, 1\}$ is any function and Alice (resp. Bob) is given $(X_i)_{i \leq n}$ (resp. $(Y_i)_{i \leq n}$). Recently, Chakraborty et al. [STACS 2022] showed that the quantum communication complexity of $f \circ G$ is $O(Q(f)\mathrm{QCC}_\mathrm{E}(G))$ when the parties are allowed to use shared entanglement, where $Q(f)$ is the query complexity of $f$ and $\mathrm{QCC}_\mathrm{E}(G)$ is the exact communication complexity of $G$. In this paper, we first show that the same statement holds \emph{without shared entanglement}, which generalizes their result. Based on the improved result, we next show tight upper bounds on $f \circ \mathrm{AND}_2$ for any symmetric function $f$ (where $\textrm{AND}_2 : \{0, 1\} \times \{0, 1\} \to \{0, 1\}$ denotes the 2-bit AND function) in both models: with shared entanglement and without shared entanglement. This matches the well-known lower bound by Razborov~[Izv. Math. 67(1) 145, 2003] when shared entanglement is allowed and improves Razborov's bound when shared entanglement is not allowed.

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok