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.
Comments
HDR dissertation defended on December 8, 2025, at Aix-Marseille University; v2 updates the cover page with details of the Jury and the date of the defence; comments are welcome!
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.
Structures that demonstrate nonclassicality are of foundational interest in quantum mechanics, and can also be seen as resources for numerous applications in quantum information processing - particularly in the Hilbert space of N qubits. The theory of entanglement, quantum contextuality, and quantum nonlocality within the N-qubit Pauli group is further developed in this thesis. The Strong Kochen-Specker theorem and the structures that prove it are introduced and explored in detail. The pattern of connections between structures that show entanglement, contextuality, and nonlocality is explained. Computational search algorithms and related tools were developed and used to perform complete searches for minimal nonclassical structures within the N-qubit Pauli group up to values of N limited by our computational resources. Our results are surveyed and prescriptions are given for using the elementary nonclassical structures we have found to construct more complex types of such structures. Families of nonclassical structures are presented for all values of N, including the most compact family of projector-based parity proofs of the Kochen-Specker theorem yet discovered in all dimensions of the form 2N, where N≥2. The applications of our results and their connection with other work is also discussed.
Quantum theory departs from classical physics in its treatment of correlations, most prominently through the phenomena of contextuality and nonlocality. Once regarded primarily as foundational curiosities, these effects are now understood as key operational resources for quantum computation, communication, and simulation. Although traditionally investigated in distinct settings, recent theoretical and experimental advances have revealed deep conceptual, mathematical, and operational connections between them. This review presents a unified perspective on these developments based on sheaf-theoretic and graph-theoretic frameworks, which provide theory-independent characterizations of statistical correlations. These approaches clarify the structural relationship between contextuality and nonlocality, facilitate the formulation of experimentally testable inequalities, and guide implementations in realistic physical platforms, with particular emphasis on photonic systems. By bridging abstract theoretical structures and concrete experimental realizations, this review sheds light on the nonclassical foundations of quantum correlations and their emerging role in quantum technologies.
Quantum contextuality plays a significant role in supporting quantum computation and quantum information theory. The key tools for this are the Kochen-Specker and non-Kochen-Specker contextual sets. Traditionally, their representation has been predominantly operator-based, mainly focusing on specific constructs in dimensions ranging from three to eight. However, nearly all of these constructs can be represented as low-dimensional hypergraphs. This study demonstrates how to generate contextual hypergraphs in any dimension using various methods, particularly those that do not scale in complexity with increasing dimensions. Furthermore, we introduce innovative examples of hypergraphs extending to dimension 32. Our methodology reveals the intricate structural properties of hypergraphs, enabling precise quantifications of contextuality. Additionally, we investigate several promising applications of hypergraphs in quantum communication and quantum computation, paving the way for future breakthroughs in the field.
The fundamental nature of causality has been challenged by quantum theory. In particular, recent developments have shown that by relaxing the standard assumption that quantum events are embedded in a fixed background causal structure, a new kind of causal relations, indefinite, can emerge. These indefinite causal structures have been interpreted as causal loops allowing for the violation of a form of causality without paradoxes. On the other hand, quantum contextuality shows that any attempt to extend quantum theory such that classical logic holds in the extended domain fails due to the rise of inconsistent logical loops. There has been increasing evidence that it is a key feature in the understanding quantum paradoxes. This thesis aims at improving our understanding of indefinite causal orders and quantum paradoxes in order to address the question: “Could the non-fundamental nature of causality be related to a form of contextuality ?”The process matrix formalism is a mathematical framework which, in analogy withentanglement and the violation of Bell inequalities (nonlocality), offers new tools - witnesses of causal nonseparability and the violation of causal inequalities with noncausalcorrelations - to study and identify indefinite causal orders. In a bottom-up approach, wehave identified a large class of physically implementable processes, the quantum circuitswith quantum control of causal order (QC-QCs), that includes causally nonseparable processes such as the celebrated “quantum switch”. However these circuits cannot be used to violate causal inequalities. Nevertheless, in another work, I have proposed a significant relaxation of assumptions to certify the causal nonseparability of many processes, showing that it can be done in a semi-device-independent scenario with untrusted local operations and trusted quantum inputs. In particular, I have shown that the quantum switch can generate noncausal correlations in this kind of scenario.In order to refine my understanding of quantum contextuality, I have investigated theorigins of the Kochen-Specker theorem and I have analysed how the Hardy paradox entails a form of logical contextuality. I have identified that the two possible intermediatemeasurements involved in a pre-post-selection version of the paradox differ causally fromeach other. This analysis might be useful to study of the Frauchiger-Renner paradox, a“meta-version” of the Hardy paradox. On a more metaphysical aspect, I have argued fora “Gödelian hunch” from quantum theory, the idea that quantum paradoxes emerge froma lack of distinction between theoretical and metatheoretical objects.Finally, in order to establish a link between indefinite causal orders and contextuality,I have proposed a new causal game, in which the grandfather paradox is formalized interms of a logical inequality. Some process matrices can violate the causal inequalitywithout violating the logical one. I suggest that the emergence of logical inconsistenciesfrom the violation of a logical inequality might be interpreted as a form of contextuality.
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.
We address the problem of deriving the set of quantum correlations for every Bell and Kochen-Specker (KS) contextuality scenario from simple assumptions. We show that the correlations that are possible according to quantum theory are equal to those possible under the assumptions that there is a nonempty set of correlations for every KS scenario and a statistically independent realization of any two KS experiments. The proof uses tools of the graph-theoretic approach to correlations and deals with Bell nonlocality and KS contextuality in a unified way.