⚛️ quantum physics

Non-local games and communication complexity with noisy entanglement

This paper investigates the impact of four distinct noise models on quantum nonlocality and entanglement-assisted communication complexity, establishing new bounds on game values, proving parallel repetition theorems, demonstrating a separation between noisy and noiseless entanglement, and resolving open questions regarding the resources required for communication tasks.

Original authors: Srijita Kundu, Olivier Lalonde

Published 2026-09-07

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Srijita Kundu, Olivier Lalonde

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 strange and counterintuitive world of quantum mechanics, two particles can become linked in a way that defies our everyday experience. When particles are entangled, a change to one instantly influences the other, no matter how far apart they are. Scientists have long used this connection as a powerful resource, allowing two people, traditionally named Alice and Bob, to perform tasks that would be impossible or require far more effort if they were limited to classical physics. They can play games with higher winning odds or send messages with less communication than classical rules allow. However, these ideal scenarios assume the particles are perfectly pure and the connection is flawless. In the real world, things are never perfect. Noise from the environment, heat, or imperfect equipment inevitably corrupts these delicate quantum links, turning a pristine connection into a fuzzy, imperfect one. The big question for researchers has been: just how much does this noise ruin the advantage? Does a slightly noisy connection still offer a massive boost, or does it crumble under the weight of imperfection?

A team of researchers has now mapped out exactly how different types of noise degrade these quantum advantages. They focused on a specific scenario where Alice and Bob share not just one, but an unlimited number of these noisy quantum links. They tested four distinct ways these links can get corrupted: a type of noise that scrambles the information randomly, a type that preserves some symmetry, a type that resets the particles to a specific state with a bias, and a type that simply erases the information entirely. Their work reveals a clear boundary between what is possible with perfect connections and what remains possible with noisy ones. They found that while having unlimited noisy links is better than having nothing at all, it is strictly weaker than having even a few perfect links. In fact, for certain tasks, the difference is so profound that it requires a massive amount of extra communication to make up for the lack of perfection.

The researchers began by studying a famous game called CHSH, which serves as a standard test for quantum power. In this game, Alice and Bob receive random inputs and must produce outputs that satisfy a specific condition. With perfect quantum links, they can win about 85 percent of the time, beating the best possible classical strategy. The team calculated the maximum winning probability for this game when the links are noisy. They discovered that the winning chance drops as the noise increases, but the drop is not linear. Crucially, they proved that no matter how clever Alice and Bob are with their measurements, they cannot exceed a specific upper limit determined by the noise level. This limit is lower than the perfect quantum value, and for some noise levels, it is so low that the players might as well be playing without any quantum help at all.

To understand the full impact of this noise, the researchers looked at what happens when the game is played many times in parallel. In the world of perfect quantum mechanics, playing the game many times allows the players to maintain their high winning rate. However, the team proved that with noisy links, the winning rate for the combined game drops much faster than it does with perfect links. They showed that for a wide range of noise levels, the advantage of using quantum links shrinks significantly as the number of games increases. This is a surprising result because it suggests that noise doesn't just add a small penalty; it fundamentally changes the scaling of the advantage. The researchers were able to calculate exactly how fast this rate drops, showing that in a specific range of noise, the quantum advantage is strictly smaller than what is possible with perfect links, even though the particles are still technically entangled.

This finding led to a major discovery about communication. The researchers constructed a specific problem that Alice and Bob could solve with zero communication if they shared perfect quantum links. However, if they were forced to use only noisy links, they would need to exchange a number of bits proportional to the size of the problem to solve it with the same success rate. This proves that noisy entanglement is not just a slightly degraded version of perfect entanglement; it is a fundamentally different resource. The gap is so large that no amount of clever strategy can bridge it without paying a heavy price in communication. This result also has implications for "distillation," the process of trying to clean up noisy links to create perfect ones. The team showed that to create a certain number of perfect links from noisy ones, Alice and Bob must communicate a number of bits proportional to the number of links they want to create. They cannot do this with a tiny amount of communication, proving that the standard methods for cleaning up these links are already as efficient as possible.

The study also revisited the question of whether noisy randomness could replace perfect shared randomness in communication tasks. In the classical world, if Alice and Bob share a large amount of imperfectly correlated random data, they can often simulate the effect of perfect randomness, but it usually requires a lot of that data. The researchers showed that even with noisy quantum links, which are a stronger resource than classical randomness, you still need a polynomial amount of the noisy resource to perform simple tasks like checking if two large numbers are equal with constant communication. This answers a long-standing question in the field: having a logarithmic amount of noisy shared data is not enough. You need a much larger, polynomial amount. This means that the efficiency gains promised by quantum resources are fragile; they rely heavily on the quality of the connection, and once noise is introduced, the savings in communication vanish unless you are willing to invest a significant amount of the noisy resource itself.

Ultimately, this work draws a sharp line between the theoretical power of quantum mechanics and the practical reality of noisy systems. It confirms that while quantum entanglement is a robust resource, its power is not infinite or immune to degradation. The researchers have provided precise mathematical bounds on how much noise can be tolerated before the quantum advantage disappears or becomes too expensive to maintain. Their results suggest that in the near future, as we build quantum networks, we cannot simply assume that having many noisy connections is equivalent to having a few perfect ones. The cost of noise is real, measurable, and in some cases, it requires a complete overhaul of how we think about communication efficiency. The findings serve as a guide for what is achievable in the real world, tempering the excitement of perfect quantum theory with the hard constraints of physical reality.

Technical Summary: Non-local games and communication complexity with noisy entanglement

Problem Statement

This work investigates the impact of noise on two fundamental pillars of quantum information theory: non-local games and entanglement-assisted communication complexity. While the standard models assume access to perfect, noiseless entanglement (specifically, an unbounded supply of EPR pairs), practical near-term applications involve noisy shared resources. The authors study a model where Alice and Bob share an arbitrarily large number of independent copies of a fixed noisy entangled state $\Psi_{E_A E_B}$ , generated by passing one half of a perfect EPR pair through a noisy channel.

The paper addresses two primary questions:

How does noise affect the winning probability (value) of non-local games, particularly the CHSH game, when players share noisy EPR pairs?
Does noisy entanglement provide the same computational power as noiseless entanglement in communication complexity tasks, specifically regarding the Equality function and relational problems?

The study considers four specific noise models: depolarizing noise, unital noise (a general class including depolarizing and dephasing), biased reset noise, and erasure noise.

Methodology

The authors employ a combination of operator algebra, hypercontractivity inequalities, and geometric arguments to derive their results.

1. Maximal Correlation and Hypercontractivity

A central tool is the maximal correlation ( $MC$ ) of the shared state, a quantum generalization of the classical notion introduced by Beigi. The authors compute the maximal correlation for EPR pairs under the four noise models.

They establish hypercontractivity theorems for the noise channels. For depolarizing noise, they utilize known results; for general unital noise, they prove a new hypercontractivity theorem using King's multiplicativity result; for erasure noise, they adapt existing results.
These theorems allow the authors to bound the joint probability distribution of outputs $P_{AB|xy}(a,b)$ in terms of the product of marginal distributions $P_{A|x}(a)P_{B|y}(b)$ raised to a power dependent on the noise parameter (specifically, $1/(1+\rho)$ where $\rho$ is the maximal correlation).

2. Non-local Game Analysis

Upper Bounds: The authors derive upper bounds on the value of the CHSH game under noisy entanglement. For unital noise, they use an NPA local level 1 semidefinite programming (SDP) relaxation with an additional constraint derived from the maximal correlation. For general noise, they derive a bound based on the maximal correlation directly, utilizing the specific structure of the CHSH bias.
Parallel Repetition: They prove noisy parallel repetition theorems. Unlike standard parallel repetition theorems where the base of the exponential decay depends on the single-copy quantum value, these theorems express the decay rate in terms of the classical value and the maximal correlation.
- For general games, they use the pointwise bound and Rényi divergence to relate the noisy quantum value to the classical parallel-repeated value.
- For unique games (including CHSH), they introduce a collision value ( $col_p(G)$ ), defined via induced norms of collision operators. They partition the output space into "buckets" based on marginal probabilities and bound the winning probability by interpolating between a "hard list bound" (based on classical value) and a "collision list bound" (based on the collision value).

3. Communication Complexity Analysis

Separation Results: The authors construct relational problems (specifically threshold versions of the CHSH game) to separate communication models. They show that while perfect entanglement allows solving certain problems with zero communication, noisy entanglement requires linear communication.
Simulation of Entanglement: They generalize the simulation of perfect shared randomness with noisy shared randomness (from [CGMS15]) to the entanglement-assisted setting. They reduce two-way entanglement-assisted protocols to the problem of estimating the inner product of vectors. Using Johnson-Lindenstrauss dimensionality reduction and polynomial expansions of correlated random variables, they construct a Simultaneous Message Passing (SMP) protocol using noisy shared randomness.
Lower Bounds for Equality: To prove lower bounds for the Equality function ( $EQ_n$ ), they combine a standard packing argument with the singular value decomposition of the maximal correlation map. They show that for constant communication, the number of noisy EPR pairs required must grow polynomially with $n$ .

Key Contributions and Results

1. Bounds on the CHSH Game Value

The paper provides new upper and lower bounds for the CHSH game under all four noise models.

Upper Bounds: The value is upper bounded by functions of the maximal correlation $\rho$ . For unital noise, the bound is $\min\left(\frac{1}{2} + \frac{1}{4}\sqrt{1-\rho^2}, \frac{1}{2} + \frac{\sqrt{1+\rho}}{4}\right)$ . For general noise, it is $\min\left(\frac{1}{2} + \frac{1}{4\sqrt{1-\rho^2}}, \frac{1}{2} + \frac{1}{2\sqrt{2}}\right)$ .
Significance: These bounds hold without assumptions on the observables used (unlike previous work [FQXY26] which required traceless observables). The authors note that for depolarizing noise, the bound is not tight at low noise levels (where the state is still entangled but the bound exceeds the classical value).

2. Noisy Parallel Repetition Theorems

General Games: The noisy quantum value of $n$ parallel copies of a game $G$ is upper bounded by $(2\rho \log(|A||B|) \cdot w_G)^{\frac{n}{1+\rho}}$ , where $w_G$ is the classical value.
Unique Games: A sharper bound is derived: $O(n^2) \cdot \left( (col_{1+\rho}(G))^{4\rho} w_G^{1-\rho} \right)^{\frac{n}{1+3\rho}}$ .
CHSH Specifics: For the CHSH game under depolarizing, unital, and erasure noise, the authors prove that the parallel repetition rate is strictly smaller than the noiseless quantum rate ( $\cos^2(\pi/8)$ ) for a non-trivial range of noise parameters (specifically, maximal correlation $\rho \le 0.36$ ). This is significant because it demonstrates that noise degrades the advantage of entanglement even before the state becomes separable.

3. Separation in Communication Complexity

Noisy vs. Noiseless Entanglement: The authors prove a separation between communication with perfect EPR pairs and noisy EPR pairs. There exists a relational problem (based on $t$ -out-of- $n$ CHSH) that can be solved with zero communication using perfect entanglement but requires $\Theta(n)$ two-way classical communication when using noisy entanglement (for sufficiently noisy states).
Implication: This implies an $\Omega(n)$ lower bound on the two-way communication cost required to distill $n$ near-perfect EPR pairs from noisy ones in this regime, showing that known distillation protocols are optimal in terms of communication cost for these states.
Noisy Entanglement vs. Perfect Randomness: For sufficiently low noise, noisy entanglement is strictly weaker than perfect shared randomness for certain tasks, as noisy entanglement cannot simulate perfect randomness without communication overhead in the same way perfect randomness can.

4. Cost of Noisy Entanglement for Equality

Polynomial Lower Bound: The paper proves that computing the Equality function ( $EQ_n$ ) with constant communication requires a polynomial number of noisy EPR pairs (specifically $n^{\Omega(1)}$ ) under all four noise models.
Resolution of Open Question: This answers a question from [CGMS15] in the negative: logarithmically many noisy shared bits (or noisy EPR pairs) are not sufficient for constant-communication protocols for Equality. The required resource cost is exponentially higher than in the perfect correlation case (where $O(\log n)$ suffices).

5. Simulation of Protocols

The authors show that any interactive entanglement-assisted communication protocol can be simulated by an SMP protocol using noisy shared randomness, with an exponential blowup in communication. This generalizes previous results on simulating noiseless shared randomness.

Significance and Claims

The paper claims to be the first to systematically study communication complexity in the presence of noisy entanglement, establishing that this model is strictly weaker than the noiseless model for several tasks.

Non-trivial Noise Regime: A key contribution is demonstrating that the degradation of quantum advantage occurs in a "non-trivial" noise regime where the shared state is still entangled (e.g., for depolarizing noise, $\rho > 1/3$ ). The parallel repetition rate drops below the noiseless quantum rate even while the state remains entangled.
Optimality of Distillation: The separation result implies that existing entanglement distillation protocols are optimal in terms of two-way communication cost for specific noisy states, a result not previously established for distilling $n$ pairs.
Resource Scaling: The work clarifies the resource scaling for noisy entanglement, showing that polynomially many copies are necessary for constant-communication Equality, contrasting sharply with the logarithmic scaling possible with perfect resources.

The authors acknowledge limitations, noting that their techniques do not currently apply to amplitude damping noise (where maximal correlation is 1) and that the parallel repetition theorem for biased reset noise remains open due to a lack of appropriate hypercontractivity results. They also suggest that the bounds on parallel repetition rates could potentially be improved.