Simple Algorithm
Quantum Computing · Rydberg State · 30 min

Commuting Observables & Contextuality

Kochen–Specker and the Peres–Mermin square.

Could every observable have a definite value before you measure it, with the measurement merely revealing it? For a single qubit, yes. For two qubits, a 3×3 grid of Pauli operators makes it impossible for every state, and that impossibility turns out to be a resource for quantum computation.

What you’ll learn

  • Define non-contextual hidden-variable (NCHV) models and the constraints they must obey on commuting observables.
  • Prove the Peres–Mermin state-independent contextuality theorem and analyze the magic-square game (8/98/9 classically, 11 quantumly).
  • State the Kochen–Specker theorem and verify the 18-vector parity proof in R4\R^4.
  • Derive the non-contextual bounds of Cabello's inequality (44 versus 66) and of the KCBS inequality (22 versus 5\sqrt5).
  • Explain how contextuality acts as a resource for magic-state computation, measurement-based computation and shallow-circuit advantage.

Commuting observables and value assignments

Commuting observables can be measured together, because they share an eigenbasis, and their outcomes obey every algebraic relation that the operators obey: if [A,B]=0\comm{A}{B} = 0 and C=ABC = AB, a joint measurement always finds c=abc = ab.

A set of mutually commuting observables measured together is a context. The same observable can belong to several contexts: AA might be measured alongside BB, or alongside some CC that does not commute with BB.

For one qubit such models exist, as the Gleason lesson showed: each projector belongs to a single context. Contextuality needs at least three dimensions, where contexts overlap. Two qubits (d=4d = 4) are enough to produce a contradiction using nothing but Pauli operators.

The Peres–Mermin square

RowColumn 1Column 2Column 3Row product
1X⊗IX\otimes\idI⊗X\id\otimes XX⊗XX\otimes X+I+\id
2I⊗Z\id\otimes ZZ⊗IZ\otimes\idZ⊗ZZ\otimes Z+I+\id
3X⊗ZX\otimes ZZ⊗XZ\otimes XY⊗YY\otimes Y+I+\id
Column product+I+\id+I+\id−I-\idn/a
The observables in each row, and in each column, commute pairwise. Every row multiplies to +I+\id; the columns multiply to +I+\id, +I+\id and −I-\id. For example (X⊗Z)(Z⊗X)=(XZ)⊗(ZX)=(−iY)⊗(iY)=Y⊗Y(X\otimes Z)(Z\otimes X) = (XZ)\otimes(ZX) = (-iY)\otimes(iY) = Y\otimes Y, while (X⊗X)(Z⊗Z)=(−iY)⊗(−iY)=−Y⊗Y(X\otimes X)(Z\otimes Z) = (-iY)\otimes(-iY) = -Y\otimes Y.
DerivationNo NCHV model, whatever the state
  1. Each row and each column is a context, and its operator product is ±I\pm\id as shown.

  2. An NCHV model gives each of the nine observables one value v∈{±1}v\in\{\pm1\}, the same in its row and in its column, and the three values in each context must multiply to the sign of that context's product.

  3. ∏rows ∏cells in rowv=(+1)3=+1,∏columns ∏cells in columnv=(+1)(+1)(−1)=−1\prod_{\text{rows}}\ \prod_{\text{cells in row}} v = (+1)^3 = +1, \qquad \prod_{\text{columns}}\ \prod_{\text{cells in column}} v = (+1)(+1)(-1) = -1

    Multiply all the row constraints, then all the column constraints.

  4. Every observable appears in exactly one row and one column, so both double products equal the product of all nine values: +1=−1+1 = -1. No assignment exists, whatever quantum state is prepared (Peres 1990; Mermin 1990). ■\blacksquare

Predict before you look

With questions chosen uniformly at random, what is the best possible classical winning probability in the magic-square game, in percent?

Show the answer

88.9 %

A deterministic strategy that won all 9 question pairs would define one consistent ±1\pm1 value per cell satisfying all six parity constraints, which the Peres–Mermin argument forbids. So at least one of the 9 pairs is lost: at most 8/9≈88.9%8/9 \approx 88.9\%. This is achievable: fill the grid so that every constraint except column 3's holds, and let Bob flip one cell of column 3. Shared randomness cannot beat the best deterministic strategy.

Check your understanding

Why can quantum players win the magic-square game every time, even though no table of pre-assigned values exists?

  1. They secretly communicate through the entangled state
  2. No context-independent values exist, but jointly measuring commuting observables on ∣Φ+⟩⊗2\ket{\Phi^+}^{\otimes 2} makes the two players' results for the shared cell agree with certainty
  3. Quantum outcomes violate the parity constraints
  4. The referee's questions are not really random
Show the answer

B. No context-independent values exist, but jointly measuring commuting observables on ∣Φ+⟩⊗2\ket{\Phi^+}^{\otimes 2} makes the two players' results for the shared cell agree with certainty

The outcome for, say, X⊗ZX\otimes Z is not fixed before Alice measures her whole row. Yet because ⟨O⊗O⟩=+1\expval{O\otimes O} = +1 for every cell on ∣Φ+⟩⊗2\ket{\Phi^+}^{\otimes2}, Alice's and Bob's results for the shared cell always agree. The game converts contextuality into nonlocal correlations, without any signaling.

Kochen–Specker with vectors

Read v(u)=1v(u) = 1 as "the projector ∣u⟩ ⁣⟨u∣\dyad u would give outcome 11", and each orthonormal basis as a context. Kochen and Specker's original set had 117 vectors in R3\R^3; Peres (1991) found one with 33, and the smallest known in R3\R^3, due to Conway and Kochen, has 31. Computer-assisted searches have established lower bounds in the low-to-mid twenties. In R4\R^4, Cabello, Estebaranz and García-Alcaine (1996) found 18 vectors in 9 bases, and computer searches show that no smaller set works there.

Basisv1v_1v2v_2v3v_3v4v_4
1(0,0,0,1)(0,0,0,1)(0,0,1,0)(0,0,1,0)(1,1,0,0)(1,1,0,0)(1,1ˉ,0,0)(1,\bar1,0,0)
2(0,0,0,1)(0,0,0,1)(0,1,0,0)(0,1,0,0)(1,0,1,0)(1,0,1,0)(1,0,1ˉ,0)(1,0,\bar1,0)
3(1,1ˉ,1,1ˉ)(1,\bar1,1,\bar1)(1,1ˉ,1ˉ,1)(1,\bar1,\bar1,1)(1,1,0,0)(1,1,0,0)(0,0,1,1)(0,0,1,1)
4(1,1ˉ,1,1ˉ)(1,\bar1,1,\bar1)(1,1,1,1)(1,1,1,1)(1,0,1ˉ,0)(1,0,\bar1,0)(0,1,0,1ˉ)(0,1,0,\bar1)
5(0,0,1,0)(0,0,1,0)(0,1,0,0)(0,1,0,0)(1,0,0,1)(1,0,0,1)(1,0,0,1ˉ)(1,0,0,\bar1)
6(1,1ˉ,1ˉ,1)(1,\bar1,\bar1,1)(1,1,1,1)(1,1,1,1)(1,0,0,1ˉ)(1,0,0,\bar1)(0,1,1ˉ,0)(0,1,\bar1,0)
7(1,1,1ˉ,1)(1,1,\bar1,1)(1,1,1,1ˉ)(1,1,1,\bar1)(1,1ˉ,0,0)(1,\bar1,0,0)(0,0,1,1)(0,0,1,1)
8(1,1,1ˉ,1)(1,1,\bar1,1)(1ˉ,1,1,1)(\bar1,1,1,1)(1,0,1,0)(1,0,1,0)(0,1,0,1ˉ)(0,1,0,\bar1)
9(1,1,1,1ˉ)(1,1,1,\bar1)(1ˉ,1,1,1)(\bar1,1,1,1)(1,0,0,1)(1,0,0,1)(0,1,1ˉ,0)(0,1,\bar1,0)
The 18 vectors (unnormalized, with 1ˉ=−1\bar1 = -1) arranged in 9 orthogonal bases. Each vector appears in exactly two bases; you can check the orthogonality within each row by eye.
DerivationThe parity proof
  1. Each of the 9 bases must contain exactly one vector with v=1v = 1, so summing over the bases counts nine 1s.

  2. Each of the 18 vectors lies in exactly two of the bases, so the same sum counts every 1-valued vector twice.

  3. 9  =  ∑bases b ∑u∈bv(u)  =  2∑u∈Sv(u)9 \;=\; \sum_{\text{bases } b}\ \sum_{u\in b} v(u) \;=\; 2\sum_{u\in S} v(u)

    An odd number equals an even one, so no assignment exists. ■\blacksquare

Think first Could a similar trick work for a single qubit?

No. In C2\C^2 every ray uu belongs to exactly one basis, {u,u⊥}\{u, u^\perp\}, so "exactly one 1 per basis" is trivially satisfiable: pick one vector from each pair. This is the same loophole that defeats Gleason's theorem in d=2d=2, and it is why explicit hidden-variable models for a qubit exist.

Contextuality inequalities

The Peres–Mermin argument becomes an experimentally testable inequality (Cabello 2008). Let RiR_i be the product of the three ±1\pm1 outcomes when row ii is measured, and CjC_j likewise for column jj, each context being measured jointly, or sequentially since its observables commute.

DerivationNon-contextual bound 4, quantum value 6
  1. χ=⟨R1⟩+⟨R2⟩+⟨R3⟩+⟨C1⟩+⟨C2⟩−⟨C3⟩\chi = \expval{R_1} + \expval{R_2} + \expval{R_3} + \expval{C_1} + \expval{C_2} - \expval{C_3}

    The witness.

  2. R1R2R3 C1C2 (−C3)=−(∏9 cellsv)2=−1R_1R_2R_3\,C_1C_2\,(-C_3) = -\Big(\prod_{\text{9 cells}} v\Big)^2 = -1

    In an NCHV model each term is a product of three predetermined ±1\pm1 values, and every value appears in exactly two terms.

  3. χNCHV  ≤  5−1=4\chi_{\text{NCHV}} \;\le\; 5 - 1 = 4

    So an odd number of the six terms, and in particular at least one, equals −1-1 for every λ\lambda. Averaging over λ\lambda preserves the bound.

  4. χQM=6for every state\chi_{\text{QM}} = 6\quad\text{for every state}

    Quantum mechanically each row product is the operator +I+\id, and the column products are +I+\id, +I+\id and −I-\id.

State-dependent tests need fewer measurements. In the KCBS inequality (Klyachko, Can, Binicioğlu & Shumovsky 2008), five projectors P1,…,P5P_1,\dots,P_5 on a qutrit form a cycle with Pi⊥Pi+1P_i\perp P_{i+1} (indices mod 5). Adjacent events are exclusive, so a non-contextual model can make at most two of them true at once: ∑i⟨Pi⟩≤2\sum_i\expval{P_i} \le 2. Quantum mechanics reaches 5≈2.236\sqrt5 \approx 2.236. In general, for events with exclusivity graph GG, the non-contextual maximum is the independence number α(G)\alpha(G) and the quantum maximum is the Lovász theta number ϑ(G)\vartheta(G) (Cabello, Severini & Winter 2014); for the pentagon, α=2\alpha = 2 and ϑ=5\vartheta = \sqrt5.

Contextuality as a resource

Contextuality is not just a foundational curiosity: it marks where quantum computation leaves classical simulation behind.

  • Magic states. For qudits of odd prime dimension, contextuality with respect to stabilizer measurements is necessary for a state to promote stabilizer operations to universal computation by magic-state distillation (Howard, Wallman, Veitch & Emerson 2014). It is closely tied to negativity of the discrete Wigner function.
  • Measurement-based computing. A measurement-based computation that uses Pauli measurements and parity (XOR) processing and computes a non-linear Boolean function, such as AND, with certainty must be contextual (Raussendorf 2013).
  • Shallow circuits. Bravyi, Gosset and König (2018) proved that constant-depth quantum circuits solve a problem that constant-depth classical circuits with bounded fan-in cannot; the proof turns a nonlocal game, a cousin of the magic-square game, into a circuit lower bound.

Key takeaways

  • Commuting observables are jointly measurable. A non-contextual model must give each observable one value, respecting the operator relations within every context.
  • Peres–Mermin: nine two-qubit Paulis in six contexts produce a parity contradiction for every state. In the magic-square game this becomes 8/98/9 classically versus 11 quantumly.
  • Kochen–Specker: in d≥3d\ge3, finite vector sets admit no {0,1}\{0,1\} colorings, for example 18 vectors in R4\R^4 by a parity count. A single qubit admits non-contextual models.
  • Contextuality inequalities make this testable: Cabello's χ≤4\chi\le4 versus 66, KCBS ≤2\le2 versus 5\sqrt5, and in general α(G)\alpha(G) versus ϑ(G)\vartheta(G).
  • Contextuality is a resource for magic-state computation on qudits, measurement-based computation and shallow-circuit quantum advantage.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

In the Peres–Mermin square, which context multiplies to −I-\id?

  1. The row X⊗IX\otimes\id, I⊗X\id\otimes X, X⊗XX\otimes X
  2. The column X⊗XX\otimes X, Z⊗ZZ\otimes Z, Y⊗YY\otimes Y
  3. The row X⊗ZX\otimes Z, Z⊗XZ\otimes X, Y⊗YY\otimes Y
  4. None: every context multiplies to +I+\id
Show the answer

B. The column X⊗XX\otimes X, Z⊗ZZ\otimes Z, Y⊗YY\otimes Y

(X⊗X)(Z⊗Z)=(XZ)⊗(XZ)=(−iY)⊗(−iY)=−Y⊗Y(X\otimes X)(Z\otimes Z) = (XZ)\otimes(XZ) = (-iY)\otimes(-iY) = -Y\otimes Y, so multiplying by Y⊗YY\otimes Y gives −I-\id.

Question 2

Why does the Peres–Mermin argument rule out NCHV models for every state, rather than for one particular entangled state?

  1. It uses only operator identities among the nine observables, not the expectation values of any particular state
  2. Because every two-qubit state is entangled
  3. Because the square contains Y⊗YY\otimes Y, which is maximally entangling
  4. It doesn't: it only works for Bell states
Show the answer

A. It uses only operator identities among the nine observables, not the expectation values of any particular state

The contradiction comes from six product identities that hold as operator equations. No value assignment can respect all of them, whatever state is prepared.

Question 3

The 18-vector Kochen–Specker proof in R4\R^4 rests on which counting fact?

  1. 18 is even
  2. Each basis contains 4 vectors
  3. The vectors have entries 00 and ±1\pm1
  4. There are 9 bases, an odd number, and every vector lies in exactly 2 of them
Show the answer

D. There are 9 bases, an odd number, and every vector lies in exactly 2 of them

Counting value-1 vectors basis by basis gives 99, but each such vector is counted twice, so the total must be even. Contradiction.

Question 4

In the KCBS scenario, why can a non-contextual model reach at most ∑i⟨Pi⟩=2\sum_i\expval{P_i} = 2?

  1. Because each projector has probability at most 25\tfrac25
  2. Because a qutrit has only three dimensions
  3. Because adjacent events are exclusive, and at most two vertices of a pentagon can be chosen with no two adjacent
  4. Because quantum mechanics forbids values above 22
Show the answer

C. Because adjacent events are exclusive, and at most two vertices of a pentagon can be chosen with no two adjacent

A deterministic non-contextual assignment makes each PiP_i true or false, with no two neighbors both true. The largest such set in a 5-cycle has 2 elements, its independence number. Quantum mechanics exceeds this, reaching 5\sqrt5.

Further reading

  • S. Kochen & E. P. Specker, "The problem of hidden variables in quantum mechanics", Journal of Mathematics and Mechanics 17 (1967).
  • N. D. Mermin, "Hidden variables and the two theorems of John Bell", Reviews of Modern Physics 65 (1993).
  • A. Cabello, J. M. Estebaranz & G. García-Alcaine, "Bell–Kochen–Specker theorem: a proof with 18 vectors", Physics Letters A 212 (1996).
  • M. Howard, J. Wallman, V. Veitch & J. Emerson, "Contextuality supplies the 'magic' for quantum computation", Nature 510 (2014).
  • C. Budroni, A. Cabello, O. Gühne, M. Kleinmann & J.-Å. Larsson, "Kochen–Specker contextuality", Reviews of Modern Physics 94 (2022).