Nonlocal Games & Self-Testing
Certifying quantum devices from their statistics alone.
Bell's theorem says quantum correlations cannot be faked classically. Self-testing says something much stronger: essentially the only way to win the CHSH game with probability is to share a Bell pair and measure it with Pauli observables. From statistics alone you can certify what is inside a black box, and pushing this idea to its limit led to .
What you’ll learn
- Define nonlocal games and their classical, entangled and no-signalling values; compute them for CHSH, the Mermin–Peres magic square and the GHZ game.
- State the CHSH rigidity (self-testing) theorem and derive the anticommutation relations it rests on from the sum-of-squares certificate.
- Explain robust self-testing and how rigidity enables device-independent randomness, key distribution and verified delegated computation.
- Summarize and its consequences for computing entangled values, Tsirelson's problem and Connes' embedding problem.
Games as Bell tests
| Game | Rules | ||
|---|---|---|---|
| CHSH | uniform; win iff | , with one Bell pair | |
| Magic square (Mermin–Peres) | Alice gets a row, Bob a column of a grid. Alice fills her row with entries whose product is , Bob his column with entries whose product is ; they win iff they agree on the shared cell | , with two Bell pairs | |
| GHZ (three players) | uniform; win iff | , with a GHZ state: measure on input 0 and on input 1 |
Games with are called pseudo-telepathy: quantum players never lose, classical players sometimes must. In the magic square game the quantum players share two Bell pairs, with Alice holding one half of each, and each player measures the three commuting observables of their row or column of the Mermin–Peres square:
Why must every classical strategy for the magic square game lose on at least one of the nine question pairs?
- Because the questions are chosen at random
- A table agreeing on all nine cells would have total product when multiplied by rows and when multiplied by columns
- Because entries can never multiply to
- Because Alice and Bob cannot share randomness
Show the answer
B. A table agreeing on all nine cells would have total product when multiplied by rows and when multiplied by columns
A deterministic strategy fixes Alice's three rows and Bob's three columns. If they agreed on every cell they would define one table whose rows multiply to and columns to , yet both products equal the product of all nine entries. So at least one cell disagrees: , and is achievable.
Rigidity: CHSH self-tests a Bell pair
Start from the sum-of-squares certificate of Tsirelson's bound, with and .
Both squares must annihilate the state: on , Alice's observables act like fixed combinations of Bob's.
Move Alice's operator past Bob's (they commute) and apply the previous line again.
Do the same for and add: Alice's observables anticommute on the state, exactly like and . The symmetric argument shows that and act as anticommuting observables on Bob's side.
Anticommuting observables define a qubit: on the relevant subspace, and generate a Pauli algebra, and similarly for Bob. A "swap" circuit on each side, built from controlled- and controlled- gates acting on a fresh ancilla qubit, moves this virtual qubit into the ancilla. The relations above force the two ancillas into , and whatever is left over is the junk.
Robustness. Experiments reach , not . Robust self-testing provides a local isometry with . This scaling is optimal: a slightly non-maximally entangled state at distance from loses only in . Kaniewski (2016) derived an analytic bound on the extractable singlet fidelity, linear in , that becomes non-trivial (better than the fidelity available without entanglement) once .
Think first Why can no self-test ever certify the physical basis of the devices, or their exact Hilbert-space dimension?
Statistics are unchanged by a local change of basis (applied to both the state and the observables) and by appending an untouched system . Self-testing statements are therefore always "up to local isometries", which is exactly what the definition builds in.
Certification from statistics alone
Rigidity turns Bell tests into certification protocols in which the devices are untrusted black boxes:
- Randomness. If the devices reach CHSH value , nobody, not even the manufacturer, can predict an output with probability above (Pironio et al., 2010). This gives the min-entropy bound below; finite-size security proofs use entropy accumulation.
- Key distribution. Device-independent QKD bounds an eavesdropper's information using the CHSH value alone. Security against general attacks was established in the 2010s, and the first experiments followed in 2022.
- Verified delegated computation. Reichardt, Unger & Vazirani (2013) proved rigidity for sequential CHSH games: a classical verifier can force two non-communicating provers to share many Bell pairs and perform prescribed Pauli measurements, enough to command, and verify, a quantum computation.
A pair of black boxes achieves . How many bits of min-entropy per round does this bound certify?
Show the answer
0.27 bits
, so and bits per round. A moderate violation already certifies genuine randomness, but the rate falls steeply as .
Beyond CHSH. Self-testing extends far beyond one Bell pair. Every pure bipartite entangled state can be self-tested (Coladangelo, Goh & Scarani, 2017), and games such as the magic square, played in parallel, certify many Bell pairs and Pauli measurements at once. Robust parallel self-tests of this kind are the engine of the proof.
MIP* = RE
In complexity language a nonlocal game is an interactive proof: a polynomial-time verifier (the referee) questions two provers who cannot communicate. With classical provers, (Babai, Fortnow & Lund, 1991). Entangled provers might use entanglement to cheat, but rigidity also lets the verifier command them. The known power of climbed: (Ito & Vidick, 2012), (Natarajan & Wright, 2019), and then all the way.
Consequences:
- Uncomputability. Contrast XOR games, whose entangled value is an SDP, and classical values, which are computable (though NP-hard in general).
- Tsirelson's problem has a negative answer. The NPA hierarchy converges to from above, while searching over finite-dimensional strategies converges to from below. If the two values always agreed, running both searches would compute to any accuracy, contradicting . So some game has : the closure of the finite-dimensional correlations differs from the commuting-operator set .
- Connes' embedding problem (operator algebras, 1976) has a negative answer, through its known equivalence with Tsirelson's problem.
- Earlier, Slofstra (2019) showed that the set of finite-dimensional quantum correlations is not closed: some correlations are reachable only as limits of ever larger dimensions.
Key takeaways
- Nonlocal games have values : CHSH ( vs ), magic square ( vs ), GHZ ( vs ).
- CHSH is rigid: certifies and Pauli measurements up to local isometry, because the SOS equalities force .
- Robust self-testing, with errors, powers device-independent randomness, DIQKD and verified delegation with two provers.
- : approximating is undecidable, so (Tsirelson's problem) and the Connes embedding conjecture is false.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
A pair of black boxes achieves exactly. Which statement is certified by the statistics alone?
- The devices use photons
- The state is written in the lab's computational basis
- Up to a local isometry, the state contains a maximally entangled qubit pair and the observables act as , , on it
- Each side's Hilbert space has dimension exactly 2
Show the answer
C. Up to a local isometry, the state contains a maximally entangled qubit pair and the observables act as , , on it
That is the CHSH rigidity theorem. Physical platform, basis and dimension are invisible to the statistics, so a self-test can only ever certify a strategy up to local isometries and junk.
Why can no algorithm compute the entangled value of general nonlocal games, even approximately?
- Because finite-dimensional strategies cannot be enumerated
- Because reduces the halting problem to distinguishing from
- Because the NPA hierarchy does not converge
- Because is usually irrational
Show the answer
B. Because reduces the halting problem to distinguishing from
The theorem maps each Turing machine to a game whose entangled value is if it halts and at most otherwise; an approximation algorithm would decide the halting problem.
From and , with observables, which relation follows?
Show the answer
A.
Commuting Alice's operators past Bob's gives , because .
At the maximal violation , what is the bound on anyone's probability of guessing an output?
Show the answer
D.
, so the square root vanishes and the guessing probability is : each output is a perfectly random bit, certified device-independently.
Further reading
- R. Cleve, P. Høyer, B. Toner & J. Watrous, "Consequences and limits of nonlocal strategies", IEEE Conference on Computational Complexity (2004).
- D. Mayers & A. Yao, "Self testing quantum apparatus", Quantum Inf. Comput. 4, 273 (2004).
- B. W. Reichardt, F. Unger & U. Vazirani, "Classical command of quantum systems", Nature 496, 456 (2013).
- I. Šupić & J. Bowles, "Self-testing of quantum systems: a review", Quantum 4, 337 (2020).
- Z. Ji, A. Natarajan, T. Vidick, J. Wright & H. Yuen, "" (2020), arXiv:2001.04383.