Quantum Game Theory — A Mathematical Venture

Image © Wall.Alphacoders: Image used for representational purposes only

Ever wondered if you could figure out how to win a game even before it started? Or how could you emerge as the forerunner in an auction, all with the help of mathematics? If you did, then welcome to the world of game theory, a branch of mathematics specifically developed (by von Neumann, one of the mathematically brilliant minds of the 20th century) to maximize what is known as one’s “payoff” in games.

But recently, this theory has seen a major extension, as other numerous other fields, and has emerged into quantum game theory, which, courtesy of a few breakthrough papers, has shown quite positive outcomes recently. One of the most famous games in game theory, the prisoner’s dilemma, has also been developed into a quantum analogue. But that’s not the subject of this particular article. Here, we will analyze a much simpler two-person game, the quantum penny flip.

So, what is quantum game theory and how can quantum mechanics change the possible payoff?

A Few Introductory Terms

Before delving into quantum game theory, we need to understand a few basic terms related to classical game theory:

1. Players — Pretty much a self-explanatory term. The various participants in an event are called its players.
2. Strategy — Again a self-explanatory term. The various ways in which the players of a game try to maximize their profits are called strategies.
3. Payoff — The outcome of a particular strategy played by a player, mapped to a numerical scale, is called the payoff (the higher the payoff, the better the strategy.)
4. Nash Equilibrium (N.E.) — One of the most important concepts in game theory, Nash equilibrium is a situation where there is maximal possible payoff for each player. That is, no player can increase his payoff by unilaterally changing his strategy. You could think of it as an ideal situation of a draw in a chess game — no player is in a piece of clear-cut advantage or disadvantage.
5. Pareto Optimal Outcome — A Pareto optimal outcome is a situation in which no player can increase his payoff without decreasing another player’s payoff. A good example would be that of a market. In an ideally competitive market, no seller can increase his advantage unilaterally, that is, without decreasing his competitor’s advantage.

Quantum Games Overview

With that, we are ready to delve into quantum game theory. Let’s jump in and define a few basic mathematical equations that will help us later on. Let us call the two players of our game Alice and Bob and let their respective strategies be  and B̂. We’ll call the entangling operator Ĥ (which also controls the degree of entanglement, i.e. “how quantum our game is”) and our disentangling operator Ĥ′ (which is just the conjugate transpose of Ĥ, i.e. Ĥ′=Ĥ^†), so our generalized quantum circuit for a two-person game becomes:

Generalized quantum circuit for a two-player game.

where the final |ϕ⟩ signifies the final payoff after the strategies have been made by both players.

Quite intuitively, extending the space to multiple players would mean that we apply the entangling operator to all the qubits (equal to the number of players), then apply the individual strategies of each player, and finally, the disentangling operator to all again.

Analyzing this circuit, the final state can be computed as:

Mathematical Representation of the final state.

where |00⟩ is the initial state. Let us denote the expectation value of the final state by 〈$〉 (payoff value) which can be calculated by the general formula for expectation:

The general formula for calculating the expectation value of a variable (here the payoff is denoted by 〈$〉). The first qubit belongs to Alice’s state and the second qubit belongs to Bob’s.

Now, we want to see how going from classical to quantum will help Alice and/or Bob. As a result, we will have to define a parametrized version of our entangling operator Ĥ, so that we can control our degree of entanglement from “purely classical” to “hybrid” to “purely quantum”. Thus, the entangling operator Ĥ can be defined mathematically as follows.

The general form of the entangling operator for N×2 games; ɣ is the parameter controlling the degree of entanglement; 𝜎_x is the Pauli X matrix; i is the imaginary constant √(-1).

where ɣ is the parameter that controls the degree of entanglement, 𝜎_x is the Pauli X matrix, i is the imaginary number, and N is the number of strategies available for each player (so in the case in which each player has only two moves to play, N=2). One question might arise about why we use 𝜎_x and not 𝜎_y or 𝜎_z. Well, that’s because we have currently chosen our basis as the X basis (due to the relative ease of working with it). It is completely fine if you take Y or Z as the basis as long as you can handle the calculations!

Let’s plug in some values of ɣ and see what happens to our entangling operator Ĥ:

1. ɣ=0
   As soon as we put ɣ=0, the argument of the exponent of e just becomes 0, and we end up getting e⁰, which is just 1! So, there is no entanglement happening here, which corresponds to… a classical game. This is equivalent to just using an identity matrix as the entangling operator.
2. ɣ=π/2
   When we put the parameter as π/2, we end up achieving the maximally entangled state (why? because it corresponds to a π/2 rotation around the Bloch sphere, which is the region of maximum entanglement) by simplifying the exponent using Euler’s formula:

Placing the value of ɣ as π/2 and then simplifying the exponent using Euler’s formula, e^iθ = cos θ + i sin θ.

Now, applying the trigonometric functions to the Pauli X matrix in the argument [1]:

Applying sine and cosine functions for 𝜎_x leads us to the maximally entangled case. Here, I have directly used the results for the trigonometric functions of the Pauli X. For a rigorous proof of the same, refer to [1]. I-hat is the identity matrix.

So, we see that the degree of entanglement varies from the minimally entangled case at ɣ=0 to the maximally entangled case at ɣ=π/2. This range covers all the possible values of the “quantumness” of the game, as a result, we define ɣ ∈ [0, π/2].

As should be quite intuitive by now, the space of all available strategies is effectively covered by the set of all the 2×2 unitary matrices that can form a quantum gate, which is a subset of the special unitary group SU(2). So, one last mathematical definition required for us is:

A-hat, B-hat … and so on are the specific strategies of each player (in our specific case, it is 2) and U-hat (sub) is the generalized notation for such strategies. SU(2) is an acronym for special unitary group 2, that is, the group of all 2×2 unitary matrices that have determinant 1.

Quantum Penny Flip

Let us consolidate these ideas through the quantum version of a penny flip game. The gameplay goes as follows,

Alice prepares a coin in the heads state without, and after this preparation no player can see the current state of the coin until a measurement is taken.

Bob then has a turn at the coin who can either leave the coin untouched or can flip the coin. Then, Alice has the opportunity to do the same with the coin, and then finally, Bob has a final go at the coin.

Finally, the measurement is taken: Bob wins if the coin shows heads.

Let’s see what happens now when we give one of the players a quantum advantage. Suppose this quantum advantage is available to Bob. So Bob can leverage this quantum advantage to gain a clear advantage over Alice.

Bob can use a simple Hadamard gate to increase his payoff over Alice. We use a numerical mapping hereon, where 0 corresponds to heads and 1 to tails. The circuit of the whole game would be:

Quantum Circuit for penny flip game when Bob has the quantum advantage. Alice prepares the state |0⟩, and Bob in his first move applies a Hadamard. Alice then plays Ac (any classical move), and finally, Bob in his second move again applies the Hadamard, which yields the state |ϕf⟩

Let’s do some math for the final state |ϕf⟩. The final state can be given by:

Mathematical equality for finding the final state. The equivalence holds as H†=H.

First, applying H on |0⟩ yields the |+⟩ state:

The outer product form of the Hadamard applied on |0⟩.

Here we have used the property that〈0|0〉=1 and〈1|0⟩=0, which yields the |+〉 state.

Now let’s consider the two possible cases of A_c. As it is a classical strategy, by the rules of the game there are only two possible moves that Alice can play: either flip the coin or leave the coin untouched.

But, in the case of the coin flip, you might recognize that it corresponds to reversing the qubits, i.e. a bit flip operation that means we are just interchanging |1⟩ and |0⟩. You can see that applying this operation to our current state would leave the system unaltered!

So, in all cases, what we have after Alice plays her move is the |+〉 state itself. And that means that when we apply Hadamard:

Here I have used the matrix representation of the Hadamard and applied it to the |+〉 state we had got after Alice’s move.

On simplifying the above expression, we get the final state to be |0⟩

Hence we see that the final state is |0⟩, which would give us a classical 0 100% of the times in the absence of all measurement errors. And what does 0 represent in our numerical map? Heads! That means that Bob has a clear-cut advantage over Alice, and is guaranteed to win the game!

Some people might argue that we got the previous result because of the specific mapping that we took, so let’s see what happens when Alice prepares the tails state and Bob wins on getting a tails.

The only difference would be that our initial state would now be in the |1〉 state rather than in the |0〉 state. Applying Hadamard, we get the |–〉 state and a bit flip would mean that we get –|–〉 state, but if you recall, the negative sign has no significance as it is a global phase. Hence, what we would get after measurement would be 1, 100% of the times, which was our numerical mapping to tails!

The mathematics of the same is illustrated below:

The outer product form of the Hadamard applied on |1〉 state.

Simplifying the previous equation yields the |–〉 state.

The expression for finding the final state. Note the term here is -1 times the |–〉 state. The minus sign comes from flipping the qubit in Alice’s move. Note that I have only considered the case where Alice flips the coin, skipping the other case for its obviousness.

Simplifying the previous expression gives us –|1〉, but the negative has no significance! Therefore, it can be ignored and what we would get would be |1〉 itself.

So we saw how extending the space of strategies from classical to quantum can increase the payoff of the quantum player, and can even ensure a win to the player. As you might be thinking correctly, a quantum player can do at least as well as a classical player in all cases, as the classical strategy just forms a subset of the much larger quantum set of strategies.

Well, the quantum coin flip was quite a simple game, and you might have felt that what we have covered would be obvious. In a future article, we will be analyzing the quantum prisoner’s dilemma, and hopefully, what we have covered here would help us there to get a sense of things as we have just started on this trail of quantum game theory!

Underneath, I have attached a few references and additional readings which you may refer to clear things up in case you get stuck up somewhere.

References and Additional Readings

1. rob (https://math.stackexchange.com/users/166791/rob), Exponential of Pauli Matrices, URL (version: 2019–05–24): https://math.stackexchange.com/q/3237834
2. Flitney, A. P.; Abbott, D. (2002). AN INTRODUCTION TO QUANTUM GAME THEORY. Fluctuation and Noise Letters, 2(4), R175–R187. doi:10.1142/s0219477502000981
3. J. Eisert, M. Wilkens and M. Lewenstein, Quantum Games and Quantum Strategies, Phys. Rev. Lett. 83 (1999) 3077–3088; 87 (2001) 069802.
4. Quantum Coin Toss | Physics Magazine: https://physicsworld.com/a/the-quantum-coin-toss/
5. https://getmyuni.azureedge.net/assets/main/study-material/notes/mechanical_engineering_operation-research_game-theory_notes.pdf

To read more such articles and series, subscribe to the Quantum Untangled publication here.