# Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 38 references that are in the map.
- First posted on arXiv 19 Oct 2025.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games](https://mlsanity.com/paper/2204.11417/) (2022)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [Sublinear quantum algorithms for training linear and kernel-based classifiers](https://mlsanity.com/paper/1904.02276/) (2019)
- [Faster Rates for No-Regret Learning in General Games via Cautious Optimism](https://mlsanity.com/paper/2503.24340/) (2025)
- [Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling](https://mlsanity.com/paper/2301.03763/) (2023)
- [Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Games](https://mlsanity.com/paper/2506.05005/) (2025)
- [Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrence](https://mlsanity.com/paper/2211.01681/) (2022)
- [Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games](https://mlsanity.com/paper/2304.14197/) (2023)
- [No-Regret Learning and Equilibrium Computation in Quantum Games](https://mlsanity.com/paper/2310.08473/) (2023)
- [Learning in quantum games](https://mlsanity.com/paper/2302.02333/) (2023)
- [A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games](https://mlsanity.com/paper/2311.10859/) (2023)

## Abstract (arXiv)

Computing Nash equilibria of zero-sum games in classical and quantum settings is extensively studied. For general-sum games, computing Nash equilibria is PPAD-hard and the computing of a more general concept called correlated equilibria has been widely explored in game theory. In this paper, we initiate the study of quantum algorithms for computing varepsilon-approximate correlated equilibria (CE) and coarse correlated equilibria (CCE) in multi-player normal-form games. Our approach utilizes quantum improvements to the multi-scale Multiplicative Weight Update (MWU) method for CE calculations, achieving a query complexity of tildeO(m√n) for fixed varepsilon. For CCE, we extend techniques from quantum algorithms for zero-sum games to multi-player settings, achieving query complexity tildeO(m√n/varepsilon2.5). Both algorithms demonstrate a near-optimal scaling in the number of players m and actions n, as confirmed by our quantum query lower bounds.