⚛️ quantum physics

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement

This paper demonstrates the maximum possible separation in quantum communication complexity by presenting relation problems solvable with zero communication using shared entanglement, while requiring $\Omega(n)$ qubits without it, thereby refuting a quantum analog of Newman's theorem.

Original authors: Atsuya Hasegawa, François Le Gall, Augusto Modanese

Published 2026-04-20

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Atsuya Hasegawa, François Le Gall, Augusto Modanese

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.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

Imagine two friends, Alice and Bob, who are trying to solve a puzzle together. They are in separate rooms and cannot talk to each other directly. The only way they can coordinate is by sending messages (like text messages or letters) back and forth.

In the world of computer science, this is called Communication Complexity. The goal is to solve the puzzle using as few messages as possible.

This paper explores a fascinating question: What happens if Alice and Bob share a "magic connection" before they start?

The Magic Connection: Quantum Entanglement

In the quantum world, Alice and Bob can share a special resource called entanglement. Think of this as a pair of "magic coins." No matter how far apart they are, if Alice flips her coin and it lands on Heads, Bob's coin instantly lands on Tails (or some other specific result), even though they never spoke.

The paper asks: Does having these magic coins help them solve puzzles without sending any messages at all?

The Big Discovery: The Ultimate Gap

The authors found a specific type of puzzle (based on something called the "Magic Square Game") where the difference between having magic coins and not having them is absolutely massive.

With Magic Coins (Entanglement): Alice and Bob can solve the puzzle without sending a single message. They just look at their magic coins, do some math, and write down their answers. They win 100% of the time.
- Communication Cost: Zero.
Without Magic Coins: If they don't have the magic coins, they are forced to send messages. The authors proved that to solve the same puzzle, they must send a huge number of messages—specifically, a number of messages that grows directly with the size of the puzzle.
- Communication Cost: Huge (proportional to the puzzle size).

The Analogy:
Imagine you and a friend are trying to guess a secret code.

With Entanglement: You both have a special crystal ball. You look at yours, and it instantly tells you exactly what to say. You don't need to call or text each other. Cost: 0.
Without Entanglement: You have to write down your guess, put it in an envelope, and mail it to your friend. They read it, write their guess, and mail it back. To solve a complex code, you might need to mail back and forth thousands of times. Cost: High.

The paper shows that for certain puzzles, the "Magic Coin" method is infinitely better than the "Mailing Letters" method. This is the maximum possible separation between the two methods.

The Twist: It Only Works for "Relationship" Puzzles

Here is the most interesting part. The authors also discovered a rule about what kind of puzzles this works for.

Relationship Puzzles (Relations): These are puzzles where there might be multiple correct answers. For example, "Find a pair of numbers that add up to 10." (2+8, 3+7, 4+6 are all valid).
- Result: For these, the Magic Coins allow zero communication.
Function Puzzles (Functions): These are puzzles where there is only one single correct answer. For example, "What is the square root of 16?" (The answer is only 4).
- Result: If a puzzle has a unique answer, the Magic Coins do not help you skip communication. If you can solve it with zero messages using magic coins, you can also solve it with zero messages without magic coins.

The Metaphor:

Relationship Puzzle: "Pick any valid outfit for a party." With magic coins, you and your friend instantly agree on a look without talking. Without them, you might have to text back and forth to agree.
Function Puzzle: "What is the capital of France?" If you both know the answer is Paris, you don't need magic coins to know it. If you didn't know it, magic coins wouldn't magically make you know the one specific answer without you looking it up (communicating).

Why This Matters

This paper breaks a long-held belief in the field. Scientists used to think that "Shared Randomness" (like sharing a list of random numbers) could always replace a lot of communication, similar to how "Shared Entanglement" was thought to work.

The authors proved that this is not true for quantum entanglement.

For Relationships, entanglement is a superpower that eliminates the need for talking entirely.
For Functions, entanglement doesn't give you that superpower; you still have to do the work.

Summary

The paper is like discovering a new law of physics for information:

"If you have a shared quantum connection, you can solve certain 'open-ended' puzzles instantly without speaking. But if you don't have that connection, you'll have to shout across the room for a very long time. However, if the puzzle has only one specific right answer, the quantum connection doesn't give you a free pass; you're stuck with the same rules as everyone else."

This is the first time anyone has proven that the gap between "having entanglement" and "not having it" can be this huge (from zero messages to thousands of messages) for a specific type of problem.

1. Problem Statement

The paper investigates the fundamental power of shared entanglement in quantum communication complexity. Specifically, it seeks to quantify the maximum possible gap (separation) between:

Entanglement-assisted models ( $Q^*$ ): Protocols where Alice and Bob share an arbitrary amount of prior entanglement but communicate zero bits.
Unassisted models ( $Q_{pub}^2$ ): Protocols where Alice and Bob share public randomness but no prior entanglement, and must communicate to solve the problem.

The central question is: Can there exist a problem that is solvable with zero communication if entanglement is allowed, but requires linear communication ( $\Omega(n)$ ) if entanglement is forbidden?

2. Key Contributions and Results

The authors present three main theorems that establish the limits of entanglement's utility:

Theorem 1: Maximum Separation for Relations

Result: There exists a relation problem $R$ $R$ such that:
- $Q^*(R) = 0$ (Solvable with zero communication using shared entanglement).
- $Q_{pub}^2(R) = \Theta(n)$ (Requires linear qubit communication without entanglement).
Significance: This represents the maximum possible asymptotic separation in communication complexity. Since the input size is $n$ , the trivial upper bound is $O(n)$ . Achieving $\Theta(n)$ for the unassisted case while the assisted case is 0 is the strongest possible separation.
Specific Problem: The relation $R$ $R$ is the parallel repetition of the Magic Square Game (repeated $n$ $n$ times).
- The Magic Square Game has a perfect quantum strategy (winning probability 1) but a classical winning probability of $8/9$ .
- Due to the Parallel Repetition Theorem, the probability of winning $n$ copies of the game simultaneously drops exponentially ( $2^{-cn}$ ) for any strategy that does not use the perfect quantum strategy.

Theorem 2: No Separation for Functions

Result: For any function $F: X \times Y \to Z$ , if $Q^*(F) = 0$ , then $Q_2(F) = 0$ .
Significance: This refutes a potential "Quantum Analog of Newman's Theorem." While Newman's theorem states that shared randomness can be replaced by $O(\log n)$ private randomness with a small error penalty, this result shows that for functions, shared entanglement provides no advantage over zero communication if the goal is to compute a function with zero error (or high probability). If a function can be solved with zero communication using entanglement, it can also be solved with zero communication without it.
Contrast: This highlights a fundamental difference between relations (where multiple outputs are valid) and functions (where the output is unique).

Theorem 3: Separation with Non-Signaling Correlations

Result: There exists a relation $R$ $R$ such that:
- $Q_{NS}(R) = 0$ (Solvable with zero communication using non-signaling correlations).
- $Q_2^*(R) = \Theta(n)$ (Requires linear communication even with shared entanglement).
Specific Problem: The parallel repetition of the CHSH game.
Significance: This demonstrates that non-signaling correlations (a theoretical resource stronger than entanglement, allowing perfect winning of CHSH) are strictly more powerful than shared entanglement in the context of communication complexity.

3. Methodology and Proof Strategies

The proofs rely on a combination of quantum teleportation, parallel repetition theorems, and reduction techniques.

Lower Bound Proof (Theorem 1 & 3)

To prove that $\Omega(n)$ communication is required without entanglement (or with entanglement but against non-signaling), the authors use a reduction by contradiction:

Assumption: Assume there exists a 2-way quantum protocol $P$ without entanglement that solves the parallel repetition problem with high probability using $c' n$ qubits of communication.
Teleportation Conversion: Using Quantum Teleportation, the authors convert the quantum communication protocol into a classical communication protocol.
- If the parties share $c'n$ EPR pairs, $c'n$ qubits of communication can be replaced by $2c'n$ classical bits.
Randomness Simulation: The authors construct a protocol $P'$ $P^{'}$ where the parties share the public randomness and the EPR pairs but do not communicate. They use the shared randomness to "guess" the communication transcript.
- If the guess is correct, they proceed; if not, they abort.
- The probability of guessing the correct $2c'n$ bits is $2^{-2c'n}$ .
Entanglement Removal: To remove the entanglement requirement entirely, the shared EPR pairs are replaced by a maximally mixed state (separable state).
- The maximally mixed state can be decomposed into a mixture of the EPR state and other orthogonal states.
- This introduces an additional error factor, resulting in a total success probability scaling roughly as $p \cdot 2^{-4c'n}$ .
Parallel Repetition Theorem: The success probability of the parallel repetition of the Magic Square (or CHSH) game is known to decay exponentially ( $2^{-cn}$ ) for any strategy that is not the perfect quantum strategy.
Contradiction: By comparing the upper bound on success probability derived from the Parallel Repetition Theorem ( $2^{-cn}$ ) with the lower bound derived from the simulation ( $p \cdot 2^{-4c'n}$ ), the authors show that if the communication $c'n$ is too small (specifically $c' < c/4$ ), the success probability becomes exponentially small ( $2^{-\Omega(n)}$ ). Thus, to achieve high success, communication must be $\Omega(n)$ .

Upper Bound Proof (Theorem 2)

To prove that functions with $Q^*(F)=0$ also have $Q_2(F)=0$ :

Simulation of Marginals: Since the protocol $P$ uses zero communication, Alice's output depends only on her input $x$ and her half of the entangled state. Bob's output depends only on $y$ and his half.
Independence: Because there is no communication, the marginal distribution of Alice's measurement outcomes is independent of Bob's input $y$ , and vice versa.
Deterministic Simulation: Alice can locally simulate her marginal distribution using the reduced density matrix of her entangled state (which is a maximally mixed state). She simply outputs the most probable outcome. Bob does the same.
Correctness: Since the original protocol computes the function $F$ with high probability, the most probable outcome for Alice and the most probable outcome for Bob must be the correct values of $F(x)$ and $F(y)$ (or consistent with the function definition). Thus, they can compute $F$ with zero communication and zero entanglement.

4. Significance and Implications

Refutation of Quantum Newman's Theorem: The results show that a direct quantum analog of Newman's theorem (which reduces shared randomness to private randomness) does not hold for relations in the presence of entanglement. While shared randomness can be compressed, shared entanglement cannot be replaced by a small amount of private resources without communication for certain relation problems.
Tight Trade-off: The paper establishes an asymptotically tight trade-off between the amount of entanglement and communication. For the parallel Magic Square game:
- With $\Omega(n)$ EPR pairs: 0 communication.
- With $o(n)$ EPR pairs: $\Omega(n)$ communication is required.
Hierarchy of Correlations: The work clarifies the hierarchy of resources:
- Non-signaling correlations > Shared Entanglement > Shared Randomness (in the context of zero-communication solvability for specific relations).
Relation vs. Function: It provides a rigorous theoretical distinction showing that the power of entanglement in communication complexity is heavily dependent on whether the task is a function (unique solution) or a relation (multiple valid solutions).

5. Conclusion

This paper resolves a long-standing question regarding the limits of entanglement in communication complexity. It proves that for relation problems, shared entanglement can reduce communication complexity from linear to zero, a separation that is maximal. However, this power vanishes for functions, where entanglement offers no advantage over zero-communication protocols. The results rely on the exponential decay of parallel repetition theorems and the unique properties of quantum teleportation and non-signaling correlations.