{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T04:18:45Z","timestamp":1746591525964,"version":"3.40.5"},"reference-count":81,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T00:00:00Z","timestamp":1746489600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["DGE-2146752"],"award-info":[{"award-number":["DGE-2146752"]}]},{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","award":["ANR-15- IDEX-02"],"award-info":[{"award-number":["ANR-15- IDEX-02"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]},{"name":"LabEx PERSYVAL","award":["ANR-11-LABX-002501"],"award-info":[{"award-number":["ANR-11-LABX-002501"]}]},{"name":"MIAI@Grenoble Alpes","award":["ANR-19- P3IA-0003"],"award-info":[{"award-number":["ANR-19- P3IA-0003"]}]},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["MIS 5154714"],"award-info":[{"award-number":["MIS 5154714"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"name":"AI Singapore Program","award":["AISG2-RP-2020-016"],"award-info":[{"award-number":["AISG2-RP-2020-016"]}]},{"name":"NRF","award":["NRF-NRFF2018- 07"],"award-info":[{"award-number":["NRF-NRFF2018- 07"]}]},{"name":"NRF","award":["NRF2019NRF-ANR095"],"award-info":[{"award-number":["NRF2019NRF-ANR095"]}]},{"name":"PIESGP","award":["PIESGP-AI-2020-01"],"award-info":[{"award-number":["PIESGP-AI-2020-01"]}]},{"name":"AME Programmatic Fund","award":["A20H6b015"],"award-info":[{"award-number":["A20H6b015"]}]},{"name":"Provost\u2019s Chair Professorship","award":["RGEPPV2101"],"award-info":[{"award-number":["RGEPPV2101"]}]},{"name":"Vannevar Bush Faculty Fellowship","award":["N00014-21-1-2941"],"award-info":[{"award-number":["N00014-21-1-2941"]}]},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["ERC-2022-SYG-OCEAN-101071601"],"award-info":[{"award-number":["ERC-2022-SYG-OCEAN-101071601"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"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 O<\/mml:mi><\/mml:mrow>(<\/mml:mo>d<\/mml:mi>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi>2<\/mml:mn><\/mml:msup>)<\/mml:mo><\/mml:math> iterations to &#x03F5;<\/mml:mi><\/mml:math>-Nash equilibria in the 4<\/mml:mn>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 O<\/mml:mi><\/mml:mrow>(<\/mml:mo>d<\/mml:mi>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi>)<\/mml:mo><\/mml:math> iterations to &#x03F5;<\/mml:mi><\/mml:math>-Nash equilibria. This quadratic speed-up relative to Jain and Watrous' original algorithm sets a new benchmark for computing &#x03F5;<\/mml:mi><\/mml:math>-Nash equilibria in quantum zero-sum games.<\/jats:p>","DOI":"10.22331\/q-2025-05-06-1737","type":"journal-article","created":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T16:40:36Z","timestamp":1746549636000},"page":"1737","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":0,"title":["A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games"],"prefix":"10.22331","volume":"9","author":[{"given":"Francisca","family":"Vasconcelos","sequence":"first","affiliation":[{"name":"UC Berkeley"}]},{"given":"Emmanouil-Vasileios","family":"Vlatakis-Gkaragkounis","sequence":"additional","affiliation":[{"name":"UC Berkeley, UW Madison"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2026-9616","authenticated-orcid":false,"given":"Panayotis","family":"Mertikopoulos","sequence":"additional","affiliation":[{"name":"Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France"}]},{"given":"Georgios","family":"Piliouras","sequence":"additional","affiliation":[{"name":"Google DeepMind"}]},{"given":"Michael I.","family":"Jordan","sequence":"additional","affiliation":[{"name":"UC Berkeley, Inria Paris"}]}],"member":"9598","published-online":{"date-parts":[[2025,5,6]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"John Von Neumann. ``Zur Theorie der Gesellschaftsspiele''. Mathematische Annalen 100, 295\u2013320 (1928).","DOI":"10.1007\/BF01448847"},{"key":"1","doi-asserted-by":"publisher","unstructured":"John Nash. ``Non-Cooperative Games''. Annals of Mathematics 54, 286\u2013295 (1951).","DOI":"10.2307\/1969529"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Parvathy S. Pillai and Shrisha Rao. ``Resource Allocation in Cloud Computing Using the Uncertainty Principle of Game Theory''. IEEE Systems Journal 10, 637\u2013648 (2016).","DOI":"10.1109\/JSYST.2014.2314861"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Steven J. Brams. ``Game theory and politics''. Free Press. (1975).","DOI":"10.2307\/2129553"},{"key":"4","doi-asserted-by":"publisher","unstructured":"David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. ``Mastering the game of Go with deep neural networks and tree search''. Nature 529, 484\u2013489 (2016).","DOI":"10.1038\/nature16961"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. ``Generative adversarial networks''. Communications of the ACM 63, 139\u2013144 (2020).","DOI":"10.1145\/3422622"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. ``Robust adversarial reinforcement learning''. In Proceedings of the 34th International Conference on Machine Learning - Volume 70. Page 2817\u20132826. JMLR (2017).","DOI":"10.5555\/3305890.3305972"},{"key":"7","doi-asserted-by":"publisher","unstructured":"J. S. Bell. ``On the Einstein Podolsky Rosen paradox''. Physics Physique Fizika 1, 195\u2013200 (1964).","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195"},{"key":"8","doi-asserted-by":"publisher","unstructured":"John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. ``Proposed Experiment to Test Local Hidden-Variable Theories''. Phys. Rev. Lett. 23, 880\u2013884 (1969).","DOI":"10.1103\/PhysRevLett.23.880"},{"key":"9","doi-asserted-by":"publisher","unstructured":"N. David Mermin. ``Simple unified form for the major no-hidden-variables theorems''. Phys. Rev. Lett. 65, 3373\u20133376 (1990).","DOI":"10.1103\/PhysRevLett.65.3373"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Lucien Hardy. ``Nonlocality for two particles without inequalities for almost all entangled states''. Phys. Rev. Lett. 71, 1665\u20131668 (1993).","DOI":"10.1103\/PhysRevLett.71.1665"},{"key":"11","doi-asserted-by":"publisher","unstructured":"P. K. Aravind. ``Bell\u2019s Theorem Without Inequalities and Only Two Distant Observers''. Journal of Genetic Counseling 15, 397\u2013405 (2002).","DOI":"10.1023\/A:1021272729475"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. ``Going Beyond Bell's Theorem''. Pages 69\u201372. Springer Netherlands. (1989).","DOI":"10.1007\/978-94-017-0849-4_10"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Ben W. Reichardt, Falk Unger, and Umesh Vazirani. ``Classical command of quantum systems''. Nature 496, 456\u2013460 (2013).","DOI":"10.1038\/nature12035"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. ``MIP* = RE''. Commununications of the ACM 64, 131\u2013138 (2021).","DOI":"10.1145\/3485628"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. ``Quantum Advantage from Any Non-local Game''. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023. Pages 1617\u20131628. ACM (2023).","DOI":"10.1145\/3564246.3585164"},{"key":"16","doi-asserted-by":"publisher","unstructured":"G. Gutoski. ``Upper bounds for quantum interactive proofs with competing provers''. In 20th Annual IEEE Conference on Computational Complexity (CCC'05). Pages 334\u2013343. (2005).","DOI":"10.1109\/CCC.2005.37"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Gus Gutoski and John Watrous. ``Quantum Interactive Proofs with Competing Provers''. In STACS 2005. Pages 605\u2013616. (2005).","DOI":"10.1007\/978-3-540-31856-9_50"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Gus Gutoski and John Watrous. ``Toward a General Theory of Quantum Games''. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing. Page 565\u2013574. STOC '07. ACM (2007).","DOI":"10.1145\/1250790.1250873"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Hirotada Kobayashi and Keiji Matsumoto. ``Quantum multi-prover interactive proof systems with limited prior entanglement''. Journal of Computer and System Sciences 66, 429\u2013450 (2003).","DOI":"10.1016\/S0022-0000(03)00035-7"},{"key":"20","doi-asserted-by":"publisher","unstructured":"R. Cleve, P. Hoyer, B. Toner, and J. Watrous. ``Consequences and limits of nonlocal strategies''. In Proceedings of the 19th IEEE Annual Conference on Computational Complexity, 2004. Pages 236\u2013249. (2004).","DOI":"10.1109\/CCC.2004.1313847"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, and Thomas Vidick. ``Using Entanglement in Quantum Multi-Prover Interactive Proofs''. Computational Complexity 18, 273\u2013307 (2009).","DOI":"10.1007\/s00037-009-0275-3"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick. ``Entangled Games Are Hard to Approximate''. SIAM Journal on Computing 40, 848\u2013877 (2011).","DOI":"10.1137\/090751293"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Andris Ambainis. ``A New Protocol and Lower Bounds for Quantum Coin Flipping''. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. Page 134\u2013142. STOC '01. ACM (2001).","DOI":"10.1145\/380752.380788"},{"key":"24","doi-asserted-by":"publisher","unstructured":"R. W. Spekkens and Terry Rudolph. ``Quantum Protocol for Cheat-Sensitive Weak Coin Flipping''. Phys. Rev. Lett. 89, 227901 (2002).","DOI":"10.1103\/PhysRevLett.89.227901"},{"key":"25","unstructured":"Carlos Mochon. ``Quantum weak coin flipping with arbitrarily small bias'' (2007). arXiv:0711.4114."},{"key":"26","doi-asserted-by":"publisher","unstructured":"Carl A. Miller. ``The Impossibility of Efficient Quantum Weak Coin Flipping''. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Page 916\u2013929. STOC '20. ACM (2020).","DOI":"10.1145\/3357713.3384276"},{"key":"27","doi-asserted-by":"publisher","unstructured":"David A. Meyer. ``Quantum Strategies''. Phys. Rev. Lett. 82, 1052\u20131055 (1999).","DOI":"10.1103\/PhysRevLett.82.1052"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Rahul Jain and John Watrous. ``Parallel Approximation of Non-interactive Zero-sum Quantum Games''. In 2009 24th Annual IEEE Conference on Computational Complexity. Pages 243\u2013253. (2009).","DOI":"10.1109\/CCC.2009.26"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Pierre-Luc Dallaire-Demers and Nathan Killoran. ``Quantum generative adversarial networks''. Phys. Rev. A 98, 012324 (2018).","DOI":"10.1103\/PhysRevA.98.012324"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Shouvanik Chakrabarti, Yiming Huang, Tongyang Li, Soheil Feizi, and Xiaodi Wu. ``Quantum wasserstein GANs''. In Proceedings of the 33rd International Conference on Neural Information Processing Systems. Pages 6781 \u2013 6792. NIPS '19 (2019).","DOI":"10.5555\/3454287.3454896"},{"key":"31","doi-asserted-by":"publisher","unstructured":"John Bostanci and John Watrous. ``Quantum game theory and the complexity of approximating quantum Nash equilibria''. Quantum 6, 882 (2022).","DOI":"10.22331\/q-2022-12-22-882"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Kyriakos Lotidis, Panayotis Mertikopoulos, Nicholas Bambos, and Jose Blanchet. ``Payoff-based learning with matrix multiplicative weights in quantum games''. In Proceedings of the 37th International Conference on Neural Information Processing Systems. NIPS '23 (2023).","DOI":"10.5555\/3666122.3667774"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Koji Tsuda, Gunnar R\u00e4tsch, and Manfred K. Warmuth. ``Matrix Exponentiated Gradient Updates for On-line Learning and Bregman Projection''. Journal of Machine Learning Research 6, 995\u20131018 (2005).","DOI":"10.5555\/1046920.1088706"},{"key":"34","unstructured":"Arkadi Semen Nemirovski and David Berkovich Yudin. ``Problem complexity and method efficiency in optimization''. Wiley. New York, NY (1983)."},{"key":"35","doi-asserted-by":"publisher","unstructured":"Amir Beck and Marc Teboulle. ``Mirror descent and nonlinear projected subgradient methods for convex optimization''. Operations Research Letters 31, 167\u2013175 (2003).","DOI":"10.1016\/S0167-6377(02)00231-6"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Rahul Jain, Georgios Piliouras, and Ryann Sim. ``Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrence''. In Proceedings of the 36th International Conference on Neural Information Processing Systems. NIPS '22 (2022).","DOI":"10.5555\/3600270.3600568"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. ``QIP = PSPACE''. Journal of the ACM 58, 30:1\u201330:27 (2011).","DOI":"10.1145\/2049697.2049704"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora and Satyen Kale. ``A Combinatorial, Primal-Dual Approach to Semidefinite Programs''. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing. Page 227\u2013236. STOC '07. ACM (2007).","DOI":"10.1145\/1250790.1250823"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, and Sushant Sachdeva. ``A Simple Framework for Finding Balanced Sparse Cuts via APSP''. In Symposium on Simplicity in Algorithms (SOSA). Pages 42\u201355. SIAM (2023).","DOI":"10.1137\/1.9781611977585.ch5"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia. ``Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates''. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. Page 237\u2013245. STOC '15New York, NY, USA (2015). Association for Computing Machinery.","DOI":"10.1145\/2746539.2746610"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Panayotis Mertikopoulos, E. Veronica Belmega, and Aris L. Moustakas. ``Matrix exponential learning: Distributed optimization in MIMO systems''. In 2012 IEEE International Symposium on Information Theory Proceedings. Pages 3028\u20133032. (2012).","DOI":"10.1109\/ISIT.2012.6284117"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Panayotis Mertikopoulos and Aris L. Moustakas. ``Learning in an Uncertain World: MIMO Covariance Matrix Optimization With Imperfect Feedback''. IEEE Transactions on Signal Processing 64, 5\u201318 (2016).","DOI":"10.1109\/TSP.2015.2477053"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Olivier Bilenne, Panayotis Mertikopoulos, and Elena Veronica Belmega. ``Fast Optimization With Zeroth-Order Feedback in Distributed, Multi-User MIMO Systems''. IEEE Transactions on Signal Processing 68, 6085\u20136100 (2020).","DOI":"10.1109\/TSP.2020.3029983"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Sham M Kakade, Shai Shalev-Shwartz, and Ambuj Tewari. ``Regularization techniques for learning with matrices''. The Journal of Machine Learning Research 13, 1865\u20131890 (2012).","DOI":"10.5555\/2188385.2343703"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora, Elad Hazan, and Satyen Kale. ``The Multiplicative Weights Update Method: a Meta-Algorithm and Applications''. Theory of Computing 8, 121\u2013164 (2012).","DOI":"10.4086\/toc.2012.v008a006"},{"key":"46","doi-asserted-by":"publisher","unstructured":"Wayne Lin, Georgios Piliouras, Ryann Sim, and Antonios Varvitsiotis. ``No-Regret Learning and Equilibrium Computation in Quantum Games''. Quantum 8, 1569 (2024).","DOI":"10.22331\/q-2024-12-17-1569"},{"key":"47","doi-asserted-by":"publisher","unstructured":"Arkadi Nemirovski. ``Prox-Method with Rate of Convergence O(1\/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems''. SIAM Journal on Optimization 15, 229\u2013251 (2004).","DOI":"10.1137\/S1052623403425629"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Alfred Auslender and Marc Teboulle. ``Interior projection-like methods for monotone variational inequalities''. Mathematical Programming 104, 39\u201368 (2005).","DOI":"10.1007\/s10107-004-0568-x"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Yuyuan Ouyang and Yangyang Xu. ``Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems''. Mathematical Programming 185, 1\u201335 (2021).","DOI":"10.1007\/s10107-019-01420-0"},{"key":"50","unstructured":"Galina M Korpelevich. ``The extragradient method for finding saddle points and other problems''. Matecon 12, 747\u2013756 (1976). url: https:\/\/cir.nii.ac.jp\/crid\/1571698600143951616."},{"key":"51","doi-asserted-by":"publisher","unstructured":"B. T. Polyak and A. B. Juditsky. ``Acceleration of Stochastic Approximation by Averaging''. SIAM Journal on Control and Optimization 30, 838\u2013855 (1992).","DOI":"10.1137\/0330046"},{"key":"52","doi-asserted-by":"publisher","unstructured":"Leonid Denisovich Popov. ``A modification of the Arrow-Hurwicz method for search of saddle points''. Mathematical notes of the Academy of Sciences of the USSR 28, 845\u2013848 (1980).","DOI":"10.1007\/BF01141092"},{"key":"53","doi-asserted-by":"publisher","unstructured":"Sasha Rakhlin and Karthik Sridharan. ``Optimization, learning, and games with predictable sequences''. Advances in Neural Information Processing Systems 26 (2013).","DOI":"10.5555\/2999792.2999954"},{"key":"54","unstructured":"Kyriakos Lotidis, Panayotis Mertikopoulos, and Nicholas Bambos. ``Learning in quantum games'' (2023). arXiv:2302.02333."},{"key":"55","doi-asserted-by":"publisher","unstructured":"Kyriakos Lotidis, Panayotis Mertikopoulos, and Nicholas Bambos. ``The Stability of Matrix Multiplicative Weights Dynamics in Quantum Games''. In 2023 62nd IEEE Conference on Decision and Control (CDC). Pages 1225\u20131232. (2023).","DOI":"10.1109\/CDC49753.2023.10384169"},{"key":"56","unstructured":"Ilayda Canyakmaz, Wayne Lin, Georgios Piliouras, and Antonios Varvitsiotis. ``Multiplicative updates for online convex optimization over symmetric cones'' (2023). arXiv:2307.03136."},{"key":"57","doi-asserted-by":"publisher","unstructured":"Alina Ene and Huy L\u00ea Nguy\u00ean. ``Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence''. Proceedings of the AAAI Conference on Artificial Intelligence 36, 6559\u20136567 (2022).","DOI":"10.1609\/aaai.v36i6.20609"},{"key":"58","doi-asserted-by":"publisher","unstructured":"Gerard Debreu. ``A Social Equilibrium Existence Theorem''. Proceedings of the National Academy of Sciences 38, 886\u2013893 (1952).","DOI":"10.1073\/pnas.38.10.886"},{"key":"59","doi-asserted-by":"publisher","unstructured":"Gesualdo Scutari, Daniel P. Palomar, Francisco Facchinei, and Jong-shi Pang. ``Convex Optimization, Game Theory, and Variational Inequality Theory''. IEEE Signal Processing Magazine 27, 35\u201349 (2010).","DOI":"10.1109\/MSP.2010.936021"},{"key":"60","doi-asserted-by":"publisher","unstructured":"Stephen Boyd and Lieven Vandenberghe. ``Convex Optimization''. Cambridge University Press. (2004).","DOI":"10.1017\/CBO9780511804441"},{"key":"61","doi-asserted-by":"publisher","unstructured":"Shai Shalev-Shwartz. ``Online Learning and Online Convex Optimization''. Foundations and Trends in Machine Learning 4, 107\u2013194 (2012).","DOI":"10.1561\/2200000018"},{"key":"62","doi-asserted-by":"publisher","unstructured":"John Watrous. ``The Theory of Quantum Information''. Cambridge University Press. (2018).","DOI":"10.1017\/9781316848142"},{"key":"63","doi-asserted-by":"publisher","unstructured":"Carl D. Meyer and Ian Stewart. ``Matrix Analysis and Applied Linear Algebra, Second Edition''. Society for Industrial and Applied Mathematics. Philadelphia, PA (2023).","DOI":"10.1137\/1.9781611977448"},{"key":"64","unstructured":"Xingyu Zhou. ``On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradient'' (2018). arXiv:1803.06573."},{"key":"65","unstructured":"D. Bertsekas, A. Nedic, and A. Ozdaglar. ``Convex Analysis and Optimization''. Athena Scientific optimization and computation series. Athena Scientific. (2003)."},{"key":"66","doi-asserted-by":"publisher","unstructured":"Constantin Zalinescu. ``Convex Analysis in General Vector Spaces''. World scientific. (2002).","DOI":"10.1142\/5021"},{"key":"67","unstructured":"Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. ``Optimistic mirror descent in saddle-point problems: Going the extra(-gradient) mile''. In International Conference on Learning Representations. (2019). url: https:\/\/openreview.net\/forum?id=Bkg8jjC9KQ."},{"key":"68","doi-asserted-by":"publisher","unstructured":"S\u00e9bastien Bubeck. ``Convex optimization: Algorithms and complexity''. Found. Trends Mach. Learn. 8, 231\u2013357 (2015).","DOI":"10.1561\/2200000050"},{"key":"69","doi-asserted-by":"publisher","unstructured":"Yurii Nesterov. ``Primal-dual subgradient methods for convex problems''. Mathematical Programming 120, 221\u2013259 (2009).","DOI":"10.1007\/s10107-007-0149-x"},{"key":"70","unstructured":"Andersen Ang. ``Projected gradient algorithm''. https:\/\/angms.science\/doc\/CVX\/CVX_PGD.pdf (2023). Version: July 13, 2023. First draft: August 2, 2017."},{"key":"71","doi-asserted-by":"publisher","unstructured":"Satyen Kale. ``Efficient algorithms using the multiplicative weights update method''. PhD thesis. Princeton University. (2007).","DOI":"10.5555\/1368636"},{"key":"72","doi-asserted-by":"publisher","unstructured":"Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. ``Solving Variational Inequalities with Stochastic Mirror-Prox Algorithm''. Stochastic Systems 1, 17\u201358 (2011).","DOI":"10.1287\/10-SSY011"},{"key":"73","unstructured":"Yao-Liang Yu. ``The strong convexity of von neumann\u2019s entropy''. Lecture Notes for MSE 213: Optimization Theory (2020). Available online: https:\/\/web.stanford.edu\/ sidford\/courses\/20fa_opt_theory\/sidford_mse213_2020fa_chap_5_extensions.pdf."},{"key":"74","doi-asserted-by":"publisher","unstructured":"Wayne Lin, Georgios Piliouras, Ryann Sim, and Antonios Varvitsiotis. ``Quantum Potential Games, Replicator Dynamics, and the Separability Problem'' (2023). arXiv:2302.04789.","DOI":"10.22331\/q-2025-04-03-1689"},{"key":"75","doi-asserted-by":"publisher","unstructured":"Shengyu Zhang. ``Quantum strategic game theory''. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. Pages 39\u201359. (2012).","DOI":"10.1145\/2090236.209024"},{"key":"76","doi-asserted-by":"publisher","unstructured":"Zhaohui Wei and Shengyu Zhang. ``Full characterization of quantum correlated equilibria.''. Quantum Information and Computation 13, 846\u2013860 (2013).","DOI":"10.5555\/2535680.2535687"},{"key":"77","doi-asserted-by":"publisher","unstructured":"Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. ``Tight last-iterate convergence rates for no-regret learning in multi-player games''. Advances in Neural Information Processing Systems 33, 20766\u201320778 (2020).","DOI":"10.5555\/3495724.3497468"},{"key":"78","unstructured":"Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. ``Linear last-iterate convergence in constrained saddle-point optimization'' (2021). arXiv:2006.09517."},{"key":"79","doi-asserted-by":"publisher","unstructured":"D. Petz. ``Bregman divergence as relative operator entropy''. Acta Mathematica Hungarica 116, 127\u2013131 (2007).","DOI":"10.1007\/s10474-007-6014-9"},{"key":"80","doi-asserted-by":"publisher","unstructured":"Jean-Baptiste Hiriart-Urruty and Claude Lemar\u00e9chal. ``Fundamentals of convex analysis''. Page 259. Grundlehren Text Editions. Springer Berlin, Heidelberg. (2001). 1 edition.","DOI":"10.1007\/978-3-642-56468-0"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-05-06-1737\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T16:40:41Z","timestamp":1746549641000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-05-06-1737\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,6]]},"references-count":81,"URL":"https:\/\/doi.org\/10.22331\/q-2025-05-06-1737","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,6]]},"article-number":"1737"}}