Skip to content
DraconiticResearch
Search Sources API
194,067 studies31 sourcesUpdated 41 min ago
PreprintCC BY 4.0arXiv

On the Limits of Quantum Multiparty Simultaneous Communication

  • Pedro Montealegre
  • Ivan Rapaport
  • Jorge Valenzuela
Open at sourcePDFDOICite

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 xj∈{0,1}n, and the referee must decide whether x1⊕⋯⊕ xk=0n. For k≥8 and worst-case error at most 1/3, we prove quantum lower bounds of Ω(min{n,k2}) 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=k2 and worst-case error at most 1/3, we prove that quantum protocols require maximum message length Ω(√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 Ω(n1−1/k) on maximum message length, matched by a classical private-coin protocol. For any fixed error ε∈(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≥ clog n for any fixed c>0.

Related

  1. Performance Analysis of Multiparty GHZ-State Quantum Conference Key Agreement over Optical Fiber Channel
    Dipanjan Bera, Ramniwas Meena, Neel Kanth Kundu
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  2. Beyond Maximal Entanglement: Exact Resources for Multiparty Encrypted Quantum Cloning
    Pritam Roy, Shashank Gupta
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  3. Photonically Generated Simultaneous Multi-Band Terahertz Communication System
    Feng Liu, James Seddon, John Wu +4
    Optics ExpressPeer-reviewedLicence not statedOptics & photonicsCrossref
  4. Fermionic Genuine Multiparty Entanglement
    James Allen, Liuke Lyu, William Witczak-Krempa
    arXivPreprintCC BY 4.0Full textCondensed matterQuantum physics & quantum informationarXiv
  5. Simultaneous Reduction of Observables and Measured Qudits in Entanglement-Assisted Quantum Local Recovery
    Ryutaroh Matsumoto
    arXivPreprintarXiv licenceFull textGeneral mathematicsQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{montealegre2026limits,
  title = {{On the Limits of Quantum Multiparty Simultaneous Communication}},
  author = {Pedro Montealegre and Ivan Rapaport and Jorge Valenzuela},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.10289},
  eprint = {2609.10289},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.10289},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On the Limits of Quantum Multiparty Simultaneous Communication
AU  - Pedro Montealegre
AU  - Ivan Rapaport
AU  - Jorge Valenzuela
PY  - 2026
DA  - 2026/10/09
PB  - arXiv
DO  - 10.48550/arxiv.2609.10289
UR  - https://arxiv.org/abs/2609.10289
AB  - 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∈{0,1}^n, and the referee must decide whether x_1⊕⋯⊕ x_k=0^n. For k≥8 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 Ω(√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 ε∈(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≥ clog n for any fixed c>0.
ER  -