⚛️ quantum physics

Formalizing CHSH Rigidity in Lean 4

This paper presents a formalization in Lean 4 of the CHSH rigidity theorem, demonstrating that any strategy achieving near-optimal CHSH values is locally isometric to the canonical qubit strategy, while simultaneously identifying a gap in the original proof by McKague, Yang, and Scarani.

Original authors: Tianrun Zhao, Nengkun Yu

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tianrun Zhao, Nengkun Yu

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

Imagine you are a detective trying to solve a mystery in a world where the rules of reality are a bit weird. This paper is about a specific mystery called the CHSH Game, a famous test used to prove that two people (let's call them Alice and Bob) are sharing a "spooky" quantum connection that classical physics can't explain.

Here is the story of what the authors did, explained simply:

1. The Mystery: The "Perfect" Score

In the quantum world, there is a game Alice and Bob play. If they play using normal, everyday logic (classical physics), the best score they can get is 2. But if they use quantum magic (entangled particles), they can get a higher score, up to 2.82 (which is $2\sqrt{2}$ ). This maximum score is called Tsirelson's bound.

The big question is: If Alice and Bob get a score that is almost perfect (like 2.81), does that mean they are definitely using the "perfect" quantum setup?

The answer is yes. This is called Rigidity. It's like saying, "If you run a marathon in 2 hours and 1 minute (when the world record is 2 hours), you must be running with the exact same perfect form as the world record holder, maybe just a tiny bit tired."

2. The Problem: A Flaw in the Old Map

For years, scientists had a "map" (a mathematical proof) explaining why this rigidity works. They said, "If you get a high score, we can mathematically transform your setup to look exactly like the perfect one."

However, the authors of this paper found a hole in the map.

The Analogy: Imagine the old map told you to cross a river by stepping on stones. But the map assumed the river was always shallow. In one specific, weird case (where the river is actually dry or the stones are missing), the instructions didn't make sense. The old proof tried to force a solution that didn't work in that specific edge case.
The Fix: The authors found this gap and fixed it. They didn't just patch the hole; they redesigned the bridge so it works in every situation, even the weird ones.

3. The Solution: Building a "Digital Twin"

To prove their point, the authors didn't just write the proof on paper. They built it inside a computer program called Lean 4.

Think of Lean 4 as a super-strict accountant or a robot referee.

In normal math, you can say "and so on" or "it's obvious."
In Lean 4, you cannot. You have to write down every single step, every tiny assumption, and every logical jump. If you skip a step, the robot says, "Error! I don't understand."

By forcing the proof to be this strict, they ensured the logic was bulletproof.

4. How They Did It (The "Extraction" Trick)

The core of their proof is a process called Extraction.

The Scenario: Alice and Bob have a messy, complicated quantum machine. It's full of extra junk and weird parts.
The Goal: The authors wanted to show that if the machine scores high, you can "extract" a tiny, perfect core from it.
The Metaphor: Imagine you have a giant, rusty, over-engineered toaster that somehow makes perfect toast. The authors showed that you can take that toaster apart, strip away all the rust and extra gears, and find a tiny, perfect, brand-new toaster hidden inside.
The Result: They proved that no matter how messy the original machine is, if the score is high enough, you can mathematically "peel away" the junk and find the perfect Bell State (the ideal quantum connection) and the perfect measurement tools hidden inside.

5. Why This Matters

You might ask, "Why do we need a computer to check this?"

Human Error: Quantum physics involves long chains of complex math. It's easy for a human to make a tiny mistake in a calculation that ruins the whole conclusion.
Trust: By using Lean 4, the authors created a certified proof. It's like having a notary public sign off on a legal document. We can be 100% sure the logic is correct because the computer checked every single step.
Future Tech: This is crucial for Quantum Cryptography. If we want to build unbreakable codes based on quantum physics, we need to be absolutely sure that the "spooky" connections we are using are real and not a trick. This paper gives us that certainty.

Summary

In short, these researchers took a famous quantum physics rule, found a small crack in the old explanation, fixed it, and then used a super-strict computer program to prove that the fix works perfectly. They showed that if two people play the quantum game well, they must be using the ideal quantum setup, hidden inside whatever messy machine they are using.

It's like proving that if a car drives at the speed of light, it must be made of pure gold, even if it looks like a rusty junk heap on the outside. And they proved it so rigorously that a robot can't find a single flaw.

Based on the paper "Formalizing CHSH Rigidity in Lean 4" by Tianrun Zhao and Nengkun Yu, here is a detailed technical summary covering the problem, methodology, key contributions, results, and significance.

1. Problem Statement

The paper addresses the Robust CHSH Rigidity Theorem, a fundamental result in quantum information theory. The CHSH inequality distinguishes classical from quantum correlations. While it is known that the maximum quantum violation (Tsirelson's bound, $2\sqrt{2}$ ) is achieved uniquely by a specific canonical strategy (an EPR pair with specific Pauli observables), the rigidity property asserts that any strategy achieving a value close to $2\sqrt{2}$ must be locally isometric to this canonical strategy (up to a "junk" system).

The specific challenges addressed are:

Formal Precision: Translating the often terse, high-level mathematical arguments found in literature (specifically Cleve's notes and the work of [9]) into a rigorous, machine-checkable format.
Robustness: Handling the "near-optimal" case where the CHSH value is $2\sqrt{2} - \epsilon$ , requiring precise spectral estimates and norm bounds.
Literature Gaps: Identifying and correcting subtle errors in existing proofs regarding the definition of extracted operators when observables are not invertible.

2. Methodology

The authors utilized Lean 4, an interactive theorem prover, to formalize the entire proof. The methodology involved:

Modular Architecture: The proof was decomposed into composable, reusable components rather than a single monolithic proof. The workflow follows a pipeline:
1. Bias Assumption: Assuming the CHSH value is near-optimal.
2. Ideal Expectation Bound: Deriving spectral estimates.
3. Extracted Qubit Analysis: Analyzing the structure of the extracted observables.
4. Bell-State Overlap: Proving the state is close to the ideal Bell state.
5. State/Operator Extraction: Constructing local isometries to map the physical strategy to the canonical one.
Mathlib Integration: The development leveraged the Mathlib ecosystem for foundational linear algebra, normed spaces, and tensor product manipulations, avoiding the need to formalize basic mathematics from scratch.
Explicit Tensor Management: A significant portion of the formalization effort was dedicated to rigorously handling tensor reassociation (regrouping factors). In informal proofs, maps like $regSwap$ (reordering $(C^2 \otimes H_A) \otimes (C^2 \otimes H_B)$ to $(C^2 \otimes C^2) \otimes (H_A \otimes H_B)$ ) are often implicit. In Lean, these must be explicit linear maps.
Modified Bob-Side Construction: The authors modified the standard proof (Cleve's notes) by incorporating a specific rotation $R$ directly into Bob's extractor unitary $U_B$ and the ancilla state $|aux\rangle$ from the start, rather than applying it as a final cleanup step. This ensures the extracted operators match the standard CHSH observables ( $H, H'$ ) exactly at the intermediate stage.

3. Key Contributions

A. Identification of a Gap in Literature

The authors identified a critical flaw in the argument presented in reference [9].

The Flaw: The original authors defined Bob's extracted operators $X'_B$ and $Z'_B$ using a modulus convention where the operator acts as the identity on the kernel of the denominator. They claimed these operators anticommute ( $\{X'_B, Z'_B\} = 0$ ).
The Counterexample: The authors constructed a counterexample (dimension 2, $B_0 = B_1 = \sigma_z$ ) where the denominator is zero, and under the "identity on kernel" convention, the resulting operators are $I$ and $\sigma_z$ , which do not anticommute.
The Fix: The Lean formalization avoids this ambiguity by using a conjugation trick (rotating the basis via $R$ ) to ensure the extracted operators are unitary by construction, bypassing the need for arbitrary kernel conventions.

B. Formalization of the Rigidity Theorem

The paper provides the first machine-checked proof of the robust CHSH rigidity theorem. It formally establishes that for any strategy $S$ with bias $\beta(S) \geq 2\sqrt{2} - \epsilon$ , there exist local isometries $V_A, V_B$ and a junk state such that:

State Extraction: The transformed state is within $O(\sqrt{\epsilon})$ of $|\Phi^+\rangle \otimes |\Phi_{junk}\rangle$ .
Operator Extraction: The transformed observables $A_0, A_1, B_0, B_1$ are within $O(\sqrt{\epsilon})$ (with specific constants derived) of the canonical Pauli/Hadamard operators acting on the extracted qubit.

C. Explicit Constants and Bounds

Unlike informal proofs that use big-O notation loosely, the formalization produces explicit inequalities with concrete constants (e.g., $c = 128\sqrt{2}$ ), making the robustness bounds fully verifiable.

4. Results

Verified Theorem: The main theorem (Theorem 3.1 in the paper) is fully proven in Lean 4. It confirms that near-optimal CHSH strategies are structurally equivalent to the canonical EPR strategy.
Corrected Proof Path: The formalization validates a corrected proof path that resolves the non-invertibility issue in the original literature, ensuring the anticommutation relations hold strictly.
Code Availability: The formalization is modular and available in a public repository, serving as a reusable library for future quantum information formalizations.

5. Significance

Reliability of Quantum Proofs: The paper demonstrates that formal verification is a crucial tool for quantum information theory, where long chains of calculations often hide subtle errors (as evidenced by the gap found in [9]).
Self-Testing Foundation: Robust rigidity is the theoretical backbone of device-independent quantum cryptography and self-testing. By formalizing this, the authors provide a certified foundation for protocols that rely on verifying quantum devices without trusting their internal workings.
Methodological Shift: The work illustrates a shift towards "agentic autoformalization," where AI assistants help draft lemmas, but human experts must rigorously define the algebraic structures and verify the logic to prevent the AI from silently adding incorrect hypotheses.
Community Resource: By building on and extending the Mathlib ecosystem, this work contributes a specialized library for quantum mechanics in Lean, lowering the barrier for future formalizations in the field.

In summary, this paper not only certifies a major theorem in quantum foundations but also exposes a previously unnoticed error in the literature, showcasing the power of formal methods to enhance the reliability of theoretical physics.