skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


This content will become publicly available on May 6, 2026

Title: 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 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.  more » « less
Award ID(s):
2023505
PAR ID:
10635683
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
arxiv
Date Published:
Journal Name:
Quantum
Volume:
9
ISSN:
2521-327X
Page Range / eLocation ID:
1737
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Boundaries of Walker-Wang models have been used to construct commuting projector models which realize chiral unitary modular tensor categories (UMTCs) as boundary excitations. Given a UMTC A representing the Witt class of an anomaly, the article \cite{MR4640433} gave a commuting projector model associated to an A -enriched unitary fusion category X on a 2D boundary of the 3D Walker-Wang model associated to A . That article claimed that the boundary excitations were given by the enriched center/Müger centralizer Z A ( X ) of A in Z ( X ) .In this article, we give a rigorous treatment of this 2D boundary model, and we verify this assertion using topological quantum field theory (TQFT) techniques, including skein modules and a certain semisimple algebra whose representation category describes boundary excitations. We also use TQFT techniques to show the 3D bulk point excitations of the Walker-Wang bulk are given by the Müger center Z 2 ( A ) , and we construct bulk-to-boundary hopping operators Z 2 ( A ) Z A ( X ) reflecting how the UMTC of boundary excitations Z A ( X ) is symmetric-braided enriched in Z 2 ( A ) .This article also includes a self-contained comprehensive review of the Levin-Wen string net model from a unitary tensor category viewpoint, as opposed to the skeletal 6 j symbol viewpoint. 
    more » « less
  2. We show that if L 1 \mathcal {L}_1 and L 2 \mathcal {L}_2 are linear transformations from Z d \mathbb {Z}^d to Z d \mathbb {Z}^d satisfying certain mild conditions, then, for any finite subset A A of Z d \mathbb {Z}^d , | L 1 A + L 2 A | ≥<#comment/> ( | det ( L 1 ) | 1 / d + | det ( L 2 ) | 1 / d ) d | A | −<#comment/> o ( | A | ) . \begin{equation*} |\mathcal {L}_1 A+\mathcal {L}_2 A|\geq \left ( |\det (\mathcal {L}_1)|^{1/d}+|\det (\mathcal {L}_2)|^{1/d} \right )^d|A|- o(|A|). \end{equation*} This result corrects and confirms the two-summand case of a conjecture of Bukh and is best possible up to the lower-order term for certain choices of L 1 \mathcal {L}_1 and L 2 \mathcal {L}_2 . As an application, we prove a lower bound for | A + λ<#comment/> ⋅<#comment/> A | |A + \lambda \cdot A| when A A is a finite set of real numbers and λ<#comment/> \lambda is an algebraic number. In particular, when λ<#comment/> \lambda is of the form ( p / q ) 1 / d (p/q)^{1/d} for some p , q , d ∈<#comment/> N p, q, d \in \mathbb {N} , each taken as small as possible for such a representation, we show that | A + λ<#comment/> ⋅<#comment/> A | ≥<#comment/> ( p 1 / d + q 1 / d ) d | A | −<#comment/> o ( | A | ) . \begin{equation*} |A + \lambda \cdot A| \geq (p^{1/d} + q^{1/d})^d |A| - o(|A|). \end{equation*} This is again best possible up to the lower-order term and extends a recent result of Krachun and Petrov which treated the case λ<#comment/> = 2 \lambda = \sqrt {2}
    more » « less
  3. We consider minimizing harmonic maps u u from Ω<#comment/> ⊂<#comment/> R n \Omega \subset \mathbb {R}^n into a closed Riemannian manifold N \mathcal {N} and prove: 1. an extension to n ≥<#comment/> 4 n \geq 4 of Almgren and Lieb’s linear law. That is, if the fundamental group of the target manifold N \mathcal {N} is finite, we have\[ H n −<#comment/> 3 ( sing ⁡<#comment/> u ) ≤<#comment/> C ∫<#comment/> ∂<#comment/> Ω<#comment/> | ∇<#comment/> T u | n −<#comment/> 1 d H n −<#comment/> 1 ; \mathcal {H}^{n-3}(\operatorname {sing} u) \le C \int _{\partial \Omega } |\nabla _T u|^{n-1} \,\mathrm {d}\mathcal {H}^{n-1}; \]2. an extension of Hardt and Lin’s stability theorem. Namely, assuming that the target manifold is N = S 2 \mathcal {N}=\mathbb {S}^2 we obtain that the singular set of u u is stable under small W 1 , n −<#comment/> 1 W^{1,n-1} -perturbations of the boundary data. In dimension n = 3 n=3 both results are shown to hold with weaker hypotheses, i.e., only assuming that the trace of our map lies in the fractional space W s , p W^{s,p} with s ∈<#comment/> ( 1 2 , 1 ] s \in (\frac {1}{2},1] and p ∈<#comment/> [ 2 , ∞<#comment/> ) p \in [2,\infty ) satisfying s p ≥<#comment/> 2 sp \geq 2 . We also discuss sharpness. 
    more » « less
  4. We determine for which exotic tori T \mathcal {T} of dimension d ≠<#comment/> 4 d\neq 4 the homomorphism from the group of isotopy classes of orientation-preserving diffeomorphisms of T \mathcal {T} to S L d ( Z ) \mathrm {SL}_d(\mathbf {Z}) given by the action on the first homology group is split surjective. As part of the proof we compute the mapping class group of all exotic tori T \mathcal {T} that are obtained from the standard torus by a connected sum with an exotic sphere. Moreover, we show that any nontrivial S L d ( Z ) \mathrm {SL}_d(\mathbf {Z}) -action on T \mathcal {T} agrees on homology with the standard action, up to an automorphism of S L d ( Z ) \mathrm {SL}_d(\mathbf {Z}) . When combined, these results in particular show that many exotic tori do not admit any nontrivial differentiable action by S L d ( Z ) \mathrm {SL}_d(\mathbf {Z})
    more » « less
  5. We introduce a topological intersection number for an ordered pair of SL 3 \operatorname {SL}_3 -webs on a decorated surface. Using this intersection pairing between reduced ( SL 3 , A ) (\operatorname {SL}_3,\mathcal {A}) -webs and a collection of ( SL 3 , X ) (\operatorname {SL}_3,\mathcal {X}) -webs associated with the Fock–Goncharov cluster coordinates, we provide a natural combinatorial interpretation of the bijection from the set of reduced ( SL 3 , A ) (\operatorname {SL}_3,\mathcal {A}) -webs to the tropical set A PGL 3 , S ^<#comment/> + ( Z t ) \mathcal {A}^+_{\operatorname {PGL}_3,\hat {S}}(\mathbb {Z}^t) , as established by Douglas and Sun in [Forum Math. Sigma 12 (2024), p. e5, 55]. We provide a new proof of the flip equivariance of the above bijection, which is crucial for proving the Fock–Goncharov duality conjecture of higher Teichmüller spaces for SL 3 \operatorname {SL}_3
    more » « less