Quantum Games: when the players enjoy entanglement

Game Theory is a quite recent field of science, recognized as an important tool in many disciplines, coming with various applications, from biology to economics, as well as in engineering and mathematics [I1, I2].

These games became even more interesting when they were mixed with Quantum Information Theory (QIT), leading to a brand new field: Quantum Game Theory [I3]. This field aims to introduce the formalisms present in
QIT for the development of new strategies and new games, the performance of which would be based on the use of superposition
and entanglement as a factor for improving results.

In this medium article, we propose to explore two quantum games, their principles, and the classical strategies associated and to have a closer look at how moving to the quantum setup can impact the performance of the players.

CHSH game

The CHSH game, also known as Bell (inequality) game, is one of the most famous quantum games, and it is probably the first that one would learn in Quantum Game Theory. It is a two-party game designed to test the concept of local realism in physics. It was first proposed by John Clauser, Michael Horne, Abhay Shimony, and Richard Holt in 1969 [C1] as a way to experimentally test whether certain predictions made by quantum mechanics are true.

Principle of the game

Karla and Marta met at the laboratory and decided to play a game during lunchtime. They asked their colleague Henri to help them select a fun game. Since he studied non-locality and contextuality (see his latest article on that topic just below) in his Ph.D., he likes sometimes to play quantum games, and he proposed the CHSH game.

https://medium.com/colibritd-quantum/contextuality-in-quantum-computing-7815f25a1e19

The game is composed of three main participants: the referee Henri (H), and two players Karla (K) and Marta (M). K and M are not allowed to communicate during the game.

The referee H sends a binary question to each player: K receives a question x, M a question y, with x,y ∈ {0,1}. Then, each player has to provide a binary answer in order to satisfy a specific equation. K will send back a bit k to H, and M a bit m, without knowing what the other player decided to play.

For winning the game, the questions (x,y) and the answers (k,m) must satisfy the following equation:

K and M don’t know in advance what question H will provide. The core of the game is, thus, for K and M to find a strategy (agreed upon before playing the game) that maximizes the probability of winning.

Best classical strategies

One can imagine many ways for K and M to agree in advance on how to answer depending on their respective question. But none of the classical strategies can allow them to win the game with probability 1.

To see that, let us denote by k(x) and m(y) the respective answers of K and M to their questions x and y. Winning the game is equivalent to finding a deterministic strategy, an assignment to k(0), k(1), m(0), and m(1) that would always satisfy the equation. In other terms, it will be equivalent to solving the following equations:

One can show that this system doesn’t have a solution. To keep it simple, if we sum (modulo 2, ⊕︀) these equations, we can deduce the following one:

This leads to the trivially false equation 0 = 1, showing that the system has no solution. However, if we remove one equation, we can find a winning strategy.

This can be understood in another way: the maximum probability that players can reach using a classical strategy is 3/4 = 75%. One can find several strategies that could achieve this performance, and the easiest one is probably to always answer ‘0’, whatever the question is. In other terms:

With this strategy, the players only fail when they both receive the question ‘1’.

The quantum strategy

After playing several rounds with classical strategies, Karla and Marta got bored and wanted to improve their mutual performance. They quickly returned to their laboratory and prepared a Bell pair: a two-qubit entangled state (see our introduction to quantum entanglement below). Each of them takes one of the pairs of particles, and they come back to Henri to play again.

https://medium.com/colibritd-quantum/quantum-entanglement-how-to-classify-it-df6a7777d4c7

Before arriving, Karla and Marta agreed on a specific quantum strategy.

1. If K receives the question ‘0’, she has to measure her qubit in the computational basis (Z-basis) {|0⟩, |1⟩}. If she measures the state |0⟩, she answers k = 0. Otherwise, she answers k = 1 to H.
2. If K receives the question ‘1’, she must measure her qubit in the Hadamard basis (X-basis) {|+⟩, | — ⟩}. If she measures the state |+⟩, she answers k = 0. If the state | — ⟩ is measured, she returns k = 1.
3. If M receives the question ‘0’, she has to measure her qubit in the basis {|Φ₀⟩, |Φ₁⟩}, which direction in the Bloch sphere is between the one of the Z and X basis, which corresponds to a rotation of π/4 of the computational basis. If she measures the state |Φᵢ⟩, she answers k = i.
4. If M receives the question ‘1’, she has to measure her qubit in the basis {|δ₀⟩, |δ₁⟩}, which corresponds to a rotation of 3π/4 of the computational basis. If she measures the state |δᵢ⟩, she answers k = i.

We detail below the expression of these basis states :

We will not detail the whole explanation of how to compute the probability of winning for Karla and Marta using this quantum strategy [C2], but we will rather try to give some elements of answer for the case (x, y) = (0, 0). We just recall that one can rewrite the state |0⟩ and |1⟩ in the following manner:

In that case, for K and M to win, they need to provide the same answer to H. Let us suppose, for simplicity, that K measures her qubit first. She received the question ‘0’, so she will measure her qubit in the computational basis. She has half probability to get |0⟩ or |1⟩.

1. If K measured |0⟩, she will answer ‘0’, and M will have to do the same. Since K and M share an entangled state, immediately M has her qubit in the state |0⟩, but she still did not measure it. For her to answer ‘0’ on that case, she will have to measure the state |Φ₀⟩. The probability that she measures it is equal to |cos(π/8)|².
2. If K measured |1⟩, she will answer ‘1’, and M will have to do the same. M has her qubit in the state |1⟩, and she will have to measure the state |Φ₁⟩. The probability that she measures it is thus also equal to |cos(π/8)|².

Therefore, if we combine both cases, the probability of winning for them will be equal to |cos(π/8)|². One can compute the other combinations of questions (x, y), and use the equality |sin(3π/8)|² = |cos(π/8)|² to deduce the overall probability of gain.

At the end of the day, K and M have a probability of |cos(π/8)|² = 85.36% of winning the game if they leverage this quantum strategy, based on the sharing of an entangled state. This provides a clear advantage over the best classical strategy. One can show that no other quantum strategy can provide better performance than the one presented here (they can be worse or equivalent).

Minority Game

The Minority Game is based on the El Farol bar problem. This problem is a well-known problem in game theory, created in 1994 by W. Brian Arthur [M1], and inspired by a bar in Santa Fe (New Mexico). The same problem was also formulated and dynamically solved six years earlier [M2]. We first present a simplified instance of the game with four players, discuss the best classical strategy, and then introduce the quantum strategy that provides an advantage.

Principle of the game

We propose to introduce the game using an equivalent but original setup with four players. We want to stress that the game can be generalized to any number of players, where the rules and strategies will differ from the four-player setup.

Laurent, Jonas, Nadia, and Hacène have received a unique ticket to attend a conference, given by John Bell, taking place near Niagara falls. They struggle to decide which one will go, as they are all huge fans of the physicist. They agree to play the Minority Game to decide who will go there.

Each of them has two cards, labeled ‘0’ and ‘1’. They have to choose one card and play it: the person that is in minority wins the game. If everybody plays the same card, then there is no winner. If half of them play a card, and the other half plays the other card, again there is no winner. The only way to win, in the case of four players, is to be the only player to play a given card.

Usually, this game is played over several rounds. Here, we considered a unique round to decide which one will win the ticket. Therefore, the goal for the players will be to find the best strategy to maximize their probability of winning. This is what we explore in the following subsections.

Classical strategies

The first observation we can make is that if all the players apply the same deterministic strategy, none of them can win the game. In fact, if the strategy suggests to play ‘0’, then all players will have the same card, and no minority is existing.

In Game Theory, one possible alternative, when all deterministic strategies are losing, is to consider mixed strategies. The principle is to associate with each card a probability to be chosen. If all players implement the same mixed strategy (have the same probability to play the card ‘0’ for instance), one can show that there exists a unique Nash Equilibrium. In a general setting of the Minority game, this probability would depend for instance on the number N of players and the threshold under which it is a minority.

In our case, players have no better choice than to randomly and uniformly choose between cards ‘0’ or ‘1’. If we list all possible responses for the 4 players (2⁴ = 16 in total) and count the number of cases where a given player is a winner, we notice that it only happens in 2/16 = 1/8 = 12.5% of the cases. Furthermore, in half of the cases, no one can win because either all players played the same card, or two cards ‘0’ and two cards ‘1’.

However, if we move to the quantum setup of the game, the players can expect to increase their probability of gain.

The quantum strategy

In this section, we explain how one could translate this game to play it in a quantum fashion and what can a quantum strategy bring in terms of gain. The formalism used to define the quantum version of the Minority Game is common in Quantum Game Theory (Quantum Prisoner’s Dilemma [M3] is defined in the same way, for instance), originating from the work of Benjamin & Hayden [M4].

The four players start by preparing an entangled state, namely the four qubit state |GHZ₄⟩, and each of them keeps a particle composing the state.

For each player, applying a strategy will consist in applying a unitary gate to the qubit they possess. After that, they measure their qubit in the computational basis (Z-basis). If they measure ‘0’ they play the card ‘0’, or play the card ‘1’ otherwise.

For example, one possible strategy S for one player could be expressed as shown in the equation below:

If we suppose that every player applies strategy S, after the application of the gate on each qubit, the players will share the following state:

One can first observe that we don’t have all the possible basis states appearing in the expression of the shared state, but only half of them. Among these 8 states, two are optimal for each player, which results in a probability of winning for each player of 2/8 = 1/4 = 25%, which is the double of the maximum performance achievable with a classical strategy.

In addition, the strategy eliminates all states that do not result in a gain for either player. Furthermore, when all players use strategy S, one can show that a Nash equilibrium is achieved. In other words, if one player decides to change his strategy unilaterally, he will not be able to improve his results, regardless of the choice of the unitary.

At ColibrITD

We believe that Quantum Computing and Quantum Information Processing have the potential to improve and enhance many computations and protocols used in industry and research.

At ColibrITD, we explore how these quantum games, and the advantage they can provide, could be applied in real-world problems. We believe that introducing quantum strategies in some setups could improve the performance of many systems, from economy, to resource allocation, including energy management.

References

[I1] : Wikipedia contributors. “Game theory.” Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 3 Jan. 2023. Web. 18 Jan. 2023.
[I2] : An introduction to game theory, Martin J. Osborne, Oxford University Press, New York et ©2004.
[I3] : Flitney, A. P., & Abbott, D. (2002). An introduction to quantum game theory. Fluctuation and Noise Letters, 2(04), R175-R187.
[C1] : Clauser J.F., Horne M.A., Shimony A.,Holt R.A. An Experiment to Test Local Hidden-Variable Theories. Physical Review Letters 23 (15 1969), pp. 880-884.
[C2] : H Jaffali, I Nounouh, Théorie de l’Information Quantique : Jeux Quantiques et Applications a l’Énergie, UTBM, 2017
[M1] : Arthur, B. W. (1994). Inductive reasoning and bounded rationality: the El Farol problem. An. Econ. Rev. 84, 406–411.
[M2] : B. A. Huberman, T. Hogg. (1988). The Ecology of Computation, Studies in Computer Science and Articial Intelligence, North Holland publisher, page 99.
[M3] : Eisert, J., Wilkens, M., & Lewenstein, M. (1999). Quantum games and quantum strategies. Physical Review Letters, 83(15), 3077.
[M4] : Simon C. Benjamin, Patrick M. Hayden. (2001). Multi-Player Quantum Games. Centre for Quantum Computation, Clarendon Laboratory, University of Oxford, OX1 3PU, UK.