Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games

We propose the first online quantum algorithm for solving zero-sum games with $\tilde{O}(1)$ regret under the game setting. Moreover, our quantum algorithm computes an $\epsilon$-approximate Nash equilibrium of an $m\times n$ matrix zero-sum game in quantum time $\tilde{O}(\sqrt{m+n}\mathrm{/}{\epsilon }^{2.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.