{"id":"arxiv/2609.10289","url":"https://arxiv.org/abs/2609.10289","tags":["cs.CC","quant-ph"],"score":0,"title":"On the Limits of Quantum Multiparty Simultaneous Communication","domain":"cs.CC","source":"arxiv","authors":["Pedro Montealegre","Ivan Rapaport","Jorge Valenzuela"],"reviews":0,"subject":"cs.CC","summary":"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\\ge8$ and worst-case…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-09","reactions":{}}