arXiv:2609.19862
Automated search for highly contextual Kochen-Specker proofs
Axel Muller, Metod Saniga
Abstract
Observable-based Kochen-Specker proofs are configurations of multi-qubit Pauli observables grouped into contexts whose products are plus or minus the indentity. Their robustness as state-independent contextuality tests can be measured by the tolerated error per context $\varepsilon = 2d/|H|$, where $d$ is the contextuality degree and $|H|$ the number of contexts. Since the degree depends only on an underlying abstract structure called the hypergram i.e. the pair formed by the context hypergraph and the anticommutation graph, the search for highly contextual proofs can be carried out on them instead, with no reference to qubits or to any particular Pauli labeling. We further exploit this by enumerating anticommutation graphs first, and then by associating to each graph $G$ the single hypergram carrying its entire hypergraph support $HS(G)$, so that exactly one candidate is examined per graph. Applied to the House of Graphs database and to censuses of vertex-transitive graphs on at most 24 vertices, this pipeline recovers the Peres-Mermin square, the doily and the Mermin pentagram, and yields configurations reaching $\varepsilon = 0.707$, against $0.424$ for the previous published record. The best configurations are predominantly those stemming from line graphs and unions of graphs; we explain the former by showing that every perfect matching of a graph is a context of its line graph, which exhibits the Peres-Mermin square and the doily as the first members of two infinite families. We close with finite geometric descriptions of the most striking configurations inside symplectic polar spaces, in terms of ovoids, hyperbolic quadrics and Fano planes.
AI Summary
The paper searches for noise-robust, state-independent Kochen–Specker proofs built from multi-qubit Pauli observables. Robustness is measured by $\varepsilon=2d/|H|$, where $d$ is the minimum number of context-product constraints violated by any classical value assignment and $|H|$ is the number of contexts. Using the previously established invariance of $d$ under Pauli realizations of a hypergram, the search enumerates anticommutation graphs rather than observable labelings. Each graph is paired with its full hypergraph support: all independent vertex sets satisfying the binary parity condition for admissible contexts. The pipeline examines 13,864 connected, reduced House of Graphs entries with at most 30 vertices and 18,948 vertex-transitive graphs with at most 24 vertices, followed by targeted extensions. Exact SAT computations yield $\varepsilon=0.6$ for $L(K_{5,5})$ and a maximum confirmed $\varepsilon=152/215\approx0.707$ for three disjoint Petersen graphs, corresponding to three commuting Mermin pentagrams with 30 observables, 215 contexts and $d=76$. The cited previous published record was $0.424$, under a magic-set restriction. A theorem shows that every perfect matching of a base graph supplies a context in its line graph; geometric descriptions accompany selected configurations. The search does not establish optimality: subsets of the full support might improve $\varepsilon$, graph databases introduce sampling bias, and exact degree calculations become limiting. Larger examples have only heuristic upper bounds, $\varepsilon\leq0.778$ and $\varepsilon\leq0.806$, not certified robustness values. The asymptotic robustness of repeated disconnected constructions remains open.
Anthropic Claude Opus 5 was used during the writing process of this article.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.