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:2609.38835

Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games

Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong

quant-phcs.GTcs.LGmath.OCSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

Optimistic matrix mirror-prox (OMMP) computes $ε$-approximate Nash equilibria in quantum zero-sum games with an $O(1/\varepsilon)$ average-iterate guarantee [arXiv:2311.10859]. We investigate whether this dependence on accuracy is tight and whether geometric last-iterate convergence can be guaranteed. We study these questions through explicit games with one qubit per player. First, we prove an $Ω(1/\varepsilon)$ lower bound for the uniform-average output that includes the maximally mixed initial state, independently of the regularizer and step size. Second, we construct a fixed game on which optimistic gradient descent-ascent (OGDA), initialized at the maximally mixed state, has last-iterate Frobenius distance to equilibrium $Θ(1/t)$ and duality gap $Θ(1/t^3)$ for every sufficiently small fixed step size. A separate fixed game exhibits arbitrarily long delays in reducing the initial error by a constant factor across a family of initial states. Finally, we give a fixed game with a unique, strictly complementary equilibrium on which optimistic matrix multiplicative weights updates (OMMWU) converge only polynomially from the maximally mixed state for every fixed positive step size. The last-iterate Frobenius distance and quantum relative entropy from the equilibrium to the iterates decay as $Θ(1/t)$, while the duality gap decays as $Θ(1/t^2)$.

AI Summary

The paper asks whether the $O(1/\varepsilon)$ average-iterate guarantee for optimistic matrix mirror-prox (OMMP) in quantum zero-sum games is tight, and whether its Euclidean and entropy-based variants inherit geometric last-iterate convergence from classical matrix games. It studies explicit, fixed games with one qubit per player. For uniform averaging that includes the maximally mixed initial state, a diagonal game gives $G(\bar\Psi_T)\ge 1/T$ for every feasible sequence, independently of the update rule, regularizer, or step size. The proof makes the duality gap affine, so the initial error alone supplies the lower bound; this is an obstruction to the specified averaging rule, not an algorithm-independent complexity bound. For the two-projection optimistic gradient descent–ascent (OGDA) formulation, a game with a unique pure equilibrium yields distance $\sim4/(\eta t)$ and gap $\sim4/(\eta^3t^3)$ from maximally mixed initialization, for fixed $0<\eta\le1/8$. Bloch-ball projection reduces the boundary dynamics to a quadratic scalar recurrence, adapting a known curved-domain example. A separate game demonstrates initialization-dependent delays, despite geometric bounds for each fixed trajectory. For optimistic matrix multiplicative weights, a unique, strictly complementary equilibrium still permits distance and equilibrium-to-iterate relative entropy $\Theta(1/t)$, and gap $\Theta(1/t^2)$, for every fixed positive step size. Exact score-matrix formulas show exponential eigenvalue concentration but only $1/t$ eigenvector alignment. Numerical experiments check the rates and constants. All constructions have singular equilibrium strategies. The results leave open faster convergence under full-rank equilibrium assumptions and do not exclude improvements through alternative algorithms or averaging rules.

Little sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
38 pages, 6 figures

Related papers

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•5 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•9 citations

Payoff-based learning with matrix multiplicative weights in quantum games

Kyriakos Lotidis, Panayotis Mertikopoulos, Nicholas Bambos +1 more

In this paper, we study the problem of learning in quantum games - and other classes of semidefinite games - with scalar, payoff-based feedback. For concreteness, we focus on the widely used matrix multiplicative weights (MMW) algorithm and, instead of requiring players to have full knowledge of the game (and/or each other's chosen states), we introduce a suite of minimal-information matrix multiplicative weights (3MW) methods tailored to different information frameworks. The main difficulty to attaining convergence in this setting is that, in contrast to classical finite games, quantum games have an infinite continuum of pure states (the quantum equivalent of pure strategies), so standard importance-weighting techniques for estimating payoff vectors cannot be employed. Instead, we borrow ideas from bandit convex optimization and we design a zeroth-order gradient sampler adapted to the semidefinite geometry of the problem at hand. As a first result, we show that the 3MW method with deterministic payoff feedback retains the $\mathcal{O}(1/\sqrt{T})$ convergence rate of the vanilla, full information MMW algorithm in quantum min-max games, even though the players only observe a single scalar. Subsequently, we relax the algorithm's information requirements even further and we provide a 3MW method that only requires players to observe a random realization of their payoff observable, and converges to equilibrium at an $\mathcal{O}(T^{-1/4})$ rate. Finally, going beyond zero-sum games, we show that a regularized variant of the proposed 3MW method guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.

arXiv:2311.02423•Nov 4, 2023•1 citation

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

Tongyang Li, Xinzhao Wang, Yexin Zhang

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.

arXiv:2510.16782•neural information processing systems•Jan 1, 2025•0 citations

Payoff-based learning with matrix multiplicative weights in quantum games

Kyriakos Lotidis, Panayotis Mertikopoulos, Nicholas Bambos +1 more

In this paper, we study the problem of learning in quantum gamesand other classes of semidefinite games-with scalar, payoff-based feedback. For concreteness, we focus on the widely used matrix multiplicative weights (MMW) algorithm and, instead of requiring players to have full knowledge of the game (and/or each other's chosen states), we introduce a suite of minimal-information matrix multiplicative weights (3MW) methods tailored to different information frameworks. The main difficulty to attaining convergence in this setting is that, in contrast to classical finite games, quantum games have an infinite continuum of pure states (the quantum equivalent of pure strategies), so standard importance-weighting techniques for estimating payoff vectors cannot be employed. Instead, we borrow ideas from bandit convex optimization and we design a zeroth-order gradient sampler adapted to the semidefinite geometry of the problem at hand. As a first result, we show that the 3MW method with deterministic payoff feedback retains the O(1/ √ T) convergence rate of the vanilla, full information MMW algorithm in quantum min-max games, even though the players only observe a single scalar. Subsequently, we relax the algorithm's information requirements even further and we provide a 3MW method that only requires players to observe a random realization of their payoff observable, and converges to equilibrium at an O(T −1/4) rate. Finally, going beyond zero-sum games, we show that a regularized variant of the proposed 3MW method guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.

•Dec 10, 2023•0 citations

Projected Variational Quantum Extragradient for Zero-Sum Games

Duong The Do, Matthew Aldridge, Duong Tung Nguyen

We propose a projected variational quantum extragradient framework for computing approximate Nash equilibria in two-player zero-sum matrix games. Mixed strategies are parameterized as Born distributions of parameterized quantum circuits, transforming the classical bilinear saddle-point problem into a smooth but generally nonconvex-nonconcave problem in circuit-parameter space. To support arbitrary game sizes, we introduce a dominated embedding that maps$({m},{n})$games to qubit-compatible power-of-two dimensions while preserving equilibrium structure. We develop a projected extragradient method using parameter-shift gradient estimators and establish variance bounds scaling as${O}({1}/{S})$with the number of measurement shots$S$, together with convergence to approximate first-order stationarity under standard assumptions. Since stationarity does not necessarily imply equilibrium optimality, performance is evaluated using the game-space Nash gap. Numerical results show high-precision equilibrium computation on structured instances up to${32} \times {32}$, while highlighting challenges in unstructured settings.

arXiv:2604.16466•IEEE Control Systems Letters•Jan 1, 2026•0 citations
Optimistic matrix mirror-prox (OMMP) computes εεε-approximate Nash equilibria in quantum zero-sum games with an O(1/ε)O(1/\varepsilon)O(1/ε) average-iterate guarantee [arXiv:2311.10859]. We investigate whether this dependence on accuracy is tight and whether geometric last-iterate convergence can be guaranteed. We study these questions through explicit games with one qubit per player. First, we prove an Ω(1/ε)Ω(1/\varepsilon)Ω(1/ε) lower bound for the uniform-average output that includes the maximally mixed initial state, independently of the regularizer and step size. Second, we construct a fixed game on which optimistic gradient descent-ascent (OGDA), initialized at the maximally mixed state, has last-iterate Frobenius distance to equilibrium Θ(1/t)Θ(1/t)Θ(1/t) and duality gap Θ(1/t3)Θ(1/t^3)Θ(1/t3) for every sufficiently small fixed step size. A separate fixed game exhibits arbitrarily long delays in reducing the initial error by a constant factor across a family of initial states. Finally, we give a fixed game with a unique, strictly complementary equilibrium on which optimistic matrix multiplicative weights updates (OMMWU) converge only polynomially from the maximally mixed state for every fixed positive step size. The last-iterate Frobenius distance and quantum relative entropy from the equilibrium to the iterates decay as Θ(1/t)Θ(1/t)Θ(1/t), while the duality gap decays as Θ(1/t2)Θ(1/t^2)Θ(1/t2).
The paper asks whether the O(1/ε)O(1/\varepsilon)O(1/ε) average-iterate guarantee for optimistic matrix mirror-prox (OMMP) in quantum zero-sum games is tight, and whether its Euclidean and entropy-based variants inherit geometric last-iterate convergence from classical matrix games. It studies explicit, fixed games with one qubit per player.
For uniform averaging that includes the maximally mixed initial state, a diagonal game gives G(ΨˉT)≥1/TG(\bar\Psi_T)\ge 1/TG(ΨˉT​)≥1/T for every feasible sequence, independently of the update rule, regularizer, or step size. The proof makes the duality gap affine, so the initial error alone supplies the lower bound; this is an obstruction to the specified averaging rule, not an algorithm-independent complexity bound.
For the two-projection optimistic gradient descent–ascent (OGDA) formulation, a game with a unique pure equilibrium yields distance ∼4/(ηt)\sim4/(\eta t)∼4/(ηt) and gap ∼4/(η3t3)\sim4/(\eta^3t^3)∼4/(η3t3) from maximally mixed initialization, for fixed 0<η≤1/80<\eta\le1/80<η≤1/8. Bloch-ball projection reduces the boundary dynamics to a quadratic scalar recurrence, adapting a known curved-domain example. A separate game demonstrates initialization-dependent delays, despite geometric bounds for each fixed trajectory.
For optimistic matrix multiplicative weights, a unique, strictly complementary equilibrium still permits distance and equilibrium-to-iterate relative entropy Θ(1/t)\Theta(1/t)Θ(1/t), and gap Θ(1/t2)\Theta(1/t^2)Θ(1/t2), for every fixed positive step size. Exact score-matrix formulas show exponential eigenvalue concentration but only 1/t1/t1/t eigenvector alignment. Numerical experiments check the rates and constants.
All constructions have singular equilibrium strategies. The results leave open faster convergence under full-rank equilibrium assumptions and do not exclude improvements through alternative algorithms or averaging rules.
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 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.
In this paper, we study the problem of learning in quantum games - and other classes of semidefinite games - with scalar, payoff-based feedback. For concreteness, we focus on the widely used matrix multiplicative weights (MMW) algorithm and, instead of requiring players to have full knowledge of the game (and/or each other's chosen states), we introduce a suite of minimal-information matrix multiplicative weights (3MW) methods tailored to different information frameworks. The main difficulty to attaining convergence in this setting is that, in contrast to classical finite games, quantum games have an infinite continuum of pure states (the quantum equivalent of pure strategies), so standard importance-weighting techniques for estimating payoff vectors cannot be employed. Instead, we borrow ideas from bandit convex optimization and we design a zeroth-order gradient sampler adapted to the semidefinite geometry of the problem at hand. As a first result, we show that the 3MW method with deterministic payoff feedback retains the O(1/T)\mathcal{O}(1/\sqrt{T})O(1/T​) convergence rate of the vanilla, full information MMW algorithm in quantum min-max games, even though the players only observe a single scalar. Subsequently, we relax the algorithm's information requirements even further and we provide a 3MW method that only requires players to observe a random realization of their payoff observable, and converges to equilibrium at an O(T−1/4)\mathcal{O}(T^{-1/4})O(T−1/4) rate. Finally, going beyond zero-sum games, we show that a regularized variant of the proposed 3MW method guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.
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.
In this paper, we study the problem of learning in quantum gamesand other classes of semidefinite games-with scalar, payoff-based feedback. For concreteness, we focus on the widely used matrix multiplicative weights (MMW) algorithm and, instead of requiring players to have full knowledge of the game (and/or each other's chosen states), we introduce a suite of minimal-information matrix multiplicative weights (3MW) methods tailored to different information frameworks. The main difficulty to attaining convergence in this setting is that, in contrast to classical finite games, quantum games have an infinite continuum of pure states (the quantum equivalent of pure strategies), so standard importance-weighting techniques for estimating payoff vectors cannot be employed. Instead, we borrow ideas from bandit convex optimization and we design a zeroth-order gradient sampler adapted to the semidefinite geometry of the problem at hand. As a first result, we show that the 3MW method with deterministic payoff feedback retains the O(1/ √ T) convergence rate of the vanilla, full information MMW algorithm in quantum min-max games, even though the players only observe a single scalar. Subsequently, we relax the algorithm's information requirements even further and we provide a 3MW method that only requires players to observe a random realization of their payoff observable, and converges to equilibrium at an O(T −1/4) rate. Finally, going beyond zero-sum games, we show that a regularized variant of the proposed 3MW method guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.
We propose a projected variational quantum extragradient framework for computing approximate Nash equilibria in two-player zero-sum matrix games. Mixed strategies are parameterized as Born distributions of parameterized quantum circuits, transforming the classical bilinear saddle-point problem into a smooth but generally nonconvex-nonconcave problem in circuit-parameter space. To support arbitrary game sizes, we introduce a dominated embedding that maps(m,n)({m},{n})(m,n)games to qubit-compatible power-of-two dimensions while preserving equilibrium structure. We develop a projected extragradient method using parameter-shift gradient estimators and establish variance bounds scaling asO(1/S){O}({1}/{S})O(1/S)with the number of measurement shotsSSS, together with convergence to approximate first-order stationarity under standard assumptions. Since stationarity does not necessarily imply equilibrium optimality, performance is evaluated using the game-space Nash gap. Numerical results show high-precision equilibrium computation on structured instances up to32×32{32} \times {32}32×32, while highlighting challenges in unstructured settings.