Quantum games and synchronicity
Understand this faster with AI
AbstractIn the flavour of categorical quantum mechanics, we extend nonlocal games to allow quantum questions and answers, using quantum sets (special symmetric dagger Frobenius algebras) and the quantum functions of Musto, Reutter, and Verdon. Equations are presented using a diagrammatic calculus for tensor categories. To this quantum question and answer setting, we extend the standard definitions, including strategies, correlations, and synchronicity, and we use these definitions to extend results about synchronicity. We extend the graph homomorphism (isomorphism) game to quantum graphs, and show it is synchronous (bisynchronous) and connect its perfect (bi)strategies to quantum graph homomorphisms (isomorphisms). Our extended definitions agree with the existing quantum games literature, except in the case of synchronicity.Featured image: This graphical Cauchy-Schwarz style inequality for quantum functions $E,F$ is a key graphical tool established here and used to study synchronous quantum games.Talk at Isaac Newton Institute relating to this paper: Podcast episode aimed at the public, discussing the graphical calculus and the emphasis of relational/compositional structures. Popular summaryNonlocal games are theoretical protocols in quantum information theory, where two separated parties aim to cooperate in a task overseen by a referee. Given some (classical) question data, each party needs to respond with a (classical) answer. The two parties may make use of a shared quantum resource. Nonlocal games are used to study foundational concepts in quantum information theory, often in an experimentally verifiable way. This paper approaches nonlocal games using graphical equations, with the aim of integrating nonlocal games with the larger program of categorical quantum mechanics (CQM). CQM invites a compositional, categorical approach to quantum information. By recasting nonlocal games in the language of CQM, we are able to naturally generalize them to quantum games (where the question and answer data may be quantum states). We extend some well-studied properties of nonlocal games. We also quantize some general classes of nonlocal games played on graphs.► BibTeX data@article{Goldberg2026quantumgames, doi = {10.22331/q-2026-01-14-1964}, url = {https://doi.org/10.22331/q-2026-01-14-1964}, title = {Quantum games and synchronicity}, author = {Goldberg, Adina}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1964}, month = jan, year = {2026} }► References [1] Samson Abramskyand Bob Coecke ``A categorical semantics of quantum protocols'' Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, 2004. 415-425 (2004). https://doi.org/10.1109/LICS.2004.1319636 [2] Albert Atserias, Laura Mančinska, David Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis, ``Quantum and non-signalling graph isomorphisms'' Journal of Combinatorial Theory, Series B 136 (2019). https://doi.org/10.1016/j.jctb.2018.11.002 [3] Michael Brannan, Priyanga Ganesan, and Samuel J. Harris, ``The quantum-to-classical graph homomorphism game'' Journal of Mathematical Physics 63, 112204 (2022). https://doi.org/10.1063/5.0072288 [4] Arkadiusz Bochniak, Paweł Kasprzak, and Piotr M Sołtan, ``Quantum Correlations on Quantum Spaces'' International Mathematics Research Notices 2023, 12400–12440 (2023). https://doi.org/10.1093/imrn/rnac139 [5] Michael Brannan, Alexandru Chirvasitu, Kari Eifler, Samuel Harris, Vern Paulsen, Xiaoyu Su, and Mateusz Wasilewski, ``Bigalois Extensions and the Graph Isomorphism Game'' Communications in Mathematical Physics 375, 1777–1809 (2019). https://doi.org/10.1007/s00220-019-03563-9 [6] Michael Brannan, Samuel J. Harris, Ivan G. Todorov, and Lyudmila Turowska, ``Synchronicity for quantum non-local games'' Journal of Functional Analysis 284, 109738 (2023). https://doi.org/10.1016/j.jfa.2022.109738 https://www.sciencedirect.com/science/article/pii/S0022123622003585 [7] Michael Brannan, Samuel J. Harris, Ivan G. Todorov, and Lyudmila Turowska, ``Quantum no-signalling bicorrelations'' Advances in Mathematics 449, 109732 (2024). https://doi.org/10.1016/j.aim.2024.109732 https://www.sciencedirect.com/science/article/pii/S0001870824002470 [8] Francesco Buscemi ``All entangled quantum states are nonlocal.'' Physical review letters 108 20, 200401 (2011). https://doi.org/10.1103/PhysRevLett.108.200401 https://api.semanticscholar.org/CorpusID:14393220 [9] Bob Coecke, Chris Heunen, and Aleks Kissinger, ``Categories of Quantum and Classical Channels'' Quantum Information Processing 15 (2013). https://doi.org/10.1007/s11128-014-0837-4 [10] B. Coeckeand A. Kissinger ``Picturing Quantum Processes'' Cambridge University Press (2017). https://doi.org/10.1017/9781316219317 https://books.google.ca/books?id=I9gcDgAAQBAJ [11] Tom Cooney, Marius Junge, Carlos Palazuelos, and David Pérez-García, ``Rank-one quantum games'' computational complexity 24, 133–196 (2011). https://doi.org/10.1007/s00037-014-0096-x https://api.semanticscholar.org/CorpusID:6122906 [12] Jason Crann, Rupert H. Levene, Ivan G. Todorov, and Lyudmila Turowska, ``Values of cooperative quantum games'' (2023). arXiv:2310.17735 [13] Runyao Duanand Andreas Winter ``No-Signalling-Assisted Zero-Error Capacity of Quantum Channels and an Information Theoretic Interpretation of the Lovász Number'' IEEE Transactions on Information Theory 62, 891–914 (2016). https://doi.org/10.1109/TIT.2015.2507979 [14] Tobias Fritz ``Tsirelson's problem and Kirchberg's conjecture'' Reviews in Mathematical Physics 24, 1250012 (2012). https://doi.org/10.1142/S0129055X12500122 [15] Adina Goldberg ``Synchronous and quantum games: Graphical and algebraic methods'' thesis (2025) Available online at https://hdl.handle.net/10012/21736. https://hdl.handle.net/10012/21736 [16] Gage Hoeferand Ivan G. Todorov ``Quantum hypergraph homomorphisms and non-local games'' (2022). arXiv:2211.04851 [17] Gage Hoeferand Ivan G. Todorov ``Homomorphisms of quantum hypergraphs'' Journal of Mathematical Analysis and Applications 543, 128907 (2025). https://doi.org/10.1016/j.jmaa.2024.128907 https://www.sciencedirect.com/science/article/pii/S0022247X24008291 [18] C. Heunenand J. Vicary ``Categories for Quantum Theory: An Introduction'' Oxford University Press (2019). https://books.google.ca/books?id=PdG8DwAAQBAJ [19] Nathaniel Johnston, Rajat Mittal, Vincent Russo, and John Watrous, ``Extended non-local games and monogamy-of-entanglement games'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 472, 20160003 (2016). https://doi.org/10.1098/rspa.2016.0003 [20] Andre Kornell ``Quantum sets'' Journal of Mathematical Physics 61, 102202 (2020). https://doi.org/10.1063/1.5054128 [21] Martino Lupini, Laura Mančinska, and David E. Roberson, ``Nonlocal games and quantum permutation groups'' Journal of Functional Analysis 279, 108592 (2020). https://doi.org/10.1016/j.jfa.2020.108592 https://www.sciencedirect.com/science/article/pii/S002212362030135X [22] Debbie W. Leung, Ben Toner, and John Watrous, ``Coherent state exchange in multi-prover quantum interactive proof systems'' Chic. J. Theor. Comput. Sci. 2013 (2008). https://doi.org/10.4086/cjtcs.2013.011 https://api.semanticscholar.org/CorpusID:1517639 [23] Laura Mančinskaand David E. Roberson ``Quantum homomorphisms'' Journal of Combinatorial Theory, Series B 118, 228–267 (2016). https://doi.org/10.1016/j.jctb.2015.12.009 [24] Benjamin Musto, David Reutter, and Dominic Verdon, ``A compositional approach to quantum functions'' Journal of Mathematical Physics 59 (2018). https://doi.org/10.1063/1.5020566 [25] Vern Paulsen ``Entanglement and Non-Locality'' University of Waterloo lecture notes for PMATH 990/QIC 890 (2016). [26] Vern I. Paulsen, Simone Severini, Daniel Stahlke, Ivan G. Todorov, and Andreas Winter, ``Estimating quantum chromatic numbers'' Journal of Functional Analysis 270, 2188–2222 (2016). https://doi.org/10.1016/j.jfa.2016.01.010 [27] Vern I.
Paulsenand Mizanur Rahaman ``Bisynchronous games and factorizable maps'' Annales Henri Poincaré 22, 593–614 (2021). https://doi.org/10.1007/s00023-020-01003-2 [28] Carlos Palazuelosand Thomas Vidick ``Survey on nonlocal games and operator space theory'' Journal of Mathematical Physics 57, 015220 (2016). https://doi.org/10.1063/1.4938052 [29] Oded Regevand Thomas Vidick ``Quantum XOR Games'' ACM Trans. Comput. Theory 7 (2015). https://doi.org/10.1145/2799560 [30] Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski, and Stephanie Wehner, ``A monogamy-of-entanglement game with applications to device-independent quantum cryptography'' New Journal of Physics 15, 103002 (2013). https://doi.org/10.1088/1367-2630/15/10/103002 [31] Ivan G Todorovand Lyudmila Turowska ``Quantum no-signalling correlations and non-local games'' Communications in Mathematical Physics 405, 141 (2024). https://doi.org/10.1007/s00220-024-05001-x [32] Jamie Vicary ``Categorical Formulation of Finite-Dimensional Quantum Algebras'' Communications in Mathematical Physics 304, 765–796 (2010). https://doi.org/10.1007/s00220-010-1138-0 [33] Nik Weaver ``Quantum relations'' (2010). arXiv:1005.0354Cited byCould not fetch Crossref cited-by data during last attempt 2026-01-14 11:55:30: Could not fetch cited-by data for 10.22331/q-2026-01-14-1964 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-01-14 11:55:31: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractIn the flavour of categorical quantum mechanics, we extend nonlocal games to allow quantum questions and answers, using quantum sets (special symmetric dagger Frobenius algebras) and the quantum functions of Musto, Reutter, and Verdon. Equations are presented using a diagrammatic calculus for tensor categories. To this quantum question and answer setting, we extend the standard definitions, including strategies, correlations, and synchronicity, and we use these definitions to extend results about synchronicity. We extend the graph homomorphism (isomorphism) game to quantum graphs, and show it is synchronous (bisynchronous) and connect its perfect (bi)strategies to quantum graph homomorphisms (isomorphisms). Our extended definitions agree with the existing quantum games literature, except in the case of synchronicity.Featured image: This graphical Cauchy-Schwarz style inequality for quantum functions $E,F$ is a key graphical tool established here and used to study synchronous quantum games.Talk at Isaac Newton Institute relating to this paper: Podcast episode aimed at the public, discussing the graphical calculus and the emphasis of relational/compositional structures. Popular summaryNonlocal games are theoretical protocols in quantum information theory, where two separated parties aim to cooperate in a task overseen by a referee. Given some (classical) question data, each party needs to respond with a (classical) answer. The two parties may make use of a shared quantum resource. Nonlocal games are used to study foundational concepts in quantum information theory, often in an experimentally verifiable way. This paper approaches nonlocal games using graphical equations, with the aim of integrating nonlocal games with the larger program of categorical quantum mechanics (CQM). CQM invites a compositional, categorical approach to quantum information. By recasting nonlocal games in the language of CQM, we are able to naturally generalize them to quantum games (where the question and answer data may be quantum states). We extend some well-studied properties of nonlocal games. We also quantize some general classes of nonlocal games played on graphs.► BibTeX data@article{Goldberg2026quantumgames, doi = {10.22331/q-2026-01-14-1964}, url = {https://doi.org/10.22331/q-2026-01-14-1964}, title = {Quantum games and synchronicity}, author = {Goldberg, Adina}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1964}, month = jan, year = {2026} }► References [1] Samson Abramskyand Bob Coecke ``A categorical semantics of quantum protocols'' Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, 2004. 415-425 (2004). https://doi.org/10.1109/LICS.2004.1319636 [2] Albert Atserias, Laura Mančinska, David Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis, ``Quantum and non-signalling graph isomorphisms'' Journal of Combinatorial Theory, Series B 136 (2019). https://doi.org/10.1016/j.jctb.2018.11.002 [3] Michael Brannan, Priyanga Ganesan, and Samuel J. Harris, ``The quantum-to-classical graph homomorphism game'' Journal of Mathematical Physics 63, 112204 (2022). https://doi.org/10.1063/5.0072288 [4] Arkadiusz Bochniak, Paweł Kasprzak, and Piotr M Sołtan, ``Quantum Correlations on Quantum Spaces'' International Mathematics Research Notices 2023, 12400–12440 (2023). https://doi.org/10.1093/imrn/rnac139 [5] Michael Brannan, Alexandru Chirvasitu, Kari Eifler, Samuel Harris, Vern Paulsen, Xiaoyu Su, and Mateusz Wasilewski, ``Bigalois Extensions and the Graph Isomorphism Game'' Communications in Mathematical Physics 375, 1777–1809 (2019). https://doi.org/10.1007/s00220-019-03563-9 [6] Michael Brannan, Samuel J. Harris, Ivan G. Todorov, and Lyudmila Turowska, ``Synchronicity for quantum non-local games'' Journal of Functional Analysis 284, 109738 (2023). https://doi.org/10.1016/j.jfa.2022.109738 https://www.sciencedirect.com/science/article/pii/S0022123622003585 [7] Michael Brannan, Samuel J. Harris, Ivan G. Todorov, and Lyudmila Turowska, ``Quantum no-signalling bicorrelations'' Advances in Mathematics 449, 109732 (2024). https://doi.org/10.1016/j.aim.2024.109732 https://www.sciencedirect.com/science/article/pii/S0001870824002470 [8] Francesco Buscemi ``All entangled quantum states are nonlocal.'' Physical review letters 108 20, 200401 (2011). https://doi.org/10.1103/PhysRevLett.108.200401 https://api.semanticscholar.org/CorpusID:14393220 [9] Bob Coecke, Chris Heunen, and Aleks Kissinger, ``Categories of Quantum and Classical Channels'' Quantum Information Processing 15 (2013). https://doi.org/10.1007/s11128-014-0837-4 [10] B. Coeckeand A. Kissinger ``Picturing Quantum Processes'' Cambridge University Press (2017). https://doi.org/10.1017/9781316219317 https://books.google.ca/books?id=I9gcDgAAQBAJ [11] Tom Cooney, Marius Junge, Carlos Palazuelos, and David Pérez-García, ``Rank-one quantum games'' computational complexity 24, 133–196 (2011). https://doi.org/10.1007/s00037-014-0096-x https://api.semanticscholar.org/CorpusID:6122906 [12] Jason Crann, Rupert H. Levene, Ivan G. Todorov, and Lyudmila Turowska, ``Values of cooperative quantum games'' (2023). arXiv:2310.17735 [13] Runyao Duanand Andreas Winter ``No-Signalling-Assisted Zero-Error Capacity of Quantum Channels and an Information Theoretic Interpretation of the Lovász Number'' IEEE Transactions on Information Theory 62, 891–914 (2016). https://doi.org/10.1109/TIT.2015.2507979 [14] Tobias Fritz ``Tsirelson's problem and Kirchberg's conjecture'' Reviews in Mathematical Physics 24, 1250012 (2012). https://doi.org/10.1142/S0129055X12500122 [15] Adina Goldberg ``Synchronous and quantum games: Graphical and algebraic methods'' thesis (2025) Available online at https://hdl.handle.net/10012/21736. https://hdl.handle.net/10012/21736 [16] Gage Hoeferand Ivan G. Todorov ``Quantum hypergraph homomorphisms and non-local games'' (2022). arXiv:2211.04851 [17] Gage Hoeferand Ivan G. Todorov ``Homomorphisms of quantum hypergraphs'' Journal of Mathematical Analysis and Applications 543, 128907 (2025). https://doi.org/10.1016/j.jmaa.2024.128907 https://www.sciencedirect.com/science/article/pii/S0022247X24008291 [18] C. Heunenand J. Vicary ``Categories for Quantum Theory: An Introduction'' Oxford University Press (2019). https://books.google.ca/books?id=PdG8DwAAQBAJ [19] Nathaniel Johnston, Rajat Mittal, Vincent Russo, and John Watrous, ``Extended non-local games and monogamy-of-entanglement games'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 472, 20160003 (2016). https://doi.org/10.1098/rspa.2016.0003 [20] Andre Kornell ``Quantum sets'' Journal of Mathematical Physics 61, 102202 (2020). https://doi.org/10.1063/1.5054128 [21] Martino Lupini, Laura Mančinska, and David E. Roberson, ``Nonlocal games and quantum permutation groups'' Journal of Functional Analysis 279, 108592 (2020). https://doi.org/10.1016/j.jfa.2020.108592 https://www.sciencedirect.com/science/article/pii/S002212362030135X [22] Debbie W. Leung, Ben Toner, and John Watrous, ``Coherent state exchange in multi-prover quantum interactive proof systems'' Chic. J. Theor. Comput. Sci. 2013 (2008). https://doi.org/10.4086/cjtcs.2013.011 https://api.semanticscholar.org/CorpusID:1517639 [23] Laura Mančinskaand David E. Roberson ``Quantum homomorphisms'' Journal of Combinatorial Theory, Series B 118, 228–267 (2016). https://doi.org/10.1016/j.jctb.2015.12.009 [24] Benjamin Musto, David Reutter, and Dominic Verdon, ``A compositional approach to quantum functions'' Journal of Mathematical Physics 59 (2018). https://doi.org/10.1063/1.5020566 [25] Vern Paulsen ``Entanglement and Non-Locality'' University of Waterloo lecture notes for PMATH 990/QIC 890 (2016). [26] Vern I. Paulsen, Simone Severini, Daniel Stahlke, Ivan G. Todorov, and Andreas Winter, ``Estimating quantum chromatic numbers'' Journal of Functional Analysis 270, 2188–2222 (2016). https://doi.org/10.1016/j.jfa.2016.01.010 [27] Vern I.
Paulsenand Mizanur Rahaman ``Bisynchronous games and factorizable maps'' Annales Henri Poincaré 22, 593–614 (2021). https://doi.org/10.1007/s00023-020-01003-2 [28] Carlos Palazuelosand Thomas Vidick ``Survey on nonlocal games and operator space theory'' Journal of Mathematical Physics 57, 015220 (2016). https://doi.org/10.1063/1.4938052 [29] Oded Regevand Thomas Vidick ``Quantum XOR Games'' ACM Trans. Comput. Theory 7 (2015). https://doi.org/10.1145/2799560 [30] Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski, and Stephanie Wehner, ``A monogamy-of-entanglement game with applications to device-independent quantum cryptography'' New Journal of Physics 15, 103002 (2013). https://doi.org/10.1088/1367-2630/15/10/103002 [31] Ivan G Todorovand Lyudmila Turowska ``Quantum no-signalling correlations and non-local games'' Communications in Mathematical Physics 405, 141 (2024). https://doi.org/10.1007/s00220-024-05001-x [32] Jamie Vicary ``Categorical Formulation of Finite-Dimensional Quantum Algebras'' Communications in Mathematical Physics 304, 765–796 (2010). https://doi.org/10.1007/s00220-010-1138-0 [33] Nik Weaver ``Quantum relations'' (2010). arXiv:1005.0354Cited byCould not fetch Crossref cited-by data during last attempt 2026-01-14 11:55:30: Could not fetch cited-by data for 10.22331/q-2026-01-14-1964 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-01-14 11:55:31: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
Tags
Source Information
Discussion
0 professional contributions
Sign in to join this professional discussion.
Be the first to add a constructive contribution.