The Quad- C 5 C_{5} Graph: Maximum Contextuality Gap on Eight Vertices
Ugur Tamer, Özgür E. Müstecaplıoğlu, Alper Dizdar, Zafer Gedik · 2026
Read The Quad- C 5 C_{5} Graph: Maximum Contextuality Gap on Eight Vertices by Ugur Tamer, Özgür E. Müstecaplıoğlu, Alper Dizdar, Zafer Gedik (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-12828.txt.
Introduction
Tamer and four colleagues search all 11,117 connected eight-vertex graphs for the strongest separation between quantum predictions and noncontextual explanations of measurement outcomes. They identify a sparse ten-edge graph, Quad-C5, built from four overlapping five-event pentagons, as the unique maximiser. It already shows contextuality in a three-level system and, in a four-level system, reaches the full graph-theoretic quantum bound.
Catalog record
| CREATOR | Ugur Tamer, Özgür E. Müstecaplıoğlu, Alper Dizdar, Zafer Gedik |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51123 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.12828
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Quad- C 5 C_{5} Graph: Maximum Contextuality Gap on Eight Vertices Ugur Tamer, Özgür E. Müstecaplıoğlu, Alper Dizdar, Zafer Gedik Abstract Quantum contextuality rules out classical descriptions in which measurement outcomes are independent of the compatible measurements performed alongside them. While the KCBS pentagon provides the minimal qutrit test, identifying larger but still compact contextuality witnesses remains important for understanding how contextuality can be organized, amplified, and benchmarked. We solve the eight-event version of this problem within the graph-theoretic framework for contextuality. An exhaustive search over all 11,117 connected non-isomorphic graphs with eight vertices identifies a sparse ten-edge graph, which we call Quad- C 5 \text{Quad-}C_{5} , as the maximum-gap witness. The graph has a larger absolute contextuality gap than the Wagner graph, a standard eight-vertex benchmark, despite having fewer exclusivity relations. Its structure is transparent: it is formed from four overlapping KCBS pentagons, with each edge shared by two pentagons. We prove that Quad- C 5 \text{Quad-}C_{5} is already contextual for a single qutrit by giving an explicit three-dimensional construction. In this qutrit realization its contextuality margin equals that of KCBS, whereas its full quantum advantage is reached numerically in four dimensions and exceeds that of the Wagner graph. Quad- C 5 \text{Quad-}C_{5} therefore provides a compact bridge between minimal qutrit contextuality and stronger four-dimensional contextuality witnesses. I Introduction Quantum contextuality KochenSpecker1967 captures an irreducible tension between quantum mechanics and classical realism: measurement outcomes cannot, in general, be assigned pre-existing values independently of which compatible measurements are performed alongside them. Unlike Bell nonlocality, contextuality does not require spatially separated subsystems and can already appear in a single finite-dimensional quantum system. This makes it both a foundational signature of nonclassicality and a resource for quantum information processing, with established connections to quantum computation, communication, and sensing Budroni2022 ; Howard2014 ; Raussendorf2013 . Identifying simple yet strong contextuality witnesses is a central goal in this program. The Klyachko–Can–Binicioğlu–Shumovsky (KCBS) construction demonstrated that five cyclically compatible measurements on a single spin-1 system are sufficient for a state-dependent contextuality test Klyachko2002 ; Klyachko2008 . This pentagonal structure became the canonical minimal qutrit example and was subsequently embedded in the broader family of n -cycle contextuality scenarios, where noncontextual inequalities and their quantum violations admit analytic characterization Araujo2013 . Such closed-form results are rare: separating classical, quantum, and more general probabilistic correlations is, in general, a hard problem. Most experimental contextuality tests have focused on minimal or highly structured scenarios, such as the KCBS pentagon for qutrits and n -cycle inequalities Araujo2013 . These examples are essential as foundational tests, but recent resource-theoretic developments motivate a broader question: how can contextuality be organized, amplified, and benchmarked in larger but still experimentally manageable exclusivity structures? This question is especially relevant because contextuality has been connected to advantages in quantum computation Howard2014 ; Raussendorf2013 , communication Gupta2023 , and metrology Lostaglio2020 . From this viewpoint, small-graph optimization plays a role analogous to the search for compact Bell inequalities or small quantum error-correcting codes: one seeks the strongest nonclassical signature under limited resources. Here we address the eight-vertex absolute-gap optimization problem beyond the analytically understood cycle family and the standard Wagner benchmark. A systematic approach to this optimization is provided by the graph-theoretic framework of Cabello, Severini, and Winter Cabello2014 . Each measurement event is represented as a vertex, and mutually exclusive events are connected by edges, yielding an exclusivity graph G=(V,E) . For projective measurements, the total event probability satisfies \alpha(G)\leq\sum_{i\in V}p_{i}\leq\vartheta(G), (1) where \alpha(G) is the independence number, giving the noncontextual bound, and \vartheta(G) is the Lovász theta number Lovasz1979 , giving the projective quantum bound Cabello2014 . The contextuality gap \Delta(G)=\vartheta(G)-\alpha(G) (2) measures the separation between quantum and noncontextual descriptions within this graph model; a larger gap provides a stronger contextuality resource Budroni2022 . Maximizing the contextuality gap for a fixed vertex count is a nontrivial combinatorial problem. Adding edges introduces additional exclusivity constraints that can suppress the quantum value, yet may also lower the classical bound and reorganize the geometry of the witness. Consequently, the densest or most symmetric graph need not yield the strongest contextuality, and even the eight-vertex case presents a non-obvious optimization landscape. Known examples chart the structure of this hierarchy. The pentagon C_{5} realizes the KCBS witness, and the seven-cycle C_{7} belongs to the analytically characterized n -cycle family Araujo2013 . At eight vertices, the Wagner graph has served as a standard non-cycle benchmark Cabello2014 ; Lovasz1979 . The full eight-vertex landscape, however, extends well beyond these symmetric examples, and it is not a priori clear whether any of these known graphs achieves the global maximum gap or whether a different, less symmetric structure outperforms them all. A closely related graph-enumeration program was used in the study of fully contextual correlations, where the independence number, Lovász theta number, and fractional packing number were computed for nonisomorphic graphs with fewer than 11 vertices Amselem2012 . This database was later used to identify experimentally accessible graphs maximizing the ratio \vartheta(G)/\alpha(G) , a relative measure of contextuality strength Canas2016 . The ratio \vartheta(G)/\alpha(G) has since been studied as a graph-based dimension witness Ray2021 , and the CSW exclusivity-graph framework has been extended to linear games and Bell inequalities Gnacinski2016 . Building on this graph-theoretic viewpoint, we focus on a complementary optimization criterion: the absolute CSW gap \Delta(G)=\vartheta(G)-\alpha(G) . This criterion selects compact witnesses with the largest absolute quantum advantage, determined by the largest additive separation between the quantum and noncontextual bounds. We use it to identify the optimal connected eight-vertex graph and then analyze the structure, dimension dependence, and noise robustness of the resulting witness. Maximizing \vartheta(G)/\alpha(G) favors large relative violations, often with smaller classical bounds, whereas maximizing \vartheta(G)-\alpha(G) favors large additive separations between the quantum and noncontextual limits. These two objectives need not select the same graph, and at eight vertices they do not. We resolve this question by an exhaustive semidefinite-programming search over all connected eight-vertex graphs. The numerically certified global maximum is attained by a ten-edge graph, which we call \text{Quad-}C_{5} , that outperforms both the Wagner graph and every cycle in this vertex range. Its structure is transparent: four overlapping KCBS pentagons share edges in a regular pattern, providing a compact mechanism by which KCBS-type contextuality is efficiently combined within a larger exclusivity graph. We additionally determine the minimal Hilbert-space dimension needed to realize this advantage. An explicit three-dimensional orthogonal representation establishes that \text{Quad-}C_{5} is already qutrit-contextual, and numerical evidence shows that its full graph-theoretic quantum value is first reached in four dimensions. The graph thus bridges minimal qutrit contextuality and the regime of stronger four-dimensional witnesses; we compare its noise robustness against both KCBS and Wagner. The paper is organized as follows. Section II reviews the graph-theoretic background and the dimension-restricted quantum quantities used in the analysis. Section III describes the exhaustive graph search and numerical certification. Section IV presents the \text{Quad-}C_{5} graph and its structural properties. Section V analyzes dimension dependence, noise robustness, and comparisons with KCBS and Wagner. Section VI discusses experimental implementation strategies and platform requirements. Section VII summarizes the conclusions. Appendix A provides the explicit qutrit construction establishing the analytic lower bound. Appendix B collects supplementary tables including the