We establish a strong link between two apparently unrelated topics: the study of conflicting information in the formal framework of valuation algebras, and the phenomena of non-locality and contextuality. In particular, we show that these peculiar features of quantum theory are mathematically equivalent to a general notion of disagreement between information sources. This result vastly generalizes previously observed connections between contextuality, relat- ional databases, constraint satisfaction problems and logical paradoxes, and gives further proof that contextual behaviour is not a phenomenon limited to quantum physics, but pervades various domains of mathematics and computer science. The connection allows to translate theorems, methods and algorithms from one field to the other, and paves the way for the application of generic inference algorithms to study contextuality. This article is part of the theme issue ‘Contextuality and probability in quantum mechanics and beyond’.
We establish a strong link between two apparently unrelated topics: the study of conflicting information in the formal framework of valuation algebras, and the phenomena of non-locality and contextuality. In particular, we show that these peculiar features of quantum theory are mathematically equivalent to a general notion of disagreement between information sources. This result vastly generalizes previously observed connections between contextuality, relat- ional databases, constraint satisfaction problems and logical paradoxes, and gives further proof that contextual behaviour is not a phenomenon limited to quantum physics, but pervades various domains of mathematics and computer science. The connection allows to translate theorems, methods and algorithms from one field to the other, and paves the way for the application of generic inference algorithms to study contextuality. This article is part of the theme issue ‘Contextuality and probability in quantum mechanics and beyond’.
The main subjects of this thesis are non-locality and contextuality, two fundamental features of quantum mechanics that constitute valuable resources for quantum computation. Our analysis is based on Abramsky & Brandenburger's sheaf theoretic framework, which captures both these phenomena in a unified treatment and in a very general setting. This high-level description transcends quantum physics and allows to precisely characterise the notion of contextuality as the apparent paradox realised by data being locally consistent but globally inconsistent. More specifically, we aim to develop a deeper understanding of so-called logical forms of contextuality, i.e. situations where the phenomenon can be witnessed using purely logical arguments, disregarding probabilities. The sheaf theoretic description of logical contextuality has recently inspired the development of a topological treatment of the phenomenon based on sheaf cohomology. In this thesis, we embark on a detailed analysis of the cohomology of contextuality, exposing key shortcomings in the current methods, and introducing an (almost) complete cohomological characterisation of logical forms of contextuality. More specifically, we show that, in its current formulation, sheaf cohomology does not constitute a complete invariant for contextuality, not even in its strongest forms, and that higher cohomology groups cannot be used to study the phenomenon. Then, we solve these issues by introducing a novel construction, which derives refined versions of the presheaves describing empirical models to expose their deeper extendability properties, resulting in a sheaf cohomological invariant which is applicable to the vast majority of empirical models, and conjectured to work universally. We propose a general theory of contextual semantics using the language of valuation algebras. In particular, we give a general definition of contextual behaviour as a fundamental gap between local agreement and global disagreement of information sources. Not only does this formalism aptly capture and generalise the known instances of contextuality beyond quantum theory, but it also provides inspiration for further applications of the phenomenon, and paves the way for the transfer of results and techniques between different fields. We give a prime example of this potential by developing faster algorithms to detect contextuality based on mainstream methods of generic inference. Finally, we turn our attention back to instances of contextuality in quantum physics, and study strong contextuality in multi-qubit states. We give a complete combinatorial characterisation of All-vs-Nothing proofs of strong contextuality in stabiliser quantum mechanics. This allows to produce the complete list of all stabiliser states exhibiting this kind of contextuality, which consitututes an important resource in certain models of quantum computation. Then, we extend our search for strongly contextual behaviour beyond stabiliser states, and identify the minimum quantum resources needed to realise strong non-locality. Additional results include a partial classification of strongly non-local models comprised of three-qubit states and local projective measurements, and the introduction of a new infinite family of strongly non-local three-qubit states.
Non-locality and contextuality are key features of quantum mechanics that distinguish it from classical physics. We aim to develop a deeper, more structural understanding of these phenomena, underpinned by robust and elegant mathematical theory with a view to providing clarity and new perspectives on conceptual and foundational issues. A general framework for logical non-locality is introduced and used to prove that 'Hardy's paradox' is complete for logical non-locality in all (2,2,l) and (2,k,2) Bell scenarios, a consequence of which is that Bell states are the only entangled two-qubit states that are not logically non-local, and that Hardy non-locality can be witnessed with certainty in a tripartite quantum system. A number of developments of the unified sheaf-theoretic approach to non-locality and contextuality are considered, including the first application of cohomology as a tool for studying the phenomena: we find cohomological witnesses corresponding to many of the classic no-go results, and completely characterise contextuality for large families of Kochen-Specker-like models. A connection with the problem of the existence of perfect matchings in k-uniform hypergraphs is explored, leading to new results on the complexity of deciding contextuality. A refinement of the sheaf-theoretic approach is found that captures partial approximations to locality/non-contextuality and can allow Bell models to be constructed from models of more general kinds which are equivalent in terms of non-locality/contextuality. Progress is made on bringing recent results on the nature of the wavefunction within the scope of the logical and sheaf-theoretic methods. Computational tools are developed for quantifying contextuality and finding generalised Bell inequalities for any measurement scenario which complement the research programme. This also leads to a proof that local ontological models with `negative probabilities' generate the no-signalling polytopes for all Bell scenarios.
A central result in the foundations of quantum mechanics is the Kochen-Specker theorem. In short, it states that quantum mechanics is in conflict with classical models in which the result of a measurement does not depend on which other compatible measurements are jointly performed. Here, compatible measurements are those that can be performed simultaneously or in any order without disturbance. This conflict is generically called quantum contextuality. In this article, we present an introduction to this subject and its current status. We review several proofs of the Kochen-Specker theorem and different notions of contextuality. We explain how to experimentally test some of these notions and discuss connections between contextuality and nonlocality or graph theory. Finally, we review some applications of contextuality in quantum information processing.
The theme of this issue is ‘Quantum contextuality, causality and freedom of choice.’ Contextuality, including non-locality as its special case, has long since becomeone of the central topics in foundations of quantum mechanics, also making inroads in computer science, psychology and linguistics. Contextuality (or lack thereof, non-contextuality) is a property of a system of measurements, broadly understood. The measurements have generally random outcomes, and, as a preliminary intuition, a system of measurements is contextual if one cannot find a joint distribution for their outcomes subject to certain constraints. A precise definition depends on how a system of measurements is represented, which can be done in several different ways.
Contextuality is a key feature of quantum mechanics that provides an important non-classical resource for quantum information and computation. Abramsky and Brandenburger used sheaf theory to give a general treatment of contextuality in quantum theory [New Journal of Physics 13 (2011) 113036]. However, contextual phenomena are found in other fields as well, for example database theory. In this paper, we shall develop this unified view of contextuality. We provide two main contributions: firstly, we expose a remarkable connection between contexuality and logical paradoxes; secondly, we show that an important class of contextuality arguments has a topological origin. More specifically, we show that "All-vs-Nothing" proofs of contextuality are witnessed by cohomological obstructions.