The quantum monad on relational structures

Samson Abramsky, Rui Soares Barbosa, Nadish De Silva, Octavio Zapata

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish
Title of host publication42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
EditorsKim G. Larsen, Hans L. Bodlaender, Jean-Francois Raskin
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages19
Volume83
ISBN (Electronic)9783959770460
DOIs
Publication statusPublished - 1 Nov 2017
Externally publishedYes
Event42nd International Symposium on Mathematical Foundations of Computer Science: August 21-25, 2017, Aalborg (Denmark) - Aalborg University, Aalborg, Denmark
Duration: 21 Aug 201725 Aug 2017
Conference number: 42
http://mfcs2017.cs.aau.dk/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
Volume83
ISSN (Electronic)1868-8969

Conference

Conference42nd International Symposium on Mathematical Foundations of Computer Science
Abbreviated titleMFCS 2017
Country/TerritoryDenmark
CityAalborg
Period21/08/1725/08/17
Internet address

Keywords

  • Monads
  • Non-local games
  • Quantum computation

Fingerprint

Dive into the research topics of 'The quantum monad on relational structures'. Together they form a unique fingerprint.

Cite this