# The Mermin-Peres Magic Square Game

## by Greg Egan

I read about the Mermin-Peres Magic Square Game in a fascinating article by Philip Ball in Scientific American[1]. That article gives a great description of the general concepts, but doesn’t really delve into the specific choice of quantum measurements that make the solution work. I’d previously read about the underlying construction by Mermin[2] in a textbook by Peres[3], though it wasn’t presented there as a game, and this predated the suggestion by Brassard et al.[5] to use entanglement to provide a winning strategy.

In any case, I thought it would be fun to write up a description of the game that covers a bit more of the mathematical details. For readers who are already familiar with the mathematics of quantum spin, the article by Xu et al.[6] on their experimental results starts with a concise description of the same theoretical ideas.

## The Magic Square Game

The Magic Square Game is a game for two players. It has become a convention to call the participants in any quantum game (or cryptographic exchange, etc.) Alice and Bob, to the point that this might make some readers roll their eyes, so instead I will call the players Rowena and Colin, which should at least make them groan for a different reason. This is a team game, where Rowena and Colin aim to cooperate, to achieve a certain outcome as often as they can, earning points together rather than individual scores.

In each round of the game, the quizmaster Qaadir starts by drawing a blank 3 × 3 grid. He then picks a row number between 1 and 3 at random, which he tells Rowena, and he asks her to provide three numbers, all of them either 1 or –1, that he will write into the specified row of the grid. These three numbers are subject to the rule that when they are multiplied together, the result must be 1.

Next, Qaadir picks a column number between 1 and 3 at random, which he tells Colin, and he asks him to provide three numbers, again all either 1 or –1, that he will write into the specified column of the grid. This time, the three numbers multiplied together must come to –1.

Any choice of row and column will intersect in precisely one square of the grid, so for that square, Qaadir will be given one number by Rowena, and another by Colin. If the two numbers are identical, that counts as a win for the team. If they are different, it’s a loss.

Rowena and Colin are kept separate from each other, and they do not get to hear each other’s conversation with Qaadir, or see what is written in the grid. They can agree on any kind of strategy they like prior to the start of the game, but once the game begins they are not permitted to communicate.

Here is a round of the game where the team wins:

Rowena: 1, 1 and 1.
Colin: –1, 1 and 1.

 –1 1, 1 1 1 1

And here is a round of the game where the team loses:

Rowena: 1, –1 and –1.
Colin: 1, –1 and 1.

 1 –1 1 –1 –1, 1

Is there any strategy that Rowena and Colin can adopt that will allow them to win every single round? You might think they could just fill out a single version of the grid with suitable numbers, and each take an identical copy with them, so Rowena can simply read off any row that Qaadir asks for, and Colin can read off any column, with no possibility of them disagreeing on any of the squares. But no single 3 × 3 grid can simultaneously meet the condition that the products of the numbers in each of the three rows are all 1, which implies that the product of all nine numbers is 1, while the products of the numbers in each of the three columns are all –1, which implies that the product of all nine numbers is –1.

These conflicting demands on any shared grid mean that at least one square out of the nine must be different when Rowena supplies it as part of a row in her answer to Qaadir, compared to when Colin gives it as part of a column. It is not hard to come up with strategies that yield an 8/9 chance of winning each round, but if all Rowena and Colin can share are “classical resources” — pre-existing tables of numbers, and maybe some source of randomness like dice or coins to toss — then there is no way to guarantee that they will win 100% of the time.

## The Quantum Mechanics of Spin

A quantum system that has two possible spin states is described by a 2-dimensional complex vector space, with any specific state of the system given by a unit-length vector in that space (with the proviso that multiplying a given vector by a phase, a complex number of magnitude 1, makes no difference to the physical state it describes).

If we choose to represent the spin up and spin down states of the system with the vectors (1,0) and (0,1), then the spin measurements along three perpendicular x, y and z axes are described by the Pauli spin matrices:

σx =
 0 1 1 0
σy =
 0 -i i 0
σz =
 1 0 0 -1

These matrices will always yield a spin of +1 or –1, but if we are measuring the spin in particular physical units, we would multiply the matrices by an appropriate factor. In everything that follows, as far as we are concerned all our spins are just ±1.

What it means for a matrix M like this to describe a measurement is that for a quantum state vector ψ, the average value of the quantity M that the matrix M measures is given by:

average M = <ψ, M ψ>

where the angle brackets here denote the complex inner product:

<(a, b), (c, d)> = a*c + b*d

This is the same as the standard dot product on R2, except we take the complex conjugate of the components of the first vector. (Sometimes the inner product is defined with the complex conjugate of the second vector, rather than the first. Which one is conjugated is just a convention, and all that really matters is being consistent about the choice.)

If the quantum state vector is an eigenvector of the matrix M, with eigenvalue λ, i.e.:

M ψ = λ ψ

then the average value of the measured quantity M is:

average M = <ψ, M ψ> = <ψ, λ ψ> = λ

because ψ is a unit vector. What’s more, in this case the measurement is guaranteed to produce a definite result of λ, rather than merely an average over many repetitions. If M has two eigenvectors with different eigenvalues, say:

M ψ1 = λ1 ψ1
M ψ2 = λ2 ψ2

then the two eigenvectors ψ1 and ψ2 will be orthogonal, and the probability that the quantity M for some arbitrary quantum state vector φ will be found to take each value λ1 or λ2 will be:

P(M = λ1) = |<φ, ψ1>|2
P(M = λ2) = |<φ, ψ2>|2

For example, the Pauli spin matrix σz has eigenvectors (1,0) and (0,1) with eigenvalues ±1:

σz (1,0) = 1 (1,0)
σz (0,1) = –1 (0,1)

while the eigenvectors for the other Pauli matrices, again with eigenvalues ±1, are:

σx (1,1)/√2 = 1 (1,1)/√2
σx (–1,1)/√2 = –1 (–1,1)/√2

σy (–i,1)/√2 = 1 (–i,1)/√2
σy (i,1)/√2 = –1 (i,1)/√2

When we have a quantum system that consists of two particles, the complex vector space that describes the whole system is formed as the tensor product of the spaces that describe the individual particles. This is a space whose dimension is the product of the dimensions of the original spaces, and we form states in this space with an operation we denote with the symbol ⊗. Taking the tensor product of two vectors in 2-dimensional spaces to give a single vector in a 4-dimensional space:

(a, b) ⊗ (c, d) = (ac, ad, bc, bd)

There are more mathematically elegant ways to write this, where we give the components of the tensor product two subscripts that range over the dimensions of the original spaces, but for our current purposes this is the most concrete way to proceed: we multiply each component of the first vector by the whole of the second vector, then flatten out the result into a list of four components.

Similarly, when we measure something about the first particle with a matrix M, and another thing about the second particle with a matrix N, we can form a tensor product matrix MN that tells us how to measure the quantity MN on the whole system. We obtain the components of the new matrix by multiplying each component of the first matrix by the whole of the second matrix, and then flattening out the result into a single matrix:

 a b c d
 e f g h
=
 ae af be bf ag ah bg bh ce cf de df cg ch dg dh

## The Mermin-Peres Square

The following 3 × 3 grid, specifying nine quantum measurements that could potentially be performed on a pair of particles, was devised by David Mermin[2] in 1990:

 1 ⊗ σz σz ⊗ 1 σz ⊗ σz σx ⊗ 1 1 ⊗ σx σx ⊗ σx –σx ⊗ σz –σz ⊗ σx σy ⊗ σy

Here by 1 we mean the 2 × 2 identity matrix. As a quantum measurement, the identity matrix means “don’t do anything to the particle, and always assign the measured quantity a value of 1.” That might sound a bit weird, but it is consistent with everything else we have said about measurements, because every quantum state vector is an eigenvector of the identity matrix, with eigenvalue 1.

If all these symbols look a bit abstract to you, you might prefer the more long-winded but concrete way of writing exactly the same thing, as a grid of nine 4 × 4 matrices:

 1 0 0 0 0 -1 0 0 0 0 1 0 0 0 0 -1
 1 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 -1
 1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 1
 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0
 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0
 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0
 0 0 -1 0 0 0 0 1 -1 0 0 0 0 1 0 0
 0 -1 0 0 -1 0 0 0 0 0 0 1 0 0 1 0
 0 0 0 -1 0 0 1 0 0 1 0 0 -1 0 0 0

If we forget about the quantum mechanics for a moment and just talk purely in terms of the mathematics of these nine matrices:

• The three matrices in any one row, or in any one column, of this grid all commute with each other. That is, we can multiply any two or three of them together in any order, and the result will not be affected by the order.
• If we multiply all three matrices in any row, we always get the identity matrix.
• If we multiply all three matrices in any column, we always get the opposite of the identity matrix.
• For each of the nine matrices, all of their eigenvectors have eigenvalues of 1 or –1.

So, these matrices possess something a bit like the properties we want for the answers from Rowena and Colin for the rows and columns in the Magic Square Game, which need to multiply together to give 1 or –1 respectively. Nevertheless, they are 4 × 4 matrices, not single numbers, so how can they help?

This is where their interpretation as quantum measurements comes in. Suppose we pick a row or column of the grid, and look at the three matrices there. Because they all commute with each other, we can find four orthogonal vectors in the 4-dimensional space that are, simultaneously, eigenvectors of all three matrices at once. For example, for the first row, the standard basis vectors:

{(1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)}

are eigenvectors of all three matrices, and we can just read the four corresponding eigenvalues off the diagonals of the three matrices in turn:

{1, –1, 1, –1}
{1, 1, –1, –1}
{1, –1, –1, 1}

For the second row of matrices, the four eigenvectors are:

{½(1,1,1,1), ½(1,–1,–1,1), ½(–1,1,–1,1), ½(–1,–1,1,1)}

For every row and every column, we can find four eigenvectors like this. The full set of 24 eigenvectors has some interesting geometric properties, which will discuss in a later section.

What this means is that, in principle, we can construct a single measurement on the quantum system that tells us all three quantities measured by the three matrices in the row or column, all at once. Just how difficult this is to do experimentally is another matter, but mathematically, we can certainly construct a single matrix that corresponds to the measurement of a single number from which we can deduce the three eigenvalues of the original three matrices. For example, if we formed a matrix by adding together the first matrix, twice the second matrix, and four times the third matrix, this weighted sum of all three matrices would have eigenvalues of either {1,–3,–5,7}, for a row, or {–1,3,5,–7}, for a column, corresponding to the four triplets of eigenvalues whose products are 1 or –1 respectively. For example, for the first row in the grid, the matrix we obtained this way would have 7, –3, –5 and 1 along its diagonal, and zeroes everywhere else.

The original purpose for which Mermin constructed this set of nine measurements was to demonstrate that if quantum mechanics is true, the results of measurements are unavoidably contextual. Suppose you could say of every quantum system, such as the pair of particles in this example, that whatever set of measurements we actually performed in a particular experiment, there would always be a definite value for each individual measurement: a result that we would have obtained even if we’d done that measurement as part of a different set of measurements. Then for any particular pair of particles, there ought to be a 1 or a –1 that can rightfully be placed in each square of the 3 × 3 grid, as the corresponding measurement. We can’t actually measure all nine things at once, but under our supposition these nine numbers would exist. But then we’d have a problem: if we came along and did the measurements corresponding to any specific row or column, the three numbers we obtained would have to match the numbers from the grid ... and we know, from our discussion of the Magic Square Game, that you can’t write down nine numbers that multiply correctly for every row and every column.

Okay, but how does this help Rowena and Colin? They still can’t do the mathematically impossible and fill out a 3 × 3 grid with a fixed set of numbers that they can use to win the game.

Note that if Rowena or Colin receive a pair of particles in any quantum state, they can take the matrices corresponding to Qaadir’s instructions from Mermin’s 3 × 3 grid, and the three measurements they obtain for the row or column will always be valid, in the sense that they would all be 1 or –1, and would multiply to give the correct product. The only thing missing is making sure that Rowena’s and Colin’s measurements agree where the row and column intersect.

We can achieve that agreement by giving Rowena and Colin separate pairs of particles that are suitably entangled with each other. Specifically, we need to generate four particles in the state:

where u = (1,0) and d = (0,1), and the subscripts identify which player receives each particle. This state says that any of the four possible combinations of spin up and down for Rowena’s two particles is accompanied by the same combination for Colin’s particles.

Whenever Rowena and Colin apply the same measurement from Mermin’s grid to their respective particles in this state, they will receive the same result. In mathematical language:

(MM) ψ = ψ

whichever of the nine matrices from the grid we use for M. The entangled state ψ is an eigenvector of every one of these measurements of MRowena MColin, with eigenvalue 1, and the product of the numbers Rowena and Colin measure for the same square of the grid can only equal 1 if those numbers are equal.

So, if Rowena and Colin prepare a supply of entangled particles like this before the start of the game, and measure them according to the recipes encoded in Mermin’s grid, they can win the game 100% of the time!

We have concentrated on the theoretical quantum mechanics and linear algebra behind this strategy. To read about the experiment that succeeded in putting a version of this into practice, see the article by Philip Ball in Scientific American[1], or the paper by the experimenters themselves, Xu et al.[6].

## The 24-cell of Eigenvectors

The image above shows a 4-dimensional polytope known as a 24-cell (rotating in R4, and projected down to three dimensions). It has:

• 24 vertices
• 96 edges
• 96 triangular faces
• 24 octahedral cells.

In the image, we have split the 24 vertices into three sets of 8 and coloured them red, green, and blue. Within each single colour, these vertices are the 4 simultaneous eigenvectors of the 3 operators belonging to one of the rows of the Mermin grid, along with their opposites.

We have marked one of the 24 octahedral cells of the polytope with black edges. The centres of all 24 such cells turn out to be the simultaneous eigenvectors of the 3 operators belonging to each of the columns of the Mermin grid. The centres of the cells will lie at a different distance from the origin than the vertices, but the quantum state vector in either case is always normalised to be a unit-length vector. And when normalised, the 24 cell-centres have exactly the same geometry as the 24 vertices; they form their own 24-cell, dual to the original one.

The two 24-cells here are closely related to the appearance of the same structures in the binary octahedral group, which is a set of 48 points in R4 comprised of a 24-cell and its dual, with the points construed as quaternions. The choice of these 48 points comes from treating unit quaternions as defining rotations of three-dimensional objects:

Rr(q) = r q r–1

The points in question correspond to the 24 rotational symmetries of a cube or an octahedron (every unit quaternion r and its opposite –r produce the same rotation), while the 24 points that are the vertices of one of the 24-cells correspond to the 12 rotational symmetries of a tetrahedron formed from half the vertices of the same cube. If you haven’t encountered these ideas before, you might want to read this page I wrote on Symmetries and the 24-cell, which walks through all the details of this construction.

As well as treating a single unit quaternion as defining a rotation in three dimensions, we can treat pairs of unit quaternions as defining rotations in four dimensions:

R(r, s)(q) = r q s–1

Under that correspondence, we can obtain the same 4 × 4 matrices as we did from the Mermin grid from the quaternion pairs:

 (j, j) (i, i) (k, k) (i, k) (k, j) (j, i) (k, i) (j, k) (i, j)

The eigenvectors of these rotations are then quaternions q that are either fixed or reversed by the operation r q s–1, so that:

r q s–1 = ± q
r q = ± q s
r = ± q s q–1
Rq(s) = ± r

What this means is that any eigenvector q of the rotation due to the pair (r, s), when we treat it as a three-dimensional rotation, maps s into ± r. But since any row or column of this grid has s take on all three values from the set {i, j, k}, which, along with their opposites, are the six vertices of an octahedron, and since r in each case is from the same set, what this tells us is that the simultaneous eigenvectors of any row or column will map vertices of that octahedron to other vertices. So it will be a symmetry of the octahedron, making it an element of the binary octahedral group.

## References

[1] “Researchers Use Quantum ‘Telepathy’ to Win an ‘Impossible’ Game” by Philip Ball, Scientific American, October 25, 2022.

[2] “Simple Unified Form for the Major No-Hidden-Variables Theorems” by N. David Mermin, Physical Review Letters 65, 3373 (1990).

[3] Quantum Theory: Concepts and Methods by Asher Peres, Kluwer Academic Publishers, Dordrecht, 1993. Section 7.1.

[4] “Hidden variables and the two theorems of John Bell” by N. David Mermin, Reviews of Modern Physics 65, 803 (1993); Errata Reviews of Modern Physics 85, 919 (2013); Reviews of Modern Physics 88, 039902 (2016); Reviews of Modern Physics 89, 049901 (2017).

[5] “Quantum Pseudo-Telepathy” by Gilles Brassard, Anne Broadbent, and Alain Tapp, Foundations of Physics 35, 1877–1907 (2005).

[6] “Experimental Demonstration of Quantum Pseudotelepathy” by Jia-Min Xu, Yi-Zheng Zhen, Yu-Xiang Yang, Zi-Mo Cheng, Zhi-Cheng Ren, Kai Chen, Xi-Lin Wang, and Hui-Tian Wang, Physical Review Letters 129, 050402 (2022).

Science Notes / The Mermin-Peres Magic Square Game / created Tuesday, 1 November 2022