Automated search for highly contextual Kochen-Specker proofs

Technische Samenvatting: Geautomatiseerde zoektocht naar hoog-contextuele Kochen-Specker bewijzen

Probleemstelling
Op observabelen gebaseerde Kochen-Specker (KS) bewijzen maken gebruik van configuraties van multi-qubit Pauli-observabelen die gegroepeerd zijn in "contexten" (verzamelingen van onderling commuteerende observabelen) waarvan het product $\pm I^{\otimes n}$ is. Deze bewijzen demonstreren staat-onafhankelijke kwantumcontextualiteit. De robuustheid van een dergelijk bewijs tegen experimentele ruis wordt gekwantificeerd door de getolereerde fout per context, aangeduid als $\varepsilon = 2d/|H|$, waarbij $d$ de contextualiteitsgraad is (het minimum aantal context-tekens dat niet gereproduceerd kan worden door een klassieke toewijzing) en $|H|$ het totaal aantal contexten is.

Eerdere zoektochten naar hoog-$\varepsilon$ bewijzen waren grotendeels beperkt tot "magic sets", waarbij observabelen in een even aantal contexten liggen en negatieve contexten een oneven aantal hebben. Hoewel dit contextualiteit garandeert, beperkt het de zoektocht tot een smal gebied binnen de configuratieruimte, waarbij het Peres-Mermin vierkant ($\varepsilon \approx 0.33$) en het Mermin pentagram ($\varepsilon = 0.40$) dienen als kleine voorbeelden. Het doel van dit werk is om systematisch te zoeken naar configuraties met hogere $\varepsilon$-waarden, waarbij de beperkingen van magic sets worden overstegen.

Methodologie
De auteurs maken gebruik van het concept van de hypergram, een abstracte structuur gedefinieerd als een tripel $(V, H, G)$ bestaande uit een context-hypergraaf $(V, H)$ en een anticommutatiegraaf $(V, G)$. Een cruciaal theoretisch inzicht uit eerder werk [MG25a] is dat de contextualiteitsgraad een invariant is van de hypergram alleen, onafhankelijk van het specifieke aantal qubits of de Pauli-labeling.

Om de zoektocht te optimaliseren, stellen de auteurs een pijplijn voor die de traditionele enumeratievolgorde omdraait:

1. Graph-First Enumeratie: In plaats van hypergrafen te enumereren en vervolgens te controleren op compatibele anticommutatiegrafen, enumereren de auteurs eenvoudige, gereduceerde anticommutatiegrafen $G$.
2. Hypergraph Support ($HS(G)$): Voor elke graaf $G$ construeren zij de hypergraph support, $HS(G)$, die alle mogelijke contexten bevat (onafhankelijke verzamelingen van $G$ die voldoen aan de pariteitvoorwaarde vereist voor toewijsbaarheid).
3. Canonieke Kandidaatselectie: In plaats van alle deelverzamelingen van $HS(G)$ te testen, onderzoekt de pijplijn de enkele hypergram $(V, HS(G), G)$ voor elke graaf. Deze "maximale" configuratie wordt verondersteld de hoogste $\varepsilon$ te leveren.
4. Zoekruimte: De pijplijn werd toegepast op twee verschillende bronnen in aparte fasen:
   • De House of Graphs database: 13.864 verbonden, gereduceerde grafen met $\le 30$ vertices.
   • Census van vertex-transitieve grafen: Alle dergelijke grafen met $\le 24$ vertices (18.948 grafen), wat een breder bereik dekt dan de subset van de House of Graphs.
5. Verificatie: Toewijsbaarheid wordt gecontroleerd via een matrixconditie ($H \cdot G = 0$ over $\mathbb{F}_2$). Contextualiteitsgraden worden berekend met SAT-solvers (exact) of heuristische solvers (voor grotere instanties).

Belangrijkste Bijdragen

1. Systematische Zoekpijplijn: Het artikel vestigt een volledige, geautomatiseerde pijplijn voor het ontdekken van KS-bewijzen door te opereren op het niveau van abstracte hypergrammen afgeleid van anticommutatiegrafen, waardoor de noodzaak voor expliciete qubit-labeling tijdens de zoekfase wordt geëlimineerd.
2. Ontdekking van Hoog-$\varepsilon$ Configuraties: De zoektocht identificeerde configuraties die de vorige gepubliceerde record van $\varepsilon = 0.424$ (uit [TLC22a], die beperkt was tot magic sets) aanzienlijk overtreffen.
3. Structurele Inzichten:
   • Lijngrafen: De auteurs bewijzen (Theorema 4) dat elke perfecte matching van een basisgraaf $H$ een context vormt in zijn lijngraaf $L(H)$. Dit verklaart waarom lijngrafen frequent hoog-$\varepsilon$ configuraties opleveren en identificeert het Peres-Mermin vierkant en de doily als de eerste leden van oneindige families van dergelijke configuraties.
   • Disjoint Unions (Disjuncte Verenigingen): De studie laat zien dat disjuncte verenigingen van grafen superieure resultaten opleveren. Omdat het aantal contexten in een disjuncte vereniging multiplicatief is terwijl het aantal observabelen additief is, verhoogt het stapelen van kopieën van kleine, hoog-presterende grafen (zoals de Petersen-graaf of $L(K_{3,3})$) de $\varepsilon$ drastisch.
4. Geometrische Interpretatie: Het artikel biedt eindige geometrische beschrijvingen van de top-configuraties binnen symplectische poolruimtes ($W_n$), waarbij ze worden gekoppeld aan specifieke structuren zoals ovoiden, hyperbolische quadrics en Fano-vlakken.

Resultaten
De pijplijn heeft bekende configuraties succesvol gereproduceerd (Peres-Mermin vierkant, Mermin pentagram, doily) en nieuwe, hoog-contextuele configuraties ontdekt:

• Recordbrekende $\varepsilon$: De beste gevonden configuratie is de 3-Petersen graaf (drie disjuncte kopieën van de Petersen-graaf), die een $\varepsilon = 0.707$ oplevert. Dit overtreft het vorige record van 0.424 (uit [TLC22a]) en het ongepubliceerde record van 0.5.
• Andere Opmerkelijke Configuraties:
  • $3L(K_{3,3})$ (drie disjuncte kopieën van de lijngraaf van $K_{3,3}$): $\varepsilon = 0.637$.
  • $2L(K_6)$: $\varepsilon = 0.612$.
  • $L(K_5,5)$ (Rook's graph): $\varepsilon = 0.600$.
  • $L(C(10, \{1, 3\}))$: $\varepsilon = 0.500$ (geïdentificeerd als de configuratie die eerder in [Mul25] werd gevonden).
• Database Statistieken: De zoektocht besloeg 13.864 grafen uit de House of Graphs database en 18.948 vertex-transitieve grafen. Slechts een klein deel leverde geldige, contextuele hypergrammen op. De resultaten bevestigen dat hoge symmetrie (vertex-transitiviteit) en specifieke structurele eigenschappen (het zijn van lijngrafen of disjuncte verenigingen) correleren met een hoge $\varepsilon$.

Betekenis en Claims
Het artikel claimt dat door de focus van de zoektocht te verschuiven van specifieke kwantumconfiguraties naar de onderliggende abstracte hypergrammen, het mogelijk is om KS-bewijzen met aanzienlijk hogere robuustheid tegen ruis te ontdekken. De auteurs benadrukken dat de disjuncte vereniging van grafen de meest effectieve structurele eigenschap is voor het maximaliseren van $\varepsilon$, omdat het gebruik maakt van de multiplicatieve aard van contextgeneratie.

Het werk identificeert het Peres-Mermin vierkant en de doily niet als geïsoleerde anomalieën, maar als de eerste leden van oneindige families gegenereerd door lijngrafen. Bovendien merken de auteurs op dat hoewel hun huidige zoektocht beperkt wordt door computationele restricties (SAT-solvers worstelen bij meer dan ~1.000 contexten), de heuristische benadering suggereert dat zelfs grotere configuraties (bijv. $K_6 \square K_6$) nog hogere $\varepsilon$-waarden kunnen opleveren, die potentieel de 1 benaderen. Het artikel concludeert door voor te stellen dat toekomstig werk zou kunnen bestaan uit geautomatiseerde loops met behulp van AI om graaffamilies en conjecturen voor te stellen, hoewel de huidige resultaten gebaseerd zijn op mensgestuurde exploratie van bestaande databases.