# Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 58 references that are in the map.
- First posted on arXiv 27 Apr 2023.

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

- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [Variance Reduction for Matrix Games](https://mlsanity.com/paper/1907.02056/) (2019)
- [Online Learning of Quantum States](https://mlsanity.com/paper/1802.09025/) (2018)
- [Quantum Perceptron Models](https://mlsanity.com/paper/1602.04799/) (2016)
- [Quantum SDP-Solvers: Better upper and lower bounds](https://mlsanity.com/paper/1705.01843/) (2017)
- [Sublinear quantum algorithms for training linear and kernel-based classifiers](https://mlsanity.com/paper/1904.02276/) (2019)
- [Faster Matrix Multiplication via Asymmetric Hashing](https://mlsanity.com/paper/2210.10173/) (2022)
- [A Quantum Interior Point Method for LPs and SDPs](https://mlsanity.com/paper/1808.09266/) (2018)
- [Adaptive Online Learning of Quantum States](https://mlsanity.com/paper/2206.00220/) (2022)
- [Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergence](https://mlsanity.com/paper/2210.12812/) (2022)
- [Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling](https://mlsanity.com/paper/2301.03763/) (2023)
- [More Practical and Adaptive Algorithms for Online Quantum State Learning](https://mlsanity.com/paper/2006.01013/) (2020)
- [Preparing Many Copies of a Quantum State in the Black-Box Model](https://mlsanity.com/paper/2207.11014/) (2022)

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

- [Quantum Langevin Dynamics for Optimization](https://mlsanity.com/paper/2311.15587/) (2023)
- [Payoff-based learning with matrix multiplicative weights in quantum games](https://mlsanity.com/paper/2311.02423/) (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 propose the first online quantum algorithm for solving zero-sum games with widetilde O(1) regret under the game setting. Moreover, our quantum algorithm computes an varepsilon-approximate Nash equilibrium of an m × n matrix zero-sum game in quantum time widetilde O(√m+n/varepsilon2.5). Our algorithm uses standard quantum inputs and generates classical outputs with succinct descriptions, facilitating end-to-end applications. Technically, our online quantum algorithm "quantizes" classical algorithms based on the optimistic multiplicative weight update method. At the heart of our algorithm is a fast quantum multi-sampling procedure for the Gibbs sampling problem, which may be of independent interest.