Projected Variational Quantum Extragradient for Zero-Sum Games

Duong The Do, Matthew Aldridge, Duong Tung Nguyen · 2026

Read Projected Variational Quantum Extragradient for Zero-Sum Games by Duong The Do, Matthew Aldridge, Duong Tung Nguyen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-16466.txt.

Introduction

Do, Aldridge and Nguyen develop a quantum approach to near Nash equilibria in two-player zero-sum games. Mixed strategies become Born distributions of parameterized quantum circuits, turning the game into a smooth minmax problem. A dominated embedding maps games of any size to qubit-friendly power-of-two dimensions, preserving equilibrium structure. A projected extragradient method using shot-based estimates comes with variance bounds and near-stationarity convergence. Judged by Nash gap, it solved structured 32 by 32 games with high precision, though unstructured games stayed hard.

Catalog record

CREATORDuong The Do, Matthew Aldridge, Duong Tung Nguyen
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37610
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.16466

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Projected Variational Quantum Extragradient for Zero-Sum Games Duong The Do, Matthew Aldridge, Duong Tung Nguyen Abstract We propose a projected variational quantum extragradient (VQEG) framework for computing approximate Nash equilibria in two-player zero-sum matrix games. Mixed strategies are parameterized as Born distributions of parameterized quantum circuits (PQCs), transforming the classical bilinear saddle-point problem into a smooth but generally nonconvex–nonconcave min–max optimization in circuit-parameter space. The expected payoff is expressed as the expectation of a diagonal observable, enabling gradient evaluation via the parameter-shift rule and compatibility with shot-based quantum hardware. To support arbitrary game sizes, we introduce a dominated embedding that maps ( m , n ) (m,n) games to qubit-compatible power-of-two dimensions while preserving equilibrium structure. We then develop a projected extragradient method using stochastic gradient estimates derived from finite measurement shots, and establish variance bounds scaling as O ⁡ ( 1 / S ) O(1/S) with respect to the number of measurement shots S S , along with convergence to approximate first-order stationarity under standard assumptions. Since stationarity does not guarantee equilibrium optimality, we evaluate performance using the game-space Nash gap. Numerical results demonstrate high-precision solutions on structured instances up to 32 × 32 32\times 32 , while highlighting challenges in unstructured settings. I INTRODUCTION Two-player zero-sum games are a widely used model for competitive decision-making and arise in a wide range of applications, including cybersecurity [ 17 ] , adversarial machine learning [ 3 ] , robust control [ 11 ] , online learning and operations research [ 16 ] , and reinforcement learning for competitive multi-agent systems [ 18 ] . The central solution concept in these games is the Nash equilibrium (NE), which characterizes a strategy profile in which no player can improve its payoff through unilateral deviation [ 2 ] . In finite zero-sum games, NE always exist and correspond to minimax and maximin strategies [ 14 ] . This equivalence connects equilibrium computation with saddle-point optimization and motivates iterative methods for solving zero-sum games. Although equilibria in zero-sum games can be computed exactly via linear programming, many modern applications involve large-scale or oracle-based settings where direct methods become impractical. This has motivated the development of scalable first-order methods, including extragradient, mirror-prox, and optimistic gradient algorithms, which exploit the saddle-point structure and provide strong convergence guarantees [ 13 , 7 , 12 , 5 , 10 ] . In parallel, no-regret learning dynamics offer an alternative approach by interpreting equilibrium computation as repeated play [ 1 , 4 ] . There is also growing interest in last-iterate convergence to obtain stronger practical guarantees for equilibrium computation, since practical performance depends on the actual strategies generated by the algorithm rather than only on averaged iterates [ 1 , 10 , 6 ] . Also, residual-based methods that directly optimize equilibrium measures, such as the duality gap, have also been studied for approximating equilibria in zero-sum games [ 9 ] . These highlight the importance of designing scalable algorithms that can exploit problem structure while remaining practical for complex game settings. Despite these advances, most existing methods operate directly in the strategy space, which can become high-dimensional and computationally expensive. These challenges have motivated the study of alternative computational frameworks that can represent and optimize player strategies. In this work, we propose a variational quantum approach for finite two-player zero-sum games. Our approach leverages PQCs to represent mixed strategies via Born distributions, inducing a smooth mapping from circuit parameters to probability simplices [ 15 ] . Under this representation, the classical bilinear objective can be expressed as the expectation of a diagonal observable, leading to a parametric min–max optimization problem in circuit-parameter space. However, this transformation introduces nonlinearity, resulting in a generally nonconvex-nonconcave saddle-point problem. To address this challenge, we develop a projected variational quantum extragradient (VQEG) method that performs stable saddle-point updates in parameter space using parameter-shift gradient estimators compatible with shot-based quantum hardware. To enable qubit-compatible representations, we introduce a dominated embedding that maps arbitrary (m,n) games to power-of-two dimensions while preserving equilibrium structure. We further analyze the stochastic optimization process and establish convergence to approximate first-order stationarity under standard smoothness and bounded-variance assumptions. Since stationarity in parameter space does not necessarily imply equilibrium optimality in the original game, we evaluate the induced strategies using the game-space Nash gap as an empirical certificate. Our main contributions are summarized below. • We introduce a variational quantum parameterization of mixed strategies for zero-sum matrix games using PQC-induced Born distributions and the corresponding expected payoff is expressed in an observable form. • We develop an equilibrium-preserving dominated embedding that enables qubit-compatible representations of arbitrary game sizes. • We propose a variational quantum extragradient (VQEG) algorithm that updates the circuit parameters through a two-step extragradient procedure using parameter-shift gradient estimators, and we analyze the resulting circuit-evaluation and shot complexity. • We prove convergence to approximate first-order stationarity in parameter space under standard smoothness and bounded-variance assumptions, and we assess equilibrium in the original game space via the Nash gap. • Experimental results are conducted to validate the efficacy of the proposed VQEG framework. The rest of the paper is organized as follows. Section II reviews preliminaries on finite two-player zero-sum games and the equilibrium certificates used in this work. Section III presents the proposed VQEG method. Section IV provides the convergence analysis. Section V presents numerical results, and Section VI concludes the paper. II PRELIMINARIES: ZERO-SUM GAMES AND EQUILIBRIUM CERTIFICATES II-A Finite Zero-sum Games We consider a finite two-player zero-sum matrix game defined by a payoff matrix A\in\mathbb{R}^{m\times n} , where m and n denote the numbers of pure strategies (actions) available to the row player (Player 1) and the column player (Player 2), respectively. The column player’s payoff matrix is given by -A . Let \Delta_{s}:=\{p\in\mathbb{R}^{s}_{\geq 0}:\mathbf{1}^{\top}p=1\},s\in\left\{m,n\right\} denote the probability simplex. The players choose mixed strategies x\in\Delta_{m} and y\in\Delta_{n} , and the expected payoff to the row player is given by f(x,y)\;:=\;\left\langle x,Ay\right\rangle=x^{\top}Ay . It is easy to see that the function f(x,y) is bilinear and bounded between the minimum and maximum entries of A , i.e., we have: \displaystyle\min_{i\in[m],\,j\in[n]}A_{ij}\;\leq\;f(x,y)\;\leq\;\max_{i\in[m],\,j\in[n]}A_{ij}. (1) Definition II.1 (Nash equilibrium) . A strategy profile (x^{\star},y^{\star}) is an NE (equivalently, a saddle point) if: \displaystyle f(x^{\star},y)\geq f(x^{\star},y^{\star})\geq f(x,y^{\star}),\;\forall x\in\Delta_{m},\forall y\in\Delta_{n}. (2) By von Neumann’s minimax theorem, the game admits a value, given by: \displaystyle\max_{x\in\Delta_{m}}\min_{y\in\Delta_{n}}f(x,y)=\min_{y\in\Delta_{n}}\max_{x\in\Delta_{m}}f(x,y)=v^{\star}, (3) and every Nash equilibrium attains this value. Thus, computing equilibria in zero-sum games is equivalent to solving a saddle-point problem \max_{x\in\Delta_{m}}\min_{y\in\Delta_{n}}f(x,y) . II-B Approximate Equilibrium and Nash Gap For any strategy profile (x,y)\in\Delta_{m}\times\Delta_{n} , let \alpha(y)=\max_{x^{\prime}\in\Delta_{m}}\langle x^{\prime},Ay\rangle denote the row player’s best-response payoff against y and \beta(x)=\min_{y^{\prime}\in\Delta_{n}}\langle x,Ay^{\prime}\rangle be the column player’s best-response payoff against x . The unilateral deviation gains for the row and column players are given by: \displaystyle\delta_{\mathrm{r}}(x,y)\!=\!\alpha(y)\!-\!\left\langle x,Ay\right\rangle,\;\delta_{\mathrm{c}}(x,y)\!=\!\left\langle x,Ay\right\rangle\!-\!\beta(x), (4) where \delta_{\mathrm{r}}(x,y) is the maximum payoff improvement available to the row player by deviating from x while the column player keeps y fixed. Similarly, \delta_{\mathrm{c}}(x,y) is the maximum improvement available to the column player by deviating from y while the row player keeps x fixed. By weak minimax duality, for all (x,y) we have \beta(x)\leq v^{\star}\leq\alpha(y) . Definition II.2 (Nash gap) . For any (x,y)\in\Delta_{m}\times\Delta_{n} , the Nash gap (or duality gap) is defined as:

Read the complete text