Tag Archives: #game

What Is Quantum Pseudo Telepathy? (Quantum)

Quantum pseudo-telepathy is a phenomenon in quantum game theory resulting in anomalously high success rates in coordination games between separated players. These high success rates would require communication between the players in a purely classical (non-quantum) world; however, the game is set up such that during the game, communication is physically impossible. This means that for quantum pseudo-telepathy to occur, prior to the game the participants need to share a physical system in an entangled quantum state, and during the game have to execute measurements on this entangled state as part of their game strategy. Games in which the application of such a quantum strategy leads to pseudo-telepathy are also referred to as quantum non-locality games.

In their 1999 paper, Gilles Brassard, Richard Cleve and Alain Tapp demonstrated that winning quantum strategies can exist in simple games for which in the absence of quantum entanglement a winning strategy can result only if the participants were allowed to communicate. The term quantum pseudo-telepathy was later introduced for this phenomenon. The prefix ‘pseudo’ is appropriate, as the quantum non-locality effects that are at the heart of the phenomenon do not allow any transfer of information, but rather eliminate the need to exchange information between the players for achieving a mutual win in the game.

The phenomenon of quantum pseudo-telepathy is mostly used as a powerful and explicit thought experiment of the non-local characteristics of quantum mechanics. Yet, the effect is real and subject to experimental verification, as demonstrated by the experimental confirmation of the violation of the Bell inequalities.

An example of quantum pseudo-telepathy can be observed in the following two-player coordination game called the Mermin-Peres magic square game. In this game each player is assigning 0s and 1s to cells on a 3×3 board while trying to satisfy some parity constraints.

Craig Gidney find the Mermin-Peres magic square game a bit difficult to explain, so he tweaked it a bit. The resulting game is mathematically equivalent, but hopefully easier to grok. He described rules as follows:

• There’s a 3×3 grid, and two players (Alice and Bob).
• Alice and Bob each get two tokens, and are isolated from each other.
• A referee picks a row from the grid, and tells it to Alice.
• A referee picks a column from the grid, and tells it to Bob.
• Alice can either cover two cells of the indicated row with her tokens, or place no tokens.
• Bob has a similar choice: place no tokens, or cover two cells of the indicated column.
• They win if the cell common to the indicated row and column ends up covered by exactly one token.

Let’s go through a run of the game. Suppose the referee(s) pick the top row and the right column. By herself, Alice is told the row and decides not to use her tokens. By himself, Bob is told the column, decides to use his tokens, and places one in the top row (of the right column) and one in the bottom row. They then get together and compare. The top right cell is the one they have in common. Alice didn’t place a token on it, but Bob did, so there’s exactly one token in the common cell. They won!

The following diagram shows some examples of game outcomes, where the players either won, lost, or failed to follow the rules. The blue B tokens belong to Bob, and the green A tokens belong to Alice. When player chose to not use their tokens, the tokens are shown next to the board:

You can check that the diagram of outcomes makes sense, given the rules.

The above game has no consistently-winning strategy, if you’re limited to classical physics. Basically, the problem is that the number of placed tokens must be even whereas the total number of cells is odd. As a result, Alice and Bob can’t agree on a non-overlapping covering. They’ll end up expecting to win at most 8/9 games on average.

However, if you have access to quantum mechanics, you can win 100% of the time instead of only ~88% of the time.


There Are More Games Of Chess Possible Than Atoms In The Universe (Maths)

To anyone who has ever complained that a game of chess is boring, we can at least guarantee you this: Every game you play will be different. How do we know? Well, it’s estimated that there are more possible iterations of a game of chess than there are atoms in the known universe. In fact, the number of possible moves is so vast that no one has ever been able to calculate it exactly.

In the 1950s, mathematician Claude Shannon wrote a paper about how one could program a computer to play chess. In it, he made a quick calculation to determine how many different games of chess were possible, and came up with the number 10^120. This is a very, very large number — the number of atoms in the observable universe, by comparison, is only estimated to be around 10^80.

Shannon’s number came from a rough calculation that used averages instead of exact figures. It assumed that at any point in the game you’d have an average of 30 legal moves, for example, and that every game has an average of 80 total moves. But that’s not how chess works. You have many fewer legal moves at the beginning of a game than the end, and games can go much shorter or longer than 80 moves.

There are other complications as well: even if you have 30 possible moves, only a few will make sense strategically. This is why it’s such a challenge to calculate the number of possible games of chess, and why to this day, no one has landed on an exact figure.


References: (1) https://www.popsci.com/science/article/2010-12/fyi-how-many-different-ways-can-chess-game-unfold/ (2) https://www.scientificamerican.com/article/claude-e-shannon-founder/