⚛️ quantum physics

A Computational Tsirelson's Theorem for the Value of Compiled XOR Games

This paper proves that the compilation method proposed by Kalai et al. is sound for any two-player XOR game by demonstrating that the semidefinite programming upper bound on the quantum value holds for the compiled game up to a negligible error, thereby extending previous results from the specific CHSH case to general XOR games and enabling tight bounds on parallel repetitions, operator self-testing, and sum-of-squares certificates.

Original authors: David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, Tina Zhang

Published 2026-01-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, Tina Zhang

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 a high-stakes game show where two contestants, Alice and Bob, are locked in separate rooms. They cannot talk to each other, but they share a mysterious, invisible connection (like a pair of magic dice that always land on matching numbers, no matter how far apart they are). A referee asks them questions, and they must answer. If their answers follow a specific pattern, they win.

In the world of quantum physics, this is called a Nonlocal Game. The "magic" connection is entanglement. Scientists have long known that if Alice and Bob use quantum entanglement, they can win these games more often than if they were just using ordinary, non-magic strategies.

The Problem: One Player vs. The System

Usually, to prove Alice and Bob are using this "magic," you need two separate people who can't talk. But what if you only have one person (a single quantum computer) and you want to test if it's doing the same "magic" tricks?

In 2023, a team of researchers (Kalai et al.) invented a clever trick called a Compiler. Think of this compiler as a "time-traveling translator." It takes the two-player game and forces the single player to play the role of both Alice and Bob, one after the other.

The referee encrypts Alice's question (hiding it in a digital safe).
The player acts as Alice, opens the safe, measures their "magic" state, and sends back an encrypted answer.
The referee then reveals Bob's question (unencrypted).
The player acts as Bob, measures again, and answers.

The big question was: Does this single-player, encrypted game preserve the same winning odds as the original two-player game?

We knew it worked for classical players (no magic).
We knew it worked for the simplest quantum game (CHSH).
But we didn't know if it worked for all quantum games of a certain type.

The Breakthrough: The "XOR" Games

This paper, by Cui, Malavolta, Mehta, and others, says YES. They prove that for a huge family of games called XOR games, the compiler works perfectly.

What is an XOR game?
Imagine the winning condition is simple: "You win if your answers are the same, or if they are different, depending on the question." It's a game based on the "Exclusive OR" (XOR) logic. These games are special because they are the "training wheels" of quantum physics—they are simple enough to be solved with math, but complex enough to show off quantum power.

How They Proved It: The "Sum of Squares" Trick

To prove the single player couldn't cheat and win too often, the authors used a mathematical tool called a Sum-of-Squares (SOS) certificate.

Think of the game's winning probability as a complicated recipe. The authors found a way to rewrite this recipe as a sum of squares (like $x^2 + y^2 + z^2$ ). In math, if you have a sum of squares, you know it can't be negative.

The Old Problem: In the two-player game, the "magic" of separation (Alice and Bob being in different rooms) guarantees that certain math terms cancel out perfectly.
The New Challenge: In the single-player game, there is no physical separation. The "cancellation" isn't guaranteed by physics; it has to be guaranteed by cryptography (the security of the digital safe).
The Solution: The authors showed that for XOR games, the math is "nice" enough that even without physical separation, the cryptographic locks are strong enough to force the single player to behave exactly as if they were two separate people. The "cheating" advantage is so tiny (negligible) that it's practically zero.

What This Means (The "So What?")

Because they proved this compiler works for all XOR games, they unlocked three new superpowers:

Self-Testing (The Lie Detector):
If a player wins the compiled game almost perfectly, we can now mathematically prove exactly what their quantum machine is doing inside. It's like looking at a black box and saying, "I know you are holding a specific type of spinning top, and I know exactly how it's spinning." This is called rigidity.
Parallel Repetition (The Multiplier):
If you play the game many times at once (parallel repetition), the chance of a cheater winning drops exponentially fast. This paper proves this holds true even in the compiled, single-player setting. It's like saying, "If you try to cheat on one test, you might get lucky. If you try to cheat on 100 tests at once, you will definitely get caught."
The Magic Square Game:
They applied their method to a famous puzzle called the Magic Square Game. They proved that even in this compiled version, if a player wins, their machine must contain two specific "opposing" forces (operators) that refuse to commute (they don't play nice together). This confirms the machine is truly quantum.

The Bottom Line

This paper is a bridge. It takes a complex, theoretical tool (the compiler) that was only known to work for simple cases and proves it works for a whole class of important quantum games. It confirms that we can trust a single, encrypted quantum computer to perform tasks that usually require two separate, entangled quantum computers, without losing any of the "quantum magic" in the process.

In short: They found a way to lock a quantum game inside a digital safe, force one person to play both sides, and proved that the game inside the safe is just as fair and magical as the original game played by two people in separate rooms.

Technical Summary: A Computational Tsirelson's Theorem for the Value of Compiled XOR Games

Problem Statement

Nonlocal games are fundamental to understanding entanglement and constructing quantum protocols involving multiple spatially separated devices. A central challenge in this field is translating these multi-prover results to a model where a classical verifier interacts with a single, computationally bounded quantum prover. The "non-communication" assumption between provers is difficult to enforce in practice.

To address this, Kalai et al. (STOC '23) proposed a generic compiler that transforms any $k$ -player one-round nonlocal game into a multi-round single-prover protocol using Quantum Homomorphic Encryption (QHE). While they proved the compiler preserves the classical value, the preservation of the quantum value remained an open question for general games. Natarajan and Zhang (FOCS '23) resolved this for the specific case of the CHSH game, but the question persisted for the broader class of two-player XOR games.

This paper addresses the question: Does the Kalai et al. compiler preserve the quantum value for any two-player XOR game?

Methodology

The authors employ two complementary approaches to bound the quantum value of the compiled game, both relying on the specific algebraic structure of XOR games.

1. Sum-of-Squares (SOS) Certificates and Pseudo-Expectations

The standard method for upper-bounding the quantum value of a nonlocal game involves associating a game with a polynomial $p$ and finding a Sum-of-Squares (SOS) decomposition of $\omega \mathbb{1} - p$ . In the nonlocal setting, the spatial separation of provers implies that measurement operators commute ( $[A_x, B_y] = 0$ ), allowing the construction of a "pseudo-expectation" that maps positive operators to positive numbers.

In the compiled setting, the single prover acts sequentially, so the commutativity constraint is lost. The authors overcome this by:

Constructing "Nice" SOS Certificates: Building on work by Slofstra, they show that every XOR game admits a "nice" SOS certificate for the bias polynomial. In these certificates, the terms in the decomposition are of degree 1 and depend on at most one Alice observable ( $A_x$ ).
Defining Cryptographic Pseudo-Expectations: They define a degree-2 pseudo-expectation operator $\tilde{E}_S$ induced by a compiled strategy. Due to the security of the QHE scheme, this operator satisfies the necessary positivity properties (mapping squares to non-negative values) up to a negligible error, provided the SOS certificate has the specific "nice" structure (linear dependence on $A_x$ ).
Bounding the Value: By applying this pseudo-expectation to the "nice" SOS certificate, they demonstrate that the winning probability of any compiled strategy is bounded by the optimal quantum bias of the original game, up to a negligible term.

2. Tsirelson's Correspondence and Vector Strategies

The paper also outlines an alternative proof utilizing Tsirelson's correspondence, which maps vector strategies to quantum strategies.

They apply Jensen's inequality to the Bob operators in the compiled setting.
This allows them to bound the bias of any quantum strategy for the compiled XOR game by the bias achieved by some vector strategy for the original nonlocal XOR game.
Since Tsirelson's theorem establishes that the optimal vector bias equals the optimal quantum bias for XOR games, this provides an upper bound on the compiled value.

Key Contributions and Results

1. Main Theorem: Soundness for XOR Games

The primary result (Theorem 1.1 and Theorem 3.1) establishes that for any two-player XOR game $G$ , the quantum value of the compiled game $G_{comp}$ is preserved up to a negligible error. Specifically, any polynomial-time prover wins $G_{comp}$ with probability at most $\omega^*_q(G) + \text{negl}(\lambda)$ , where $\omega^*_q(G)$ is the optimal quantum value of the original game. This resolves the open question posed by Natarajan and Zhang.

2. Self-Testing for All XOR Games

Using the SOS framework and results from Slofstra, the authors derive a self-testing statement for any compiled XOR game (Theorem 4.3).

Result: For any near-optimal strategy in a compiled XOR game, the measurement operators of the "Bob" party must approximately satisfy specific algebraic relations (the "solution algebra" of the game).
Significance: This generalizes the self-test for anticommutation found in the CHSH game to all XOR games, providing rigidity for the compiled setting.

3. Parallel Repetition Theorem

The paper establishes the first parallel repetition theorem for compiled games (Theorem 5.5).

Result: The quantum value of a compiled parallel-repeated XOR game decays perfectly exponentially with the number of repetitions, matching the behavior of the underlying nonlocal game.
Method: This is achieved by relating the parallel repetition of compiled games to the sum (modulo 2) of compiled XOR games and applying the main soundness result.

4. Self-Testing for the Magic Square Game

Although the Magic Square game is not an XOR game, the authors extend their techniques to show that its compilation is a self-test for a pair of anticommuting operators (Theorem 6.7). This mirrors the self-testing properties known in the two-prover setting.

Significance

The paper claims that its results provide a "Computational Tsirelson's Theorem," extending the exact characterization of XOR game values via Semidefinite Programming (SDP) to the compiled, single-prover setting.

Theoretical Bridge: It bridges the gap between the well-understood theory of XOR games (where Tsirelson's theorem applies) and the emerging field of compiled nonlocal games.
Rigidity in Computation: It demonstrates that the "rigidity" of quantum strategies—where near-optimal performance forces specific operator structures—persists even when spatial separation is replaced by cryptographic assumptions.
Foundation for Protocols: By confirming that the compiler preserves quantum values for the broad class of XOR games, the work supports the use of compiled games for efficient delegation of quantum computations and other cryptographic protocols where the non-communication assumption is replaced by computational hardness (specifically, the hardness of the Learning With Errors problem).

The authors note that while their techniques currently rely on the specific structure of XOR games (specifically the existence of "nice" SOS certificates), determining whether similar techniques extend to general nonlocal games remains an open direction for future research.