Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism

Technische Samenvatting: Schrijver–Delsarte Rigiditeit in Associatie-schema's en Onbeslisbaarheid van Kwantum Grafenhomomorfisme

Probleemstelling
Het artikel behandelt de computationele complexiteit van het kwantum grafenhomomorfisme-probleem, aangeduid als $\text{CSP}_q(G')$. Gegeven een vaste doelgraaf $G'$, is de vraag of een invoergraaf $G$ een kwantumnomomorfisme naar $G'$ toelaat. Hoewel de klassieke versie van dit probleem goed begrepen is (NP-volledig voor niet-bipartiete doelen, polynomiaal voor bipartiete), is het kwantumlandschap minder duidelijk. Het is bekend dat voor onbeperkte kwantumstrategieën het probleem RE-volledig is (recursief opsombaar volledig) vanwege de $MIP^* = RE$ stelling. Het vaststellen van RE-volledigheid voor specifieke, niet-uniforme doelgrafen vereist echter het bewijzen van de existentie van "commutativiteitsgadgets"—structuren die kwantumstrategieën dwingen om klassiek (niet-contextueel) te gedragen of die reducties naar bekende harde problemen mogelijk maken.

De auteurs richten zich op een systematische aanpak om de complexiteit van $\text{CSP}_q(G)$ te classificeren voor specifieke families van grafen afgeleid van associatie-schema's, inclusief Kneser-grafen, $q$-Kneser-grafen, en complementen van Johnson-, Grassmann- en Hamming-grafen. De centrale uitdaging is bepalen wanneer deze grafen commutativiteitsgadgets toestaan, wat volgens de theorie van kwantumpolymorfismen equivalent is aan het bewijzen dat alle kwantumpolymorfismen van de graaf niet-contextueel zijn.

Methodologie
Het artikel ontwikkelt een spectrale methode om de niet-contextualiteit van kwantumpolymorfismen vast te stellen. De aanpak combineert drie theoretische pijlers:

1. Schrijvers Theta en Projectieve Inpakkingen: De auteurs maken gebruik van Schrijvers parameter $\vartheta^-(G)$, een versterking van de Lovász theta-functie, die de onafhankelijkheidsgetal $\alpha(G)$ bovengrenst. Zij maken gebruik van Robersons resultaat dat $\vartheta^-(G)$ ook het projectieve inpakkingsgetal $\alpha_p(G)$ begrenst, wat op zijn beurt het kwantum onafhankelijkheidsgetal $\alpha_q(G)$ begrenst. De kern van hun methode berust op het geval waarin deze grenzen nauw aansluiten ($\alpha(G) = \alpha_p(G) = \vartheta^-(G)$).
2. Rigiditeit en Gelijkheid-analyse: Wanneer de grens nauw aansluit, analyseren de auteurs de structuur van de "certificaat"-matrices die deze gelijkheid getuigen. Zij bewijzen dat als een graaf een specif kind type "Schrijver-rigide" representatie toelaat, de projectoren die een perfecte kwantumstrategie definiëren, moeten liggen in een beperkt deelruimte (de kern van het certificaat). Deze beperking dwingt lineaire identiteiten af tussen de projectoren.
3. Tamme Disjunctie-representaties en Associatie-schema's: Om de spectrale conditie te vertalen naar een controleerbaar criterium, introduceren de auteurs "tamme disjunctie-representaties". Dit zijn injectieve afbeeldingen van grafenknopen naar verzamelingen van kenmerken zodanig dat aangrenzende knopen naar disjuncte verzamelingen mappen. Zij definiëren een representatie als Schrijver-rigide als de kern van het optimale Schrijver-certificaat samenvalt met de incidentieruimte van de representatie.
   • Cruciaal is dat voor grafen afgeleid van associatie-schema's (Johnson, Grassmann, Hamming), Schrijver-rigiditeit equivalent is aan Delsarte-rigiditeit. Delsarte-rigiditeit is een conditie die volledig binnen het lineaire programmeringskader (LP) van de Bose–Mesner algebra is geformuleerd, wat computationeel verifieerbaar is gegeven de eigenwaardematrix van het schema.
   • Verder tonen zij aan dat als een graaf een "tamme" Schrijver-rigide representatie heeft, de lineaire identiteiten afgeleid van de spectrale restricties dwingen dat alle projectoren in een kwantumpolymorfisme commuteren (niet-contextualiteit).

Belangrijkste Bijdragen en Resultaten
De primaire bijdrage is het bewijs van RE-volledigheid voor het kwantum grafenhomomorfisme-probleem geparametriseerd door verschillende families van grafen afgeleid van klassieke metrische associatie-schema's.

• Hoofdtheorema (Theorema 1.1): De auteurs bewijzen dat het bepalen of een invoergraaf een kwantumhomomorfisme toelaat naar een van de volgende grafen RE-volledig is:

  • Kneser-grafen $KG(n, k)$ met $n > 2k \ge 2$.
  • Complementen van Johnson-grafen $\overline{J(n, k)}$ met $n > 2k \ge 4$.
  • $q$-Kneser-grafen $KG_q(n, k)$ met $n > 2k \ge 2$ en $q$ een priemmacht.
  • Complementen van Grassmann-grafen $\overline{J_q(n, k)}$ met $n > 2k \ge 4$ en $q$ een priemmacht.
  • Complementen van Hamming-grafen $\overline{H(d, q)}$ met $d \ge 2$ en $q \ge 3$.

• Resolutie van Openstaande Vragen: Dit resultaat lost de complexiteitsvraag voor "odd graphs" ($O_n = KG(2n-1, n-1)$) op, een klasse van grafen waarvoor het bestaan van commutativiteitsgadgets voorheen onopgelost was. De auteurs vestigen RE-volledigheid voor deze grafen in zowel de orakel- als de niet-orakel setting.

• Technisch Kader: Het artikel slaat een brug tussen spectrale grafentheorie (Schrijvers grens) en de algebraïsche theorie van associatie-schema's (Delsartes LP-grens). Het demonstreert dat voor deze symmetrische structuren de complexe SDP-condities die nodig zijn voor niet-contextualiteit kunnen worden gereduceerd tot het controleren van LP-condities op de eigenwaarden van het schema.

Betekenis en Claims
Het artikel claimt aanzienlijke vooruitgang te hebben geboekt richting een "kwantum Hell–Nešetřil classificatie", die ernaar streeft grafenhomomorfisme-problemen te dichotomiseren in problemen die in polynomiale tijd oplosbaar zijn en problemen die RE-volledig zijn. Door een spectraal criterium (Schrijver-rigiditeit) te bieden dat RE-volledigheid garandeert, bieden de auteurs een systematisch instrument voor de analyse van nieuwe graffamilies.

Echter, de auteurs zijn bescheiden over de reikwijdte van hun methode. Zij stellen expliciet dat hun spectrale benadering niet het volledige landschap van RE-volledige problemen vastlegt. Zij leveren tegenvoorbeelden:

• Sommige grafen (zoals de diamant-graaf of de Moser-spindel) zijn RE-volledig maar bezitten geen commutativiteitsgadgets (en falen dus aan de niet-contextualiteitsconditie).
• Andere grafen (zoals oneven cycli van lengte $\ge 5$) bezitten commutativiteitsgadgets maar falen aan het spectrale criterium omdat de Schrijvers grens daar niet nauw aansluit.

Concluderend stellen de auteurs dat een volledige classificatie waarschijnlijk een combinatie zal vereisen van hun spectrale argumenten met combinatorische methoden (zoals contextualiteits-bifurcaties), in plaats van enkel te vertrouaien op spectrale rigiditeit. Het werk stelt geen nieuwe experimentele protocollen voor, maar biedt een rigoureus theoretisch kader voor het begrijpen van de computationele kracht van verstrengeling in specifieke grafenhomomorfisme-spellen.