{"ID":2866198,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.21570","arxiv_id":"2509.21570","title":"Breaking $1/ε$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes","abstract":"Long studied as a toy model, quantum zero-sum games have recently resurfaced as a canonical playground for modern areas such as non-local games, quantum interactive proofs, and quantum machine learning. In this simple yet fundamental setting, two competing quantum players send iteratively mixed quantum states to a referee, who performs a joint measurement to determine their payoffs. In 2025, Vasconcelos et al. [arXiv:2311.10859] connected quantum communication channels with a hierarchy of quantum optimization algorithms that generalize Matrix Multiplicative Weights Update ($\\texttt{MMWU}$) through extra-gradient mechanisms, establishing an average-iterate convergence rate of $\\mathcal{O}(1/ε)$ iterations to $ε$-Nash equilibria. While a long line of work has shown that bilinear games over polyhedral domains admit gradient methods with linear last-iterate convergence rates of $\\mathcal{O}(\\log(1/ε))$, it has been conjectured that a fundamental performance gap must persist between quantum feasible sets (spectraplexes) and classical polyhedral sets (simplices). We resolve this conjecture in the negative. We prove that matrix variants of $\\textit{Nesterov's iterative smoothing}$ ($\\texttt{IterSmooth}$) and $\\textit{Optimistic Gradient Descent-Ascent}$ ($\\texttt{OGDA}$) achieve last-iterate convergence at a linear rate in quantum zero-sum games, thereby matching the classical polyhedral case. Our analysis relies on a new generalization of error bounds in semidefinite programming geometry, establishing that (SP-MS) holds for monotone operators over spectrahedra, despite their uncountably many extreme points. Finally, as a byproduct, we obtain an exponential speed-up over the classical Jain-Watrous [arXiv:0808.2775] method for parallel approximation of strictly positive semidefinite programs.","short_abstract":"Long studied as a toy model, quantum zero-sum games have recently resurfaced as a canonical playground for modern areas such as non-local games, quantum interactive proofs, and quantum machine learning. In this simple yet fundamental setting, two competing quantum players send iteratively mixed quantum states to a refe...","url_abs":"https://arxiv.org/abs/2509.21570","url_pdf":"https://arxiv.org/pdf/2509.21570v1","authors":"[\"Yiheng Su\",\"Emmanouil-Vasileios Vlatakis-Gkaragkounis\",\"Pucheng Xiong\"]","published":"2025-09-25T20:51:13Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"quant-ph\"]","methods":"[]","has_code":false}