Conference item
The quantum monad on relational structures
- Abstract:
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 588.4KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.MFCS.2017.35
Authors
- Publisher:
- Schloss Dagstuhl – Leibniz Center for Informatics
- Host title:
- 42nd International Symposium on Mathematical Foundations of Computer Science
- Journal:
- 42nd International Symposium on Mathematical Foundations of Computer Science More from this journal
- Publication date:
- 2017-11-01
- Acceptance date:
- 2017-06-12
- DOI:
- ISSN:
-
1868-8969
- Keywords:
- Pubs id:
-
pubs:710491
- UUID:
-
uuid:ff966d42-a16f-45bd-af9c-21b32f9ed28d
- Local pid:
-
pubs:710491
- Source identifiers:
-
710491
- Deposit date:
-
2017-08-03
Terms of use
- Copyright holder:
- Abramsky et al
- Copyright date:
- 2017
- Notes:
-
© Samson Abramsky, Rui Soares Barbosa, Nadish de Silva, and Octavio Zapata;
licensed under Creative Commons License CC-BY
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record