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

arXiv: https://arxiv.org/abs/2311.10859 · HTML: https://mlsanity.com/paper/2311.10859/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 31 references that are in the map.
- First posted on arXiv 17 Nov 2023.

## Builds on (most cited first, 7 of 7)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates](https://mlsanity.com/paper/1506.04838/) (2015)
- [Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence](https://mlsanity.com/paper/2010.07799/) (2020)
- [No-Regret Learning and Equilibrium Computation in Quantum Games](https://mlsanity.com/paper/2310.08473/) (2023)
- [Learning in Quantum Common-Interest Games and the Separability Problem](https://mlsanity.com/paper/2302.04789/) (2023)
- [Quantum Advantage from Any Non-Local Game](https://mlsanity.com/paper/2203.15877/) (2022)

## Built on by (most cited first, 4 of 4)

- [Optimistic Online Learning in Symmetric Cone Games](https://mlsanity.com/paper/2504.03592/) (2025)
- [Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games](https://mlsanity.com/paper/2510.16782/) (2025)
- [Coherent Swap Regret and Channel-Proof Learning](https://mlsanity.com/paper/2606.02655/) (2026)
- [Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games](https://mlsanity.com/paper/2609.38835/) (2026)

## Abstract (arXiv)

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.