The Quad-$C_5$ Graph: Maximum Contextuality Gap on Eight Vertices

This paper identifies the "Quad-$C_5$" graph as the eight-vertex structure that maximizes the quantum contextuality gap between the Lovász theta function and the independence number, demonstrating its superiority over the Wagner graph in both gap magnitude and noise robustness while revealing its unique algebraic connection to the KCBS pentagon and qutrit systems.

The Gist

Imagine you are trying to solve a complex puzzle where the rules are dictated by the strange laws of quantum mechanics. In this puzzle, you have a set of "events" (like flipping a switch or measuring a particle). Some of these events are mutually exclusive—they cannot happen at the same time. If you draw a line between any two events that can't happen together, you create a map (or a graph) of exclusions.

The paper you provided is about finding the perfect map for an 8-point puzzle that reveals the biggest possible difference between how a classical world works and how a quantum world works.

Here is the story of their discovery, broken down into simple concepts:

1. The Game: Classical vs. Quantum

Think of a game where you have to assign "Yes" or "No" answers to different events.

• The Classical Rule: In a normal, everyday world, there is a limit to how many "Yes" answers you can give without breaking the rules of exclusivity. This limit is called the Independence Number ($\alpha$). It's like saying, "In a room of 8 people, you can pick at most 3 people who don't know each other."
• The Quantum Rule: In the quantum world, things are fuzzier. You can sometimes get a higher score than the classical limit allows. The maximum possible quantum score is called the Lovász Theta Function ($\vartheta$).
• The Gap ($\Delta$): The difference between the Quantum Score and the Classical Score is the Contextuality Gap. A bigger gap means the quantum world is acting more strangely and is a better "resource" for doing cool quantum tricks.

2. The Search: Finding the Champion

The authors wanted to find the best possible map for a puzzle with 8 points (vertices).

• They didn't just guess; they checked every single possible map that connects 8 points without breaking the rules. There were over 11,000 different maps to check!
• They used powerful computer math (called "semidefinite programming") to calculate the gap for every single one.

3. The Winner: The "Quad-C5" Graph

They found a new champion, which they named the Quad-C5 graph.

• Why it's special: It beats the previous champion, known as the "Wagner graph," by a significant margin.
• The Efficiency Surprise: Usually, you'd think a more complex map with more connections (lines/edges) would create a bigger gap. But the Quad-C5 graph actually wins with fewer connections (10 lines) than the old champion (12 lines).
  • Analogy: Imagine two bridges. The old bridge was heavy and had lots of steel beams. The new bridge is lighter, uses less steel, but holds up a heavier load. The Quad-C5 graph is a "lightweight champion" that gets more quantum power out of fewer resources.

4. The Secret Ingredient: The Golden Ratio

What makes this graph so powerful?

• The graph is built out of four overlapping pentagons (five-pointed shapes).
• In the world of math, the five-pointed shape (the "KCBS pentagon") is famous for being the simplest example of quantum weirdness.
• The Quad-C5 graph is like a "quad-core" processor made of these pentagons. The math behind it is deeply tied to the Golden Ratio (a famous number often found in nature, like in seashells or sunflowers).
• The authors discovered that the quantum advantage of this graph is exactly $1 + \sqrt{5}$. This connects the new graph directly to the old, famous pentagon, suggesting they are algebraic cousins.

5. The "Qutrit" vs. "Two-Qubit" Distinction

To play this quantum game, you need a physical system (like a photon or an atom).

• The Old Champion (Wagner): To get its full power, it needs a system with 4 levels (like two tiny magnets, or "two qubits"). This is harder to build in a lab.
• The New Champion (Quad-C5): It can achieve its maximum power using a system with only 3 levels (a "qutrit").
  • Analogy: The old champion needs a complex, expensive engine to run. The new champion runs just as fast (or faster) on a simpler, 3-cylinder engine. This makes it much easier for scientists to test in real experiments.

6. Noise Resistance: The "Static" Test

Real-world experiments are messy. There is "noise" (static) that can ruin the results.

• The authors tested how much noise each graph could handle before the quantum magic disappeared.
• The Coincidence: Surprisingly, the new Quad-C5 graph (when using the 3-level system) handles noise exactly as well as the simplest 5-point pentagon graph. Even though it is a much more complex 8-point map, it is just as tough against noise.
• The 4-Level Bonus: If you do use the more complex 4-level system, the Quad-C5 graph becomes even more robust than the old Wagner champion, handling noise better than anyone else.

Summary

The authors did a massive digital treasure hunt through 11,000 maps and found a new, simpler, and more powerful map called Quad-C5.

• It creates a bigger gap between classical and quantum reality than any previous 8-point map.
• It achieves this with fewer connections (lines) than the old record-holder.
• It is built from four overlapping pentagons, linking it mathematically to the Golden Ratio.
• It is easier to test in the lab because it works perfectly with simpler 3-level quantum systems, and it is incredibly tough against experimental noise.

This discovery tells us that to get the most out of quantum mechanics, you don't always need the most complicated or connected structures; sometimes, a cleverly arranged, lighter structure is the key to the strongest quantum advantage.

Technical Summary

Technical Summary: The Quad-C5 Graph and Maximum Contextuality Gap on Eight Vertices

Problem Statement
Quantum contextuality, the inability to assign non-contextual hidden-variable values to measurement outcomes, serves as a fundamental distinction between quantum mechanics and classical realism, as well as a resource for quantum information processing. Within the Cabello–Severini–Winter (CSW) framework, contextuality is quantified by the gap $\Delta(G) = \vartheta(G) - \alpha(G)$, where $\vartheta(G)$ is the Lovász theta function (the quantum bound for projective measurements) and $\alpha(G)$ is the independence number (the non-contextual bound) of an exclusion graph $G$. While small-cycle graphs like the five-cycle ($C_5$, the KCBS scenario) and seven-cycle ($C_7$) are known contextuality witnesses, the landscape of optimal witnesses for $n=8$ vertices was previously incomplete. The Wagner graph ($W$), a non-cycle example with $\Delta \approx 0.414$, had served as a prominent benchmark. The objective of this work is to perform an exhaustive search over all connected non-isomorphic simple graphs on eight vertices to identify the graph that maximizes $\Delta(G)$ and to characterize its algebraic and dimensional properties.

Methodology
The authors conducted an exhaustive computational search over the 11,117 connected non-isomorphic simple graphs on $n=8$ vertices, retrieved from McKay's database. The analysis pipeline involved:

1. Graph Enumeration and Filtering: All graphs were filtered for connectivity.
2. Independence Number ($\alpha$): Computed via maximum-weight clique search on the complement graph, cross-validated by brute-force enumeration of all $2^8$ vertex subsets.
3. Lovász Theta ($\vartheta$): Calculated using semidefinite programming (SDP). A bulk screening was performed using the SCS solver (precision $10^{-4}$–$10^{-6}$), followed by high-precision resolution ($\sim 10^{-10}$–$10^{-12}$) using the CLARABEL solver for the top 50 candidates. Uniqueness was certified by running solvers multiple times to ensure non-overlapping value intervals.
4. Dimension Classification: The minimum quantum dimension $d^*$ required to exceed the classical bound was determined by optimizing $\eta_d(G)$ (the maximum eigenvalue of the sum of projectors in dimension $d$) using a three-phase constrained optimization strategy with 300 random restarts.
5. Algebraic Identification: The PSLQ integer-relation algorithm was applied at 50-digit precision to identify closed-form algebraic expressions for numerical results, specifically for $\eta_3(G)$.

Key Contributions and Results

• Discovery of Quad-C5: The search identified a previously uncharacterized graph, named Quad-C5 (graph6 code: GCQb'o), as the unique maximizer of the contextuality gap for $n=8$.
  • Parameters: Quad-C5 has 8 vertices, 10 edges, and a degree sequence of $(2^4, 3^4)$.
  • Performance: It achieves a gap of $\Delta = 0.46784$, surpassing the Wagner graph ($W$, $\Delta \approx 0.414$) by approximately 13%, despite using two fewer edges.
• Structural Analysis: Quad-C5 contains four mutually overlapping induced five-cycles ($C_5$). Every edge in the graph belongs to exactly two of these $C_5$ subgraphs, providing a "perfect two-fold edge coverage." The adjacency spectrum is dominated by eigenvalues in the golden-ratio field $\mathbb{Q}(\sqrt{5})$, linking the graph's spectral properties directly to the KCBS pentagon.
• Dimensional Hierarchy:
  • Qutrit Witness: Quad-C5 is a certified qutrit witness ($d^*=3$). Numerical optimization at 50-digit precision, confirmed by PSLQ, determines that $\eta_3(\text{Quad-C5}) = 1 + \sqrt{5} \approx 3.23607$. This value satisfies the minimal polynomial $x^2 - 2x - 4 = 0$.
  • Comparison with Wagner Graph: In contrast, the Wagner graph ($W$) and the second-ranked graph appear to be "pure two-qubit witnesses" ($d^*=4$), where numerical searches consistently yield $\eta_3 = \alpha = 3$, requiring a four-dimensional Hilbert space to exhibit contextuality.
• Noise Robustness: Under depolarizing noise, the critical visibility $v^*$ for Quad-C5 at $d=3$ is analytically shown to be identical to that of the KCBS witness ($v^* \approx 0.585$). This equality arises from a uniform shift in the parameters $\alpha$, $\eta_3$, and $n/d$ between the two graphs. At $d=4$, Quad-C5 strictly outperforms the Wagner graph in noise robustness, requiring approximately 2.6% less visibility.

Significance
The paper claims that Quad-C5 demonstrates that denser exclusion graphs do not necessarily yield stronger contextuality; in fact, a sparser graph (10 edges vs. 12 for $W$) can achieve a larger gap. The discovery highlights a more efficient "contextuality geometry" where four interlocking KCBS pentagons encode quantum advantage more effectively per edge than the symmetric 3-regular structure of the Wagner graph.

Crucially, the work establishes that the maximum contextuality gap for $n=8$ is achievable within a three-level system (qutrit), whereas the previous benchmark (Wagner graph) appears to require a four-dimensional (two-qubit) space. This suggests that qutrit-accessible contextuality can be more efficient than two-qubit scenarios. The algebraic connection of Quad-C5 to the golden ratio and the KCBS pentagon provides a spectral-graph-theoretic explanation for its enhanced performance. Finally, the finding that Quad-C5 shares the exact noise threshold of the simplest KCBS witness implies that any experimental apparatus capable of testing KCBS contextuality can immediately certify Quad-C5 contextuality without relaxing noise requirements.