mlsanityData to 14 Oct 2026

Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games

arXiv 2304.14197 ↗First posted 27 Apr 2023quant-ph cs.LG math.OCcited by 6

Not on the map. Why?

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.

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

20 of 58 references.

References · 20

  1. 2018Supervised learning with quantum enhanced feature spacescited by 665
  2. 2017Training GANs with Optimismcited by 217
  3. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  4. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  5. 2016Quantum Recommendation Systemscited by 70
  6. 2020A Refined Laser Method and Faster Matrix Multiplicationcited by 56
  7. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  8. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  9. 2019Variance Reduction for Matrix Gamescited by 38
  10. 2018Online Learning of Quantum Statescited by 37
  11. 2016Quantum Perceptron Modelscited by 28
  12. 2017Quantum SDP-Solvers: Better upper and lower boundscited by 27
8 more
  1. 2019Sublinear quantum algorithms for training linear and kernel-based classifierscited by 19
  2. 2022Faster Matrix Multiplication via Asymmetric Hashingcited by 19
  3. 2018A Quantum Interior Point Method for LPs and SDPscited by 17
  4. 2022Adaptive Online Learning of Quantum Statescited by 12
  5. 2022Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergencecited by 8
  6. 2023Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Samplingcited by 7
  7. 2020More Practical and Adaptive Algorithms for Online Quantum State Learningcited by 3
  8. 2022Preparing Many Copies of a Quantum State in the Black-Box Modelcited by 2

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 2; 2025: 2.

6 papers.

  1. 2023Quantum Langevin Dynamics for Optimizationcited by 7
  2. 2023Payoff-based learning with matrix multiplicative weights in quantum gamescited by 2
  3. 2025Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexitiescited by 2
  4. 2024Gradient Testing and Estimation by Comparisonscited by 0
  5. 2024Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descentcited by 0
  6. 2025Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Gamescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model
  2. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model
  3. 2021Quantum Algorithms for Reinforcement Learning with a Generative Model
  4. 2023Multi-Armed Bandits and Quantum Channel Oracles
  5. 2026Reinforcement learning for quantum processes with memory
  6. 2024Quantum framework for Reinforcement Learning: Integrating Markov decision process, quantum arithmetic, and trajectory search
  7. 2026High-Probability Nash Regret for Decentralized Learning in Markov α-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
  8. 2024widetildeO(T-1) Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Games