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:

Superposed initial states,
Quantum entanglement of initial states,
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 $g_{n}$ given by

$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 $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 $|0\rangle$ and the state where the star is facing up as $|1\rangle$ , after shaking the box up, we can describe the state of the face-up part of the cards as:

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

where each $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 $U_{k}={\begin{bmatrix}1&0\\0&e^{i\pi r_{k}}\end{bmatrix}}$ . This matrix is equal to $I$ if $r_{k}$ is 0 and $Z$ if $r_{k}$ is 1. He then creates his machine by putting this matrix between two Hadamard gates, so his machine now looks as follows:

$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 $|0\rangle$ gives

$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 $|000\rangle$ to his machine, he obtains

$(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

$|\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

$|\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]

References

^ 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.
^ 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.
^ https://play.google.com/store/apps/details?id=com.QuantumGamesLLC.QuantumTwoUp ^{[bare URL]}
^ 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
^ Du, Jiangfeng; Xu, Xiaodong; Li, Hui; Zhou, Xianyi; Han, Rongdian (2003). "Playing Prisoner's Dilemma with Quantum Rules". arXiv:quant-ph/0301042.
^ 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.
^ Weesie, Jeroen, and Axel Franzen. "Cost sharing in a volunteer's dilemma." Journal of conflict resolution 42.5 (1998): 600-618.
^ Koh, Enshan Dax; Kumar, Kaavya; Goh, Siong Thye (2024). "Quantum Volunteer's Dilemma". arXiv:2409.05708 [quant-ph].
^ ^a ^b Price, Elizabeth. "Quantum Games and Game Strategy" (PDF). University of Chicago. {{cite journal}}: Cite journal requires |journal= (help)
^ Cantwell, Christopher (2019-07-10). "Quantum Chess: Developing a Mathematical Framework and Design Methodology for Creating Quantum Games". arXiv:1906.05836 [quant-ph].
^ "Quantum Chess Rules". Quantum Realm Games. 2020.
^ 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.
^ 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.
^ 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.
^ Piotrowski, E. W.; Sladkowski, J. (2002-02-13). "Quantum solution to the Newcomb's paradox". arXiv:quant-ph/0202074.

Quantum mechanics
Background	Introduction History Timeline Classical mechanics Old quantum theory Glossary
Fundamentals	Born rule Bra–ket notation Complementarity Density matrix Energy level Ground state Excited state Degenerate levels Zero-point energy Entanglement Hamiltonian Interference Decoherence Measurement Nonlocality Quantum state Superposition Tunnelling Scattering theory Symmetry in quantum mechanics Uncertainty Wave function Collapse Wave–particle duality
Formulations	Formulations Heisenberg Interaction Matrix mechanics Schrödinger Path integral formulation Phase space
Equations	Klein–Gordon Dirac Weyl Majorana Rarita–Schwinger Pauli Rydberg Schrödinger
Interpretations	Bayesian Consistent histories Copenhagen de Broglie–Bohm Ensemble Hidden-variable Local Superdeterminism Many-worlds Objective collapse Quantum logic Relational Transactional Von Neumann–Wigner
Experiments	Bell test Davisson–Germer Delayed-choice quantum eraser Double-slit Franck–Hertz Mach–Zehnder interferometer Elitzur–Vaidman Popper Quantum eraser Stern–Gerlach Wheeler's delayed choice
Science	Quantum biology Quantum chemistry Quantum chaos Quantum cosmology Quantum differential calculus Quantum dynamics Quantum geometry Quantum measurement problem Quantum mind Quantum stochastic calculus Quantum spacetime
Technology	Quantum algorithms Quantum amplifier Quantum bus Quantum cellular automata Quantum finite automata Quantum channel Quantum circuit Quantum complexity theory Quantum computing Timeline Quantum cryptography Quantum electronics Quantum error correction Quantum imaging Quantum image processing Quantum information Quantum key distribution Quantum logic Quantum logic gates Quantum machine Quantum machine learning Quantum metamaterial Quantum metrology Quantum network Quantum neural network Quantum optics Quantum programming Quantum sensing Quantum simulator Quantum teleportation
Extensions	Quantum fluctuation Casimir effect Quantum statistical mechanics Quantum field theory History Quantum gravity Relativistic quantum mechanics
Related	Schrödinger's cat in popular culture Wigner's friend EPR paradox Quantum mysticism
Category

Topics of game theory
Definitions	Congestion game Cooperative game Determinacy Escalation of commitment Extensive-form game First-player and second-player win Game complexity Graphical game Hierarchy of beliefs Information set Normal-form game Preference Sequential game Simultaneous game Simultaneous action selection Solved game Succinct game Mechanism design
Equilibrium concepts	Bayes correlated equilibrium Bayesian Nash equilibrium Berge equilibrium Core Correlated equilibrium Coalition-proof Nash equilibrium Epsilon-equilibrium Evolutionarily stable strategy Gibbs equilibrium Mertens-stable equilibrium Markov perfect equilibrium Nash equilibrium Pareto efficiency Perfect Bayesian equilibrium Proper equilibrium Quantal response equilibrium Quasi-perfect equilibrium Risk dominance Satisfaction equilibrium Self-confirming equilibrium Sequential equilibrium Shapley value Strong Nash equilibrium Subgame perfection Trembling hand equilibrium
Strategies	Appeasement Backward induction Bid shading Collusion Cheap talk De-escalation Deterrence Escalation Forward induction Grim trigger Markov strategy Pairing strategy Dominant strategies Pure strategy Mixed strategy Strategy-stealing argument Tit for tat
Classes of games	Auction Bargaining problem Global game Intransitive game Mean-field game n-player game Perfect information Large Poisson game Potential game Repeated game Screening game Signaling game Strictly determined game Stochastic game Symmetric game Zero-sum game
Games	Go Chess Infinite chess Checkers All-pay auction Prisoner's dilemma Gift-exchange game Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Lewis signaling game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Electronic mail game Rock paper scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division Fair cake-cutting Bertrand competition Cournot competition Stackelberg competition Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Induction puzzles Trust game Princess and monster game Rendezvous problem
Theorems	Aumann's agreement theorem Folk theorem Minimax theorem Nash's theorem Negamax theorem Purification theorem Revelation principle Sprague–Grundy theorem Zermelo's theorem
Key figures	Albert W. Tucker Amos Tversky Antoine Augustin Cournot Ariel Rubinstein Claude Shannon Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin John Conway Jean Tirole Jean-François Mertens Jennifer Tour Chayes John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Olga Bondareva Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Axelrod Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Suzanne Scotchmer Thomas Schelling William Vickrey
Search optimizations	Alpha–beta pruning Aspiration window Principal variation search max^n algorithm Paranoid algorithm Lazy SMP
Miscellaneous	Bounded rationality Combinatorial game theory Confrontation analysis Coopetition Evolutionary game theory Glossary of game theory List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons

Fahrer / Team für die Suche eingeben: