[edit]
Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:2932-2952, 2023.
Abstract
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 ˜O(√m+n⋅ϵ−2.5+ϵ−3) and outputs a classical representation of the ϵ-approximate Nash equilibrium. This improves upon the best prior quantum runtime of ˜O(√m+n⋅ϵ−3) obtained by [van Apeldoorn, Gilyen ’19] and the classical ˜O((m+n)⋅ϵ−2) runtime due to [Grigoradis, Khachiyan ’95] whenever ϵ=Ω((m+n)−1). We obtain this result by designing new quantum data structures for efficiently sampling from a slowly-changing Gibbs distribution.