{
  "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\\ge8$ and worst-case error at most $1/3$, we prove quantum lower bounds of $Ω(\\min\\{n,k^2\\})$ on total communication and $Ω(\\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 $Ω(\\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 $Ω(n^{1-1/k})$ on maximum message length, matched by a classical private-coin protocol. For any fixed error $\\varepsilon\\in(0,1/8)$, we also prove a bounded-error quantum lower bound of $Ω(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$.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.10289",
  "author_total": 3,
  "authors": [
    {
      "name": "Pedro Montealegre"
    },
    {
      "name": "Ivan Rapaport"
    },
    {
      "name": "Jorge Valenzuela"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/c88fzh21cgrmr.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.10289",
  "fulltext_url": null,
  "id": "c88fzh21cgrmr",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.10289",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.CC"
    ],
    [
      "arxiv",
      "quant-ph"
    ],
    [
      "openalex",
      "1702|Quantum Information and Cryptography"
    ]
  ],
  "openalex": "W7212176778",
  "pdf_url": "https://arxiv.org/pdf/2609.10289",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-09",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/c88fzh21cgrmr.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:28:36Z",
      "native_id": "2609.10289",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.10289"
    }
  ],
  "subjects": [
    {
      "field": "physics",
      "origin": "arxiv:quant-ph",
      "subfield": "quantum"
    }
  ],
  "title": "On the Limits of Quantum Multiparty Simultaneous Communication",
  "title_text": "On the Limits of Quantum Multiparty Simultaneous Communication",
  "type": "preprint",
  "updated_at": "2026-10-30T12:28:36Z",
  "url": "https://research.draconitic.com/paper/c88fzh21cgrmr",
  "venue": "arXiv",
  "versions": []
}