Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.16466 · IEEE Control Systems Letters

Projected Variational Quantum Extragradient for Zero-Sum Games

Duong The Do, Matthew Aldridge, Duong Tung Nguyen

Published Jan 1, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/lcsys.2026.3710797

Related papers

Quantum algorithms for zero-sum games

Joran van Apeldoorn, András Gilyén

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 $\varepsilon$-approximate Nash equilibrium strategies in complexity $\tilde{O}(\sqrt{n+m}/\varepsilon^3)$ and $\tilde{O}(\sqrt{s}/\varepsilon^{3.5})$ respectively, where $n\times 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 $\tilde{O}(\sqrt{n+m}γ^3)$ and $\tilde{O}(\sqrt{s}γ^{3.5})$ for the dense and sparse access models respectively, where $γ$ is the relevant "scale-invariant" precision parameter

arXiv:1904.03180•Apr 5, 2019•60 citations

A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games

Francisca Vasconcelos, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos +2 more

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.

arXiv:2311.10859•Quantum•May 6, 2025•5 citations

Game, Set, Quantum: Parameterized Quantum Circuit for Correlated Equilibrium in Bayesian Games

Param Pathak, Vidhi Oad, Nouhaila Innan +2 more

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(2^{2n})$ 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}\leq10^{-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.

quant-pharXiv:2606.03109•Jun 3, 2026•0 citations

Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games

Tongyang Li, Xinzhao Wang, Yexin Zhang

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 $\varepsilon$-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 $\tilde{O}(m\sqrt{n})$ for fixed $\varepsilon$. For CCE, we extend techniques from quantum algorithms for zero-sum games to multi-player settings, achieving query complexity $\tilde{O}(m\sqrt{n}/\varepsilon^{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.

arXiv:2510.16782•neural information processing systems•Jan 1, 2025•0 citations

Quantum-Assisted Computation for Nash Equilibrium in Bimatrix Games

Duong The Do, Duong Tung Nguyen

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.

•Feb 27, 2026•0 citations

Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling

Adam Bouland, Yosheb Getachew, Yujia Jin +2 more

We give a quantum algorithm for computing an $ε$-approximate Nash equilibrium of a zero-sum game in a $m \times n$ payoff matrix with bounded entries. Given a standard quantum oracle for accessing the payoff matrix our algorithm runs in time $\widetilde{O}(\sqrt{m + n}\cdot ε^{-2.5} + ε^{-3})$ and outputs a classical representation of the $ε$-approximate Nash equilibrium. This improves upon the best prior quantum runtime of $\widetilde{O}(\sqrt{m + n} \cdot ε^{-3})$ obtained by [vAG19] and the classic $\widetilde{O}((m + n) \cdot ε^{-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.

arXiv:2301.03763•Jan 10, 2023•9 citations
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)({m},{n})(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){O}({1}/{S})O(1/S)with the number of measurement shotsSSS, 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{32} \times {32}32×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 ε\varepsilonε-approximate Nash equilibrium strategies in complexity O~(n+m/ε3)\tilde{O}(\sqrt{n+m}/\varepsilon^3)O~(n+m​/ε3) and O~(s/ε3.5)\tilde{O}(\sqrt{s}/\varepsilon^{3.5})O~(s​/ε3.5) respectively, where n×mn\times mn×m is the size of the matrix describing the game and sss 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)\tilde{O}(\sqrt{n+m}γ^3)O~(n+m​γ3) and O~(sγ3.5)\tilde{O}(\sqrt{s}γ^{3.5})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 nnn players, an explicit representation over type-action profiles requires O(22n)O(2^{2n})O(22n) entries, making direct linear-programming (LP) formulations increasingly costly as nnn 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)O(nL)O(nL) trainable parameters, where LLL denotes the circuit depth; for the largest trained setting, n=8n=8n=8 and L=2L=2L=2, this corresponds to 484848 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,8n=2,4,6,8n=2,4,6,8 players, feasible PQC solutions attain higher welfare than MCCFR and DCFR product-strategy baselines while satisfying εmax⁡≤10−3ε_{\max}\leq10^{-3}εmax​≤10−3, where εmax⁡ε_{\max}εmax​ denotes the maximum positive aggregated BCE obedience violation. Across five independent runs per setting, all runs are feasible for n=2,4,6n=2,4,6n=2,4,6, while four of five are feasible for n=8n=8n=8. PQC welfare remains below the exact LP optimum, with the absolute gap increasing with nnn, 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 ε\varepsilonε-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)\tilde{O}(m\sqrt{n})O~(mn​) for fixed ε\varepsilonε. For CCE, we extend techniques from quantum algorithms for zero-sum games to multi-player settings, achieving query complexity O~(mn/ε2.5)\tilde{O}(m\sqrt{n}/\varepsilon^{2.5})O~(mn​/ε2.5). Both algorithms demonstrate a near-optimal scaling in the number of players mmm and actions nnn, 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×nm \times nm×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)\widetilde{O}(\sqrt{m + n}\cdot ε^{-2.5} + ε^{-3})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)\widetilde{O}(\sqrt{m + n} \cdot ε^{-3})O(m+n​⋅ε−3) obtained by [vAG19] and the classic O~((m+n)⋅ε−2)\widetilde{O}((m + n) \cdot ε^{-2})O((m+n)⋅ε−2) runtime due to [GK95] whenever ε=Ω((m+n)−1)ε= Ω((m +n)^{-1})ε=Ω((m+n)−1). We obtain this result by designing new quantum data structures for efficiently sampling from a slowly-changing Gibbs distribution.