Maximum entropy inference is a widely used method in machine learning, particularly in the context of graphical models (McCallum et al., 2000; Kindermann & Snell, 1980; Ackley et al., 1985; Bresler, 2015; Hamilton et al., 2017) and natural language processing (Berger et al., 1996). In graphical models, it is known as the backward mapping, the problem of computing the model parameters from the marginal information (Wainwright & Jordan, 2007). The inverse problem of estimating marginal parameters from the model parameters is called the forward mapping. Maximum entropy inference is also a core concept in statistical physics (Jaynes, 1957) known as the Jaynes' principle which links statistical mechanics and information theory. The Hammersley-Clifford theorem establishes that, in the classical case, any positive probability distribution satisfying the local Markov property can be represented as a Gibbs distribution (Lafferty et al., 2001).

We propose the first online quantum algorithm for zero-sum games with $\tilde O(1)$ regret under the game setting. Moreover, our quantum algorithm computes an $\varepsilon$-approximate Nash equilibrium of an $m \times n$ matrix zero-sum game in quantum time $\tilde O(\sqrt{m+n}/\varepsilon^{2.5})$, yielding a quadratic improvement over classical algorithms in terms of $m, n$. Our algorithm uses standard quantum inputs and generates classical outputs with succinct descriptions, facilitating end-to-end applications. As an application, we obtain a fast quantum linear programming solver. 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.