More Like this

1. The quantum-to-classical graph homomorphism game

   https://doi.org/10.1063/5.0072288  

   Brannan, Michael; Ganesan, Priyanga; Harris, Samuel J. (November 2022, Journal of Mathematical Physics)

   Motivated by non-local games and quantum coloring problems, we introduce a graph homomorphism game between quantum graphs and classical graphs. This game is naturally cast as a “quantum–classical game,” that is, a non-local game of two players involving quantum questions and classical answers. This game generalizes the graph homomorphism game between classical graphs. We show that winning strategies in the various quantum models for the game is an analog of the notion of non-commutative graph homomorphisms due to Stahlke [IEEE Trans. Inf. Theory 62(1), 554–577 (2016)]. Moreover, we present a game algebra in this context that generalizes the game algebra for graph homomorphisms given by Helton et al. [New York J. Math. 25, 328–361 (2019)]. We also demonstrate explicit quantum colorings of all quantum complete graphs, yielding the surprising fact that the algebra of the four coloring game for a quantum graph is always non-trivial, extending a result of Helton et al. [New York J. Math. 25, 328–361 (2019)]. 

   more » « less
2. A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games

   Vasconcelos, F; Vlatakis-Gkaragkounis, E-V; Mertikopoulos, P; Piliouras, G; Jordan, M I (November 2023, 7th International Conference on Quantum Techniques in Machine Learning)

   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 4d-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
3. A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games

   https://doi.org/10.22331/q-2025-05-06-1737  

   Vasconcelos, Francisca; Vlatakis-Gkaragkounis, Emmanouil-Vasileios; Mertikopoulos, Panayotis; Piliouras, Georgios; Jordan, Michael I (May 2025, Quantum)

   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 $\mathcal{O}\left(d/{ϵ}^2\right)$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 $\mathcal{O}\left(d/ϵ\right)$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
4. Quantum Computational Advantage with String Order Parameters of One-Dimensional Symmetry-Protected Topological Order

   https://doi.org/https://doi.org/10.1103/PhysRevLett.126.090505  

   Daniel, Austin K; Miyake, Akimasa (March 2021, Physical review letters)

   null (Ed.)

   Nonlocal games with advantageous quantum strategies give arguably the most fundamental demonstration of the power of quantum resources over their classical counterparts. Recently, certain multiplayer generalizations of nonlocal games have been used to prove unconditional separations between limited computational complexity classes of shallow-depth circuits. Here, we show advantageous strategies for these nonlocal games for generic ground states of one-dimensional symmetry-protected topological orders (SPTOs), when a discrete invariant of a SPTO known as a twist phase is nontrivial and -1. Our construction demonstrates that sufficiently large string order parameters of such SPTOs are indicative of globally constrained correlations useful for the unconditional computational separation. 

   more » « less
5. Koszul homomorphisms and universal resolutions in local algebra

   https://doi.org/10.1017/fms.2025.21  

   Briggs, Benjamin; Cameron, James C; Letz, Janina C; Pollitz, Josh (January 2025, Forum of Mathematics, Sigma)

   Abstract We define a local homomorphism$$(Q,k)\to (R,\ell )$$to be Koszul if its derived fiber$$R\otimes ^{\mathsf {L}}_Q k$$is formal, and if$$\operatorname {Tor}^{Q}(R,k)$$is Koszul in the classical sense. This recovers the classical definition whenQis a field, and more generally includes all flat deformations of Koszul algebras. The non-flat case is significantly more interesting, and there is no need for examples to be quadratic: all complete intersection and all Golod quotients are Koszul homomorphisms. We show that the class of Koszul homomorphisms enjoys excellent homological properties, and we give many more examples, especially various monomial and Gorenstein examples. We then study Koszul homomorphisms from the perspective of$$\mathrm {A}_{\infty }$$-structures on resolutions. We use this machinery to construct universal free resolutions ofR-modules by generalizing a classical construction of Priddy. The resulting (infinite) free resolution of anR-moduleMis often minimal and can be described by a finite amount of data wheneverMandRhave finite projective dimension overQ. Our construction simultaneously recovers the resolutions of Shamash and Eisenbud over a complete intersection ring, and the bar resolutions of Iyengar and Burke over a Golod ring, and produces analogous resolutions for various other classes of local rings. 

   more » « less