⚛️ quantum physics

Nonlocal Games in the High-Noise Regime: Optimal Quantum Values and Rigidity

This paper characterizes the optimal winning probabilities of several nonlocal games in the high-noise regime and establishes the first noise-robust rigidity theorems for Pauli observables, enabling device-independent noise estimation and advancing applications in MDI cryptography and the study of $\text{MIP}^*_0$ .

Original authors: Honghao Fu, Minglong Qin, Haochen Xu, Penghui Yao

Published 2026-04-21

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Honghao Fu, Minglong Qin, Haochen Xu, Penghui Yao

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 you are a detective trying to verify that two people, Alice and Bob, are truly sharing a magical, invisible connection (quantum entanglement) that allows them to coordinate their answers perfectly without talking to each other. This is the basis of Nonlocal Games.

In a perfect world, if they win the game almost 100% of the time, you know for a fact they are using the "ideal" magic trick. This is called Rigidity: the game forces them to reveal exactly how they are doing it.

But here's the problem: In the real world, things are messy. The "magic" they share is often noisy, like a radio signal with static, or a pair of dice that are slightly weighted. For a long time, scientists thought that if the noise was too high, the game would become useless. You couldn't tell if they were cheating, using a different trick, or just getting lucky. The "rigid" structure would collapse.

This paper is a breakthrough because it says: "No, even in a very noisy world, we can still catch them in the act and know exactly what they are doing."

Here is a simple breakdown of their discoveries using everyday analogies:

1. The "Noisy Radio" Analogy

Imagine Alice and Bob are trying to tune into a specific radio station (the ideal quantum state).

The Old View: If the static (noise) is too loud, you can't hear the station. You assume the connection is broken or fake.
This Paper's View: Even with loud static, if Alice and Bob manage to tune in just enough to win the game, we can mathematically prove exactly how loud the static is and, more importantly, which specific radio frequency they are actually using.

2. The "Crowded Room" vs. "The Empty Hall"

This is the most surprising part of the paper.

In a Perfect (Noiseless) World: To get the perfect score, Alice and Bob might need to use a massive, complex machine with thousands of gears (many quantum bits) working together. It's like trying to solve a puzzle by moving every piece in a giant room at once.
In a Noisy World: The paper proves that noise actually simplifies things. If the signal is noisy, the only way to win is to ignore the massive machine and focus on one single, tiny gear.
- The Metaphor: Imagine you are trying to hear a whisper in a hurricane. You can't use a giant, complex microphone array; you have to cup your hand right over your ear and focus on one specific spot. The noise forces the players to "concentrate" their strategy on a single, simple part of their system.

3. The "Self-Testing" Detective

The authors studied two famous games:

The CHSH Game: A simple logic puzzle where players guess each other's inputs.
The Magic Square Game: A puzzle where players fill a grid with numbers to satisfy specific rules.

They calculated the exact maximum score possible for these games when the "magic" is noisy.

Why this matters: Before this, if you saw a score of 90%, you didn't know if it was because the noise was 10% or 20%. Now, the score tells you the exact noise level.
The "Rigidity" Result: If they score close to that maximum, we can prove they are using a specific, simple set of tools (Pauli measurements) on a single pair of particles. We don't need to trust their equipment; the game itself forces them to reveal their tools.

4. Why Should You Care? (The Real-World Impact)

This isn't just abstract math; it has huge practical uses:

The "Black Box" Problem: Imagine you buy a quantum computer from a company. You don't trust them, and you don't trust their hardware (it's noisy). You want to know: "Is this thing actually doing quantum magic, or is it just a fancy calculator?"
- The Solution: You play this noisy game with them. If they win with the specific score predicted by this paper, you know for a fact they are using the correct quantum tools, even if their machine is broken or noisy. This is called Device-Independent Certification.
Quantum Internet: In a future quantum internet, signals will degrade over long distances (noise). This paper gives us the rules to verify that the connection is still secure and working, even when the signal is weak.
Cryptography: It helps build unbreakable codes. Even if the devices generating the codes are imperfect, this math proves the codes are still secure.

Summary

Think of this paper as a new set of detective rules for a foggy day.
Previously, detectives thought, "If it's too foggy, we can't see the suspect's face."
This paper says, "Actually, the fog makes the suspect's silhouette stand out in a very specific way. If we see that silhouette, we know exactly who they are, what they are holding, and how bad the fog is, without ever needing to see them clearly."

They turned a limitation (noise) into a feature that simplifies the verification process, making quantum technology more robust and trustworthy for the real world.

1. Problem Statement

The paper addresses a fundamental gap in quantum information theory regarding nonlocal games (such as CHSH and Magic Square) under high-noise conditions.

Context: In realistic quantum devices, shared entangled states are rarely ideal pure states (like perfect EPR pairs) but are instead mixed states due to environmental noise.
The Challenge: Existing rigidity theorems (which certify that near-optimal game performance implies a specific quantum state and measurement structure) are formulated for noiseless settings. They rely on the assumption that the winning probability is close to the ideal quantum value (e.g., $\cos^2(\pi/8)$ for CHSH).
The Gap: In a noisy regime, the optimal achievable winning probability is strictly lower than the ideal value. Consequently, standard rigidity theorems fail because a strategy achieving the "noisy optimal" might not be close to the ideal noiseless strategy. Furthermore, it was unclear how to characterize the optimal value when players share arbitrarily many copies of a noisy state and can perform global (collective) measurements, a scenario distinct from bounded-copy assumptions in previous works.
Core Questions:
1. What is the exact optimal quantum winning probability for nonlocal games when players share arbitrarily many copies of a noisy state?
2. If a strategy achieves this noisy optimal value, what can be certified about the underlying state and measurements (Rigidity)?

2. Methodology

The authors employ a combination of techniques from quantum proof systems, quantum learning theory, and operator analysis:

Noise Modeling:
- CHSH: They model noise using Quantum Maximal Correlation ( $\rho$ ). The source prepares i.i.d. copies of a bipartite state $\Psi$ with maximally mixed marginals and maximal correlation bounded by $\rho$ . This covers depolarizing noise and one-sided Pauli noise.
- Magic Square: They focus on a specific depolarizing noise model applied to two EPR pairs ( $\Delta^{(16)}_\rho(\Phi^{\otimes 2})$ ).
Sum-of-Squares (SoS) Decompositions: The proofs utilize SoS techniques to bound the violation of Bell inequalities. By decomposing the game operator into sums of squares of operators, they derive tight upper bounds on the winning probability in the presence of noise.
Pauli Analysis and Truncation: The authors analyze the Pauli expansion of observables. They prove that near-optimal strategies in the noisy regime force the "degree" of the observables to concentrate on low-order terms (specifically degree-1), effectively suppressing high-degree correlations that would arise from collective measurements on many copies.
Register Concentration: A key technical insight is proving that despite the availability of $n$ copies, the optimal strategy effectively acts non-trivially on only one register (a single qubit or pair of qubits), while acting trivially on the rest.

3. Key Contributions and Results

A. Optimal Quantum Values (Answering Question I.1)

The paper provides explicit formulas for the maximal winning probabilities in the high-noise regime:

CHSH Game: For a state with maximal correlation $\rho$ , the optimal winning probability (under traceless observables) is:
$\omega^*_{CHSH} = \frac{1}{2} + \frac{\sqrt{2}}{4}\rho$
This holds even if players share arbitrarily many copies. The noise does not improve the value; the optimal strategy uses the same observables as the noiseless case but scaled by $\rho$ .
Magic Square Game: For the depolarized two-EPR-pair state with parameter $\rho$ , the optimal winning probability is:
$\omega^*_{MS} = \frac{1 + \rho}{2}$
2-out-of- $n$ Variants: The authors extend these results to the 2-out-of- $n$ CHSH and Magic Square games, showing the same optimal values apply, provided the players pass consistency tests.

B. Noise-Robust Rigidity Theorems (Answering Question I.2)

The paper proves that achieving a winning probability close to the noisy optimal value ( $\omega^* - \epsilon$ ) certifies specific structural properties:

Register Concentration: Unlike the noiseless case where optimal strategies can be spread across multiple registers, in the noisy regime, the observables are forced to act non-trivially on a single register (one qubit for CHSH, one 4-dimensional register for Magic Square).
Simple Unitaries: The certification requires only local unitaries acting on that single register to map the observed observables to the canonical Pauli operators ( $X, Z$ ). This contrasts with noiseless rigidity, which often requires complex "swap" isometries acting on the entire system.
Robustness: The rigidity error scales as $O(\sqrt{\epsilon})$ , matching the noiseless regime's robustness order, but with the added benefit of structural simplification (single-register support).
Specific Theorems:
- Theorem I.5 (CHSH): Certifies one pair of anticommuting Pauli observables ( $Z, X$ ) on a single qubit.
- Theorem I.6 (2-out-of- $n$ CHSH): Certifies $n$ distinct pairs of anticommuting observables on $n$ distinct registers.
- Theorem I.8 & I.9 (Magic Square): Certifies the canonical Magic Square observables on a single register (or $n$ distinct registers for the 2-out-of- $n$ variant).

C. Geometric Characterization

The authors characterize the set of quantum correlations ( $Q_\rho$ ) in the high-noise regime. They show that for the CHSH game, the set of achievable correlations is a uniformly shrunk version of the noiseless quantum set, forming a circle of radius $2\sqrt{2}\rho$ in the $(S, \tilde{S})$ plane.

4. Significance and Applications

Device-Independent Protocols: The results enable Device-Independent (DI) estimation of noise levels. By observing the winning probability, a verifier can bound the noise parameter $\rho$ without trusting the source's internal workings (beyond the i.i.d. assumption).
Measurement-Device-Independent (MDI) Cryptography: The rigidity results apply to MDI scenarios where the source is trusted but noisy, allowing for the certification of untrusted measurement devices.
Computational Complexity (MIP):* The results are crucial for the study of MIP (Multi-prover Interactive Proofs with Entanglement). Specifically, they provide tools to handle the "gap-shrinking" technique in the presence of noise, which is essential for analyzing the complexity class *MIP $_0$ * (where the completeness-soundness gap vanishes).
Structural Insight: The discovery that noise forces "register concentration" is a novel structural phenomenon. It suggests that in high-noise environments, collective measurements across many copies offer no advantage over single-copy strategies for maximizing nonlocal correlations, simplifying the verification of quantum devices.

5. Conclusion

This work establishes the first rigorous framework for nonlocal games in the high-noise regime with unbounded copies. It resolves the open question of optimal values and provides robust rigidity theorems that are stronger in terms of structural simplicity (single-register support) compared to their noiseless counterparts. These findings bridge the gap between theoretical quantum complexity and the practical limitations of near-term noisy quantum hardware.