Quantum Parallel Repetition

Here is a kind of game. A referee sends a question to each of two players, Alice and Bob. They answer without talking to each other, and a fixed rule decides if they win. They can agree on a plan before the game starts. The value of the game is their best chance of winning, with the best possible plan.

Here is a famous example, the CHSH game. The referee sends each player a random bit, 0 or 1. Each player answers with a bit. If both questions were 1, their answers must differ to win. Otherwise their answers must match.

The simple plan is to always answer 0. This wins unless both questions were 1, so it wins 3 times out of 4. No ordinary plan does better. But players can share entangled particles, whose measurement results are linked in a way that ordinary plans cannot copy. This lets them win about 85.4% of the time, still with no messages.

Now play many rounds at once. The referee sends all the questions together, the players send all their answers together, and they must win every round. This is parallel repetition. With a value of $3 / 4$ for one round, you might expect ${(3 / 4)}^{10}$ , about 5.6%, for ten rounds.

That expectation is wrong in general. A player's answer in one round can depend on the questions in other rounds. The table shows this effect in a game by Uriel Feige.

Round	Alice says	Bob says
1	Alice, $x_{1}$	Alice, $y_{2}$
2	Bob, $x_{1}$	Bob, $y_{2}$

A plan for two rounds of Feige's game. Each cell names a player and a bit. Alice's bits are

x_{1}, x_{2}

, and Bob's bits are

y_{1}, y_{2}

In Feige's game, each player gets a random bit, then names a player and a bit. They win if they name the same player and that player's real bit. One round has value $1 / 2$ . In the plan shown, Alice always answers with $x_{1}$ , and Bob always answers with $y_{2}$ . They win both rounds exactly when $x_{1}$ and $y_{2}$ are equal, so two rounds also have value $1 / 2$ , and not $1 / 4$ .

Still, the chance must fall eventually. Ran Raz proved that, for ordinary plans, the value falls exponentially if one round has a value below 1. This means that each extra round cuts the chance by about the same fraction. For entangled players, the known results were weaker, with only a slower fall in general.

OpenAI reports a proof for entangled players and every finite two-player game. If the best chance in one round is below 100%, the chance of winning all $n$ rounds falls exponentially. The exact rate depends on the gap below 100% and on the number of possible answers. Later work improves the rate.

Repeating a test is the standard way to catch cheaters. A cheater who can pass one round with some chance must now pass every round. This result says that the method still works when the cheaters share entanglement.