Projected Variational Quantum Extragradient for Zero-Sum Games

1. Problem Statement

The paper addresses the computational challenge of finding Nash Equilibria (NE) in finite two-player zero-sum matrix games. While classical methods (like Linear Programming) can solve these exactly, they become impractical for large-scale or oracle-based settings. Furthermore, modern applications often require scalable, first-order iterative methods.

The authors propose a Variational Quantum approach to solve these games. The core challenge is that representing classical mixed strategies (probability distributions) using quantum circuits transforms the original bilinear saddle-point problem (which is convex-concave) into a smooth but generally nonconvex–nonconcave min-max optimization problem in the space of circuit parameters. Additionally, quantum hardware constraints (qubit counts) require mapping arbitrary game dimensions $(m, n)$ to power-of-two dimensions without distorting the equilibrium structure.

2. Methodology

The proposed framework, Projected Variational Quantum Extragradient (VQEG), consists of four main technical components:

A. Equilibrium-Preserving Dominated Embedding

To handle arbitrary game sizes $(m, n)$ on quantum hardware (which requires dimensions $M, N$ to be powers of two, i.e., $2^q$), the authors introduce a dominated embedding:

• The original payoff matrix $A \in \mathbb{R}^{m \times n}$ is embedded into a larger matrix $\tilde{A} \in \mathbb{R}^{M \times N}$ where $M=2^{\lceil \log_2 m \rceil}$ and $N=2^{\lceil \log_2 n \rceil}$.
• Mechanism: Extra "dummy" actions are added. For row player actions $i > m$, the payoff is set to $-C$ (where $C > \|A\|_\infty$); for column player actions $j > n$, the payoff is $+C$.
• Result: These dummy actions are strictly dominated. Theoretical proof shows that in any Nash Equilibrium of the embedded game, the probability of playing a dummy action is zero. Thus, the equilibrium of the embedded game maps exactly back to the original game.

B. Variational Quantum Parameterization

Mixed strategies are parameterized using Parameterized Quantum Circuits (PQCs):

• Representation: Each player's strategy is a Born distribution generated by a unitary circuit ($U_\theta$ for the row player, $V_\phi$ for the column player) acting on $|0\rangle$.
• Ansatz: A hardware-efficient ansatz is used, consisting of alternating layers of single-qubit rotations ($R_y, R_z$) and nearest-neighbor entangling gates ($CZ$).
• Objective Function: The classical bilinear payoff $f(x, y) = x^T A y$ is re-expressed as the expectation value of a diagonal observable:
  $$L(\theta, \phi) = \text{Tr}(\rho_\theta D(y_\phi)) = \langle x_\theta, \tilde{A} y_\phi \rangle$$
  This transforms the game into a parametric min-max problem: $\max_\theta \min_\phi L(\theta, \phi)$.

C. Gradient Estimation via Parameter-Shift Rule

Since the objective is non-differentiable in the classical sense regarding quantum measurements, gradients are estimated using the parameter-shift rule:

• The partial derivative with respect to a parameter $\theta_k$ is calculated as:
  $$\frac{\partial L}{\partial \theta_k} = \frac{1}{2} \left( L(\theta_k^+, \phi) - L(\theta_k^-, \phi) \right)$$
  where $\theta_k^\pm = \theta_k \pm \frac{\pi}{2}$.
• Shot-Based Estimation: The expectation values are estimated using $S$ measurement shots. The authors prove that the resulting gradient estimator is unbiased and that the variance scales as $O(1/S)$.

D. Projected Extragradient Algorithm

To solve the nonconvex–nonconcave saddle-point problem, the authors employ a Projected Extragradient method:

1. Predictor Step: Compute a tentative update using the current stochastic gradient estimate $\hat{G}(\omega_t)$.
2. Corrector Step: Evaluate the gradient at the predictor point and perform the final update.
3. Projection: Both steps are projected onto a bounded convex set $W$ to ensure stability.
4. Algorithm: The process iterates until convergence, outputting the circuit parameters which define the strategies.

3. Key Contributions

1. Variational Quantum Formulation: Introduced a method to parameterize mixed strategies via PQC-induced Born distributions, converting the game matrix problem into a parametric min-max optimization.
2. Dominated Embedding: Developed a novel embedding technique that maps arbitrary $(m, n)$ games to qubit-compatible dimensions while mathematically guaranteeing that the equilibrium structure is preserved (dummy actions receive zero probability).
3. VQEG Algorithm: Proposed a specific extragradient algorithm tailored for quantum hardware, utilizing parameter-shift gradients and handling shot noise.
4. Convergence Analysis: Proved convergence to approximate first-order stationarity in the parameter space under standard smoothness and bounded-variance assumptions. The analysis establishes that the variance of the gradient estimator scales as $O(1/S)$.
5. Equilibrium Certification: Recognized that stationarity in parameter space does not guarantee a Nash Equilibrium in the original game space. Therefore, the authors evaluate performance using the Nash Gap (duality gap) as an empirical certificate of optimality.

4. Numerical Results

The authors evaluated VQEG on structured and unstructured games of sizes up to $32 \times 32$:

• Structured Instances (Dominant-Row & Matching Pennies):
  • VQEG achieved high-precision solutions with Nash gaps often approaching numerical precision ($10^{-10}$ to $10^{-16}$).
  • The algorithm demonstrated stable last-iterate convergence (the final strategy is close to equilibrium, not just the average).
  • "Leakage" to dummy actions was negligible ($\approx 10^{-16}$), confirming the validity of the embedding.
• Unstructured Instances (Random Games):
  • Performance was mixed. While VQEG often satisfied the $\epsilon$-equilibrium criterion ($\epsilon = 5 \times 10^{-3}$), the Nash gaps were larger compared to structured games.
  • Performance degraded as problem size increased, highlighting challenges related to circuit expressivity and stochastic noise in unstructured settings.
• Comparison: The method outperformed entropy-regularized variants in larger scales, maintaining stability where others degraded.

5. Significance

• Bridging Game Theory and Quantum Computing: This work provides a rigorous framework for applying near-term quantum devices (NISQ) to classical game-theoretic problems, moving beyond simple toy examples to structured matrix games.
• Handling Nonconvexity: It addresses the inherent nonconvexity introduced by quantum parameterization, offering a stable optimization algorithm (Extragradient) specifically adapted for quantum gradients.
• Scalability: The dominated embedding technique solves the critical issue of mapping arbitrary problem sizes to quantum hardware constraints without altering the game's solution.
• Practical Validation: By using the Nash Gap as a metric, the paper moves beyond theoretical convergence in parameter space to practical verification of equilibrium quality, demonstrating that quantum variational methods can achieve high precision on structured problems up to $32 \times 32$.

Conclusion: The paper establishes VQEG as a viable, theoretically grounded, and experimentally validated approach for computing Nash Equilibria in zero-sum games using variational quantum circuits, particularly excelling in structured environments while identifying specific challenges for unstructured, large-scale random games.