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 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.