Learning in games has emerged as a powerful tool for machine learning with numerous applications. Quantum games model interactions between strategic players who have access to quantum resources, and several recent works have studied learning in the competitive regime of quantum zero-sum games. Going beyond this setting, we introduce quantum common-interest games (CIGs) where players have density matrices as strategies and their interests are perfectly aligned. We bridge the gap between optimization and game theory by establishing the equivalence between KKT (first-order stationary) points of an instance of the Best Separable State (BSS) problem and the Nash equilibria of its corresponding quantum CIG. This allows learning dynamics for the quantum CIG to be seen as decentralized algorithms for the BSS problem. Taking the perspective of learning in games, we then introduce non-commutative extensions of the continuous-time replicator dynamics and the discrete-time best response dynamics/linear multiplicative weights update for learning in quantum CIGs. We prove analogues of classical convergence results of the dynamics and explore differences which arise in the quantum setting. Finally, we corroborate our theoretical findings through extensive experiments.
Learning in games has emerged as a powerful tool for machine learning with numerous applications. Quantum games model interactions between strategic players who have access to quantum resources, and several recent works have studied learning in the competitive regime of quantum zero-sum games. Going beyond this setting, we introduce quantum common-interest games (CIGs) where players have density matrices as strategies and their interests are perfectly aligned. We bridge the gap between optimization and game theory by establishing the equivalence between KKT (first-order stationary) points of an instance of the Best Separable State (BSS) problem and the Nash equilibria of its corresponding quantum CIG. This allows learning dynamics for the quantum CIG to be seen as decentralized algorithms for the BSS problem. Taking the perspective of learning in games, we then introduce non-commutative extensions of the continuous-time replicator dynamics and the discrete-time best response dynamics/linear multiplicative weights update for learning in quantum CIGs. We prove analogues of classical convergence results of the dynamics and explore differences which arise in the quantum setting. Finally, we corroborate our theoretical findings through extensive experiments.
As quantum processors advance, the emergence of large-scale decentralized systems involving interacting quantum-enabled agents is on the horizon. Recent research efforts have explored quantum versions of Nash and correlated equilibria as solution concepts of strategic quantum interactions, but these approaches did not directly connect to decentralized adaptive setups where agents possess limited information. This paper delves into the dynamics of quantum-enabled agents within decentralized systems that employ no-regret algorithms to update their behaviors over time. Specifically, we investigate two-player quantum zero-sum games and polymatrix quantum zero-sum games, showing that no-regret algorithms converge to separable quantum Nash equilibria in time-average. In the case of general multi-player quantum games, our work leads to a novel solution concept, that of the separable quantum coarse correlated equilibria (QCCE), as the convergent outcome of the time-averaged behavior no-regret algorithms, offering a natural solution concept for decentralized quantum systems. Finally, we show that computing QCCEs can be formulated as a semidefinite program and establish the existence of entangled (i.e., non-separable) QCCEs, which are unlearnable via the current paradigm of no-regret learning.
Recent advances in quantum computing and in particular, the introduction of quantum GANs, have led to increased interest in quantum zero-sum game theory, extending the scope of learning algorithms for classical games into the quantum realm. In this paper, we focus on learning in quantum zero-sum games under Matrix Multiplicative Weights Update (a generalization of the multiplicative weights update method) and its continuous analogue, Quantum Replicator Dynamics. When each player selects their state according to quantum replicator dynamics, we show that the system exhibits conservation laws in a quantum-information theoretic sense. Moreover, we show that the system exhibits Poincare recurrence, meaning that almost all orbits return arbitrarily close to their initial conditions infinitely often. Our analysis generalizes previous results in the case of classical games.
Game theory is a well established branch of mathematics whose formalism has a vast range of applications from the social sciences, biology, to economics. Motivated by quantum information science, there has been a leap in the formulation of novel game strategies that lead to new (quantum Nash) equilibrium points whereby players in some classical games are always outperformed if sharing and processing joint information ruled by the laws of quantum physics is allowed. We show that, for a bipartite non zero-sum game, input local quantum correlations, and separable states in particular, suffice to achieve an advantage over any strategy that uses classical resources, thus dispensing with quantum nonlocality, entanglement, or even discord between the players' input states. This highlights the remarkable key role played by pure quantum coherence at powering some protocols. Finally, we propose an experiment that uses separable states and basic photon interferometry to demonstrate the locally-correlated quantum advantage.
In this paper, we study the equilibrium convergence and stability properties of the widely used matrix multiplicative weights (MMW) dynamics for learning in general quantum games. A key difficulty in this endeavor is that the induced quantum state dynamics decompose naturally into (i) a classical, commutative component which governs the dynamics of the system's eigenvalues in a way analogous to the evolution of mixed strategies under the classical replicator dynamics; and (ii) a non-commutative component for the system's eigenvectors. This non-commutative component has no classical counterpart and, as a result, requires the introduction of novel notions of (asymptotic) stability to account for the nonlinear geometry of the game's quantum space. In this general context, we show that (i) only pure quantum equilibria can be stable and attracting under the MMW dynamics; and (ii) as a partial converse, pure quantum states that satisfy a certain “variational stability” condition are always attracting. This allows us to fully characterize the structure of quantum Nash equilibria that are stable and attracting under the MMW dynamics, a fact with significant implications for predicting the outcome of a multi-agent quantum learning process.
In classical (standard) game theory, a useful algorithm for searching Nash equilibrium in games of two players, is to determine the best response functions. For each strategy S1 of player 1 player 2 finds a best response function F2(S1), and vice versa. If the two response functions intersect, the intersection point (S1*, S2*) is a candidate for Nash equilibrium. This method is especially useful when the strategy space of each player is determined by a single variable (discrete or continuous). In the last decade, the concept of quantum games has been developed (hence we distinguish between classical and quantum games). In a quantum game with two players the strategy space of each player is composed of 2 × 2 complex unitary matrices with unit determinant. That is the group SU(2). The corresponding strategy space is characterized by three continuous variables represented by angles: 0 ≤ α ≤ 2π, 0 ≤ β ≤ 2π, 0 ≤ θ ≤ π. That turns the use of response functions impractical. In the present contribution we suggest a method for alleviating this problem by discretizing the variables as: {αi, βj, θk}, i= 1, 2, ..., I; j = 1, 2, ..., J; k = 1, 2, ... K. This enables the representation of every such triple by a single discrete variable, (αi, βj, θk) → xijk. Thereby, the strategy space is characterized by a single discrete variable taking I × J × K values and the method of response functions is feasible. We use it to show the following two results: 1) A two players quantum game with partially entangled initial state has a pure strategy Nash equilibrium. 2) A two player quantum Bayesian game with fully entangled initial state has a pure strategy Nash equilibrium.
This work concentrates on simultaneous move non-cooperating quantum games. Part of it is evidently not new, but it is included for the sake self consistence, as it is devoted to introduction of the mathematical and physical grounds of the pertinent topics, and the way in which a simple classical game is modified to become a quantum game (a procedure referred to as a quantization of a classical game). The connection between game theory and information science is briefly stressed, and the role of quantum entanglement (that plays a central role in the theory of quantum games), is exposed. Armed with these tools, we investigate some basic concepts like the existence (or absence) of a pure strategy and mixed strategy Nash equilibrium and its relation with the degree of entanglement. The main results of this work are as follows: 1) Construction of a numerical algorithm based on the method of best response functions, designed to search for pure strategy Nash equilibrium in quantum games. The formalism is based on the discretization of a continuous variable into a mesh of points, and can be applied to quantum games that are built upon two-players two-strategies classical games, based on the method of best response functions. 2) Application of this algorithm to study the question of how the existence of pure strategy Nash equilibrium is related to the degree of entanglement (specified by a continuous parameter γ ). It is shown that when the classical game GC has a pure strategy Nash equilibrium that is not Pareto efficient, then the quantum game GQ with maximal entanglement (γ = π/2) has no pure strategy Nash equilibrium. By studying a non-symmetric prisoner dilemma game, it is found that there is a critical value 0γc such that for γγc there is a pure strategy Nash equilibrium and for γ≥γc there is no pure strategy Nash equilibrium. The behavior of the two payoffs as function of γ starts at that of the classical ones at (D, D) and approaches the cooperative classical ones at (C, C) (C = confess, D = don’t confess). 3) We then study Bayesian quantum games and show that under certain conditions, there is a pure strategy Nash equilibrium in such games even when entanglement is maximal. 4) We define the basic ingredients of a quantum game based on a two-player three strategies classical game. This requires the introduction of trits (instead of bits) and quantum trits (instead of quantum bits). It is proved that in this quantum game, there is no classical commensurability in the sense that the classical strategies are not obtained as a special case of the quantum strategies.