The quantum monad on relational structures
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...
| Main Authors: | , , , |
|---|---|
| Formato: | Conference item |
| Publicado em: |
Schloss Dagstuhl – Leibniz Center for Informatics
2017
|
| _version_ | 1826307279159296000 |
|---|---|
| author | Abramsky, S Barbosa, RS de Silva, N Zapata, O |
| author_facet | Abramsky, S Barbosa, RS de Silva, N Zapata, O |
| author_sort | Abramsky, S |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T07:00:32Z |
| format | Conference item |
| id | oxford-uuid:ff966d42-a16f-45bd-af9c-21b32f9ed28d |
| institution | University of Oxford |
| last_indexed | 2024-03-07T07:00:32Z |
| publishDate | 2017 |
| publisher | Schloss Dagstuhl – Leibniz Center for Informatics |
| record_format | dspace |
| spelling | oxford-uuid:ff966d42-a16f-45bd-af9c-21b32f9ed28d2022-03-27T13:46:06ZThe quantum monad on relational structuresConference itemhttp://purl.org/coar/resource_type/c_5794uuid:ff966d42-a16f-45bd-af9c-21b32f9ed28dSymplectic Elements at OxfordSchloss Dagstuhl – Leibniz Center for Informatics2017Abramsky, SBarbosa, RSde Silva, NZapata, OHomomorphisms 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. |
| spellingShingle | Abramsky, S Barbosa, RS de Silva, N Zapata, O The quantum monad on relational structures |
| title | The quantum monad on relational structures |
| title_full | The quantum monad on relational structures |
| title_fullStr | The quantum monad on relational structures |
| title_full_unstemmed | The quantum monad on relational structures |
| title_short | The quantum monad on relational structures |
| title_sort | quantum monad on relational structures |
| work_keys_str_mv | AT abramskys thequantummonadonrelationalstructures AT barbosars thequantummonadonrelationalstructures AT desilvan thequantummonadonrelationalstructures AT zapatao thequantummonadonrelationalstructures AT abramskys quantummonadonrelationalstructures AT barbosars quantummonadonrelationalstructures AT desilvan quantummonadonrelationalstructures AT zapatao quantummonadonrelationalstructures |