Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2510.16782 · neural information processing systems

Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games

Tongyang Li, Xinzhao Wang, Yexin Zhang

Published Jan 1, 2025• 0 citations
arXivHTMLPDF

Abstract

Computing Nash equilibria of zero-sum games in classical and quantum settings is extensively studied. For general-sum games, computing Nash equilibria is PPAD-hard and the computing of a more general concept called correlated equilibria has been widely explored in game theory. In this paper, we initiate the study of quantum algorithms for computing $\varepsilon$-approximate correlated equilibria (CE) and coarse correlated equilibria (CCE) in multi-player normal-form games. Our approach utilizes quantum improvements to the multi-scale Multiplicative Weight Update (MWU) method for CE calculations, achieving a query complexity of $\tilde{O}(m\sqrt{n})$ for fixed $\varepsilon$. For CCE, we extend techniques from quantum algorithms for zero-sum games to multi-player settings, achieving query complexity $\tilde{O}(m\sqrt{n}/\varepsilon^{2.5})$. Both algorithms demonstrate a near-optimal scaling in the number of players $m$ and actions $n$, as confirmed by our quantum query lower bounds.

DOI
10.52202/085713-2544

Related papers

No-Regret Learning and Equilibrium Computation in Quantum Games

Wayne Lin, Georgios Piliouras, Ryann Sim +1 more

As quantum processors advance, the emergence of large-scale decentralized systems involving interacting quantum-enabled agents is on the horizon. Recent research efforts have explored quantum versions of Nash and correlated equilibria as solution concepts of strategic quantum interactions, but these approaches did not directly connect to decentralized adaptive setups where agents possess limited information. This paper delves into the dynamics of quantum-enabled agents within decentralized systems that employ no-regret algorithms to update their behaviors over time. Specifically, we investigate two-player quantum zero-sum games and polymatrix quantum zero-sum games, showing that no-regret algorithms converge to separable quantum Nash equilibria in time-average. In the case of general multi-player quantum games, our work leads to a novel solution concept, that of the separable quantum coarse correlated equilibria (QCCE), as the convergent outcome of the time-averaged behavior no-regret algorithms, offering a natural solution concept for decentralized quantum systems. Finally, we show that computing QCCEs can be formulated as a semidefinite program and establish the existence of entangled (i.e., non-separable) QCCEs, which are unlearnable via the current paradigm of no-regret learning.

arXiv:2310.08473•Quantum•Dec 17, 2024•4 citations

A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games

Francisca Vasconcelos, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos +2 more

Recent developments in domains such as non-local games, quantum interactive proofs, and quantum generative adversarial networks have renewed interest in quantum game theory and, specifically, quantum zero-sum games. Central to classical game theory is the efficient algorithmic computation of Nash equilibria, which represent optimal strategies for both players. In 2008, Jain and Watrous proposed the first classical algorithm for computing equilibria in quantum zero-sum games using the Matrix Multiplicative Weight Updates (MMWU) method to achieve a convergence rate of O(d/ϵ2) iterations to ϵ -Nash equilibria in the 4d -dimensional spectraplex. In this work, we propose a hierarchy of quantum optimization algorithms that generalize MMWU via an extra-gradient mechanism. Notably, within this proposed hierarchy, we introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as O(d/ϵ) iterations to ϵ -Nash equilibria. This quadratic speed-up relative to Jain and Watrous' original algorithm sets a new benchmark for computing ϵ -Nash equilibria in quantum zero-sum games.

arXiv:2311.10859•Quantum•May 6, 2025•0 citations

Quantum algorithms for zero-sum games

Joran van Apeldoorn, András Gilyén

We derive sublinear-time quantum algorithms for computing the Nash equilibrium of two-player zero-sum games, based on efficient Gibbs sampling methods. We are able to achieve speed-ups for both dense and sparse payoff matrices at the cost of a mildly increased dependence on the additive error compared to classical algorithms. In particular we can find $\varepsilon$-approximate Nash equilibrium strategies in complexity $\tilde{O}(\sqrt{n+m}/\varepsilon^3)$ and $\tilde{O}(\sqrt{s}/\varepsilon^{3.5})$ respectively, where $n\times m$ is the size of the matrix describing the game and $s$ is its sparsity. Our algorithms use the LP formulation of the problem and apply techniques developed in recent works on quantum SDP-solvers. We also show how to reduce general LP-solving to zero-sum games, resulting in quantum LP-solvers that have complexities $\tilde{O}(\sqrt{n+m}γ^3)$ and $\tilde{O}(\sqrt{s}γ^{3.5})$ for the dense and sparse access models respectively, where $γ$ is the relevant "scale-invariant" precision parameter

arXiv:1904.03180•Apr 5, 2019•18 citations

Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games

Minbo Gao, Zhengfeng Ji, Tongyang Li +1 more

We propose the first online quantum algorithm for solving zero-sum games with $\widetilde 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 $\widetilde O(\sqrt{m+n}/\varepsilon^{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.

arXiv:2304.14197•neural information processing systems•Jan 1, 2023•3 citations

Quantum game theory and the complexity of approximating quantum Nash equilibria

John Bostanci, John Watrous

This paper is concerned with complexity theoretic aspects of a general formulation of quantum game theory that models strategic interactions among rational agents that process and exchange quantum information. In particular, we prove that the computational problem of finding an approximate Nash equilibrium in a broad class of quantum games is, like the analogous problem for classical games, included in (and therefore complete for) the complexity class PPAD. Our main technical contribution, which facilitates this inclusion, is an extension of prior methods in computational game theory to strategy spaces that are characterized by semidefinite programs.

arXiv:2102.00512•Quantum•Dec 22, 2022•16 citations

On Correlated Equilibria in Marinatto–Weber Type Quantum Games

Piotr Frąckiewicz

Players’ choices in quantum game schemes are often correlated by a quantum state. This enables players to obtain payoffs that may not be achievable when classical pure or mixed strategies are used. On the other hand, players’ choices can be correlated due to a classical probability distribution, and if no player benefits by a unilateral deviation from the vector of recommended strategies, the probability distribution is a correlated equilibrium. The aim of this paper is to investigate relation between correlated equilibria and Nash equilibria in the MW-type schemes for quantum games.

Applied Sciences•Dec 16, 2020•0 citations
Computing Nash equilibria of zero-sum games in classical and quantum settings is extensively studied. For general-sum games, computing Nash equilibria is PPAD-hard and the computing of a more general concept called correlated equilibria has been widely explored in game theory. In this paper, we initiate the study of quantum algorithms for computing ε\varepsilonε-approximate correlated equilibria (CE) and coarse correlated equilibria (CCE) in multi-player normal-form games. Our approach utilizes quantum improvements to the multi-scale Multiplicative Weight Update (MWU) method for CE calculations, achieving a query complexity of O~(mn)\tilde{O}(m\sqrt{n})O~(mn​) for fixed ε\varepsilonε. For CCE, we extend techniques from quantum algorithms for zero-sum games to multi-player settings, achieving query complexity O~(mn/ε2.5)\tilde{O}(m\sqrt{n}/\varepsilon^{2.5})O~(mn​/ε2.5). Both algorithms demonstrate a near-optimal scaling in the number of players mmm and actions nnn, as confirmed by our quantum query lower bounds.
As quantum processors advance, the emergence of large-scale decentralized systems involving interacting quantum-enabled agents is on the horizon. Recent research efforts have explored quantum versions of Nash and correlated equilibria as solution concepts of strategic quantum interactions, but these approaches did not directly connect to decentralized adaptive setups where agents possess limited information. This paper delves into the dynamics of quantum-enabled agents within decentralized systems that employ no-regret algorithms to update their behaviors over time. Specifically, we investigate two-player quantum zero-sum games and polymatrix quantum zero-sum games, showing that no-regret algorithms converge to separable quantum Nash equilibria in time-average. In the case of general multi-player quantum games, our work leads to a novel solution concept, that of the separable quantum coarse correlated equilibria (QCCE), as the convergent outcome of the time-averaged behavior no-regret algorithms, offering a natural solution concept for decentralized quantum systems. Finally, we show that computing QCCEs can be formulated as a semidefinite program and establish the existence of entangled (i.e., non-separable) QCCEs, which are unlearnable via the current paradigm of no-regret learning.
Recent developments in domains such as non-local games, quantum interactive proofs, and quantum generative adversarial networks have renewed interest in quantum game theory and, specifically, quantum zero-sum games. Central to classical game theory is the efficient algorithmic computation of Nash equilibria, which represent optimal strategies for both players. In 2008, Jain and Watrous proposed the first classical algorithm for computing equilibria in quantum zero-sum games using the Matrix Multiplicative Weight Updates (MMWU) method to achieve a convergence rate of O(d/ϵ2) iterations to ϵ -Nash equilibria in the 4d -dimensional spectraplex. In this work, we propose a hierarchy of quantum optimization algorithms that generalize MMWU via an extra-gradient mechanism. Notably, within this proposed hierarchy, we introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as O(d/ϵ) iterations to ϵ -Nash equilibria. This quadratic speed-up relative to Jain and Watrous' original algorithm sets a new benchmark for computing ϵ -Nash equilibria in quantum zero-sum games.
We derive sublinear-time quantum algorithms for computing the Nash equilibrium of two-player zero-sum games, based on efficient Gibbs sampling methods. We are able to achieve speed-ups for both dense and sparse payoff matrices at the cost of a mildly increased dependence on the additive error compared to classical algorithms. In particular we can find ε\varepsilonε-approximate Nash equilibrium strategies in complexity O~(n+m/ε3)\tilde{O}(\sqrt{n+m}/\varepsilon^3)O~(n+m​/ε3) and O~(s/ε3.5)\tilde{O}(\sqrt{s}/\varepsilon^{3.5})O~(s​/ε3.5) respectively, where n×mn\times mn×m is the size of the matrix describing the game and sss is its sparsity. Our algorithms use the LP formulation of the problem and apply techniques developed in recent works on quantum SDP-solvers. We also show how to reduce general LP-solving to zero-sum games, resulting in quantum LP-solvers that have complexities O~(n+mγ3)\tilde{O}(\sqrt{n+m}γ^3)O~(n+m​γ3) and O~(sγ3.5)\tilde{O}(\sqrt{s}γ^{3.5})O~(s​γ3.5) for the dense and sparse access models respectively, where γγγ is the relevant "scale-invariant" precision parameter
We propose the first online quantum algorithm for solving zero-sum games with O~(1)\widetilde O(1)O(1) regret under the game setting. Moreover, our quantum algorithm computes an ε\varepsilonε-approximate Nash equilibrium of an m×nm \times nm×n matrix zero-sum game in quantum time O~(m+n/ε2.5)\widetilde O(\sqrt{m+n}/\varepsilon^{2.5})O(m+n​/ε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.
This paper is concerned with complexity theoretic aspects of a general formulation of quantum game theory that models strategic interactions among rational agents that process and exchange quantum information. In particular, we prove that the computational problem of finding an approximate Nash equilibrium in a broad class of quantum games is, like the analogous problem for classical games, included in (and therefore complete for) the complexity class PPAD. Our main technical contribution, which facilitates this inclusion, is an extension of prior methods in computational game theory to strategy spaces that are characterized by semidefinite programs.
Players’ choices in quantum game schemes are often correlated by a quantum state. This enables players to obtain payoffs that may not be achievable when classical pure or mixed strategies are used. On the other hand, players’ choices can be correlated due to a classical probability distribution, and if no player benefits by a unilateral deviation from the vector of recommended strategies, the probability distribution is a correlated equilibrium. The aim of this paper is to investigate relation between correlated equilibria and Nash equilibria in the MW-type schemes for quantum games.