Quantum pseudo-telepathy

Part of a series of articles about
Quantum mechanics
${\displaystyle i\hbar {\frac {\partial }{\partial t}}|\psi (t)\rangle ={\hat {H}}|\psi (t)\rangle }$ Schrödinger equation
Introduction Glossary History
Background Classical mechanics Old quantum theory Bra–ket notation Hamiltonian Interference
Fundamentals Complementarity Decoherence Entanglement Energy level Measurement Nonlocality Quantum number State Superposition Symmetry Tunnelling Uncertainty Wave function Collapse
Experiments Bell's inequality Davisson–Germer Double-slit Elitzur–Vaidman Franck–Hertz Leggett–Garg inequality Mach–Zehnder Popper Quantum eraser Delayed-choice Schrödinger's cat Stern–Gerlach Wheeler's delayed-choice
Formulations Overview Heisenberg Interaction Matrix Phase-space Schrödinger Sum-over-histories (path integral)
Equations Dirac Klein–Gordon Pauli Rydberg Schrödinger
Interpretations Overview Bayesian Consistent histories Copenhagen de Broglie–Bohm Ensemble Hidden-variable Local Many-worlds Objective collapse Quantum logic Relational Transactional
Advanced topics Relativistic quantum mechanics Quantum field theory Quantum information science Quantum computing Quantum chaos Density matrix Scattering theory Quantum statistical mechanics Quantum machine learning
Scientists Aharonov Bell Bethe Blackett Bloch Bohm Bohr Born Bose de Broglie Compton Dirac Davisson Debye Ehrenfest Einstein Everett Fock Fermi Feynman Glauber Gutzwiller Heisenberg Hilbert Jordan Kramers Pauli Lamb Landau Laue Moseley Millikan Onnes Planck Rabi Raman Rydberg Schrödinger Simmons Sommerfeld von Neumann Weyl Wien Wigner Zeeman Zeilinger
v t

Quantum pseudo-telepathy is the fact that in certain Bayesian games with asymmetric information, players who have access to a shared physical system in an entangled quantum state, and who are able to execute strategies that are contingent upon measurements performed on the entangled physical system, are able to achieve higher expected payoffs in equilibrium than can be achieved in any mixed-strategy Nash equilibrium of the same game by players without access to the entangled quantum system.

In their 1999 paper,^[1] Gilles Brassard, Richard Cleve and Alain Tapp demonstrated that quantum pseudo-telepathy allows players in some games to achieve outcomes that would otherwise only be possible if participants were allowed to communicate during the game.

This phenomenon came to be referred to as quantum pseudo-telepathy,^[2] with the prefix pseudo referring to the fact that quantum pseudo-telepathy does not involve the exchange of information between any parties. Instead, quantum pseudo-telepathy removes the need for parties to exchange information in some circumstances.

By removing the need to engage in communication to achieve mutually advantageous outcomes in some circumstances, quantum pseudo-telepathy could be useful if some participants in a game were separated by many light years, meaning that communication between them would take many years. This would be an example of a macroscopic implication of quantum non-locality.

Quantum pseudo-telepathy is generally used as a thought experiment to demonstrate the non-local characteristics of quantum mechanics. However, quantum pseudo-telepathy is a real-world phenomenon which can be verified experimentally. It is thus an especially striking example of an experimental confirmation of Bell inequality violations.

Games of asymmetric information[]

A Bayesian game is a game in which both players have imperfect information regarding the value of certain parameters. In a Bayesian game it is sometimes the case that for at least some players, the highest expected payoff achievable in a Nash equilibrium is lower than that which could have been achieved had there not have been imperfect information. Asymmetric information is a special case of imperfect information, in which different players differ in terms of the knowledge they possess regarding the value of certain parameters.

A common assumption in classical Bayesian games of asymmetric information is that all players are unaware of the values of certain crucial parameters before the game begins. Once the game begins, different players receive information regarding the value of different parameters. However, once the game begins, players are forbidden to communicate and are consequently unable to exchange the information they collectively possess regarding the game's parameters.

This assumption has a crucial implication: even if players are able to communicate and discuss strategies before the game begins, this will not enhance any player's expected payoff, because the crucial information regarding unknown parameters has not yet been 'revealed' to the game's participants. However, if the game were to be modified, so that players were permitted to communicate after the game has begun, once each player has received some information regarding the value of some of the unknown parameters, then it may be possible for the game's participants to achieve a Nash equilibrium which is Pareto optimal to any Nash equilibrium achievable in the absence of communication.

The crucial implication of quantum telepathy is that although communication before a Bayesian game of asymmetric information begins does not result in improved equilibrium payoffs, it can be proven that in some Bayesian games, allowing players to exchange entangled qubits before the game begins can allow players to achieve a Nash equilibrium which would only otherwise be achievable if in-game communication were permitted.

The Mermin–Peres magic square game[]

When attempting to construct a 3×3 table filled with the numbers +1 and −1, such that each row has an even number of negative entries and each column an odd number of negative entries, a conflict is bound to emerge.

An example of quantum pseudo-telepathy can be observed in the Mermin–Peres magic square game.

This game features two players, Alice and Bob.

At the very start of the game, Alice and Bob are separated. After they are separated, communication between them is not possible.

The game requires that Alice fill in one row, and Bob one column, of a 3×3 table with plus and minus signs.

Before the game begins, Alice does not know which row of the table she will be required to fill in. Similarly, Bob does not know which column he will be required to fill in.

After the two players are separated, Alice is randomly assigned one row of the table and asked to fill it with plus and minus signs. Similarly, Bob is randomly assigned one column of the table and asked to fill it with plus and minus signs.

The players are subject to the following requirement: Alice must fill in her row such that there is an even number of minus signs in that row. Furthermore, Bob must fill in his column such that there is an odd number of minus signs in that column.

Crucially, Alice does not know which column Bob has been asked to fill in. Similarly, Bob does not know which row Alice has been asked to fill in. Thus, this game is a Bayesian game with asymmetric imperfect information, since neither player has complete information about the game (imperfect information) and both players differ in terms of the information that they do possess (asymmetric information).

Depending on the actions taken by participants, one of two outcomes can occur in this game. Either both players win, or both players lose.

If Alice and Bob place the same sign in the cell shared by their row and column, they win the game. If they place opposite signs, they lose the game.

Note that both players place all their plus and minus signs simultaneously, and neither player can see where the other player has placed their signs until the game is finished.

It is easy to prove that in the classic formulation of this game, there is no strategy (Nash equilibrium or otherwise) which allows the players to win the game with probability greater than 8/9. If Alice and Bob meet before the game begins and exchange information, this will not impact the game in any way; the best the players can do is still win with probability 8/9.

The reason why the game can only be won with probability 8/9 is that a perfectly consistent table does not exist: it would be self-contradictory, with the sum of the minus signs in the table being even based on row sums, and being odd when using column sums, or vice versa. As a further illustration, if they use the partial table shown in the diagram (supplemented by a −1 for Alice and a +1 for Bob in the missing square) and the challenge rows and columns are selected at random, they will win 8/9 of the time. No classical strategy exists which can beat this victory rate (with random row and column selection).

If the game was modified to allow Alice and Bob to communicate after they discover which row/column they have been assigned, then there would exist a set of strategies allowing both players to win the game with probability 1. However, if quantum pseudo-telepathy were used, then Alice and Bob could both win the game without communicating.

Pseudo-telepathic strategies[]

Use of quantum pseudo-telepathy would enable Alice and Bob to win the game 100% of the time without any communication once the game has begun.

This requires Alice and Bob to possess two pairs of particles with entangled states. These particles must have been prepared before the start of the game. One particle of each pair is held by Alice and the other by Bob. When Alice and Bob learn which column and row they must fill, each uses that information to select which measurements they should make to their particles. The result of the measurements will appear to each of them to be random (and the observed partial probability distribution of either particle will be independent of the measurement performed by the other party), so no real "communication" takes place.

However, the process of measuring the particles imposes sufficient structure on the joint probability distribution of the results of the measurement such that if Alice and Bob choose their actions based on the results of their measurement, then there will exist a set of strategies and measurements allowing the game to be won with probability 1.

Note that Alice and Bob could be light years apart from one another, and the entangled particles will still enable them to coordinate their actions sufficiently well to win the game with certainty.

Each round of this game uses up one entangled state. Playing N rounds requires that N entangled states (2N independent Bell pairs, see below) be shared in advance. This is because each round needs 2-bits of information to be measured (the third entry is determined by the first two, so measuring it isn't necessary), which destroys the entanglement. There is no way to reuse old measurements from earlier games.

The trick is for Alice and Bob to share an entangled quantum state and to use specific measurements on their components of the entangled state to derive the table entries.^{[3] [4] [5]} A suitable correlated state consists of an entangled pair of Bell states:

${\displaystyle \left|\varphi \right\rangle ={\frac {1}{\sqrt {2}}}{\bigg (}\left|+\right\rangle _{a}\otimes \left|+\right\rangle _{b}+\left|-\right\rangle _{a}\otimes \left|-\right\rangle _{b}{\bigg )}\otimes {\frac {1}{\sqrt {2}}}{\bigg (}\left|+\right\rangle _{c}\otimes \left|+\right\rangle _{d}+\left|-\right\rangle _{c}\otimes \left|-\right\rangle _{d}{\bigg )}}$

here ${\displaystyle \left|+\right\rangle }$ and ${\displaystyle \left|-\right\rangle }$ are eigenstates of the Pauli operator S_x with eigenvalues +1 and −1, respectively, whilst the subscripts a, b, c, and d identify the components of each Bell state, with a and c going to Alice, and b and d going to Bob. The symbol ${\displaystyle \otimes }$ represents a tensor product.

Observables for these components can be written as products of the Pauli spin matrices:

${\displaystyle S_{x}={\begin{bmatrix}0&1\\1&0\end{bmatrix}},S_{y}={\begin{bmatrix}0&-i\\i&0\end{bmatrix}},S_{z}={\begin{bmatrix}1&0\\0&-1\end{bmatrix}}}$

Products of these Pauli spin operators can be used to fill the 3×3 table such that each row and each column contains a mutually commuting set of observables with eigenvalues +1 and −1, and with the product of the observables in each row being the identity operator, and the product of observables in each column equating to minus the identity operator. This is a so-called Mermin–Peres magic square. It is shown in below table.

${\displaystyle +I\otimes S_{z}}$	${\displaystyle +S_{z}\otimes I}$	${\displaystyle +S_{z}\otimes S_{z}}$
${\displaystyle +S_{x}\otimes I}$	${\displaystyle +I\otimes S_{x}}$	${\displaystyle +S_{x}\otimes S_{x}}$
${\displaystyle -S_{x}\otimes S_{z}}$	${\displaystyle -S_{z}\otimes S_{x}}$	${\displaystyle +S_{y}\otimes S_{y}}$

Effectively, while it is not possible to construct a 3×3 table with entries +1 and −1 such that the product of the elements in each row equals +1 and the product of elements in each column equals −1, it is possible to do so with the richer algebraic structure based on spin matrices.

The play proceeds by having each player make one measurement on their part of the entangled state per round of play. Each of Alice's measurements will give her the values for a row, and each of Bob's measurements will give him the values for a column. It is possible to do that because all observables in a given row or column commute, so there exists a basis in which they can be measured simultaneously. For Alice's first row she needs to measure both her particles in the ${\displaystyle S_{z}}$ basis, for the second row she needs to measure them in the ${\displaystyle S_{x}}$ basis, and for the third row she needs to measure them in an entangled basis. For Bob's first column he needs to measure his first particle in the ${\displaystyle S_{x}}$ basis and the second in the ${\displaystyle S_{z}}$ basis, for second column he needs to measure his first particle in the ${\displaystyle S_{z}}$ basis and the second in the ${\displaystyle S_{x}}$ basis, and for his third column he needs to measure both his particles in a different entangled basis, the Bell basis. As long as the table above is used, the measurement results are guaranteed to always multiply out to +1 for Alice, and −1 for Bob, thus winning the round. Of course, each new round requires a new entangled state, as different rows and columns are not compatible with each other.

Coordination games[]

In classical non-cooperative game theory a coordination game is any game with multiple Nash equilibria. The literature regarding pseudo-telepathy occasionally refers to games such as the Mermin–Peres game as coordination games. On one hand, this is technically correct, because the classic variant of the game does feature multiple Nash equilibria.

However, quantum pseudo-telepathy does not provide any solution to the coordination problems which characterize coordination games. Quantum pseudo-telepathy's utility lies in resolving problems with asymmetric information in Bayesian games where communication is prohibited.

For example, implementing pseudo-telepathic strategies in the Mermin–Peres game can remove the need of Bob and Alice to exchange information. However, pseudo-telepathic strategies do not resolve coordination problems. Specifically, even after implementing pseudo-telepathic strategies, Bob and Alice will only win the game with probability one if they both coordinate their pseudo-telepathic strategies in a manner isomorphic to that described above.

Current research[]

It has been demonstrated that the above-described game is the simplest two-player game of its type in which quantum pseudo-telepathy allows a win with probability one.^[6] Other games in which quantum pseudo-telepathy occurs have been studied, including larger magic square games,^[7] graph colouring games^[8] giving rise to the notion of quantum chromatic number,^[9] and multiplayer games involving more than two participants.^[10]

Recent studies tackle the question of the robustness of the effect against noise due to imperfect measurements on the coherent quantum state.^[11] Recent work has shown an exponential enhancement in the communication cost of nonlinear distributed computation, due to entanglement, when the communication channel itself is restricted to be linear.^[12]

The Greenberger–Horne–Zeilinger Game[]

The Greenberger–Horne–Zeilinger (GHZ) game is another interesting example of quantum pseudo-telepathy. Classically, the game has 75% winning probability. However, with a quantum strategy, the players will always win with winning probability equals to 1.

There are three players, Alice, Bob, and Carol playing against a referee. The referee poses a question ${\displaystyle \in \{0,1\}}$ to each of the players. The three players each respond with an answer ${\displaystyle \in \{0,1\}}$. The referee draws three questions x, y, z uniformly from the 4 options ${\displaystyle \{(0,0,0),(1,1,0),(1,0,1),(0,1,1)\}}$. As a clarification, if question triple ${\displaystyle (0,1,1)}$ is chosen, then Alice receives bit 0, Bob receives bit 1, and Carol receives bit 1 from the referee. Based on the question bit received, Alice, Bob, and Carol each respond with an answer a, b, c also in the form of 0 or 1. The players can formulate a strategy together prior to the start of the game. However, no communication is allowed during the game itself.

The players win if ${\displaystyle a\oplus b\oplus c=x\lor y\lor z}$, where ${\displaystyle \lor }$ indicates OR condition and ${\displaystyle \oplus }$ indicates summation of answers modulo 2. In other words, the sum of three answers has to be even if ${\displaystyle x=y=z=0}$. Otherwise, the sum of answers has to be odd.

Winning condition of GHZ game

${\displaystyle x}$	${\displaystyle y}$	${\displaystyle z}$	${\displaystyle a\oplus b\oplus c}$
0	0	0	0 mod 2
1	1	0	1 mod 2
1	0	1	1 mod 2
0	1	1	1 mod 2

Classical Strategy[]

Classically, Alice, Bob, and Carol can employ a deterministic strategy that always end up with odd sum (e.g. Alice always output 1. Bob and Carol always output 0). The players win 75% of the time and only lose if the questions are ${\displaystyle (0,0,0)}$.

In fact, this is the best winning strategy classically. We can only satisfy a maximum of 3 out of 4 winning conditions. Let ${\displaystyle a_{0},a_{1}}$ be Alice's response to question 0 and 1 respectively, ${\displaystyle b_{0},b_{1}}$ be Bob's response to question 0, 1, and ${\displaystyle c_{0},c_{1}}$ be Carol's response to question 0, 1. We can write all constraints that satisfy winning conditions as

${\displaystyle a_{0}+b_{0}+c_{0}=0\mod 2}$

${\displaystyle a_{1}+b_{1}+c_{0}=1\mod 2}$

${\displaystyle a_{1}+b_{0}+c_{1}=1\mod 2}$

${\displaystyle a_{0}+b_{1}+c_{1}=1\mod 2}$

Suppose that there is a classical strategy that satisfies all four winning conditions, all four conditions hold true. Through observation, each term appears twice on the left hand side. Hence, the left side sum = 0 mod 2. However, the right side sum = 1 mod 2. The contradiction shows that all four winning conditions cannot be simultaneously satisfied.

Quantum Strategy[]

Now we have come to the interesting part where Alice, Bob, and Carol decided to adopt a quantum strategy. The three of them now share a tripartite entangled state ${\textstyle |{\psi }\rangle ={\frac {1}{2}}(|000\rangle -|011\rangle -|101\rangle -|110\rangle )}$, where they each possess a qubit to take measurement.

If question 0 is received, the player takes measurement in standard basis ${\displaystyle \{|0\rangle ,|1\rangle \}}$. If question 1 is obtained, the player takes measurement in diagonal basis ${\displaystyle \{|+\rangle ,|-\rangle \}}$. If measuring in standard basis, the player responds with answer 0 if the measurement result is 0 and answer 1 if the measurement result is 1. If measuring in diagonal basis, the player responds with answer 0 if ${\displaystyle |+\rangle }$ is measured, and answer 1 if ${\displaystyle |-\rangle }$ is measured. This quantum strategy in fact has winning probability = 1.

We will show one example where the referee chooses question triple ${\displaystyle (1,1,0)}$. Alice and Bob receive question 1 and measure in diagonal basis. Carol receives question 0 and measures in standard basis. To simulate measurement results, note that measurement in diagonal basis is equivalent to Hadamard transform followed by standard basis measurement.

${\displaystyle {\begin{aligned}&{}(H\otimes H\otimes I)|\psi \rangle \\=&{}{\frac {1}{2}}(|++0\rangle -|+-1\rangle -|-+1\rangle -|--0\rangle )\\=&{}{\frac {1}{4}}{\Big (}(|000\rangle +|010\rangle +|100\rangle +|110\rangle )-(|001\rangle +|011\rangle -|101\rangle -|111\rangle )-(|001\rangle -|011\rangle +|101\rangle -|111\rangle )-(|000\rangle -|010\rangle -|100\rangle +|110\rangle ){\Big )}\\=&{}{\frac {1}{2}}(|010\rangle +|100\rangle +|111\rangle -|001\rangle )\end{aligned}}}$

Due to quantum entanglement, the post measurement states collapse into one of the four possibilities. Regardless of the measurement outcomes, the sum of three measurement = 1 mod 2, which satisfies the winning condition.

The same procedure can be repeated for all four possible question triples ${\displaystyle \{(0,0,0),(1,0,1),(0,1,1),(1,1,0)\}}$. Regardless of the questions given by the referee, the players always win the GHZ game with the quantum magic. In the GHZ game, a quantum strategy (winning probability = 1) performs significantly better than a classical strategy (winning probability = 0.75).

This state can equivalently be solved using the GHZ state, ${\textstyle |{\psi }\rangle ={\frac {1}{\sqrt {2}}}(|000\rangle +|111\rangle )}$, hence the name. In this formulation, each player measures in the X basis ${\textstyle (|+\rangle ,|-\rangle )}$ if they receive a 0, and in the Y basis ${\textstyle ({\frac {1}{\sqrt {2}}}(|0\rangle +i|1\rangle ),{\frac {1}{\sqrt {2}}}(|0\rangle -i|1\rangle ))}$ if they receive a 1. Each player reports the result of their measurement, except for player 1 who reports the opposite of their measurement. This is unitarily equivalent to the above strategy, by each player applying some unitary to their qubit first.

See also[]

Notes[]

External links[]

• Understanding and simulating quantum pseudo-telepathy
• Quantum Pseudo-Telepathy