⚛️ quantum physics

Guess your neighbor's input: Quantum advantage in Feige's game

This paper demonstrates that Feige's nonlocal game exhibits a quantum advantage, serves as a robust self-test for the three-dimensional maximally entangled state, and achieves perfect parallel repetition for non-signalling strategies when repeated an even number of times.

Original authors: Simon Schmidt, Sigurd A. L. Storgaard, Michael Walter, Yuming Zhao

Published 2026-02-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Simon Schmidt, Sigurd A. L. Storgaard, Michael Walter, Yuming Zhao

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 and your neighbor are playing a secret game of "Guess What I'm Thinking," but with a twist: you can't talk to each other, and you have to coordinate your answers perfectly to win a prize.

This paper is about a specific, tricky version of this game called Feige's Game. The authors, a team of quantum physicists, discovered something surprising: Quantum mechanics gives you a secret superpower to win this game more often than classical logic ever could.

Here is the breakdown of their discovery using simple analogies.

1. The Game: "The Silent Neighbor"

Imagine you and your neighbor are in separate rooms. A referee gives each of you a secret number (either a 0 or a 1).

The Goal: You must write down an answer. You can write "0", "1", or a special symbol "⊥" (let's call it "I give up").
The Winning Rule: To win, exactly one of you must say "I give up" (⊥). The other person must then correctly guess the number the "giver" received.
- Example: If you say "I give up," your neighbor must guess your number correctly. If your neighbor says "I give up," you must guess their number correctly.
- If both say "I give up," or neither does, or the guess is wrong, you lose.

The Classical Result:
If you and your neighbor are just normal humans using normal logic (classical physics), the best you can do is win 50% of the time. It's like flipping a coin; you can't do better than a 50/50 chance because you don't know what the other person is thinking.

The Quantum Result:
The authors found a way to use quantum entanglement (a spooky connection where two particles share a state) to win 56.25% of the time (specifically, 9/16).

The Analogy: Imagine you and your neighbor share a pair of "magic dice." Even though you are in different rooms, when you roll them, they don't just show random numbers; they show numbers that are perfectly coordinated in a way that normal dice cannot. By using these magic dice, you can coordinate your "I give up" signals and guesses much better than logic allows.

2. The "OR" Game Paradox

Here is the most mind-bending part of the paper.
The authors showed that Feige's Game is actually a combination of two simpler games played together. Let's call them Game A and Game B.

Game A: You try to guess your neighbor's number. (Classical win rate: 50%).
Game B: Your neighbor tries to guess your number. (Classical win rate: 50%).

Usually, if you combine two games where the best you can do is 50%, the combined game should also be 50%.
But here, the combination is magic: When you combine them into Feige's Game, the quantum win rate jumps to 56.25%.

The Metaphor: It's like having two separate keys that can't open a door. But if you tape them together in a specific way, the new "super-key" suddenly fits the lock perfectly. The whole is greater than the sum of its parts.

3. The "Fingerprint" of the Game (Self-Testing)

The paper also proves that this game is a "Self-Tester."

The Analogy: Imagine you have a magic box that claims to contain a specific, rare diamond. You can't open the box, but you play a game with it. If the box wins the game with the perfect quantum score, you know for a fact that the box must contain that exact diamond. There is no other way to win that score.
Why it matters: This is huge for technology. It means we can use this game to certify that a quantum computer is working correctly and holding the right kind of "entangled state" (the magic connection) without needing to look inside it. It's a way to verify quantum hardware just by playing a game.

4. The "Even vs. Odd" Repeating Game

Finally, the authors looked at what happens if you play this game many times in a row (Parallel Repetition).

The Pattern: If you play the game an even number of times (2, 4, 6...), the quantum advantage disappears, and everyone is back to the 50% win rate.
The Twist: If you play it an odd number of times (like 3), the rules get messy again. The classical players find a clever trick to win 31.25% of the time, but we don't yet know if the quantum players can beat that.
The Metaphor: It's like a rhythm. If you clap in pairs, the rhythm is steady and predictable. But if you clap in groups of three, the rhythm gets syncopated and weird, and we aren't sure who can keep the beat best yet.

Summary

This paper is a celebration of the weirdness of the quantum world. It shows that:

Quantum mechanics breaks the rules: You can win a coordination game better than logic allows.
Combining games creates magic: Two "boring" games can combine to create a "winning" game.
Games can be tests: We can use these games to prove that quantum devices are real and working correctly.

The authors didn't just guess this; they used heavy math and computer simulations to prove that the "magic dice" (quantum strategy) are the only way to achieve this specific win rate, making Feige's Game a new tool in the quantum toolbox.

1. Problem Statement

The paper investigates Feige's game ( $G_F$ ), a nonlocal game first introduced by Uri Feige in 1991 as a counterexample to the parallel repetition conjecture. The game involves two players, Alice and Bob, who receive binary inputs ( $x, y \in \{0, 1\}$ ) and must output answers from the set $\{0, 1, \perp\}$ .

Winning Condition: Exactly one player must output $\perp$ $⊥$ , and the other player must output the input received by the player who chose $\perp$ $⊥$ .
- Formally: $V(a,b,x,y) = 1$ if $(a,b) = (\perp, x)$ or $(a,b) = (y, \perp)$ .
The Conjecture: Prior to this work, it was conjectured (e.g., by Yue, 2016) that Feige's game possesses no quantum advantage, meaning the quantum value $\omega_q(G_F)$ equals the classical value $\omega_c(G_F)$ . This was considered plausible because other "guess your neighbor's input" variants lack quantum advantage.
The Gap: While Feige's game was known to have a classical value of $1/2$ that does not decrease under 2-fold parallel repetition, the exact quantum value and the existence of a quantum advantage remained unproven.

2. Methodology

The authors employ a combination of constructive quantum strategies, algebraic geometry (Sum-of-Squares decompositions), and operator algebra theory to analyze the game.

Quantum Strategy Construction:
- The authors construct an explicit quantum strategy using a maximally entangled state in dimension 3: $|\psi_3\rangle = \frac{1}{\sqrt{3}}\sum_{i=0}^2 |i\rangle|i\rangle$ .
- They utilize operators acting on $\mathbb{C}^3 \cong \mathbb{C}^2 \oplus \mathbb{C}$ , specifically $\tilde{Z} = Z \oplus 1$ and $\tilde{X} = X \oplus 1$ (where $X, Z$ are Pauli matrices).
- The strategy relies on a specific basis $\{|\tilde{0}\rangle, |\tilde{1}\rangle, |\perp\rangle\}$ derived from the commutation properties of $\tilde{Z}$ and $\tilde{X}\tilde{Z}\tilde{X}$ .
Upper Bound via Sum-of-Squares (SOS):
- To prove optimality, the authors associate a "game polynomial" $\beta$ with the winning probability.
- They use a method inspired by the NPA hierarchy to find a Sum-of-Squares decomposition: $V^* Y V = \frac{9}{16}I - \beta$ , where $Y$ is a positive definite matrix and $V$ is a vector of polynomials in the measurement operators.
- This decomposition proves that $\omega_q(G_F) \leq 9/16$ . The matrix $Y$ and vector $V$ were computed numerically and then rounded to exact rational values.
Self-Testing via Game Algebras:
- The paper utilizes the operator-algebraic framework for self-testing (based on Zhang, 2024).
- They define a "determining pair" $(\Gamma, R)$ derived from the SOS decomposition.
- They analyze the associated game algebra $C^*(G_F) = \mathcal{A}_{PV M} / \langle R \rangle$ . They prove this algebra is isomorphic to the full matrix algebra $M_3$ , which implies the existence of a unique irreducible representation (up to unitary equivalence).
Parallel Repetition Analysis:
- The authors analyze the $n$ -fold parallel repetition $G_F^{\times n}$ for classical, quantum, and non-signalling strategies, utilizing combinatorial arguments and non-signalling constraints.

3. Key Contributions and Results

A. Quantum Advantage Proven

The primary result is the disproof of the conjecture that Feige's game has no quantum advantage.

Classical Value: $\omega_c(G_F) = 1/2$ .
Quantum Value: $\omega_q(G_F) = 9/16$ .
Non-Signalling Value: $\omega_{ns}(G_F) = 2/3$ .
Significance: This is the first proof of quantum advantage for Feige's game. The optimal strategy requires a 3-dimensional Hilbert space and the maximally entangled state $|\psi_3\rangle$ .

B. Robust Self-Testing

The paper proves that Feige's game is a robust self-test for the 3-dimensional maximally entangled state and the specific measurement operators used in the optimal strategy.

Mechanism: The game algebra $C^*(G_F)$ has a unique irreducible representation.
Algebraic Structure: The relations derived from the SOS decomposition define a specific algebra of projections that generalizes Mutually Unbiased Measurements (MUMs). The authors show that for the specific stochastic matrix $\nu$ arising in this game, the unitary connecting the bases is unique up to equivalence.

C. The "OR"-Game Decomposition

The authors demonstrate that Feige's game can be decomposed as the logical "OR" of two simpler games ( $G_1$ and $G_2$ ):

$G_1$ : Alice guesses Bob's input; Bob always outputs $\perp$ .
$G_2$ : Bob guesses Alice's input; Alice always outputs $\perp$ .
Result: $\omega_q(G_F) = 9/16$ , while $\max(\omega_q(G_1), \omega_q(G_2)) = 1/2$ .
Implication: This provides a counterexample to the intuition that the quantum value of an "OR"-game is the maximum of its components. It shows that quantum resources can exploit the structure of the "OR" combination to achieve a strictly higher value than the individual games.

D. Parallel Repetition Behavior

The paper provides a comprehensive table of values for the $n$ -fold parallel repetition ( $G_F^{\times n}$ ):

Even $n$ ( $n=2m$ ): The classical, quantum, and non-signalling values all converge to $1/2^m = 1/2^{n/2}$ . This confirms Feige's original observation that the value does not decay for $n=2$ (it stays at $1/2$ ).
Odd $n$ ( $n=3$ ):
- Classical value: $5/16$ .
- Non-signalling value: $1/3$ .
- Quantum value: Unknown (open question).
- Surprise: The classical value ( $5/16$ ) is strictly greater than the product of the optimal quantum strategy for $n=1$ and the optimal classical strategy for $n=2$ ( $9/16 \times 1/2 = 9/32$ ). This indicates that the optimal classical strategy for $n=3$ is non-trivial and cannot be simply constructed by repeating the $n=1$ and $n=2$ strategies.

4. Significance

Resolution of a Long-Standing Open Problem: The paper definitively settles the question of whether Feige's game exhibits quantum advantage, showing that it does, contrary to previous conjectures.
Minimal Self-Test: It identifies Feige's game as the smallest known nonlocal game (2 questions, 3 answers per player) that self-tests the 3-dimensional maximally entangled state $|\psi_3\rangle$ . This is significant for device-independent quantum certification.
New Algebraic Insights: The work connects nonlocal games to the representation theory of C*-algebras generated by projections with specific transition probabilities (generalized MUMs), providing new tools for analyzing self-testing.
Complexity of Parallel Repetition: The results highlight the complex behavior of parallel repetition, particularly the divergence between classical and non-signalling values for odd repetitions and the existence of non-trivial classical strategies that outperform simple product strategies.

In summary, this paper transforms Feige's game from a historical counterexample in parallel repetition into a modern benchmark for quantum advantage, self-testing, and the study of nonlocal correlations.