A quadratic speedup in finding Nash equilibria of quantum zero-sum games - POLARIS - Performance analysis and Optimization of LARge Infrastructure and Systems
Communication Dans Un Congrès Année : 2023

A quadratic speedup in finding Nash equilibria of quantum zero-sum games

Résumé

Recent developments in domains such as non-local games, quantum interactive proofs, and quantum generative adversarial networks have renewed interest in quantum game theory and, specifically, quantum zero-sum games. Central to classical game theory is the efficient algorithmic computation of Nash equilibria, which represent optimal strategies for both players. In 2008, Jain and Watrous proposed the first classical algorithm for computing equilibria in quantum zerosum games using the Matrix Multiplicative Weight Updates (MMWU) method to achieve a convergence rate of O(d/ϵ 2) iterations to ϵ-Nash equilibria in the 4^d-dimensional spectraplex. In this work, we propose a hierarchy of quantum optimization algorithms that generalize MMWU via an extra-gradient mechanism. Notably, within this proposed hierarchy, we introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as O(d/ϵ) iterations to ϵ-Nash equilibria. This quadratic speed-up relative to Jain and Watrous' original algorithm sets a new benchmark for computing ϵ-Nash equilibria in quantum zero-sum games.
Fichier principal
Vignette du fichier
Quantum_Games-2.pdf (1.5 Mo) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
licence

Dates et versions

hal-04312987 , version 1 (28-11-2023)

Licence

Identifiants

Citer

Francisca Vasconcelos, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos, Georgios Piliouras, Michael I Jordan. A quadratic speedup in finding Nash equilibria of quantum zero-sum games. QTML 2023 - Annual international conference on Quantum Techniques in Machine Learning, Nov 2023, CERN, Switzerland. pp.1-54. ⟨hal-04312987⟩
91 Consultations
24 Téléchargements

Altmetric

Partager

More