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

We give a quantum algorithm for computing an \(\epsilon\)-approximate Nash equilibrium of a zero-sum game in a \(m\times n\) payoff matrix with bounded entries. Given a standard quantum oracle for accessing the payoff matrix our algorithm runs in time \(O_˜(\sqrt{√}\sqrt{m+n}\cdot {\epsilon }_{-2.5}+{\epsilon }_{-3})\) and outputs a classical representation of the \(\epsilon\)-approximate Nash equilibrium. This improves upon the best prior quantum runtime of \(O_˜(\sqrt{√}\sqrt{m+n}\cdot {\epsilon }_{-3})\)obtained by [vAG19] and the classic \(O_˜((m+n)\cdot {\epsilon }_{-2})\) runtime due to [GK95] whenever \(\epsilon =\Omega ((m+n)_{-1})\). We obtain this result by designing new quantum data structures for efficiently sampling from a slowly-changing Gibbs distribution.