Rui Soares Barbosa  (INL)

Contextuality is a key signature of quantum non-classicality, which has been shown to play a central role in enabling quantum computational advantage. Kochen and Specker's seminal work on quantum contextuality contains elements of a logical flavour that have largely been overlooked in subsequent literature on the topic. In particular, it introduced the notion of partial Boolean algebra, which provides a natural (algebraic-)logical setting for contextual systems, corresponding to a calculus of partial propositional functions.

Partial Boolean algebras provide an alternative to traditional quantum logic à la Birkhoff–von Neumann in that operations such as conjunction and disjunction are partial, being only defined in the domain where they are physically meaningful. In the key example of the projectors on a Hilbert space, the operations are only defined for commuting projectors, which correspond to properties of a quantum system that can be tested simultaneously.

In this talk, we will give an introduction to partial Boolean algebras and discuss various topics arising in our recent work. Among other things, we extend the classical Lindenbaum–Tarski dualities between finite sets and finite Boolean algebras, and more generally, between sets and complete atomic Boolean algebras (CABAs), to the setting of (transitive) partial Boolean algebras. Specifically, we establish a dual equivalence between the category of transitive partial CABAs and a category of exclusivity graphs with an appropriate notion of morphism. Vertices of such exclusivity graphs may be interpreted as possible worlds of maximal information, with edges representing logical incompatibility or mutual exclusivity between two worlds: the classical case then corresponds to complete graphs, as all possible worlds are mutually exclusive. Our result shows, in particular, how any transitive partial CABA can be reconstructed from its graph of atoms with the logical exclusivity relation, as the partial algebra of (equivalence classes of) cliques. 

We also give an explicit construction of the free transitive partial CABA on a set of propositions with a compatibility relation, via an adjunction between compatibility graphs and exclusivity graphs that generalises the powerset self-adjunction in the classical case.

The duality reveals a connection between the algebraic-logical setting of partial Boolean algebra and the graph-theoretic approach to contextuality of Cabello–Severini–Winter. Under it, a transitive partial CABA witnessing contextuality, in the Kochen–Specker sense that it has no homomorphism to the two-element Boolean algebra, corresponds to an exclusivity graph with no ‘points’, i.e. no maps from the singleton graph, which correspond to stable, maximum clique transversal sets.