Projected Variational Quantum Extragradient for Zero-Sum Games
This work addresses the problem of solving zero-sum games using quantum computing, offering a variational quantum approach that can handle larger game sizes than previous quantum methods, though it is incremental in nature.
The paper proposes a projected variational quantum extragradient (VQEG) framework for computing approximate Nash equilibria in two-player zero-sum matrix games, achieving high-precision solutions on structured instances up to 32x32, but facing challenges in unstructured settings.
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 minmax 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) 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) with respect to the number of measurement shots 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 32x32, while highlighting challenges in unstructured settings.