Simple Algorithm
Quantum Computing · Rydberg State · 32 min

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 cos⁡2(π/8)\cos^2(\pi/8) 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 MIP∗=RE\mathsf{MIP}^*=\mathsf{RE}.

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 MIP∗=RE\mathsf{MIP}^*=\mathsf{RE} and its consequences for computing entangled values, Tsirelson's problem and Connes' embedding problem.

Games as Bell tests

GameRulesω\omegaω∗\omega^*
CHSHx,y∈{0,1}x,y\in\{0,1\} uniform; win iff a⊕b=x∧ya\oplus b=x\wedge y3/43/4cos⁡2(π/8)≈0.854\cos^2(\pi/8)\approx0.854, with one Bell pair
Magic square (Mermin–Peres)Alice gets a row, Bob a column of a 3×33\times3 grid. Alice fills her row with ±1\pm1 entries whose product is +1+1, Bob his column with entries whose product is −1-1; they win iff they agree on the shared cell8/98/911, with two Bell pairs
GHZ (three players)xyz∈{000,011,101,110}xyz\in\{000,011,101,110\} uniform; win iff a⊕b⊕c=x∨y∨za\oplus b\oplus c=x\vee y\vee z3/43/411, with a GHZ state: measure XX on input 0 and YY on input 1

Games with ω∗=1>ω\omega^*=1>\omega are called pseudo-telepathy: quantum players never lose, classical players sometimes must. In the magic square game the quantum players share two Bell pairs, ∣Φ+⟩⊗2\ket{\Phi^+}^{\otimes2} 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:

(X⊗II⊗XX⊗XI⊗ZZ⊗IZ⊗Z−X⊗Z−Z⊗XY⊗Y)\begin{pmatrix} X\otimes\id & \id\otimes X & X\otimes X\\ \id\otimes Z & Z\otimes\id & Z\otimes Z\\ -X\otimes Z & -Z\otimes X & Y\otimes Y\end{pmatrix}
The observables in each row, and in each column, commute. Each row multiplies to +I+\id and each column to −I-\id. Every entry OO satisfies OT=OO^{T}=O, so on ∣Φ+⟩⊗2\ket{\Phi^+}^{\otimes2} Alice's and Bob's values for the shared cell always agree.
Check your understanding

Why must every classical strategy for the magic square game lose on at least one of the nine question pairs?

  1. Because the questions are chosen at random
  2. A table agreeing on all nine cells would have total product +1+1 when multiplied by rows and −1-1 when multiplied by columns
  3. Because ±1\pm1 entries can never multiply to −1-1
  4. Because Alice and Bob cannot share randomness
Show the answer

B. A table agreeing on all nine cells would have total product +1+1 when multiplied by rows and −1-1 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 ±1\pm1 table whose rows multiply to +1+1 and columns to −1-1, yet both products equal the product of all nine entries. So at least one cell disagrees: ω≤8/9\omega\le8/9, and 8/98/9 is achievable.

Rigidity: CHSH self-tests a Bell pair

DerivationProof sketch: from the SOS certificate to a Pauli algebra
  1. 22−⟨ψ|B|ψ⟩=12(∥P0∣ψ⟩∥2+∥P1∣ψ⟩∥2)=02\sqrt2-\mel{\psi}{\mathcal B}{\psi}=\tfrac{1}{\sqrt2}\Big(\norm{P_0\ket\psi}^2+\norm{P_1\ket\psi}^2\Big)=0

    Start from the sum-of-squares certificate of Tsirelson's bound, with P0=A0−B0+B12P_0=A_0-\tfrac{B_0+B_1}{\sqrt2} and P1=A1−B0−B12P_1=A_1-\tfrac{B_0-B_1}{\sqrt2}.

  2. A0∣ψ⟩=B0+B12∣ψ⟩,A1∣ψ⟩=B0−B12∣ψ⟩A_0\ket\psi=\frac{B_0+B_1}{\sqrt2}\ket\psi,\qquad A_1\ket\psi=\frac{B_0-B_1}{\sqrt2}\ket\psi

    Both squares must annihilate the state: on ∣ψ⟩\ket\psi, Alice's observables act like fixed combinations of Bob's.

  3. A0A1∣ψ⟩=A0B0−B12∣ψ⟩=B0−B12A0∣ψ⟩=(B0−B1)(B0+B1)2∣ψ⟩A_0A_1\ket\psi=A_0\frac{B_0-B_1}{\sqrt2}\ket\psi=\frac{B_0-B_1}{\sqrt2}A_0\ket\psi=\frac{(B_0-B_1)(B_0+B_1)}{2}\ket\psi

    Move Alice's operator past Bob's (they commute) and apply the previous line again.

  4. {A0,A1}∣ψ⟩=(B0−B1)(B0+B1)+(B0+B1)(B0−B1)2∣ψ⟩=(B02−B12)∣ψ⟩=0\acomm{A_0}{A_1}\ket\psi=\frac{(B_0-B_1)(B_0+B_1)+(B_0+B_1)(B_0-B_1)}{2}\ket\psi=(B_0^2-B_1^2)\ket\psi=0

    Do the same for A1A0A_1A_0 and add: Alice's observables anticommute on the state, exactly like ZZ and XX. The symmetric argument shows that B0+B12\tfrac{B_0+B_1}{\sqrt2} and B0−B12\tfrac{B_0-B_1}{\sqrt2} act as anticommuting ±1\pm1 observables on Bob's side.

  5. Anticommuting ±1\pm1 observables define a qubit: on the relevant subspace, ZA:=A0Z_A:=A_0 and XA:=A1X_A:=A_1 generate a Pauli algebra, and similarly for Bob. A "swap" circuit on each side, built from controlled-ZAZ_A and controlled-XAX_A gates acting on a fresh ancilla qubit, moves this virtual qubit into the ancilla. The relations above force the two ancillas into ∣Φ+⟩\ket{\Phi^+}, and whatever is left over is the junk.

Robustness. Experiments reach 22−ε2\sqrt2-\varepsilon, not 222\sqrt2. Robust self-testing provides a local isometry with ∥Φ(∣ψ⟩)−∣Φ+⟩⊗∣junk⟩∥=O(ε)\norm{\Phi(\ket\psi)-\ket{\Phi^+}\otimes\ket{\text{junk}}}=\order{\sqrt\varepsilon}. This scaling is optimal: a slightly non-maximally entangled state at distance δ\delta from ∣Φ+⟩\ket{\Phi^+} loses only O(δ2)\order{\delta^2} in SS. Kaniewski (2016) derived an analytic bound on the extractable singlet fidelity, linear in SS, that becomes non-trivial (better than the fidelity 12\tfrac12 available without entanglement) once S≳2.11S\gtrsim2.11.

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 UA⊗UBU_A\otimes U_B (applied to both the state and the observables) and by appending an untouched system ∣junk⟩\ket{\text{junk}}. 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 SS, nobody, not even the manufacturer, can predict an output with probability above 12(1+2−S2/4)\tfrac12\big(1+\sqrt{2-S^2/4}\big) (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.
Hmin⁡ ≥ 1−log⁡2 ⁣(1+2−S2/4)bits per roundH_{\min}\ \ge\ 1-\log_2\!\Big(1+\sqrt{2-S^2/4}\Big)\quad\text{bits per round}
Zero at the classical bound S=2S=2, one full bit at S=22S=2\sqrt2.
Predict before you look

A pair of black boxes achieves S=2.5S=2.5. How many bits of min-entropy per round does this bound certify?

Show the answer

0.27 bits

S2/4=1.5625S^2/4=1.5625, so 2−1.5625≈0.661\sqrt{2-1.5625}\approx0.661 and 1−log⁡21.661≈0.271-\log_2 1.661\approx0.27 bits per round. A moderate violation already certifies genuine randomness, but the rate falls steeply as S→2S\to2.

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 MIP∗=RE\mathsf{MIP}^*=\mathsf{RE} 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, MIP=NEXP\mathsf{MIP}=\mathsf{NEXP} (Babai, Fortnow & Lund, 1991). Entangled provers might use entanglement to cheat, but rigidity also lets the verifier command them. The known power of MIP∗\mathsf{MIP}^* climbed: NEXP⊆MIP∗\mathsf{NEXP}\subseteq\mathsf{MIP}^* (Ito & Vidick, 2012), NEEXP⊆MIP∗\mathsf{NEEXP}\subseteq\mathsf{MIP}^* (Natarajan & Wright, 2019), and then all the way.

Consequences:

  1. Uncomputability. Contrast XOR games, whose entangled value is an SDP, and classical values, which are computable (though NP-hard in general).
  2. Tsirelson's problem has a negative answer. The NPA hierarchy converges to ωco\omega^{\text{co}} from above, while searching over finite-dimensional strategies converges to ω∗\omega^* from below. If the two values always agreed, running both searches would compute ω∗\omega^* to any accuracy, contradicting MIP∗=RE\mathsf{MIP}^*=\mathsf{RE}. So some game has ω∗<ωco\omega^*<\omega^{\text{co}}: the closure CqaC_{qa} of the finite-dimensional correlations differs from the commuting-operator set CqcC_{qc}.
  3. Connes' embedding problem (operator algebras, 1976) has a negative answer, through its known equivalence with Tsirelson's problem.
  4. Earlier, Slofstra (2019) showed that the set CqC_q 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 ω≤ω∗≤ωns\omega\le\omega^*\le\omega_{\text{ns}}: CHSH (3/43/4 vs 0.8540.854), magic square (8/98/9 vs 11), GHZ (3/43/4 vs 11).
  • CHSH is rigid: ⟨B⟩=22\expval{\mathcal B}=2\sqrt2 certifies ∣Φ+⟩\ket{\Phi^+} and Pauli measurements up to local isometry, because the SOS equalities force {A0,A1}∣ψ⟩=0\acomm{A_0}{A_1}\ket\psi=0.
  • Robust self-testing, with O(ε)\order{\sqrt\varepsilon} errors, powers device-independent randomness, DIQKD and verified delegation with two provers.
  • MIP∗=RE\mathsf{MIP}^*=\mathsf{RE}: approximating ω∗\omega^* is undecidable, so Cqa≠CqcC_{qa}\ne C_{qc} (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.

Question 1

A pair of black boxes achieves ⟨B⟩=22\expval{\mathcal B}=2\sqrt2 exactly. Which statement is certified by the statistics alone?

  1. The devices use photons
  2. The state is ∣Φ+⟩\ket{\Phi^+} written in the lab's computational basis
  3. Up to a local isometry, the state contains a maximally entangled qubit pair and the observables act as ZZ, XX, (Z±X)/2(Z\pm X)/\sqrt2 on it
  4. 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 ZZ, XX, (Z±X)/2(Z\pm X)/\sqrt2 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.

Question 2

Why can no algorithm compute the entangled value ω∗(G)\omega^*(G) of general nonlocal games, even approximately?

  1. Because finite-dimensional strategies cannot be enumerated
  2. Because MIP∗=RE\mathsf{MIP}^*=\mathsf{RE} reduces the halting problem to distinguishing ω∗=1\omega^*=1 from ω∗≤12\omega^*\le\tfrac12
  3. Because the NPA hierarchy does not converge
  4. Because ω∗\omega^* is usually irrational
Show the answer

B. Because MIP∗=RE\mathsf{MIP}^*=\mathsf{RE} reduces the halting problem to distinguishing ω∗=1\omega^*=1 from ω∗≤12\omega^*\le\tfrac12

The theorem maps each Turing machine to a game whose entangled value is 11 if it halts and at most 12\tfrac12 otherwise; an approximation algorithm would decide the halting problem.

Question 3

From A0∣ψ⟩=B0+B12∣ψ⟩A_0\ket\psi=\tfrac{B_0+B_1}{\sqrt2}\ket\psi and A1∣ψ⟩=B0−B12∣ψ⟩A_1\ket\psi=\tfrac{B_0-B_1}{\sqrt2}\ket\psi, with ±1\pm1 observables, which relation follows?

  1. {A0,A1}∣ψ⟩=0\acomm{A_0}{A_1}\ket\psi=0
  2. [A0,A1]∣ψ⟩=0\comm{A_0}{A_1}\ket\psi=0
  3. A0∣ψ⟩=A1∣ψ⟩A_0\ket\psi=A_1\ket\psi
  4. B0∣ψ⟩=B1∣ψ⟩B_0\ket\psi=B_1\ket\psi
Show the answer

A. {A0,A1}∣ψ⟩=0\acomm{A_0}{A_1}\ket\psi=0

Commuting Alice's operators past Bob's gives {A0,A1}∣ψ⟩=(B02−B12)∣ψ⟩=0\acomm{A_0}{A_1}\ket\psi=(B_0^2-B_1^2)\ket\psi=0, because B02=B12=IB_0^2=B_1^2=\id.

Question 4

At the maximal violation S=22S=2\sqrt2, what is the bound 12(1+2−S2/4)\tfrac12\big(1+\sqrt{2-S^2/4}\big) on anyone's probability of guessing an output?

  1. cos⁡2(π/8)\cos^2(\pi/8)
  2. 3/43/4
  3. 11
  4. 1/21/2
Show the answer

D. 1/21/2

S2/4=2S^2/4=2, so the square root vanishes and the guessing probability is 12\tfrac12: 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, "MIP∗=RE\mathsf{MIP}^*=\mathsf{RE}" (2020), arXiv:2001.04383.