1 Search Results for "Zapata, Octavio"

Document
DOI: 10.4230/LIPIcs.MFCS.2017.35
The Quantum Monad on Relational Structures

Authors: Samson Abramsky, Rui Soares Barbosa, Nadish de Silva, and Octavio Zapata

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

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.
Cite as

Samson Abramsky, Rui Soares Barbosa, Nadish de Silva, and Octavio Zapata. The Quantum Monad on Relational Structures. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{abramsky_et_al:LIPIcs.MFCS.2017.35,
  author =	{Abramsky, Samson and Barbosa, Rui Soares and de Silva, Nadish and Zapata, Octavio},
  title =	{{The Quantum Monad on Relational Structures}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{35:1--35:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.35},
  URN =		{urn:nbn:de:0030-drops-81290},
  doi =		{10.4230/LIPIcs.MFCS.2017.35},
  annote =	{Keywords: non-local games, quantum computation, monads}
}
  • Refine by Author
  • 1 Abramsky, Samson
  • 1 Barbosa, Rui Soares
  • 1 Zapata, Octavio
  • 1 de Silva, Nadish

  • Refine by Classification

  • Refine by Keyword
  • 1 monads
  • 1 non-local games
  • 1 quantum computation

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact