Quantum game theory

Quantum game theory is an extension of classical game theory to the quantum domain. It differs from classical game theory in three primary ways:

1. Superposed initial states,
2. Quantum entanglement of initial states,
3. Superposition of strategies to be used on the initial states.

This theory is based on the physics of information much like quantum computing.

History

In 1969, John Clauser, Michael Horne, Abner Shimony, and Richard Holt (often referred to collectively as "CHSH") wrote an often-cited paper describing experiments which could be used to prove Bell's theorem. In one part of this paper, they describe a game where a player could have a better chance of winning by using quantum strategies than would be possible classically. While game theory was not explicitly mentioned in this paper, it is an early outline of how quantum entanglement could be used to alter a game.

^[1] In 1999, a professor in the math department at the University of California at San Diego named David A. Meyer first published Quantum Strategies which details a quantum version of the classical game theory game, matching pennies. In the quantum version, players are allowed access to quantum signals through the phenomenon of quantum entanglement. ^[2]

Since Meyer's paper, many papers have been published exploring quantum games and the way that quantum strategies could be used in games that have been commonly studied in classical game theory.

Superposed initial states

The information transfer that occurs during a game can be viewed as a physical process. In the simplest case of a classical game between two players with two strategies each, both the players can use a bit (a '0' or a '1') to convey their choice of strategy. A popular example of such a game is the prisoners' dilemma, where each of the convicts can either cooperate or defect: withholding knowledge or revealing that the other committed the crime. In the quantum version of the game, the bit is replaced by the qubit, which is a quantum superposition of two or more base states. In the case of a two-strategy game this can be physically implemented by the use of an entity like the electron which has a superposed spin state, with the base states being +1/2 (plus half) and −1/2 (minus half). Each of the spin states can be used to represent each of the two strategies available to the players. When a measurement is made on the electron, it collapses to one of the base states, thus conveying the strategy used by the player.

Entangled initial states

The set of qubits which are initially provided to each of the players (to be used to convey their choice of strategy) may be entangled. For instance, an entangled pair of qubits implies that an operation performed on one of the qubits, affects the other qubit as well, thus altering the expected pay-offs of the game. A simple example of this is a quantum version ^[3] of the Two-up coin game in which the coins are entangled.

Superposition of strategies to be used on initial states

The job of a player in a game is to choose a strategy. In terms of bits this means that the player has to choose between 'flipping' the bit to its opposite state or leaving its current state untouched. When extended to the quantum domain this implies that the player can rotate the qubit to a new state, thus changing the probability amplitudes of each of the base states. Such operations on the qubits are required to be unitary transformations on the initial state of the qubit. This is different from the classical procedure which chooses the strategies with some statistical probabilities.

Multiplayer games

Introducing quantum information into multiplayer games allows a new type of "equilibrium strategy" which is not found in traditional games. The entanglement of players' choices can have the effect of a contract by preventing players from profiting from other player's betrayal. ^[4]

Quantum Prisoner's Dilemma

The Classical Prisoner's Dilemma is a game played between two players with a choice to cooperate with or betray their opponent. Classically, the dominant strategy is to always choose betrayal. When both players choose this strategy every turn, they each ensure a suboptimal profit, but cannot lose, and the game is said to have reached a Nash equilibrium. Profit would be maximized for both players if each chose to cooperate every turn, but this is not the rational choice, thus a suboptimal solution is the dominant outcome. In the Quantum Prisoner's Dilemma, both parties choosing to betray each other is still an equilibrium, however, there can also exist multiple Nash equilibriums that vary based on the entanglement of the initial states. In the case where the states are only slightly entangled, there exists a certain unitary operation for Alice so that if Bob chooses betrayal every turn, Alice will actually gain more profit than Bob and vice versa. Thus, a profitable equilibrium can be reached in 2 additional ways. The case where the initial state is most entangled shows the most change from the classical game. In this version of the game, Alice and Bob each have an operator Q that allows for a payout equal to mutual cooperation with no risk of betrayal. This is a Nash equilibrium that also happens to be Pareto optimal. ^[5]

Additionally, the quantum version of the Prisoner's Dilemma differs greatly from the classical version when the game is of unknown or infinite length. Classically, the infinite Prisoner's Dilemma has no defined fixed strategy but in the quantum version it is possible to develop an equilibrium strategy. ^[6]

Quantum Volunteer's Dilemma

The Volunteer's dilemma is a well-known game in game theory that models the conflict players face when deciding whether to volunteer for a collective benefit, knowing that volunteering incurs a personal cost. One significant volunteer’s dilemma variant was introduced by Weesie and Franzen in 1998, ^[7] involves cost-sharing among volunteers. In this variant of the volunteer's dilemma, if there is no volunteer, all players receive a payoff of 0. If there is at least one volunteer, the reward of b units is distributed to all players. In contrast, the total cost of c units incurred by volunteering is divided equally among all the volunteers. It is shown that for classical mixed strategies setting, there is a unique symmetric Nash equilibrium and the Nash equilibrium is obtained by setting the probability of volunteering for each player to be the unique root in the open interval (0,1) of the degree-n polynomial ${\displaystyle g_{n}}$ given by

${\displaystyle g_{n}(\alpha )=(1-\alpha )^{n-1}(2n\alpha +1-\alpha )-1.}$

In 2024, a quantum variant of the classical volunteer’s dilemma is introduced with b=2 and c=1 is studied, generalizing the classical setting by allowing players to utilize quantum strategies. ^[8] This is achieved by employing the Eisert–Wilkens–Lewenstein quantization framework. In this setting, the players received an entangled n-qubit state with each player controlling one qubit. The decision of each player can be viewed as determining two angles. Symmetric Nash equilibria that attain a payoff value of ${\displaystyle 2-1/n}$ for each player is shown and each player volunteers at this Nash Equilibrium. Furthermore, these Nash Equilibrium are Pareto optimal. It is shown that the payoff function of Nash equilibrium in the quantum setting is higher than the payoff of Nash equilibrium in the classical setting.

Quantum Card Game

A classically unfair card game can be played as follows: ^[9] There are two players, Alice and Bob. Alice has three cards: one has a star on both sides, one has a diamond on both sides, and one has a star on one side and a diamond on the other side. Alice places the three cards in a box and shakes it up, then Bob draws a card so that both players can only see one side of the card. If the card has the same markings on both sides, Alice wins. But if the card has different markings on each side, Bob wins. Clearly, this is an unfair game, where Alice has a probability of winning of 2/3 and Bob has a probability of winning of 1/3. Alice gives Bob one chance to "operate" on the box and then allows him to withdraw from the game if he would like, but he can only classically obtain information on one card from this operation, so the game is still unfair.

However, Alice and Bob can play a version of this game adjusted to allow for quantum strategies. If we describe the state of a card with a diamond facing up as ${\displaystyle |0\rangle }$ and the state where the star is facing up as ${\displaystyle |1\rangle }$, after shaking the box up, we can describe the state of the face-up part of the cards as:

${\displaystyle |r\rangle =|r_{0}\ r_{1}\ r_{2}\rangle }$

where each ${\displaystyle r_{k}}$ is either 0 or 1.

Now, Bob can take advantage of his ability to operate on the box by constructing a machine as follows: First, he has a unitary matrix defined as ${\displaystyle U_{k}={\begin{bmatrix}1&0\\0&e^{i\pi r_{k}}\end{bmatrix}}}$. This matrix is equal to ${\displaystyle I}$ if ${\displaystyle r_{k}}$ is 0 and ${\displaystyle Z}$ if ${\displaystyle r_{k}}$ is 1. He then creates his machine by putting this matrix between two Hadamard gates, so his machine now looks as follows:

${\displaystyle HU_{k}H={\frac {1}{2}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}1&0\\0&e^{i\pi r_{k}}\end{bmatrix}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}={\frac {1}{2}}{\begin{bmatrix}1+e^{i\pi r_{k}}&1-e^{i\pi r_{k}}\\1-e^{i\pi r_{k}}&1+e^{i\pi r_{k}}\end{bmatrix}}}$

This machine operating on the state ${\displaystyle |0\rangle }$ gives

${\displaystyle HU_{k}H|0\rangle ={\frac {1+e^{i\pi r_{k}}}{2}}|0\rangle +{\frac {1-e^{i\pi r_{k}}}{2}}|1\rangle =|r_{k}\rangle }$

So if Bob inputs ${\displaystyle |000\rangle }$ to his machine, he obtains

${\displaystyle (HU_{k}H\otimes HU_{k}H\otimes HU_{k}H)|000\rangle =|r_{0}\ r_{1}\ r_{2}\rangle }$

and he knows the state (i.e. the mark facing up) of all three of the cards. From here, Bob can draw one card, and then choose to either withdraw, or keep playing the game. Based on the first card that he draws, he can know from his knowledge of the face-up values of the cards whether or not he has drawn a card that will give him even chances of winning going forward (in which case he can continue to play a fair game) or if he has drawn the card that will guarantee that he loses the game. In this way, he can make the game fair for himself.

This is an example of a game where a quantum strategy can make a game fair for one player when it would be unfair for them with classical strategies.

Quantum Chess

Quantum Chess was first developed by a graduate student at the University of Southern California named Chris Cantwell. His motivation to develop the game was to expose non-physicists to the world of quantum mechanics. ^[10]

The game uses the same pieces as classical chess (8 pawns, 2 knights, 2 bishops, 2 rooks, 1 queen, 1 king) and is won in the same manner (by capturing the opponent's king). However, the pieces are allowed to obey laws of quantum mechanics such as superposition. By allowed the introduction of superposition, it becomes possible for pieces to occupy more than one square in an instance. The movement rules for each piece are the same as classical chess.

The biggest difference between quantum chess and classical chess is the check rule. Check is not included in quantum chess because it is possible for the king, as well as all other pieces, to occupy multiple spots on the grid at once. Another difference is the concept of movement to occupied space. Superposition also allows two occupies to share space or move through each other.

Capturing an opponent's piece is also slightly different in quantum chess than in classical chess. Quantum chess uses quantum measurement as a method of capturing. When attempting to capture an opponent's piece, a measurement is made to determine the probability of whether or not the space is occupied and if the path is blocked. If the probability is favorable, a move can be made to capture. ^[11]

PQ Penny Flip Game

The PQ penny flip game ^[12] involves two players: Captain Picard and Q. Q places a penny in a box, then they take turns (Q, then Picard, then Q) either flipping or not flipping the penny without revealing its state to either player. After these three moves have been made, Q wins if the penny is heads up, and Picard if the penny is face down.

The classical Nash Equilibrium has both players taking a mixed strategy with each move having a 50% chance of either flipping or not flipping the penny, and Picard and Q will each win the game 50% of the time using classical strategies.

Allowing for Q to use quantum strategies, namely applying a Hadamard gate to the state of the penny places it into a superposition of face up and down, represented by the quantum state

${\displaystyle |\psi _{1}\rangle ={\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )}$

In this state, if Picard does not flip the gate, then the state remains unchanged, and flipping the penny puts it into the state

${\displaystyle |\psi _{2}\rangle ={\frac {1}{\sqrt {2}}}(|1\rangle +|0\rangle )=|\psi _{1}\rangle }$

Then, no matter Picard's move, Q can once again apply a Hadamard gate to the superposition which results in the penny being face up. In this way the quantization of Q's strategy guarantees a win against a player constrained by classical strategies.

This game is exemplary of how applying quantum strategies to classical games can shift an otherwise fair game in favor of the player using quantum strategies. ^[9]

Quantum minimax theorems

The concepts of a quantum player, a zero-sum quantum game and the associated expected payoff were defined by A. Boukas in 1999 (for finite games) and in 2020 by L. Accardi and A. Boukas (for infinite games) within the framework of the spectral theorem for self-adjoint operators on Hilbert spaces. Quantum versions of Von Neumann's minimax theorem were proved. ^{[13] [14]}

Paradoxes

Quantum game theory also offers a solution to Newcomb's Paradox.

Take the two boxes offered in Newcomb's game to be coupled, as the contents of box 2 depend on if the ignorant player takes box 1. Quantum game theory enables a situation such that foreknowledge by otherwise omniscient player isn't required in order to achieve the situation. If the otherwise omniscient player operates on the state of the two boxes using a Hadamard gate, then sets up a device that operates on the state defined by the two boxes to operate again using a Hadamard gate after the ignorant player's choice. Then, no matter the pure or mixed strategy that the ignorant player uses, the ignorant player's choice will lead to it's corresponding outcome as defined by the premise of the game. Because choosing a strategy for the game, then changing it to fool to otherwise omniscient player (corresponding to operating on the game state using a NOT gate) cannot give the ignorant player an additional advantage, as the two Hadamard operations ensure that the only two outcomes are those defined by the chosen strategy. In this way, the expected situation is achieved no matter the ignorant player's strategy without requiring a system knowledgeable about that player's future. ^[15]

See also

• Quantum tic-tac-toe: not a quantum game in the sense above, but a pedagogical tool based on metaphors for quantum mechanics
• Quantum pseudo-telepathy
• Quantum refereed game
• CHSH game
• Jan Sładkowski
• Jens Eisert

References

1. Meyer, David A. (1999-02-01). "Quantum strategies". Physical Review Letters. 82 (5): 1052–1055. arXiv: quant-ph/9804010 . Bibcode:1999PhRvL..82.1052M. doi:10.1103/PhysRevLett.82.1052. ISSN   0031-9007. S2CID   7361611.
2. Brandenburger, Adam (2010-05-01). "The relationship between quantum and classical correlation in games". Games and Economic Behavior. Special Issue In Honor of Robert Aumann. 69 (1): 175–183. doi:10.1016/j.geb.2009.10.009. ISSN   0899-8256.
3. https://play.google.com/store/apps/details?id=com.QuantumGamesLLC.QuantumTwoUp ^{[ bare URL ]}
4. Simon C. Benjamin; Patrick M. Hayden (13 August 2001), "Multiplayer quantum games", Physical Review A , 64 (3): 030301, arXiv: quant-ph/0007038 , Bibcode:2001PhRvA..64c0301B, doi:10.1103/PhysRevA.64.030301, S2CID   32056578
5. Du, Jiangfeng; Xu, Xiaodong; Li, Hui; Zhou, Xianyi; Han, Rongdian (2003). "Playing Prisoner's Dilemma with Quantum Rules". arXiv: quant-ph/0301042 .
6. Ikeda, Kazuki; Aoki, Shoto (2021-11-17). "Infinitely repeated quantum games and strategic efficiency". Quantum Information Processing. 20 (12): 387. arXiv: 2005.05588 . Bibcode:2021QuIP...20..387I. doi:10.1007/s11128-021-03295-7. ISSN   1573-1332. S2CID   244354791.
7. Weesie, Jeroen, and Axel Franzen. "Cost sharing in a volunteer's dilemma." Journal of conflict resolution 42.5 (1998): 600-618.
8. Koh, Enshan Dax; Kumar, Kaavya; Goh, Siong Thye (2024). "Quantum Volunteer's Dilemma". arXiv: 2409.05708 [quant-ph].
9. Price, Elizabeth. "Quantum Games and Game Strategy" (PDF). University of Chicago.{{cite journal}}: Cite journal requires |journal= (help)
10. Cantwell, Christopher (2019-07-10). "Quantum Chess: Developing a Mathematical Framework and Design Methodology for Creating Quantum Games". arXiv: 1906.05836 [quant-ph].
11. "Quantum Chess Rules". Quantum Realm Games. 2020.
12. Meyer, David A. (1999-02-01). "Quantum strategies". Physical Review Letters. 82 (5): 1052–1055. arXiv: quant-ph/9804010 . doi:10.1103/PhysRevLett.82.1052. ISSN   0031-9007.
13. Boukas, A. (2000). "Quantum Formulation of Classical Two Person Zero-Sum Games". Open Systems & Information Dynamics. 7: 19–32. doi:10.1023/A:1009699300776. S2CID   116795672.
14. Accardi, Luigi; Boukas, Andreas (2020). "Von Neumann's Minimax Theorem for Continuous Quantum Games". Journal of Stochastic Analysis. 1 (2). Article 5. arXiv: 2006.11502 . doi: 10.31390/josa.1.2.05 .
15. Piotrowski, E. W.; Sladkowski, J. (2002-02-13). "Quantum solution to the Newcomb's paradox". arXiv.org. Retrieved 2024-11-15.

Further reading

• Ball, Philip (18 October 1999). "Everyone wins in quantum games". Nature. doi:10.1038/news991021-3. ISSN   0028-0836. Archived from the original on 29 April 2005.
• Piotrowski, E. W.; Sładkowski, J. (2003). "An Invitation to Quantum Game Theory" (PDF). International Journal of Theoretical Physics . 42 (5). Springer Nature: 1089–1099. doi:10.1023/a:1025443111388. ISSN   0020-7748. S2CID   13630647. Archived from the original (PDF) on 15 February 2012. Retrieved 17 August 2009.
• Danaci, Onur; Zhang, Wenlei; Coleman, Robert; Djakam, William; Amoo, Michaela; Glasser, Ryan T.; Kirby, Brian T.; N'Gom, Moussa; Searles, Thomas A. (2023-02-28), ManQala: Game-Inspired Strategies for Quantum State Engineering, doi:10.48550/arXiv.2302.14582, retrieved 2024-12-06 ^[1]

1. Danaci, Onur; Zhang, Wenlei; Coleman, Robert; Djakam, William; Amoo, Michaela; Glasser, Ryan T.; Kirby, Brian T.; N'Gom, Moussa; Searles, Thomas A. (2023-02-28), ManQala: Game-Inspired Strategies for Quantum State Engineering, doi:10.48550/arXiv.2302.14582 , retrieved 2024-12-06