A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games
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 zero-sum games using the Matrix Multiplicative Weight Updates (MMWU) method to achieve a convergence rate of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>d</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:msup><mml:mi>&#x03F5;</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> iterations to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03F5;</mml:mi></mml:math>-Nash equilibria in the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mn>4</mml:mn><mml:mi>d</mml:mi></mml:msup></mml:math>-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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>d</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>&#x03F5;</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> iterations to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03F5;</mml:mi></mml:math>-Nash equilibria. This quadratic speed-up relative to Jain and Watrous' original algorithm sets a new benchmark for computing <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03F5;</mml:mi></mml:math>-Nash equilibria in quantum zero-sum games.
Authors
- Panayotis Mertikopoulos (ORCID: https://orcid.org/0000-0003-2026-9616)
- Michael I. Jordan (ORCID: https://orcid.org/0000-0001-8935-817X)
- Emmanouil-Vasileios Vlatakis-Gkaragkounis (ORCID: https://orcid.org/0009-0009-7549-538X)
- Georgios Piliouras (ORCID: https://orcid.org/0000-0002-6236-3566)
- Francisca Vasconcelos (ORCID: https://orcid.org/0000-0003-4758-2944)
Institutions
- Institut polytechnique de Grenoble (FR)
- Google (United States) (US)
- Centre National de la Recherche Scientifique (FR)
- Institut national de recherche en sciences et technologies du numérique (FR)
- Berkeley College (US)
- University of Wisconsin–Madison (US)
- Google DeepMind (United Kingdom) (GB)
- Centre Inria de l'Université Grenoble Alpes (FR)
- Laboratoire d'Informatique de Grenoble (FR)
- Université Grenoble Alpes (FR)
- University of California, Berkeley (US)
Publication Details
- Journal
- Quantum
- Published
- 2025-05-06
- DOI
- https://doi.org/10.22331/q-2025-05-06-1737
- Primary Topic
- Quantum Mechanics and Applications
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Science Foundation
- European Commission
- National Research Foundation
- Agency for Science, Technology and Research
- National University of Singapore
- National Research Foundation Singapore
- Agence Nationale de la Recherche
- National and Kapodistrian University of Athens
- Simons Institute for the Theory of Computing, University of California Berkeley
- Division of Mathematical Sciences