Projected Variational Quantum Extragradient for Zero-Sum Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914485182136320 |
|---|---|
| author | Do, Duong The Aldridge, Matthew Nguyen, Duong Tung |
| author_facet | Do, Duong The Aldridge, Matthew Nguyen, Duong Tung |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_16466 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Projected Variational Quantum Extragradient for Zero-Sum Games Do, Duong The Aldridge, Matthew Nguyen, Duong Tung Systems and Control Computer Science and Game Theory 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. |
| title | Projected Variational Quantum Extragradient for Zero-Sum Games |
| topic | Systems and Control Computer Science and Game Theory |
| url | https://arxiv.org/abs/2604.16466 |