aiqbench analysis
This research establishes tight theoretical lower bounds for convergence rates in quantum zero-sum games, proving that $O(1/\varepsilon)$ average-iterate guarantees are optimal regardless of the regularizer or step size. By constructing explicit single-qubit counterexamples, the authors demonstrate that optimistic gradient methods often fail to achieve geometric last-iterate convergence, decaying instead at polynomial rates like $\Theta(1/t)$. These findings clarify the fundamental limitations of current optimization algorithms when applied to quantum game-theoretic scenarios.
Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games
arXiv:2609.38835v1 Announce Type: new Abstract: Optimistic matrix mirror-prox (OMMP) computes $\epsilon$-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 $\Omega(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 $\Theta(1/t)$ and duality gap $\Theta(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 $\Theta(1/t)$, while the duality gap decays as $\Theta(1/t^2)$.
Abstract:Optimistic matrix mirror-prox (OMMP) computes $\epsilon$-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 $\Omega(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 $\Theta(1/t)$ and duality gap $\Theta(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 $\Theta(1/t)$, while the duality gap decays as $\Theta(1/t^2)$.
Quantum Physics (quant-ph); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG); Optimization and Control (math.OC)
arXiv:2609.38835 [quant-ph]
(or arXiv:2609.38835v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2609.38835 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 296 words
Related coverage
Humanity’s Last Invention — Richard Socher of Recursive
Latent Space · Sep 14, 2026
FP16 GEMM Optimization on AMD RDNA™ 3 and RDNA™ 4 Architectures
AMD · Oct 16, 2026
Breaking $1/\epsilon$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes
arXiv · Oct 6, 2026
Breaking $1/\epsilon$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes
arXiv · Jun 4, 2026