⚛️ quantum physics

On the Limits of Quantum Multiparty Simultaneous Communication

This paper establishes an exponential separation between public-coin classical and entanglement-free quantum communication in the multiparty simultaneous message passing model by proving that the $k$ -party Index Coordination problem requires only $O(\log n)$ bits with public randomness but $\Omega(n^{1-1/k})$ or $\Omega(n^{(k-1)/(k+1)})$ qubits without it, demonstrating that quantum superposition cannot efficiently simulate the coordination power of shared randomness.

Original authors: Pedro Montealegre, Ivan Rapaport, Jorge Valenzuela

Published 2026-09-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pedro Montealegre, Ivan Rapaport, Jorge Valenzuela

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of distributed computing, where separate computers must work together without talking to one another, a fundamental question has long puzzled researchers: how much information must be exchanged to solve a problem when everyone is working in the dark? This inquiry lives within a framework known as the simultaneous message passing model. Imagine a group of people, each holding a piece of a puzzle, who must each send a single note to a central referee. The referee, who sees no puzzle pieces themselves, must then assemble the final picture based solely on those notes. The challenge lies in the resources available to the players. They might rely on private luck, where each person flips their own coin to decide what to write. They might share a public source of randomness, like a giant, synchronized clock that everyone can see, allowing them to coordinate their notes without speaking. Or, they might try to use the strange, counterintuitive laws of quantum mechanics, sending messages encoded in particles that can exist in multiple states at once, but without sharing any pre-existing quantum connections.

For decades, scientists have known that in a simple two-person game, shared public luck is vastly superior to private luck, and that quantum messages can sometimes outperform private luck by a huge margin. However, a critical mystery remained: could quantum messages, even without pre-shared connections, mimic the powerful coordination that comes from sharing public luck? This question became even more pressing as researchers began to consider scenarios with many players, not just two. Does the advantage of quantum mechanics hold up when the team grows, or does the lack of a shared plan become a bottleneck that even the strangest physics cannot overcome?

A team of researchers from universities in Chile has now answered this question with a definitive and surprising result. They constructed a specific coordination challenge involving a team of players, each holding a long string of zeros and ones. The final player in the group holds a special map, or selector, that highlights exactly half of the positions in the strings as valid targets. The goal for the central referee is to pick one of these valid targets and report the corresponding bits from every player's string. The researchers proved that if the players share a public source of randomness, they can solve this problem with incredibly short messages, requiring only a number of bits that grows logarithmically with the size of the strings. This is an efficient solution, akin to everyone agreeing on a single random number to guide their actions.

However, when the players are forced to rely solely on their own private luck or unentangled quantum messages, the situation changes dramatically. The researchers demonstrated that without the shared public plan, the quantum messages required to solve the problem grow much larger. In fact, as the number of players increases, the amount of quantum information needed approaches the size of the entire input. The study shows that quantum superposition, the ability of particles to be in multiple states simultaneously, cannot efficiently simulate the coordination afforded by shared public randomness. Even with the full power of quantum mechanics, if the players cannot share a common random source or pre-existing entanglement, they are forced to send massive amounts of data to ensure the referee finds a valid answer.

The team established these limits by proving that the coordination required by the problem creates an information bottleneck that quantum messages cannot easily bypass. They showed that for any fixed number of players, the quantum protocol requires a message length that is exponentially larger than the public-randomness protocol. This gap widens as the team grows; for a large enough group, the quantum players must essentially send their entire inputs to the referee, while the public-randomness players still manage with tiny notes. The researchers also found that in the strictest version of the problem, where no errors are allowed, quantum communication offers no advantage over classical private randomness at all. Both require similarly large messages, suggesting that the unique power of quantum mechanics is not enough to replace the need for a shared plan in this context.

These findings settle a long-standing debate about the relative power of different communication resources in a multi-player setting. The work confirms that while quantum mechanics can outperform private classical strategies in some scenarios, it cannot replicate the efficiency of shared public randomness when players are isolated from one another. The researchers' proof relies on a new mathematical insight regarding how quantum states can be identified when they are combined from multiple sources. They showed that the ability to distinguish between different combined states is strictly limited by the product of the abilities to distinguish the individual parts. This limitation forces the players to send more information as the team size grows, effectively capping the efficiency of unentangled quantum communication.

The implications of this work extend beyond the specific puzzle the researchers solved. It provides a clear boundary for what is possible in quantum networks where players do not share entanglement. It suggests that for certain types of distributed tasks, the most effective resource is not the most exotic physics, but rather a simple, shared agreement on how to proceed. The study proves that for every integer number of players greater than one, the separation between public randomness and unentangled quantum communication is exponential. This means that as the problem scales, the quantum advantage evaporates, leaving the players with a requirement for linear communication that matches the cost of sending the full data. The result is a robust demonstration that the coordination provided by shared randomness is a resource that quantum mechanics, on its own, cannot efficiently simulate.

Technical Summary: On the Limits of Quantum Multiparty Simultaneous Communication

1. Problem Definition and Motivation

This work addresses a fundamental question in quantum communication complexity: Can unentangled quantum communication efficiently simulate the coordination capabilities afforded by classical shared randomness (public coins) in a multiparty setting?

In the Simultaneous Message Passing (SMP) model, $k$ spatially separated players receive private inputs and send a single, independent message to a central referee. The referee must evaluate a joint function or relational problem without further communication. While the hierarchy between classical private randomness, public randomness, and unentangled quantum messages is well-understood for two players (where public coins and quantum messages are incomparable), the multiparty case ( $k \ge 3$ ) remained open regarding the specific phenomenon of Index Coordination.

The authors introduce Multiparty Index Coordination ( $IC_{k,n}$ ), a natural $k$ -party generalization of the two-party Index Coordination problem.

Inputs: Players $P_1, \dots, P_{k-1}$ each receive an $n$ -bit string $x_j$ . Player $P_k$ receives an $n$ -bit string $x_k$ and a selector string $s \in \{0,1\}^n$ with Hamming weight exactly $n/2$ .
Goal: The referee must output a tuple $(i, x^{(i)}_1, \dots, x^{(i)}_k)$ such that $s(i) = 1$ .
The Bottleneck: Without shared randomness, the first $k-1$ players cannot coordinate to agree on a specific index $i$ that satisfies $P_k$ 's selector. They must send enough information to allow the referee to find a valid intersection across all inputs.

The paper investigates the communication cost (maximum message length) required to solve $IC_{k,n}$ under three resource models:

Classical Public-Coin ( $R^{\parallel}_{pub}$ ): Players share a random string.
Classical Private-Coin ( $R^{\parallel}_{priv}$ ): Players have independent local randomness.
Quantum without Pre-shared Entanglement ( $Q^{\parallel}$ ): Players send quantum states; no prior entanglement or public coins are shared.

The study covers two error regimes:

Unambiguous: The referee never outputs an incorrect tuple; it may only abort (output $\perp$ ) with probability $\le \epsilon$ .
Bounded-Error: The referee may output an incorrect tuple or abort, with the total failure probability $\le \epsilon$ .

2. Methodology and Technical Tools

2.1 Structural Theorems for State Identification

To derive lower bounds, the authors develop and apply specific theorems regarding the identification of product states:

Exact Factorization Theorem (Unambiguous): The authors prove a direct-product theorem for unambiguous quantum state identification over arbitrary finite alphabets. They demonstrate that for a product state $\rho = \bigotimes_{j=1}^k \rho_j$ , the global success probability of unambiguously identifying a specific label sequence is bounded by the product of the local success probabilities. This structural property allows the reduction of the multiparty problem to a product of local constraints.
Parity Collapse (Bounded-Error): For the bounded-error regime, a direct $k$ -party product theorem is obstructed by the complexity of Semidefinite Programming (SDP) duality. The authors circumvent this by grouping the first $k-1$ players into a single "meta-player" based on the parity of their inputs. They prove an exact factorization of the trace distance between parity states, reducing the $k$ -party coordination constraint to a two-register asymmetric state identification task. This allows them to leverage existing 2-register bounds by Gavinsky et al.

2.2 Information-Theoretic Bounds

The proofs rely heavily on:

Random Access Code (RAC) Lemmas: Used to bound the sum of capacities (predictability) of individual bits extractable from a quantum message.
- In the unambiguous regime, this yields an $L_1$ bound on the sum of success probabilities.
- In the bounded-error regime, this yields an $L_2$ bound on the sum of squared trace distances (biases).
Arithmetic Mean-Geometric Mean (AM-GM) Inequality: Used to pool the capacities of the first $k-1$ players, establishing that if the total information is limited, the product of their individual predictive powers must be small.

3. Key Contributions and Results

3.1 Classical Protocols

Public-Coin Upper Bound: The authors present a protocol where players use shared randomness to sample a random index $i$ $i$ . Since the selector $s$ $s$ has density $1/2$ $1/2$ , a constant number of trials yields a valid index with high probability.
- Cost: $O(\log n)$ bits (maximum message length).
- Regime: Works for both unambiguous and bounded-error settings.
Private-Coin Upper Bound: A protocol generalizing Ambainis's approach treats inputs as a $k$ $k$ -dimensional tensor. Players independently select random coordinates in their respective dimensions. The intersection of these hyperplanes yields a candidate index.
- Cost: $O(n^{1-1/k})$ bits.
- Regime: Unambiguous.

3.2 Quantum Lower Bounds

The paper establishes that unentangled quantum protocols cannot match the efficiency of public coins and, in the unambiguous regime, cannot even match private coins.

Unambiguous Regime:
- Lower Bound: $\Omega(n^{1-1/k})$ qubits.
- Method: Using the exact factorization theorem and RAC bounds, the authors show that the product of local success probabilities is too small to guarantee a valid global output unless the message size scales as $n^{1-1/k}$ .
- Implication: Quantum communication provides no asymptotic advantage over classical private randomness in the unambiguous regime. Both require $\Theta(n^{1-1/k})$ .
Bounded-Error Regime:
- Lower Bound: $\Omega(n^{(k-1)/(k+1)})$ qubits.
- Method: Using the parity-collapse reduction, the problem is mapped to a 2-register asymmetric identification task. The bound is derived by balancing the trace distance of the parity state against the prediction capacity of the $k$ -th player.
- Implication: While quantum communication offers a potential advantage over private coins in the bounded-error regime (as $n^{(k-1)/(k+1)} < n^{1-1/k}$ for $k \ge 3$ ), it still falls exponentially short of the public-coin $O(\log n)$ bound.

3.3 Asymptotic Behavior with $k$

The exponents of the lower bounds depend explicitly on $k$ :

As $k$ increases, the exponents $1-1/k$ and $(k-1)/(k+1)$ both approach 1.
Linear Complexity: When $k \ge c \log n$ (for any fixed $c > 0$ ), both quantum lower bounds become $\Omega(n)$ . This matches the trivial protocol where players send their full inputs, establishing tight linear complexity.
Independence of Constants: Crucially, the constants in the upper and lower bounds are independent of $k$ . This ensures the exponential separation holds for any integer-valued function $k(n) \ge 2$ , regardless of how fast $k$ grows relative to $n$ .

4. Significance and Claims

The paper claims to establish a multiparty exponential separation between classical shared randomness and unentangled quantum communication.

Incomparability Extended: The results extend the known incomparability of public coins and quantum messages (established for $k=2$ ) to arbitrary $k$ . Quantum superposition cannot efficiently simulate the coordination afforded by public randomness.
Limits of Unentangled Quantumness: In the unambiguous regime, the work demonstrates that without shared entanglement, quantum communication offers no asymptotic advantage over classical private randomness for coordination tasks. The "quantum advantage" is strictly limited to the bounded-error regime and even there, it is polynomially weaker than the public-coin advantage.
Mathematical Contribution: The paper provides an exact factorization theorem for unambiguous identification of product states over arbitrary finite alphabets. This result is presented as being of independent mathematical interest, offering a rigorous tool for analyzing multiparty state discrimination.

The authors conclude that while quantum communication is powerful, its ability to solve multiparty coordination problems without pre-shared entanglement is severely bottlenecked by the lack of a mechanism to coordinate independent inputs, a role that public randomness fills efficiently.