Chromatic quantum contextuality is a criterion of quantum nonclassicality based on (hyper)graph coloring constraints. If a quantum hypergraph requires more colors than the number of outcomes per maximal observable (context), it lacks a classical realization with n-uniform outcomes per context. Consequently, it cannot represent a “completable” noncontextual set of coexisting n-ary outcomes per maximal observable. This result serves as a chromatic analogue of the Kochen-Specker theorem. We present an explicit example of a four-colorable quantum logic in dimension three. Furthermore, chromatic contextuality suggests a novel restriction on classical truth values, thereby excluding two-valued measures that cannot be extended to n-ary colorings. Using this framework, we establish new bounds for the house, pentagon, and pentagram hypergraphs, refining previous constraints.
Chromatic quantum contextuality is a criterion of quantum nonclassicality based on (hyper)graph coloring constraints. If a quantum hypergraph requires more colors than the number of outcomes per maximal observable (context), it lacks a classical realization with n-uniform outcomes per context. Consequently, it cannot represent a “completable” noncontextual set of coexisting n-ary outcomes per maximal observable. This result serves as a chromatic analogue of the Kochen-Specker theorem. We present an explicit example of a four-colorable quantum logic in dimension three. Furthermore, chromatic contextuality suggests a novel restriction on classical truth values, thereby excluding two-valued measures that cannot be extended to n-ary colorings. Using this framework, we establish new bounds for the house, pentagon, and pentagram hypergraphs, refining previous constraints.
We discuss representations and colorings of orthogonality hypergraphs in terms of their two-valued states interpretable as classical truth assignments. Such hypergraphs, if they allow for a faithful orthogonal representation, have quantum mechanical realizations in terms of intertwined contexts or maximal observables that are widely discussed as empirically testable criteria for contextuality. A reconstruction is possible for the class of perfectly separable hypergraphs. Colorings can be constructed from a minimal set of two-valued states. Some examples from exempt categories are presented, which either cannot be reconstructed by two-valued states or whose two-valued states cannot yield a chromatic number that is equal to the maximal clique number.
Intertwined complete projective experiments share outcomes, motivating the search for a common spectral labeling across contexts. Strong coloring tests whether complete contexts admit one context-independent nondegenerate spectrum; when that labeling exists, chromatic separability tests which event distinctions it preserves. We distinguish these questions from ordinary Kochen--Specker statelessness, geometric realizability, event-order representation, and Born-probability models. A state extends to a strong d-coloring exactly when deletion of its support leaves a (d-1)-colorable graph. Faithful real 17- and 21-ray restrictions of completed Yu--Oh have separating ordinary states but forced color identities; one quantum preparation requires exactly 1/9 nonextendable weight despite admitting an ordinary-state model. Independent Hermitian projection arguments correct earlier inferences from a chromatic gap to statelessness or nonrealizability. Hesse's complex 37-ray example separates real and complex geometry and has exact state-family minima 6/7/18 for three representation requirements. A rational two-plane construction gives a linear real 65-ray example with 393,216 states and explicit event-order and probability failures. General and specified ancestry results distinguish geometric KS extensions from abstract chromatic-to-stateless constructions. Detailed enumerations, regenerated state certificates, and extended proofs are supplementary.
Kochen-Specker (KS) theorem reveals the inconsistency between quantum theory and any putative underlying model of it satisfying the constraint of KS-noncontextuality. A logical proof of the KS theorem is one that relies only on the compatibility relations amongst a set of projectors (a KS set) to witness this inconsistency. These compatibility relations can be represented by a hypergraph, referred to as a contextuality scenario. Here we consider contextuality scenarios that we term KS-uncolourable, e.g., those which appear in logical proofs of the KS theorem. We introduce a hypergraph framework to obtain noise-robust witnesses of contextuality from such scenarios. Our approach builds on the results of R. Kunjwal and R. W. Spekkens, Phys. Rev. Lett. 115, 110403 (2015), by providing new insights into the relationship between the structure of a contextuality scenario and the associated noise-robust noncontextuality inequalities that witness contextuality. The present work also forms a necessary counterpart to the framework presented in R. Kunjwal, Quantum 3, 184 (2019), which only applies to KS-colourable contextuality scenarios, i.e., those which do not admit logical proofs of the KS theorem but do admit statistical proofs. We rely on a single hypergraph invariant, defined in R. Kunjwal, Quantum 3, 184 (2019), that appears in our contextuality witnesses, namely, the weighted max-predictability. The present work can also be viewed as a study of this invariant. Significantly, unlike the case of R. Kunjwal, Quantum 3, 184 (2019), none of the graph invariants from the graph-theoretic framework for KS-contextuality due to Cabello, Severini, and Winter (the ``CSW framework", Phys. Rev. Lett. 112, 040401 (2014)) are relevant for our noise-robust noncontextuality inequalities.
Quantum contextuality is a source of quantum computational power and a theoretical delimiter between classical and quantum structures. It has been substantiated by numerous experiments and prompted generation of state independent contextual sets, that is, sets of quantum observables capable of revealing quantum contextuality for any quantum state of a given dimension. There are two major classes of state-independent contextual sets—the Kochen-Specker ones and the operator-based ones. In this paper, we present a third, hypergraph-based class of contextual sets. Hypergraph inequalities serve as a measure of contextuality. We limit ourselves to qutrits and obtain thousands of 3-dim contextual sets. The simplest of them involves only 5 quantum observables, thus enabling a straightforward implementation. They also enable establishing new entropic contextualities.
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 quantum chromatic number of a graph G is sandwiched between its chromatic number and its clique number, which are well-known NP-hard quantities. We restrict our attention to the rank-1 quantum chromatic number χq(1)(G), which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number χ(G) and the minimum dimension of orthogonal representations ξ(G). It is known that ξ(G) ≤ χq(1)(G) ≤ χ(G). We answer three open questions about these relations: we give a necessary and sufficient condition to have ξ(G) = χq(1)(G), we exhibit a class of graphs such that ξ(G) ≤ χq(1)(G), and we give a necessary and sufficient condition to have χq(1)(G) ≤ χ(G). Our main tools are Kochen-Specker sets, collections of vectors with a traditionally important role in the study of contextuality of physical theories and, more recently, in the quantification of quantum zero-error capacities. Finally, as a corollary of our results and a result by Avis et al on the quantum chromatic number, we give a family of Kochen-Specker sets of growing dimension.