2026-08-16T22:15:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8129 2024-03-06T10:40:53Z ddc:004 open_access

The Quantum Monad on Relational Structures Abramsky, Samson Barbosa, Rui Soares de Silva, Nadish Zapata, Octavio non-local games quantum computation monads Homomorphisms between relational structures play a central role in finite model theory, constraint satisfaction, and database theory. A central theme in quantum computation is to show how quantum resources can be used to gain advantage in information processing tasks. In particular, non-local games have been used to exhibit quantum advantage in boolean constraint satisfaction, and to obtain quantum versions of graph invariants such as the chromatic number. We show how quantum strategies for homomorphism games between relational structures can be viewed as Kleisli morphisms for a quantum monad on the (classical) category of relational structures and homomorphisms. We use these results to exhibit a wide range of examples of contextuality-powered quantum advantage, and to unify several apparently diverse strands of previous work. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Samson Abramsky and Rui Soares Barbosa and Nadish de Silva and Octavio Zapata 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.35 urn:nbn:de:0030-drops-81290 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.35 eng https://creativecommons.org/licenses/by/3.0/legalcode