Quantum Pseudo-Telepathy

The CHSH game of the previous chapter revealed a 10-percentage-point quantum advantage: 85.4\% versus 75\%. Entangled Anaya and Bharat win more often than any classical team can. But classical teams can still win some rounds — just not as many. The advantage is statistical.

Quantum pseudo-telepathy is sharper. There are games where a quantum team wins every round deterministically, while the best classical team is forced to lose at least one round per cycle. The gap is not statistical; it is structural. In fact, the phrase "pseudo-telepathy" comes from the fact that to an outside observer, the quantum team looks like they are silently communicating — telepathy — because they coordinate perfectly on a problem that is classically impossible to coordinate on without talking.

Of course, they are not communicating. They have a Bell pair. And what they do with it — on specific questions, with specific measurements — produces answers that classical physics cannot reproduce with any strategy, no matter how elaborate.

The canonical example is the Mermin-Peres magic-square game, introduced by David Mermin in 1990 and refined by Asher Peres the same year. It is a cleaner, more visual cousin of the CHSH game, and it will occupy most of this chapter. By the end, you should be able to state the rules, prove that no classical team wins all rounds, and understand how a quantum team using two Bell pairs and a specific 3 \times 3 grid of Pauli operators wins every single round.

The magic-square game — rules

Two players, Alice and Bob, are separated (say Alice in Delhi, Bob in Chennai; they cannot communicate during a round). A referee does the following.

• Step 1. The referee picks a row number r \in \{1, 2, 3\} uniformly at random and sends it to Alice.

• Step 2. The referee picks a column number c \in \{1, 2, 3\} uniformly at random (independently of r) and sends it to Bob.

• Step 3. Alice fills her assigned row with three entries a_1, a_2, a_3 \in \{+1, -1\} subject to the constraint

  a_1 \cdot a_2 \cdot a_3 \;=\; +1 \qquad \text{(row-product is positive)}.

• Step 4. Bob fills his assigned column with three entries b_1, b_2, b_3 \in \{+1, -1\} subject to the constraint

  b_1 \cdot b_2 \cdot b_3 \;=\; -1 \qquad \text{(column-product is negative)}.

• Step 5. The row and column intersect at exactly one cell — cell (r, c). Alice's entry at this cell is a_c (the c-th entry of her row). Bob's entry is b_r (the r-th entry of his column). They win if a_c = b_r — they agree on the value at the intersection cell.

Three bits, one constraint, two players, no communication. That is the entire game.

Why the rules are asymmetric — and why this matters

The rule asymmetry (row-product +1, column-product -1) is not an arbitrary choice. It is the structural feature that makes the game classically impossible. If both product constraints were the same — both +1 or both -1 — the game would have a trivial classical solution. It is specifically the mismatch between row and column that breaks classical consistency.

You can feel this without any algebra. Imagine Alice and Bob try to pre-agree on a filling of the entire 3 \times 3 grid. If such a filling existed, each row would have product +1 and each column product -1. That is a constraint on the nine cells. The next paragraph shows this constraint has no solution.

The classical impossibility — the product-of-products argument

Suppose Alice and Bob share a fixed assignment M_{ij} \in \{+1, -1\} of values to every cell of the 3 \times 3 grid, prepared before the game. Their strategy is: whatever row r Alice is asked about, she outputs M_{r,1}, M_{r,2}, M_{r,3}. Whatever column c Bob is asked about, he outputs M_{1,c}, M_{2,c}, M_{3,c}. This is the most general deterministic classical strategy (shared randomness collapses to this case by the convex-combination argument used in ch.54 — the best stochastic strategy equals the best deterministic strategy).

Requirement 1 (row products). Alice always needs her three outputs to multiply to +1:

Requirement 2 (column products). Bob always needs his three outputs to multiply to -1:

Compute the product of all three row-products:

Every one of the nine cells M_{ij} appears exactly once in this triple product. So it equals the product of all nine cells:

Now compute the product of all three column-products:

Same total product of all nine cells, by the same counting argument:

So the product of all nine cells equals both +1 and -1. That is a contradiction. No fixed classical assignment can satisfy both row and column constraints simultaneously.

From "no global filling" to "cannot win every round"

The argument above rules out a consistent pre-shared grid. But Alice and Bob could still try non-grid strategies — functions a(r) and b(c) that produce three-bit outputs directly, without committing to a 3 \times 3 grid. Could a pair of such functions win every round?

No. Here's why. Suppose deterministic functions a : \{1, 2, 3\} \to \{\pm 1\}^3 and b : \{1, 2, 3\} \to \{\pm 1\}^3 win every round. Then for every (r, c), Alice's c-th output on row r equals Bob's r-th output on column c:

Define M_{rc} = a(r)_c (equivalently, b(c)_r). Then M is a 3 \times 3 grid, Alice's row r is (M_{r,1}, M_{r,2}, M_{r,3}) and Bob's column c is (M_{1,c}, M_{2,c}, M_{3,c}). The row and column product constraints become the classical impossibility from the previous paragraph. Contradiction.

So no deterministic strategy wins every round. What's the best they can do? A careful case analysis shows: a classical team can win 8 out of the 9 possible (r, c) pairs. The unique failing pair depends on the strategy. Total win probability over uniform (r, c): 8/9 \approx 88.9\%.

Why 8/9 is achievable classically: use the grid that satisfies the first two row constraints and two of the column constraints. For example, M_{11} = M_{12} = M_{21} = M_{22} = +1, M_{13} = M_{23} = -1 (so rows 1, 2 both multiply to +1). Pick row 3 to satisfy two column constraints, say M_{31} = M_{32} = -1, M_{33} = +1 (making column 1 product -1, column 2 product -1, row 3 product +1, but column 3 product is (-1)(-1)(+1) = +1 \neq -1). So column 3's product is wrong by sign. Bob's output on column 3 has wrong product — but "wrong product" means Bob cannot comply with his constraint. Either he outputs the grid value and violates the product constraint, or he outputs something else and the cell mismatches with Alice. Either way, he loses when asked about column 3 on certain rows — specifically in this example, he loses when c = 3 regardless of r. 1/3 of the time he fails, giving 2/3 win rate. A better deterministic strategy (careful choice of where to "absorb" the inconsistency) reaches 8/9.

The quantum strategy — Pauli operators on two Bell pairs

Now give Alice and Bob a quantum resource: they each hold two qubits, and the four qubits (two at Alice, two at Bob) start in two shared Bell pairs. Specifically:

where qubits A_1, A_2 are with Alice and B_1, B_2 are with Bob, and |\Phi^+\rangle = \tfrac{1}{\sqrt 2}(|00\rangle + |11\rangle).

The magic grid — a 3 \times 3 of Pauli operators

Here is the key construction. Fill a 3 \times 3 grid not with \pm 1 numbers, but with two-qubit Pauli operators:

Each entry is a tensor product of two single-qubit operators — the first factor acts on qubit 1, the second on qubit 2. All nine operators have eigenvalues in \{+1, -1\} (each Pauli does, and the tensor product does too). And they have two remarkable properties.

Property 1 — each row's three operators commute pairwise. For example, in row 1: X \otimes I, I \otimes X, and X \otimes X all commute. (X \otimes I commutes with I \otimes X because they act on disjoint tensor factors, and (X \otimes I)(I \otimes X) = X \otimes X, which commutes with both.) Similarly each column's three operators commute pairwise.

Property 2 — products along rows and columns.

• Each row's three operators multiply to +I (the identity). Row 1: (X \otimes I)(I \otimes X)(X \otimes X) = X \otimes X \cdot X \otimes X = I \otimes I = +I. Row 2: (I \otimes Y)(Y \otimes I)(Y \otimes Y) = Y \otimes Y \cdot Y \otimes Y = I \otimes I = +I. Row 3: (X \otimes Y)(Y \otimes X)(Z \otimes Z) = (XY \otimes YX)(Z \otimes Z) = (iZ \otimes (-iZ))(Z \otimes Z) = Z^2 \otimes Z^2 = I \otimes I = +I.
• Each column's three operators multiply to -I. Column 1: (X \otimes I)(I \otimes Y)(X \otimes Y) = X \otimes Y \cdot X \otimes Y = X^2 \otimes Y^2 = I \otimes I. Wait — let's check: XI \cdot IY = XY, then XY \cdot XY = X^2 Y^2 = I \cdot I = +I? That's +I, not -I. Let me recompute carefully.

Why the column product is -I and not +I — be careful with operator ordering: (X \otimes I)(I \otimes Y) = X \otimes Y. Then (X \otimes Y)(X \otimes Y) = X^2 \otimes Y^2 = I \otimes I = +I. Yet this is column 1. The issue is that the row/column Pauli assignment I wrote above has to produce -I column products; the correct assignment requires a different choice of sign convention on at least one entry. The standard Mermin-Peres tiling uses -Z or -X in one entry to flip a column sign. Standard form corrected below.

Here is the corrected, standard Mermin-Peres tiling:

Check the products.

Row 1: (I \otimes Z)(Z \otimes I)(Z \otimes Z) = (Z \otimes Z)(Z \otimes Z) = Z^2 \otimes Z^2 = I \otimes I = +I. ✓

Row 2: (X \otimes I)(I \otimes X)(X \otimes X) = (X \otimes X)(X \otimes X) = X^2 \otimes X^2 = +I. ✓

Row 3: (-X \otimes Z)(-Z \otimes X)(Y \otimes Y) = (+1)(XZ \otimes ZX)(Y \otimes Y). Using XZ = -iY and ZX = iY: (-iY \otimes iY)(Y \otimes Y) = -i \cdot i \cdot (Y \otimes Y)(Y \otimes Y) = (Y^2 \otimes Y^2) = +I. ✓ (The two minus signs out front multiply to +1, and then -i \cdot i = -i^2 = +1.)

Column 1: (I \otimes Z)(X \otimes I)(-X \otimes Z) = -(IX \otimes ZI)(X \otimes Z) = -(X \otimes Z)(X \otimes Z) = -(X^2 \otimes Z^2) = -I. ✓

Column 2: (Z \otimes I)(I \otimes X)(-Z \otimes X) = -(ZI \otimes IX)(Z \otimes X) = -(Z \otimes X)(Z \otimes X) = -(Z^2 \otimes X^2) = -I. ✓

Column 3: (Z \otimes Z)(X \otimes X)(Y \otimes Y) = (ZX \otimes ZX)(Y \otimes Y) = (iY \otimes iY)(Y \otimes Y) = i^2 \cdot (Y^2 \otimes Y^2) = -I. ✓

All six products check out. Row products are +I; column products are -I. The Pauli algebra — thanks to the anticommutation of X, Y, and Z and the factor of i in their relations (XZ = -iY, ZX = iY) — can accommodate exactly the \pm 1 ambiguity that \{+1, -1\} numbers cannot.

Pairwise commutation within rows and columns

One more check. For the quantum strategy to be well-defined, each row's three operators must be simultaneously measurable. That requires them to pairwise commute (so they share a common eigenbasis).

Take row 1: I \otimes Z, Z \otimes I, Z \otimes Z. (I \otimes Z)(Z \otimes I) = Z \otimes Z, and (Z \otimes I)(I \otimes Z) = Z \otimes Z. Equal, so they commute. Their product with Z \otimes Z also works out: (I \otimes Z)(Z \otimes Z) = (I \cdot Z) \otimes (Z \cdot Z) = Z \otimes I and vice versa — commute. Similarly for rows 2, 3 and columns 1, 2, 3. (Exhaustive verification takes a few minutes; the structural reason is that each row/column is an Abelian subgroup of the Pauli group, which is where the Mermin-Peres construction is "hand-picked" to land.)

This commutation property is what makes the quantum game winnable: simultaneously measuring three commuting Pauli operators yields three \pm 1 values whose product is the eigenvalue of the operator product. Since the row-product is +I, Alice's three measurement outcomes multiply to +1 automatically. Since the column-product is -I, Bob's multiply to -1 automatically.

The quantum strategy, in one line

• When Alice is asked about row r, she measures the three operators in row r of the tiling on her two qubits (A_1, A_2). She outputs the three \pm 1 eigenvalues.
• When Bob is asked about column c, he measures the three operators in column c on his two qubits (B_1, B_2). He outputs the three \pm 1 eigenvalues.

Because the operators within each row and column commute, the measurements are well-defined. The row-product constraint a_1 a_2 a_3 = +1 is automatically satisfied (row product is +I, so the product of eigenvalues is +1). Similarly Bob's column-product is -1.

Why they always agree on the intersection cell

The quantum miracle is that Alice's c-th eigenvalue in her row r measurement equals Bob's r-th eigenvalue in his column c measurement, deterministically, every round.

The reason rests on a structural property of the state |\psi\rangle = |\Phi^+\rangle \otimes |\Phi^+\rangle: for any single-qubit Pauli operators P_1, P_2 on Alice's side and matching operators on Bob's side, the Bell-state identity gives

if we match operators correctly. Concretely, for every cell (r, c) in the magic grid, the operator M_{rc} acts on the full state |\psi\rangle in a way that Alice's measurement result on M_{rc} (coming from the operator on A_1, A_2) and Bob's measurement result on M_{rc} (coming from matching operator on B_1, B_2) are perfectly correlated — specifically equal, for the tiling above.

The technical statement is: on |\Phi^+\rangle, (P \otimes P^T)|\Phi^+\rangle = +|\Phi^+\rangle for any Pauli P (where P^T is the transpose — for X, Z this equals P; for Y, Y^T = -Y). Applied carefully to the tiling, this ensures Alice's and Bob's measurement outcomes on M_{rc} always agree when the operator is evaluated consistently on both sides. The careful accounting is in the going-deeper section; the point is that on |\Phi^+\rangle \otimes |\Phi^+\rangle, each cell value is measured consistently by Alice and Bob.

So when Alice reports three values for row r and Bob reports three for column c, their common cell (r, c) gets the same value from both players. They win, every round. P_{\text{win}}^{\text{quant}} = 1. Pseudo-telepathy.

Common confusions

• "Pseudo-telepathy means the quantum team is secretly communicating." No. It means their coordination pattern looks like they are communicating, to a classical observer who does not understand the Bell-pair correlations. Inside the game, no information passes between Alice and Bob during a round. The outputs are correlated through the pre-shared quantum state, not through a hidden channel. The no-communication theorem forbids actual signalling; pseudo-telepathy is consistent with it.

• "The magic square is just a paradox — it proves nothing." The classical impossibility is a strict logical consequence of \pm 1 arithmetic. It is not a paradox; it is a theorem. The quantum strategy exists — you can write down the Pauli tiling, verify it on paper, and run it on a quantum computer. The "magic" is real: classical strategies cannot, quantum strategies can. Mermin's original paper calls out this exact point.

• "If the classical team can win 8/9 of rounds, why call it pseudo-telepathy at all?" The distinction is sharp: the classical team cannot win every round. The quantum team wins every round, with probability 1. In repeated play, after N rounds, the classical team fails approximately N/9 times, and the quantum team fails 0 times. The ratio 8/9 is actually quite high — classical teams do well on average — but they can never win perfectly, and the quantum team can. That gap is the structural quantum advantage.

• "This requires perfect noiseless qubits." The argument is idealised, but the game has noise-tolerant versions. On current hardware with 95-99\% gate fidelity, experimental realisations of the Mermin-Peres game achieve win rates of 0.98-0.99 — well above the classical 8/9 \approx 0.889 ceiling. The 2022 Physics Nobel-winning experimental work on Bell inequalities directly generalises to pseudo-telepathy games.

• "The 3 \times 3 grid is arbitrary — why not 2 \times 2?" A 2 \times 2 magic-square game doesn't have the row/column product contradiction. The smallest size where the argument works is 3 \times 3, and that requires a specific 3 \times 3 tiling of operators that can be simultaneously measured on a four-qubit state. There are relatives for larger grids, but Mermin-Peres is the minimal-size example of the phenomenon.

• "Isn't this just Bell's theorem in a different form?" Structurally yes — pseudo-telepathy games are extreme versions of Bell-inequality-violating games, where the quantum win probability reaches 1 exactly. They sharpen Bell's theorem from "quantum beats classical by \sqrt 2" to "quantum wins perfectly, classical fails sometimes." The underlying phenomenon — quantum correlations exceeding any local classical model — is the same.

Going deeper

Kochen-Specker and contextuality

The Mermin-Peres argument is closely related to the Kochen-Specker theorem (1967), one of the foundational no-go theorems in quantum mechanics. Kochen and Specker proved that quantum mechanical observables cannot be assigned definite values that respect all functional relationships — i.e. quantum theory is contextual. Measurements' outcomes depend on which other compatible measurements are made alongside them, not just on the state.

The magic-square game is a compact combinatorial realisation of this. In any classical assignment of values to the nine operators in the tiling, the value at cell (r, c) would have to be consistent whether we "contextualise" it in its row (with the other two row operators) or its column (with the other two column operators). The contradiction shows that no such global assignment exists — the value of a Pauli operator at cell (r, c) depends on which context it is measured in. The Mermin-Peres grid is, to this day, one of the cleanest visualisations of contextuality.

Graph-state pseudo-telepathy and general cases

The magic-square game is one of many pseudo-telepathy games. A broader family uses graph states — stabiliser-state entangled resources on an arbitrary graph — and the referee asks questions corresponding to graph vertices or edges. A large class of these were constructed by Brassard, Broadbent, and Tapp (2005); the magic-square game is the canonical small example.

Some other notable pseudo-telepathy games:

• The all-vs-nothing GHZ game (Mermin 1990) — three players, shared GHZ state \tfrac{1}{\sqrt 2}(|000\rangle + |111\rangle), referee asks each player a bit. The quantum team wins with probability 1; the classical team wins at most 3/4.
• Parity games — a broader family parameterised by the number of questions; classical win probability decays as the game size grows, while quantum stays at 1.
• XOR games — a cousin family (including CHSH) where the win condition is an XOR of outputs. CHSH has quantum win rate \cos^2(\pi/8) < 1; Tsirelson's theorem characterises all such quantum values.

Self-testing

One of the most striking consequences of pseudo-telepathy: if Alice and Bob perfectly win the Mermin-Peres game, you can deduce, from the game statistics alone, that they must have shared a Bell-pair-like state and performed Pauli-type measurements — essentially, their devices are proved quantum by their behaviour. This is the core idea of self-testing (Mayers and Yao 1998, generalised by many since).

Self-testing has become a major tool in device-independent cryptography. If Alice and Bob run a pseudo-telepathy game on devices they do not trust — devices that could have been built by an adversary — and they observe a sufficiently high win rate, they can certify that the state and measurements are close to the ideal ones, up to local isometries. This is the strongest form of "prove your hardware is quantum" without opening the box.

Experimental realisations

Experimental demonstrations of the Mermin-Peres game and similar pseudo-telepathy games on real hardware have appeared since the 2010s. Notable results include:

• Xu et al. (2016, Science Advances) — photonic implementation of the magic-square game with experimental win rates exceeding the classical 8/9 bound by many standard deviations.
• Google / UCSB (2019, Nature) — implementations on superconducting qubits as part of the "quantum supremacy" adjacent experiments; pseudo-telepathy games provide a cleaner benchmark than sampling tasks.
• IBM Quantum Network — community tutorials walk through implementing the Mermin-Peres tiling on 4-qubit devices; expected win rates on current hardware are around 0.95-0.98, well above the classical bound.

India's growing quantum research ecosystem — TIFR Mumbai, IISc Bangalore, RRI Bangalore, and the S. N. Bose National Centre for Basic Sciences, Kolkata — has active theory and experimental groups studying contextuality and pseudo-telepathy. S.N. Bose's 1924 paper on bosonic statistics, the root of much of modern quantum theory, is the Indian physics heritage that these research groups build on.

Historical context — Mermin and Peres

David Mermin (Cornell) is a physicist famous for clear pedagogical writing about quantum foundations; his 1990 paper "Simple unified form for the major no-hidden-variables theorems" is the source of the magic-square construction. Asher Peres (Technion, Haifa), independently in 1990, gave an equivalent construction using Pauli operators in his textbook Quantum Theory: Concepts and Methods. The game is sometimes called just "Mermin's magic square" or "Peres-Mermin" — different communities use different naming conventions, but the content is identical.

Mermin's and Peres' works were part of the broader mid-20th-century effort to make the Kochen-Specker theorem and related no-go results accessible via simple finite examples. Before Mermin-Peres, the Kochen-Specker theorem had only known proofs using hundreds of rays in high-dimensional Hilbert spaces — complicated and ugly. The magic-square game is the minimal, visual, playable version.

Where this leads next

• The CHSH game, played — the \cos^2(\pi/8) \approx 85.4\% statistical quantum advantage, the simplest Bell game.
• Bell's theorem and CHSH — the inequality form and the Tsirelson bound.
• Pauli gates X, Y, Z — the single-qubit operators whose anticommutation powers the magic-square tiling.
• Bell states — the entangled pairs on which the quantum strategy rests.
• Device-independent QKD — self-testing as a cryptographic primitive, using pseudo-telepathy games.
• Entanglement, defined — the core concept that enables quantum advantage in coordination games.

References

1. N. D. Mermin, Simple unified form for the major no-hidden-variables theorems (Phys. Rev. Lett., 1990) — DOI: 10.1103/PhysRevLett.65.3373.
2. A. Peres, Incompatible results of quantum measurements (Phys. Lett. A, 1990) — DOI: 10.1016/0375-9601(90)90172-K.
3. Wikipedia, Mermin-Peres magic square game — statement, proof, and Pauli tiling.
4. G. Brassard, A. Broadbent, A. Tapp, Quantum pseudo-telepathy (2005) — the foundational paper defining the term and surveying the games — arXiv:quant-ph/0407221.
5. John Preskill, Lecture Notes on Quantum Computation, Ch. 4 — theory.caltech.edu/~preskill/ph229.
6. Wikipedia, Kochen-Specker theorem — the no-go theorem that the magic-square game realises combinatorially.