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

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 [vAG19] and the classic O˜((m+n)⋅ϵ−2) runtime due to [GK95] whenever ϵ=Ω((m+n)−1). We obtain this result by designing new quantum data structures for efficiently sampling from a slowly-changing Gibbs distribution.