Nonlocality and contextuality as resources
Fill a 3 × 3 grid with 0s and 1s so that every row has an even number of 1s and every column an odd number. Try it: it can’t be done, since the rows say the total is even and the columns say it is odd. Now turn it into a game for two players who can’t communicate, and give them an entangled pair. They win every single time. No classical pair can do better than eight times in nine. This is the Mermin–Peres magic square, and the quantum feature it exposes, contextuality, may be what makes quantum computers powerful.
On the plate: the magic-square game. Play rounds with a classical strategy or a quantum one.
A hierarchy of correlations
Entanglement (Chapter 106), steering (one party’s choice controls which set of states the other ends up with, Chapter 50) and Bell nonlocality (Chapter 51) are distinct: every nonlocal state is steerable, every steerable state entangled, but not the other way round, as noisy Werner states show. Beyond quantum mechanics there are hypothetical correlations that still forbid signalling: Sandu Popescu and Daniel Rohrlich’s 1994 “PR box” wins the CHSH game every time, , beyond Tsirelson’s . Why nature stops at is an open question. Established for the hierarchy; Debated for why.
Contextuality
Simon Kochen and Ernst Specker proved in 1967 that in three or more dimensions you cannot assign a fixed value to every observable in a way that is independent of which other compatible observables are measured with it: measurement outcomes depend on the context. Unlike Bell’s theorem, this needs no separated parties; it is a property of a single system. The Mermin–Peres square makes it concrete with nine two-qubit Pauli observables: each row and column commutes, the product of each row is , and of each column is except the last, which is . No assignment of ±1 values can satisfy all six products. Established
The game
A referee gives Alice a row and Bob a column, at random. Alice returns three bits for her row with even parity; Bob three for his column with odd parity. They win if they agree on the shared cell. (a fixed grid satisfying eight of nine constraints) or (two Bell pairs, each player measuring the Pauli observables of their row or column). . Classical tops out at 8/9; quantum wins every round, because the commuting observables in each row and column can be measured together and multiply as required. Established
Contextuality as a resource
Mark Howard, Joel Wallman, Victor Veitch and Joseph Emerson showed in 2014 that, in a standard model of fault-tolerant computing, the states that let you go beyond efficiently simulable Clifford circuits (Chapter 108) are exactly the contextual ones: contextuality is the “magic”. In 2018 Sergey Bravyi, David Gosset and Robert König proved an unconditional separation: a problem solved by constant-depth quantum circuits that constant-depth classical circuits cannot solve, using nonlocal games of this kind. And in 2020 Zhengfeng Ji and colleagues proved MIP* = RE: verifiers interrogating entangled provers can check answers to any problem whose yes-instances can be enumerated, including the halting problem, a result that also refuted a decades-old conjecture in operator algebras (Connes’ embedding conjecture). Established, as theorems.
What you now have
Entanglement, steering and nonlocality as a hierarchy, PR boxes, the Kochen–Specker theorem and the Mermin–Peres square, the magic-square game with its 8/9 classical limit, and contextuality as the resource behind quantum advantage.
· · ·
Three questions to carry with you.
And one to work out. What is the best classical winning probability in the magic-square game, as a decimal?
Sources: S. Kochen and E. P. Specker, J. Math. Mech. 17, 59 (1967). N. D. Mermin, Phys. Rev. Lett. 65, 3373 (1990); A. Peres, Phys. Lett. A 151, 107 (1990). S. Popescu and D. Rohrlich, Found. Phys. 24, 379 (1994). N. Brunner et al., Rev. Mod. Phys. 86, 419 (2014). M. Howard et al., Nature 510, 351 (2014). S. Bravyi, D. Gosset and R. König, Science 362, 308 (2018). Z. Ji et al., Commun. ACM 64(11), 131 (2021) (MIP* = RE). Checked by code: exhaustive search over all 512 grids gives at most 8 of 9 wins.