Quantum communication limits in multiparty coordination tasks revealed
On the Limits of Quantum Multiparty Simultaneous Communication
Computational Complexity
Summary
The paper studies how well quantum communication can replace shared randomness when multiple parties try to coordinate by sending messages simultaneously. The authors show that quantum messages need to be much longer than classical public randomness to solve certain coordination problems efficiently, and that this gap grows exponentially with the number of parties involved. This means quantum communication cannot easily mimic the benefits of shared randomness in these tasks. The result clarifies fundamental limits of quantum communication in multiparty scenarios.
What this means in practice
- •For distributed system designers: Avoid relying on quantum communication to efficiently replace public randomness in multiparty coordination protocols due to exponential message length requirements.
- •For cryptography engineers: Recognize the inherent limitations of quantum communication in multiparty settings when attempting to reduce communication using quantum superposition states without shared entanglement.
A theory result. No direct application yet.
Authors
Pedro Montealegre, Ivan Rapaport, Jorge Valenzuela
Abstract
The Simultaneous Message Passing (SMP) model provides a fundamental framework for comparing classical and quantum communication. For two players, Gavinsky et al. (STOC 2006) established a separation underlying the incomparability of shared randomness and quantum communication: \textsc{Index Coordination} needs $O(\log n)$ public-coin bits but $Ω(n^{1/3})$ bounded-error qubits. In this work, we establish a multiparty exponential separation through $\operatorname{IC}_{k,n}$, a natural $k$-party generalization of \textsc{Index Coordination}. Public-coin protocols solve it unambiguously with maximum message length $O(\log n)$ bits. In contrast, quantum SMP protocols without shared entanglement or public coins require maximum message length $Ω(n^{1-1/k})$ qubits in the unambiguous regime and $Ω(n^{(k-1)/(k+1)})$ qubits in the bounded-error regime. A classical private-coin protocol matches the unambiguous bound, so quantum communication provides no asymptotic advantage over private randomness in this regime. For fixed error parameters, all constants are independent of $k$, establishing the exponential separation for every integer-valued function $k=k(n)\ge2$, without restricting its growth. Both quantum lower bounds become $Ω(n)$ when $k\ge c\log n$ for any fixed $c>0$, matching the full-input protocol and yielding tight linear complexity in both regimes. Our results demonstrate that quantum superposition cannot efficiently simulate the coordination afforded by public randomness, extending this separation to arbitrary $k$. To bound success probabilities for multiparty product states, we prove an exact factorization theorem for unambiguous quantum state identification, which may be of independent mathematical interest.