Breaking $1/ε$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908559245049856 |
|---|---|
| author | Su, Yiheng Vlatakis-Gkaragkounis, Emmanouil-Vasileios Xiong, Pucheng |
| author_facet | Su, Yiheng Vlatakis-Gkaragkounis, Emmanouil-Vasileios Xiong, Pucheng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_21570 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Breaking $1/ε$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes Su, Yiheng Vlatakis-Gkaragkounis, Emmanouil-Vasileios Xiong, Pucheng Computer Science and Game Theory Quantum Physics 91A05, 81Q93 (Primary) 68Q32, 91A26, 37N40 (Secondary) 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. |
| title | Breaking $1/ε$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes |
| topic | Computer Science and Game Theory Quantum Physics 91A05, 81Q93 (Primary) 68Q32, 91A26, 37N40 (Secondary) |
| url | https://arxiv.org/abs/2509.21570 |