So far, most of the literature on (quantum) contextuality and the Kochen–\nSpecker theorem seems either to concern particular examples of contextuality, or be\nconsidered as quantum logic. Here, we develop a general formalism for contextuality\nscenarios based on the combinatorics of hypergraphs, which significantly refines a similar\nrecent approach by Cabello, Severini and Winter (CSW). In contrast to CSW, we\nexplicitly include the normalization of probabilities, which gives us a much finer control\nover the various sets of probabilistic models like classical, quantum and generalized\nprobabilistic. In particular, our framework specializes to (quantum) nonlocality in the\ncase of Bell scenarios, which arise very naturally from a certain product of contextuality\nscenarios due to Foulis and Randall. In the spirit of CSW, we find close relationships to\nseveral graph invariants. The recently proposed Local Orthogonality principle turns out\nto be a special case of a general principle for contextuality scenarios related to the Shannon\ncapacity of graphs. Our results imply that it is strictly dominated by a low level of\nthe Navascués–Pironio–Acín hierarchy of semidefinite programs, which we also apply\nto contextuality scenarios.\nWe derive a wealth of results in our framework, many of these relating to quantum\nand supraquantum contextuality and nonlocality, and state numerous open problems.\nFor example, we show that the set of quantum models on a con
So far, most of the literature on (quantum) contextuality and the Kochen–\nSpecker theorem seems either to concern particular examples of contextuality, or be\nconsidered as quantum logic. Here, we develop a general formalism for contextuality\nscenarios based on the combinatorics of hypergraphs, which significantly refines a similar\nrecent approach by Cabello, Severini and Winter (CSW). In contrast to CSW, we\nexplicitly include the normalization of probabilities, which gives us a much finer control\nover the various sets of probabilistic models like classical, quantum and generalized\nprobabilistic. In particular, our framework specializes to (quantum) nonlocality in the\ncase of Bell scenarios, which arise very naturally from a certain product of contextuality\nscenarios due to Foulis and Randall. In the spirit of CSW, we find close relationships to\nseveral graph invariants. The recently proposed Local Orthogonality principle turns out\nto be a special case of a general principle for contextuality scenarios related to the Shannon\ncapacity of graphs. Our results imply that it is strictly dominated by a low level of\nthe Navascués–Pironio–Acín hierarchy of semidefinite programs, which we also apply\nto contextuality scenarios.\nWe derive a wealth of results in our framework, many of these relating to quantum\nand supraquantum contextuality and nonlocality, and state numerous open problems.\nFor example, we show that the set of quantum models on a con
Cabello-Severini-Winter and Abramsky-Hardy (building on the framework of Abramsky-Brandenburger) both provide classes of Bell and contextuality inequalities for very general experimental scenarios using vastly different mathematical techniques. We review both approaches, carefully detail the links between them, and give simple, graph-theoretic methods for finding inequality-free proofs of nonlocality and contextuality and for finding states exhibiting strong nonlocality and/or contextuality. Finally, we apply these methods to concrete examples in stabilizer quantum mechanics relevant to understanding contextuality as a resource in quantum computation.
Quantum mechanics allows only certain sets of experimental results (or ``probabilistic models'') for Bell-type quantum nonlocality experiments. A derivation of this set from simple physical or information theoretic principles would represent an important step forward in our understanding of quantum mechanics, and this problem has been intensely investigated in recent years. ``Macroscopic locality,'' which requires the recovery of locality in the limit of large numbers of trials, is one of several principles discussed in the literature that place a bound on the set of quantum probabilistic models. A similar question can also be asked about probabilistic models for the more general class of quantum contextuality experiments. Here, we extend the macroscopic locality principle to this more general setting, using the hypergraph approach of Ac\'{\i}n, Fritz, Leverrier, and Sainz [Comm. Math. Phys. 334(2), 533--628 (2015)], which provides a framework to study both phenomena of nonlocality and contextuality in a unified manner. We find that the set of probabilistic models allowed by our macroscopic noncontextuality principle is equivalent to an important and previously studied set in this formalism, which is slightly larger than the quantum set. In the particular case of Bell scenarios, this set is equivalent to the set of ``almost-quantum'' models, which is of particular interest since the latter was recently shown to satisfy all but one of the principles that have been proposed to bound quantum probabilistic models, without being implied by any of them (or even their conjunction). Our condition is the first characterization of the almost-quantum set from a simple physical principle.
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.
Quantum theory departs from classical probabilistic theories in foundational ways. These departures--termed quantumness here--power quantum information and computation. This thesis charts the role of discrete structures in assessing quantumness, synthesizing elements of my postdoctoral research through this lens. After an introduction to the necessary background concepts, I present my work under three broad categories. First, I present work on contextuality that extensively relies on (undirected) graphs and hypergraphs as the discrete structures of interest; more specifically, it relies on invariants associated with them. This work includes Kochen-Specker (KS) contextuality and its operationalization to generalized contextuality, expressed via (hyper)graph-theoretic frameworks. I also present work on KS-contextuality in multiqubit systems and an application of generalized contextuality to a one-shot communication task, both of which rely on hypergraphs. Second, I present work on causality, where the discrete structures of interest are directed graphs. This includes work on indefinite causal order, specifically its connections to the gap between local operations and classical communication (LOCC) and separable operations (SEP), and a device-independent notion of nonclassicality--termed antinomicity--that generalizes Bell nonlocality without global causal assumptions. Finally, I present work on the incompatibility of quantum measurements, its connection to Bell nonlocality, and its role in discriminating between quantum and almost quantum correlations in the single-system setting. The discrete structures of interest here are hypergraphs that model joint measurability relations between quantum measurements. I conclude with a summary and an overview of work that is not covered in this thesis.
Contextuality is a key signature of quantum non-classicality, which has been shown to play a central role in enabling quantum advantage for a wide range of information-processing and computational tasks. We study the logic of contextuality from a structural point of view, in the setting of partial Boolean algebras introduced by Kochen and Specker in their seminal work. These contrast with traditional quantum logic à la Birkhoff and von Neumann in that operations such as conjunction and disjunction are partial, only being defined in the domain where they are physically meaningful. We study how this setting relates to current work on contextuality such as the sheaf-theoretic and graph-theoretic approaches. We introduce a general free construction extending the commeasurability relation on a partial Boolean algebra, i.e. the domain of definition of the binary logical operations. This construction has a surprisingly broad range of uses. We apply it in the study of a number of issues, including: - establishing the connection between the abstract measurement scenarios studied in the contextuality literature and the setting of partial Boolean algebras; - formulating various contextuality properties in this setting, including probabilistic contextuality as well as the strong, state-independent notion of contextuality given by Kochen-Specker paradoxes, which are logically contradictory statements validated by partial Boolean algebras, specifically those arising from quantum mechanics; - investigating a Logical Exclusivity Principle, and its relation to the Probabilistic Exclusivity Principle widely studied in recent work on contextuality as a step towards closing in on the set of quantum-realisable correlations; - developing some work towards a logical presentation of the Hilbert space tensor product, using logical exclusivity to capture some of its salient quantum features.
In the past century, experimental discoveries have witnessed phenomena in Nature which challenge our everyday classical intuition. In order to explain these facts, quantum theory was developed, which so far has been able to reproduce the observed results. However, I believe that our understanding of quantum mechanics can be significantly improved by the search for an operational meaning behind its mathematical formulation, which would help to identify the limitations and possibilities of the theory for information processing. An intriguing property of quantum theory is its intrinsic randomness. Indeed, Einstein, Podolsky and Rosen in 1935 questioned the completeness of quantum theory. They argued the possibility of the existence of a complete theory where variables to which we have not access determine the behaviour of physical systems, and the randomness observed in quantum mechanics is then due to our ignorance of these variables. These hidden variables theories, however, were proved not to be enough for explaining the predictions of quantum theory, as shown in the no-go theorems by Bell on quantum-nonlocality and by Kochen and Specker on quantum-contextuality. In the past decades, many experiments have corroborated the nonlocal and contextual character of Nature. However, no intuition behind these phenomena has been found, in particular about what limits their strength. In fact, special relativity alone would allow for phenomena which are more nonlocal than what quantum theory allows. Hence, much effort has been devoted to find the physical properties of quantum theory that restricts these phenomena. In this thesis, we study the constraints that arise on nonlocal and contextual phenomena when a certain exclusiveness structure compatible with quantum theory is imposed in the space of events. Here, an event denotes the situation where an outcome is obtained given that a measurement is performed on the physical system. Regarding nonlocality, we introduce a notion of orthogonality that states that events involving different outcomes of the same local measurement are exclusive, and construct constraints that the correlations among observers should satisfy. We denote this by Local Orthogonality principle (LO), which is the first intrinsically multipartite principle for bounding quantum correlations. We prove that LO identifies the supra-quantum character of some bipartite and multipartite correlations, and gets close to the quantum boundary. When studying contextuality, the same abstract event may correspond to outcomes of different measurements, which introduces a non-trivial structure in the space of events. For its study, we develop a general formalism for contextuality scenarios in the spirit of the recent approach by Cabello, Severini and Winter. In our framework, nonlocality arises as a particular case of contextuality, which allows us to study a generalization of LO. Both in nonlocality and contextuality, we find close connections to problems in combinatorics and hence use graph-theoretical tools for studying correlations. Finally, this thesis also studies the detection of nonlocal correlations. Most results on quantum nonlocality focus on few particles' experiments, while less is known about the detection of quantum nonlocality in many-body systems. Standard many-body observables involve correlations among few particles, while there is still no multipartite Bell inequality to test nonlocality merely from these data. In this thesis, we provide the first proposal for nonlocality detection in many-body systems using two-body correlations. We construct families of Bell inequalities from two-body correlators, which can detect nonlocality for systems with large number of constituents. In addition, we prove violations by systems which are relevant in nuclear and atomic physics, and show how to test these inequalities by measuring global spin components, hence opening the problem to experimental realizations.