Breaking $1/\epsilon$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes

Abstract:Quantum zero-sum games are bilinear saddle-point problems over density matrices. We study how their semidefinite geometry governs last-iterate convergence beyond existing $O(1/\varepsilon)$ average-iterate guarantees [arXiv:2311.10859]. We establish a Holder error bound with a finite, game-dependent exponent for every finite-dimensional quantum zero-sum game. If the game admits an equilibrium with both states positive definite, this bound is linear. Under this hypothesis, matrix variants of Nesterov's iterative smoothing and optimistic gradient descent-ascent (OGDA) converge linearly to the Nash equilibrium set, with $O(\log(1/\varepsilon))$ iteration complexity. The proof establishes metric subregularity under this full-rank hypothesis despite the nonpolyhedral geometry of spectraplexes. We also characterize Nash equilibria in semidefinite games through slack operators, classifying strategic directions as essential, neutral, or non-essential. This trichotomy reduces to a classical-style dichotomy when every Nash equilibrium is strictly complementary, as ensured by our rank-nondegeneracy condition. Finally, by extending the quantal response equilibrium framework to spectraplex games, we prove a $\widetilde{O}(1/\varepsilon)$ last-iterate guarantee for optimistic matrix multiplicative weights update (OMMWU) when the Nash equilibrium is unique and both equilibrium states have full rank. We further show that any $O(\log(1/\varepsilon))$ last-iterate guarantee for OMMWU must depend on a natural game condition number and hence on the ambient dimensions. Experiments show that OGDA outperforms OMMWU in the regimes studied, leaving open which spectraplex games admit provably comparable acceleration for OMMWU.

Computer Science and Game Theory (cs.GT); Quantum Physics (quant-ph)

arXiv:2509.21570 [cs.GT]

(or arXiv:2509.21570v3 [cs.GT] for this version)

https://doi.org/10.48550/arXiv.2509.21570 Focus to learn more arXiv-issued DOI via DataCite

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.