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

Abstract: Quantum zero-sum games provide a framework for non-local games, quantum interactive proofs, and quantum machine learning, where players optimize a bilinear payoff over quantum states. In contrast to classical bilinear games over polyhedral domains, for which gradient methods achieve linear last-iterate convergence, comparable guarantees over spectraplexes have remained open. Recent work achieved only an $O(1/\varepsilon)$ average-iterate rate and suggested that semidefinite geometry may preclude classical-style linear rates. We refute this obstruction. We prove that quantum zero-sum games admit algorithms with $O(\log(1/\varepsilon))$ last-iterate convergence to Nash equilibrium. In particular, matrix variants of Nesterov's iterative smoothing and Optimistic Gradient Descent--Ascent match the asymptotic rate of the classical polyhedral case. The key technical ingredient is a new error-bound theory for semidefinite games, establishing metric subregularity of the relevant monotone operator over spectrahedra despite the absence of polyhedral structure. We also give a geometric characterization of Nash equilibria via slack operators, classifying strategic directions as essential, neutral, or non-essential. Under strict complementarity or nondegeneracy, this reduces to a sharp classical-style dichotomy. Finally, we revisit Optimistic Matrix Multiplicative Weights Update. By extending the Quantal Response Equilibrium framework to spectraplex games, we prove an $\widetilde O(1/\varepsilon)$ last-iterate guarantee, while showing that any $O(\log(1/\varepsilon))$ speedup for this method must depend on a natural, dimension-dependent condition number. Experiments support the theoretical picture, with Optimistic Gradient Descent--Ascent outperforming Optimistic Matrix Multiplicative Weights Update in the regimes studied.

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

arXiv:2509.21570 [cs.GT]

(or arXiv:2509.21570v2 [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.