# Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jan 2023.

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

- [Quantum Langevin Dynamics for Optimization](https://mlsanity.com/paper/2311.15587/) (2023)
- [Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games](https://mlsanity.com/paper/2304.14197/) (2023)
- [Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11684/) (2023)
- [Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities](https://mlsanity.com/paper/2507.04438/) (2025)
- [Gradient Testing and Estimation by Comparisons](https://mlsanity.com/paper/2405.11454/) (2024)
- [Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent](https://mlsanity.com/paper/2411.03925/) (2024)
- [Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games](https://mlsanity.com/paper/2510.16782/) (2025)

## Abstract (arXiv)

We give a quantum algorithm for computing an ε-approximate Nash equilibrium of a zero-sum game in a m × n payoff matrix with bounded entries. Given a standard quantum oracle for accessing the payoff matrix our algorithm runs in time widetildeO(√m + n· ε-2.5 + ε-3) and outputs a classical representation of the ε-approximate Nash equilibrium. This improves upon the best prior quantum runtime of widetildeO(√m + n · ε-3) obtained by [vAG19] and the classic widetildeO((m + n) · ε-2) runtime due to [GK95] whenever ε = Omega((m +n)-1). We obtain this result by designing new quantum data structures for efficiently sampling from a slowly-changing Gibbs distribution.