The Quantum Monad on Relational Structures

Add to your list(s) Download to your calendar using vCal

• Nadish de Silva (University of Cambridge)
• Friday 08 November 2019, 14:00-15:00
• FW26.

If you have a question about this talk, please contact Jean Pichon-Pharabod.

This talk has been canceled/deleted

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 show a general connection between these notions and state-independent quantum realizations of strong contextuality in the Abramsky-Brandenburger formulation of contextuality. 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. https://arxiv.org/abs/1705.07310

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.