An Investigation of Quantum Computational GameTheoryScott [email protected]: Dr. Max MintzApril 19, 2006AbstractGame theory is a well established field with applications in many areas includingthe social sciences, biology, and computer science [6]. Recently, however, researchersin quantum computation have begun to study the implications of games set in thequantum domain (i.e. game theoretical situations where either one or more playershave quantum computational power or where the implementation of strategies use ssome form of quantum information). Such a setting allows for entanglement and su-perpositions of strategies and evaluation of payoffs using quantum measurement. Thisapproach to game theory, according to s ome scholars in the field, could help us un-derstand certain physical systems, improve economic markets, and develop quantumalgorithms.I have conducted an investigation into quantum game theory. I have constructedsimulation tools using Maple that, along with research into related work, have helpedgain some insight into this new field. The im portant solutions in classical game theoryare usually Nash equilibria. What do they look like in the quantum realm? In whatgames does “quantization” give an advantage to players and how? What are theimportant applications of quantum game theory? Thes e were the guiding questions ofmy projec t.1 What is quantum game theory?1.1 PQ penny flipDavid Meyer of UCSD has been credited with initiating the study of quantum games in 1999with his Starship Enterprise game [9]. In this game, also known as PQ PENNY FLIP [12],Captian Picard and a quantum computer Q square off in a coin flipping challenge as follows.A coin is placed in a box head up. Q takes the first turn and can choose to flip or not flip thecoin. Then Picard takes a turn, and then Q once again. If the coin is now head up, Q wins;1if it is tail up, Picard wins. What is interesting about the game is that since Q has quantumcomputational powers, it can employ a quantum strategy that wins every time [11].To illustrate this, define the initial state (heads) as |0i. The computational basis for thisgame is then {|0i, |1i}. The winning quantum strategy will be essentially two Hadamardtransformations (denoted by H and defined in the Appendix).|0iQ−→H1√2(|0i + |1i)P−→σxor I1√2(|0i + |1i)Q−→H|0iTheX−→Mnotation denotes an operation performed by player X represented by matrix M.Intuitively, Q’s strategy is to first put the coin in an equal superposition of heads and tails.P can then choose to flip the coin and apply the Pauli matrix σx(defined in the Appendix)or not to flip and apply the identity matrix I. After P makes his move, Q will apply thesame transformation to the coin as it did in the first move, which will return the coin tothe heads position no matter what move P makes. Thus Q always wins. Of course in theclassical instance of this game, Q can at best expect to win half of the time.1.2 Prisoner’s dilemma1.2.1 Defining the Classical Prisoner’s DilemmaThe Prisoner’s Dilemma is an example of what is known as a static non-zero-sum game.Static games, as opposed to dynamic games, require that players submit their strategiessimultaneously before payoffs are evaluated (in dynamic games players take turns makingmoves). In zero-sum games, one player’s loss is another player’s gain; it will be clear afterformalizing the Prisoner’s Dilemma that it is not a zero-sum game.We will define the two-player classical Prisoner’s Dilemma G = (SA, SB, πA, πB), whereSiis the set of strategies available to player i and πi: SA× SB→ < is the payoff functionfor player i. The Prisoner’s Dilemma is binary choice, meaning |SA| = |SB| = 2. We canindex the sets of strategies so that SA= SB= {1, 2}, and so the payoff functions can bevisualized in a 2 × 2 matrix:P ="(3, 3) (0, 5)(5, 0) (1, 1)#where Pij= (πi(i, j), πj(i, j)). Strategy 1 and 2 will hence forth be referred to as Cooperate(C) and Defect (D), respectively.When studying static non ze ro sum games we are often interested in the notion of Nashequilibria. A Nash equilibrium is a pair of strategies {sA, sB} such thatπA(sA, sB) ≥ πA(siA, sB) and πB(sA, sB) ≥ πB(sA, sjB) ∀i, j2That is, the pair of strategies such that no player can improve his payoff by changing strate-gies. By a quick inspection of P , the pair (D,D) is the only Nash equilibrium availablehere.But what if we introduce the notion of mixed strategies? This concept allows each playeri to pick a probability pisuch that he will Coop erate with probability piand Defect withprobability (1 −pi). Now we alter our definition of Nash equilibria so that the payoff functionsare now expected payoff functions:πA= 3pApB+ 0pA(1 − pB) + 5(1 − pA)pB+ 1(1 − pA)(1 − pB) = −pApB+ 4pB− pA+ 1πB= 3pApB+ 0(1 − pA)pB+ 5pA(1 − pB) + 1(1 − pA)(1 − pB) = −pApB+ 4pA− pB+ 1Now we can think of pairs of s trategies in terms of pairs of probabilities (pA, pB). For anysuch pair where pA> 0 and pB> 0, some player i can improve his payoff by setting pi= 0.However, if the pA= pB= 0, no player i can improve his payoff by changing pi, so (0, 0) isthe only Nash equilibrium. It is important to note that this pair of probabilities correspondsto both players defecting with probability 1, which is equivalent to the Nash equilibriumbefore mixed strategies were introduced.Notice, however, that πA(D,D) = πB(D,D) = 3 > πA(C,C) = πB(C,C) = 1. We say inthis case that the payoff point (3,3) jointly dominates (1,1). More formally, a payoff point(x1, y1) jointly dominates a payoff point (x2, y2) if x1≥ x2and y1≥ y2and one of theinequalities is strict. A payoff point is Pareto optimal if it is not jointly dominated by anypoint and a player cannot increase his payoff from this point without decreasing anotherplayer’s payoff. Thus (C,C) is Pareto optimal.1.2.2 Quantizing the Prisoner’s DilemmaWe will now redefine the Prisoner’s dilemma to create a quantum game and show that thereis a Nash equilibrium which is Pareto optimal. Let GQ= (H, ρ, SA, SB, πA, πB) be thequantized game, where H is the state space of the game, ρ is the initial state, SAand SBare sets of unitary operaters representing the player’s possible strategies, and πAand πBarepayoff functions.In order to build the state space H for the Prisoner’s dilemma, we need a 2-dimensionalHilbert space to hold the state of each player’s move. The standard basis for