We propose a projected variational quantum extragradient framework for computing approximate Nash equilibria in two-player zero-sum matrix games. Mixed strategies are parameterized as Born distributions of parameterized quantum circuits, transforming the classical bilinear saddle-point problem into a smooth but generally nonconvex-nonconcave problem in circuit-parameter space. To support arbitrary game sizes, we introduce a dominated embedding that maps$({m},{n})$games to qubit-compatible power-of-two dimensions while preserving equilibrium structure. We develop a projected extragradient method using parameter-shift gradient estimators and establish variance bounds scaling as${O}({1}/{S})$with the number of measurement shots$S$, together with convergence to approximate first-order stationarity under standard assumptions. Since stationarity does not necessarily imply equilibrium optimality, performance is evaluated using the game-space Nash gap. Numerical results show high-precision equilibrium computation on structured instances up to${32} \times {32}$, while highlighting challenges in unstructured settings.
We propose a projected variational quantum extragradient framework for computing approximate Nash equilibria in two-player zero-sum matrix games. Mixed strategies are parameterized as Born distributions of parameterized quantum circuits, transforming the classical bilinear saddle-point problem into a smooth but generally nonconvex-nonconcave problem in circuit-parameter space. To support arbitrary game sizes, we introduce a dominated embedding that maps(m,n)games to qubit-compatible power-of-two dimensions while preserving equilibrium structure. We develop a projected extragradient method using parameter-shift gradient estimators and establish variance bounds scaling asO(1/S)with the number of measurement shotsS, together with convergence to approximate first-order stationarity under standard assumptions. Since stationarity does not necessarily imply equilibrium optimality, performance is evaluated using the game-space Nash gap. Numerical results show high-precision equilibrium computation on structured instances up to32×32, while highlighting challenges in unstructured settings.
We derive sublinear-time quantum algorithms for computing the Nash equilibrium of two-player zero-sum games, based on efficient Gibbs sampling methods. We are able to achieve speed-ups for both dense and sparse payoff matrices at the cost of a mildly increased dependence on the additive error compared to classical algorithms. In particular we can find ε-approximate Nash equilibrium strategies in complexity O~(n+m/ε3) and O~(s/ε3.5) respectively, where n×m is the size of the matrix describing the game and s is its sparsity. Our algorithms use the LP formulation of the problem and apply techniques developed in recent works on quantum SDP-solvers. We also show how to reduce general LP-solving to zero-sum games, resulting in quantum LP-solvers that have complexities O~(n+mγ3) and O~(sγ3.5) for the dense and sparse access models respectively, where γ is the relevant "scale-invariant" precision parameter
Recent developments in domains such as non-local games, quantum interactive proofs, and quantum generative adversarial networks have renewed interest in quantum game theory and, specifically, quantum zero-sum games. Central to classical game theory is the efficient algorithmic computation of Nash equilibria, which represent optimal strategies for both players. In 2008, Jain and Watrous proposed the first classical algorithm for computing equilibria in quantum zero-sum games using the Matrix Multiplicative Weight Updates (MMWU) method to achieve a convergence rate of O(d/ϵ2) iterations to ϵ -Nash equilibria in the 4d -dimensional spectraplex. In this work, we propose a hierarchy of quantum optimization algorithms that generalize MMWU via an extra-gradient mechanism. Notably, within this proposed hierarchy, we introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as O(d/ϵ) iterations to ϵ -Nash equilibria. This quadratic speed-up relative to Jain and Watrous' original algorithm sets a new benchmark for computing ϵ -Nash equilibria in quantum zero-sum games.
Strategic decision-making among many agents under incomplete information is central to economics, security, and multi-agent artificial intelligence (AI). Computing equilibria in such settings is challenging because the joint type-action space grows exponentially with the number of players. In binary-type, binary-action Bayesian games with n players, an explicit representation over type-action profiles requires O(22n) entries, making direct linear-programming (LP) formulations increasingly costly as n grows. We propose a hybrid quantum-classical framework for approximating Bayes correlated equilibrium (BCE) using a parameterized quantum circuit (PQC). The PQC represents the conditional distribution over joint actions using O(nL) trainable parameters, where L denotes the circuit depth; for the largest trained setting, n=8 and L=2, this corresponds to 48 trainable angles. Each player count is trained independently by maximizing expected social welfare with a penalty on positive aggregated BCE obedience violations. On a strategically coupled Bayesian congestion game with n=2,4,6,8 players, feasible PQC solutions attain higher welfare than MCCFR and DCFR product-strategy baselines while satisfying εmax≤10−3, where εmax denotes the maximum positive aggregated BCE obedience violation. Across five independent runs per setting, all runs are feasible for n=2,4,6, while four of five are feasible for n=8. PQC welfare remains below the exact LP optimum, with the absolute gap increasing with n, while classical state-vector simulation prevents PQC training beyond eight players. These results demonstrate the use of a compact PQC parameterization for approximate equilibrium computation and quantify its welfare, feasibility, and classical simulation scaling on the studied benchmark.
Computing Nash equilibria of zero-sum games in classical and quantum settings is extensively studied. For general-sum games, computing Nash equilibria is PPAD-hard and the computing of a more general concept called correlated equilibria has been widely explored in game theory. In this paper, we initiate the study of quantum algorithms for computing ε-approximate correlated equilibria (CE) and coarse correlated equilibria (CCE) in multi-player normal-form games. Our approach utilizes quantum improvements to the multi-scale Multiplicative Weight Update (MWU) method for CE calculations, achieving a query complexity of O~(mn) for fixed ε. For CCE, we extend techniques from quantum algorithms for zero-sum games to multi-player settings, achieving query complexity O~(mn/ε2.5). Both algorithms demonstrate a near-optimal scaling in the number of players m and actions n, as confirmed by our quantum query lower bounds.
Nash equilibrium (NE) computation is a fundamental problem in game theory, with numerous applications in economics, control theory, computer science, and engineering. However, finding an NE remains computationally challenging, even in two-player normal-form games. In this work, we leverage quantum computing (QC) to develop an efficient quantum annealing-based algorithm for computing NEs in two-player non-cooperative games. Our approach exploits quantum parallelism to enhance computational efficiency. We first formulate the NE computation as a non-convex quadratic problem, which is then transformed into a quadratic unconstrained binary optimization (QUBO) problem through the use of penalization techniques. This reformulation is amenable to quantum annealing solvers. However, due to the probabilistic nature of quantum annealing, the solver typically returns a distribution of candidate solutions, which may not directly correspond to valid NEs. To address this, we propose a novel QA-assisted algorithm that incorporates a post-quantum processing step to refine, verify, and select approximate NEs from the sampled solutions. The effectiveness of the proposed algorithm is demonstrated through experimental validation, highlighting the potential of QC in solving complex equilibrium computation problems.
We give a quantum algorithm for computing an ε-approximate Nash equilibrium of a zero-sum game in a m×n payoff matrix with bounded entries. Given a standard quantum oracle for accessing the payoff matrix our algorithm runs in time O(m+n⋅ε−2.5+ε−3) and outputs a classical representation of the ε-approximate Nash equilibrium. This improves upon the best prior quantum runtime of O(m+n⋅ε−3) obtained by [vAG19] and the classic O((m+n)⋅ε−2) runtime due to [GK95] whenever ε=Ω((m+n)−1). We obtain this result by designing new quantum data structures for efficiently sampling from a slowly-changing Gibbs distribution.