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

20 pages

Cited by in corpus (12)

• A compositional approach to quantum functions
• Contextuality and Wigner negativity are equivalent for continuous-variable quantum measurements
• Orthogonality for Quantum Latin Isometry Squares
• Quantum sets
• Categories of Empirical Models
• A complete characterisation of All-versus-Nothing arguments for stabiliser states
• The Sheaf-Theoretic Structure of Definite Causality
• Corrected Bell and Noncontextuality Inequalities for Realistic Experiments
• Closing Bell: Boxing black box simulations in the resource theory of contextuality
• Continuous-variable nonlocality and contextuality
• Relating Structure and Power: Extended Version
• Effectus of Quantum Probability on Relational Structures