Magic Square

The game of magic square comes from a thought experiment demonstratin the non-local characteristics of quantum mechanics. It is a Bayesian game with asymmetric information: both players have incomplete information about certain parameters, and both players know different things. The game does not allow the players to communicate. We will show that while a classical round of magic square can be won only in some cases, we can devise a quantum strategy that wins every time!

Let's first look at the actual rules of the magic square game. We have two players, Alice and Bob, that work with a 3x3 grid. The contents of the grid have some constraints: the sum of each row should be even and the sum of each column should be odd.

Here, we can see that the left grid satisfies the constraint for the columns but not for the last row. In the right grid, however, all rows have even sums but the last column doesn't have an odd sum. As you might point out, it is impossible to fill a 3x3 grid that would satisfy both constraints at the same time. Luckily, Alice and Bob don't have to do that -- Alice must fill out one row and Bob must fill out one column. They win the game if the intersection of their filled in value is the same number.

(Note that many variants of this game exist: one can also fill the grid with +1/-1 or different colours. The concept of the parity constraint always remains the same.)

You might be thinking that Alice and Bob can just decide on how to fill out the grid and they can always win, easy! But they cannot communicate during the game and they only find out which row/column they must fill in when the game starts. This makes it impossible to devise a strategy that would guarantee that they always win. Even if they decide that they will always fill out their row/column according to the grid(s) below, Alice must be filling in the grid on the left while Bob must be using the grid on the right. The optimal classical strategy therefore wins in 8 out of 9 rounds.

Alice and Bob don't have to give up just yet -- they can use the power of entanglement to come up with a strategy that works 100% of the time! This requires for Alice and Bob to share two entangled pairs before they can start a round of magic square. Once the game starts and both players receive information about which row/column they're filling out, they apply three two-qubit measurements, e.g. according to the grid seen below.

For a more detailed description of why this quantum strategy works, check out these Lecture Notes on Quantum Computing (chapter 16.3).

In this application, you can convince yourself that the quantum strategy works 100% of the time by determining which rows and columns should be filled in.

In this application, you can decide which row and column should be filled in by Alice and Bob. In the Editor, you simply specify an index for Alice's row and Bob's column.

In the Results section of the Editor, you can see how Alice and Bob filled out their grid and whether the intersection really holds the same value.