Abstract

We propose the first online quantum algorithm for solving zero-sum games with$\widetilde O(1)$ regret under the game setting. Moreover, our quantumalgorithm computes an $\varepsilon$-approximate Nash equilibrium of an $m\times n$ matrix zero-sum game in quantum time $\widetildeO(\sqrt{m+n}/\varepsilon^{2.5})$. Our algorithm uses standard quantum inputsand generates classical outputs with succinct descriptions, facilitatingend-to-end applications. Technically, our online quantum algorithm "quantizes"classical algorithms based on the optimistic multiplicative weight updatemethod. At the heart of our algorithm is a fast quantum multi-samplingprocedure for the Gibbs sampling problem, which may be of independent interest.

 

Quick Read (beta)