On the Limits of Quantum Multiparty Simultaneous Communication

Abstract

We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement. We first introduce XOR Equality, a total Boolean function in which each of $k$ players receives an unrestricted string $x_j\in \{0,1{\}}^n$, and the referee must decide whether $x_1\oplus \cdots \oplus x_k=0^n$. For $k\ge 8$ and worst-case error at most $1/3$, we prove quantum lower bounds of $\Omega (\min \{n,k^2\})$ on total communication and $\Omega (\min \{n/k,k\})$ on maximum message length. A classical public-coin protocol uses two bits per player with error at most $1/4$. For $n=k^2$ and worst-case error at most $1/3$, we prove that quantum protocols require maximum message length $\Omega (\sqrt{n})$ qubits, whereas two public-coin bits per player suffice. We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a $k$-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of $\Omega (n^{1-1/k})$ on maximum message length, matched by a classical private-coin protocol. For any fixed error $\epsilon \in (0,1/8)$, we also prove a bounded-error quantum lower bound of $\Omega (n^{(k-1)/(k+1)})$ while we show that public-coin protocols solve the relation unambiguously with maximum message length $O(\log n)$, giving exponential separations in both regimes. The implicit constants are independent of $k$, and both quantum lower bounds become linear when $k\ge c\log n$ for any fixed $c>0$.

27 pages, 1 figure