arxiv: 2605.12828 · v1 · submitted 2026-05-12 · 🪐 quant-ph

Recognition: unknown

The Quad-C₅ Graph: Maximum Contextuality Gap on Eight Vertices

Ugur Tamer , \"Ozg\"ur E. M\"ustecapl{\i}o\u{g}lu

Authors on Pith no claims yet

Pith reviewed 2026-05-14 19:24 UTC · model grok-4.3

classification 🪐 quant-ph

keywords quantum contextualityLovasz theta functionKCBS inequalitygraph theoryqutrit witnesssemidefinite programmingWagner graph

0 comments

The pith

The Quad-C5 graph on eight vertices achieves the largest known contextuality gap with ten edges.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper exhaustively searches all connected non-isomorphic graphs on eight vertices using semidefinite programming to maximize the difference between the Lovasz theta number and the independence number. This gap quantifies the advantage of quantum contextuality over classical assignments in the Cabello-Severini-Winter framework. The newly identified Quad-C5 graph, with four overlapping five-cycles, reaches 0.46784, beating the Wagner graph's 0.414 while using two fewer edges. It corresponds to a qutrit witness with the exact value 1 plus square root of five, linking directly to the KCBS pentagon through its golden-ratio spectrum.

Core claim

An exhaustive semidefinite-programming search identifies the Quad-C5 graph as achieving Δ=0.46784, surpassing the Wagner graph with fewer edges, and establishes it as a qutrit contextuality witness with η3=1+√5 whose algebraic structure derives from the KCBS pentagon.

What carries the argument

The Quad-C5 graph, defined by its four mutually overlapping induced five-cycles and golden-ratio-dominated adjacency spectrum, which carries the contextuality advantage from the pentagonal KCBS structure.

If this is right

Quad-C5 serves as a three-dimensional quantum witness, unlike the four-dimensional requirement for the Wagner graph.
It matches the KCBS critical visibility of approximately 0.585 under depolarizing noise for qutrits due to a uniform shift in parameters.
At four dimensions it exceeds the Wagner graph in noise robustness.
The contextuality advantage traces algebraically to golden-ratio eigenvalues originating in the five-cycles.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Optimizing for overlapping pentagons rather than edge count alone may yield better contextuality witnesses on small vertex sets.
Similar exhaustive searches on nine or ten vertices could uncover graphs with even larger gaps or lower-dimensional realizations.
The coincidence in noise tolerance suggests a deeper parametric relation between graph structure and visibility thresholds that might generalize to other cycle-based graphs.

Load-bearing premise

The semidefinite programming relaxation exactly equals the true quantum maximum for the Quad-C5 graph, and the high-precision numerical fit correctly identifies the algebraic value without artifacts.

What would settle it

A explicit three-dimensional quantum representation of the measurements on the Quad-C5 graph that produces a contextuality gap measurably below 0.46784 or a different minimal polynomial.

Figures

Figures reproduced from arXiv: 2605.12828 by \"Ozg\"ur E. M\"ustecapl{\i}o\u{g}lu, Ugur Tamer.

read the original abstract

We perform an exhaustive semidefinite-programming search over all 11{,}117 connected non-isomorphic simple graphs on eight vertices to maximize the quantum contextuality gap $\Delta(G)=\vartheta(G)-\alpha(G)$, where $\vartheta(G)$ is the Lov\'{a}sz theta function and $\alpha(G)$ is the independence number of the exclusion graph $G$ within the Cabello--Severini--Winter framework for projective measurements. A previously uncharacterized graph on $n=8$ vertices and $m=10$ edges, which we name the Quad-$C_5$ graph (graph6 code: \texttt{GCQb`o}), achieves $\Delta=0.46784$, surpassing the Wagner graph $W$ ($\Delta\approx0.414$, $m=12$) with two fewer edges. We determine numerically, via the PSLQ integer-relation algorithm at 50-digit precision, that Quad-$C_5$ is a \emph{qutrit} contextuality witness with $\eta_3=1+\sqrt{5}$ (minimal polynomial $x^2-2x-4=0$), while numerical evidence indicates the Wagner graph requires a four-dimensional (two-qubit) Hilbert space. The graph contains four mutually overlapping induced five-cycles, and its adjacency spectrum is dominated by golden-ratio eigenvalues, tracing the contextuality advantage algebraically to the KCBS pentagon. Under depolarizing noise, Quad-$C_5$ at $d=3$ shares the critical visibility $v^*=1/(3\sqrt{5}-5)\approx0.585$ of the KCBS witness -- an analytically provable coincidence arising from a uniform shift of the graph parameters -- while at $d=4$ it strictly surpasses the Wagner graph in noise robustness.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Quad-C5 is a new 8-vertex graph that numerically beats the Wagner graph on contextuality gap via exhaustive search, but the exact 1+sqrt(5) claim and qutrit realization rest on floating-point SDP plus PSLQ without closed-form backup.

read the letter

The paper's core result is straightforward: they enumerated all 11,117 connected graphs on eight vertices, ran the Lovasz theta SDP on each, and found that the Quad-C5 graph (10 edges) gives a larger gap Delta than the Wagner graph (12 edges). The numerical value is around 0.4678, and they tie the advantage to four overlapping C5 cycles whose spectrum is dominated by golden-ratio eigenvalues. They also compare noise robustness under depolarizing channels and note that at dimension 3 the critical visibility matches KCBS exactly due to a uniform parameter shift. That computational sweep and the noise calculation are the parts that hold up cleanly on the evidence given. The enumeration is exhaustive and uses standard SDP, so the ranking among graphs looks solid. The noise comparison is a useful addition for anyone thinking about experiments. The soft spot is the algebraic identification. The claim that eta_3 equals exactly 1 + sqrt(5) comes from feeding 50-digit SDP output into PSLQ; there is no exact SDP solution, no closed-form derivation, and no explicit set of qutrit vectors supplied to confirm the bound is tight in dimension 3. The same numerical route is used to argue the Wagner graph needs dimension 4. Until those steps are tightened or the vectors are exhibited, the precise algebraic statement and the dimension claim remain provisional. This is a targeted computational note rather than a broad theoretical advance. It will interest people who build or test small contextuality witnesses and need concrete graphs with good noise margins. The work shows clear engagement with the Cabello-Severini-Winter framework and prior examples like KCBS and Wagner, so it is worth sending to referees who can check the numerics and ask for the missing exact or constructive parts.

Referee Report

3 major / 2 minor

Summary. The manuscript performs an exhaustive semidefinite-programming search over all 11,117 connected non-isomorphic graphs on eight vertices to maximize the contextuality gap Δ(G) = ϑ(G) − α(G) in the Cabello-Severini-Winter framework. It identifies a new 10-edge graph (Quad-C5, graph6 code GCQb`o) achieving Δ ≈ 0.46784, exceeding the Wagner graph, and uses 50-digit PSLQ to claim an exact qutrit value η₃ = 1 + √5 together with a noise-robustness comparison.

Significance. If the numerical identification holds, the work supplies a new minimal-edge qutrit contextuality witness whose algebraic structure traces to the KCBS pentagon via golden-ratio eigenvalues, potentially simplifying experimental tests and improving noise tolerance relative to the Wagner graph.

major comments (3)

[§3] §3 (Results section): The identification of η₃ = 1 + √5 for Quad-C5 rests entirely on PSLQ reconstruction of the floating-point SDP output; no explicit projective vectors in dimension 3 or exact-arithmetic SDP solution is supplied to confirm that the Lovász theta is attained in d=3 rather than requiring higher dimension.
[§2] §2 (Methods): The central claim that the SDP relaxation exactly equals the quantum value for this graph assumes no gap between ϑ(G) and the true quantum bound realizable by finite-dimensional projective measurements; an explicit construction or proof ruling out such a gap is needed to support the qutrit-witness assertion.
[Table 2] Table 2 (comparison table): The reported superiority in noise robustness at d=4 over the Wagner graph is presented numerically, but the paper does not verify whether the SDP value remains tight under the depolarizing channel or provide the corresponding optimal measurements.

minor comments (2)

[Abstract] Abstract: The graph6 code is written with backticks; rendering in a monospace environment or code block would improve readability.
[§4] §4 (noise analysis): The phrase 'uniform shift of the graph parameters' is invoked to explain the shared v* with KCBS but is not accompanied by the explicit parameter mapping or derivation.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and will revise the manuscript to incorporate explicit constructions where feasible.

read point-by-point responses

Referee: [§3] §3 (Results section): The identification of η₃ = 1 + √5 for Quad-C5 rests entirely on PSLQ reconstruction of the floating-point SDP output; no explicit projective vectors in dimension 3 or exact-arithmetic SDP solution is supplied to confirm that the Lovász theta is attained in d=3 rather than requiring higher dimension.

Authors: We agree that an explicit construction strengthens the claim. In the revised manuscript we will include the optimal projective vectors in dimension 3 recovered from the SDP solution; these vectors attain the numerical value to machine precision and confirm that the Lovász theta is realized exactly by qutrit measurements, yielding the algebraic value 1 + √5. revision: yes
Referee: [§2] §2 (Methods): The central claim that the SDP relaxation exactly equals the quantum value for this graph assumes no gap between ϑ(G) and the true quantum bound realizable by finite-dimensional projective measurements; an explicit construction or proof ruling out such a gap is needed to support the qutrit-witness assertion.

Authors: The SDP furnishes an upper bound; our numerical search finds a matching lower bound with three-dimensional projectors. The revised version will supply the explicit set of rank-1 projectors in ℂ³ that saturate the SDP value, thereby demonstrating that the quantum bound equals ϑ(G) with no gap for this graph. revision: yes
Referee: [Table 2] Table 2 (comparison table): The reported superiority in noise robustness at d=4 over the Wagner graph is presented numerically, but the paper does not verify whether the SDP value remains tight under the depolarizing channel or provide the corresponding optimal measurements.

Authors: We will augment Table 2 and the surrounding text with the optimal projective measurements under the depolarizing channel at d=4 for both graphs. These explicit operators confirm that the SDP bound remains tight and substantiate the reported visibility thresholds. revision: yes

Circularity Check

0 steps flagged

Exhaustive SDP enumeration over all 8-vertex graphs yields non-circular maximum contextuality gap

full rationale

The paper's central derivation is an exhaustive computational search over the complete external set of 11,117 connected non-isomorphic graphs on eight vertices. For each graph it directly evaluates the Lovász theta function ϑ(G) via standard semidefinite programming and subtracts the independence number α(G) to obtain Δ(G), then reports the maximum. No parameters are fitted to any subset of these graphs and then reused to 'predict' a related quantity on the same set; no self-citation chain or author-supplied uniqueness theorem is invoked to force the choice of graph or the value of Δ; and the subsequent PSLQ identification of the numerical result as 1+√5 is a post-processing guess rather than a definitional reduction. The derivation is therefore self-contained against the external benchmarks of graph enumeration and off-the-shelf SDP solvers.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard assumption that the Lovasz theta SDP gives the quantum bound in the CSW framework and that the known enumeration of 11,117 graphs is complete; no new free parameters or invented entities are introduced.

axioms (2)

domain assumption Lovasz theta function via SDP equals the quantum value in the Cabello-Severini-Winter framework
Invoked throughout the abstract as the definition of the quantum side of the gap
domain assumption The list of 11,117 connected non-isomorphic graphs on eight vertices is exhaustive
Basis for the exhaustive search claim

pith-pipeline@v0.9.0 · 5649 in / 1316 out tokens · 33770 ms · 2026-05-14T19:24:09.397224+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages · 1 internal anchor

[1]

We therefore report: η3(Quad-C5) = 1 + √ 5≈3.23607 (13) 5 TABLE VI

The residual test yields r=|P(η 3)|/ |P ′(η3)| ·ε SDP ≈0.3≪1,(12) confirming a genuine algebraic relation (false positives haver≫1). We therefore report: η3(Quad-C5) = 1 + √ 5≈3.23607 (13) 5 TABLE VI. Edge lists for the six highest-ranked connected 8-vertex contextuality witnesses. All ∆ values from CLARABEL. Rank ∆d ∗ |E|Edge list 1 0.46784 3 10 (0,3),(0...

work page arXiv
[2]

All 500 independent restarts converged toλ max = 3.236068

Orthogonality er- ror max (i,j)∈E |⟨vi|vj⟩|<2.5×10 −14. All 500 independent restarts converged toλ max = 3.236068. i v (1) i v(2) i v(3) i 0−0.327925−0.827319 +0.456080 1 +0.591738 +0.502702 +0.630188 2 +0.265430−0.544016−0.795986 3 +0.265430−0.544016−0.795986 4−0.676200 +0.735118 +0.048537 5 +0.906649−0.139967 +0.397992 6−0.072902 +0.811912−0.579210 7 +0...

work page
[3]

Budroni, A

C. Budroni, A. Cabello, O. G¨ uhne, M. Klein- mann, and J.- ˚A. Larsson,Kochen-Specker contex- tuality, Rev. Mod. Phys.94, 045007 (2022), doi: 10.1103/RevModPhys.94.045007

work page doi:10.1103/revmodphys.94.045007 2022
[4]

Howard, J

M. Howard, J. Wallman, V. Veitch, and J. Emerson,Con- textuality supplies the ‘magic’ for quantum computation, Nature510, 351 (2014), doi:10.1038/nature13460

work page doi:10.1038/nature13460 2014
[5]

Contextuality in measurement- based quantum computation.Physical Review A, 88(2), August 2013.doi:10.1103/physreva.88.022322

R. Raussendorf,Contextuality in measurement-based quantum computation, Phys. Rev. A88, 022322 (2013), doi:10.1103/PhysRevA.88.022322

work page doi:10.1103/physreva.88.022322 2013
[6]

Kochen and E

S. Kochen and E. P. Specker,The problem of hidden variables in quantum mechanics, J. Math. Mech.17, 59 (1967), doi:10.1512/iumj.1968.17.17004

work page doi:10.1512/iumj.1968.17.17004 1967
[7]

Cabello, S

A. Cabello, S. Severini, and A. Winter,Graph-theoretic approach to quantum correlations, Phys. Rev. Lett.112, 040401 (2014), doi:10.1103/PhysRevLett.112.040401

work page doi:10.1103/physrevlett.112.040401 2014
[8]

Lov´ asz,On the Shannon capacity of a graph, IEEE Trans

L. Lov´ asz,On the Shannon capacity of a graph, IEEE Trans. Inf. Theory25, 1 (1979), doi: 10.1109/TIT.1979.1055985

work page doi:10.1109/tit.1979.1055985 1979
[9]

A. A. Klyachko,Coherent states, entanglement, and geo- metric invariant theory, arXiv:quant-ph/0206012 (2002)

work page internal anchor Pith review Pith/arXiv arXiv 2002
[10]

A. A. Klyachko, M. A. Can, S. Binicio˘ glu, and A. S. Shu- movsky,Simple test for hidden variables in spin-1 systems, Phys. Rev. Lett.101, 020403 (2008), doi: 10.1103/PhysRevLett.101.020403

work page doi:10.1103/physrevlett.101.020403 2008
[11]

Ara´ ujo, M

M. Ara´ ujo, M. T. Quintino, C. Budroni, M. Terra Cunha, and A. Cabello,All noncontextuality inequalities for the n-cycle scenario, Phys. Rev. A88, 022118 (2013), doi: 10.1103/PhysRevA.88.022118

work page doi:10.1103/physreva.88.022118 2013
[12]

B. D. McKay and A. Piperno,Practical graph iso- morphism, II, J. Symb. Comput.60, 94 (2014), doi: 10.1016/j.jsc.2013.09.003; graph databases athttps:// users.cecs.anu.edu.au/~bdm/data/graphs.html

work page doi:10.1016/j.jsc.2013.09.003 2014
[13]

A. A. Hagberg, D. A. Schult, and P. J. Swart, Exploring network structure, dynamics, and func- 8 tion using NetworkX, inProc. 7th Python in Sci- ence Conf. (SciPy2008), pp. 11–15 (2008), doi: 10.25080/TCWV9851

work page doi:10.25080/tcwv9851 2008
[14]

Diamond and S

S. Diamond and S. Boyd,CVXPY: A Python-embedded modeling language for convex optimization, J. Mach. Learn. Res.17, 1 (2016);https://www.jmlr.org/ papers/v17/15-408.html

work page 2016
[15]

O’Donoghue, E

B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd,Conic optimization via operator splitting and homogeneous self- dual embedding, J. Optim. Theory Appl.169, 1042 (2016), doi:10.1007/s10957-016-0892-3

work page doi:10.1007/s10957-016-0892-3 2016
[16]

D. H. Bailey and H. R. P. Ferguson,Numerical re- sults on relations between numerical constants using a new algorithm, Math. Comput.53, 649 (1989), doi: 10.1090/S0025-5718-1989-0979934-9; see also D. H. Bai- ley and D. J. Broadhurst,Parallel integer rela- tion detection, Math. Comput.70, 1719 (2001), doi: 10.1090/S0025-5718-00-01278-3

work page doi:10.1090/s0025-5718-1989-0979934-9 1989
[17]

Nakata,A numerical evaluation of highly accurate multiple-precision arithmetic version of semidefinite pro- gramming solver: SDPA-GMP, -QD and -DD, inProc

M. Nakata,A numerical evaluation of highly accurate multiple-precision arithmetic version of semidefinite pro- gramming solver: SDPA-GMP, -QD and -DD, inProc. 2010 IEEE Multi-Conf. Systems and Control, pp. 29–34 (2010), doi:10.1109/CACSD.2010.5612693

work page doi:10.1109/cacsd.2010.5612693 2010
[18]

D. E. Knuth,The sandwich theorem, Electron. J. Comb. 1, A1 (1994), doi:10.37236/1193

work page doi:10.37236/1193 1994
[19]

Molina-Terriza, J

G. Molina-Terriza, J. P. Torres, and L. Torner, Twisted photons, Nature Phys.3, 305 (2007), doi: 10.1038/nphys607

work page doi:10.1038/nphys607 2007
[20]

Hu, J.-S

X.-M. Hu, J.-S. Chen, B.-H. Liu, Y. Guo, Y.-F. Huang, Z.-Q. Zhou, C.-F. Li, and G.-C. Guo,Experimental test of compatibility-loophole-free contextuality with spatially separated entangled qutrits, Phys. Rev. Lett.117, 170403 (2016), doi:10.1103/PhysRevLett.117.170403

work page doi:10.1103/physrevlett.117.170403 2016
[21]

R. W. Spekkens,Contextuality for preparations, transfor- mations, and unsharp measurements, Phys. Rev. A71, 052108 (2005), doi:10.1103/PhysRevA.71.052108

work page doi:10.1103/physreva.71.052108 2005
[22]

Ac´ ın, T

A. Ac´ ın, T. Fritz, A. Leverrier, and A. B. Sainz,A combi- natorial approach to nonlocality and contextuality, Com- mun. Math. Phys.334, 533 (2015), doi:10.1007/s00220- 014-2260-1

work page doi:10.1007/s00220- 2015
[23]

D. M. Cvetkovi´ c, M. Doob, and H. Sachs,Spectra of Graphs: Theory and Applications(Academic Press, New York, 1980)

work page 1980