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

Technische Zusammenfassung: Schrijver–Delsarte-Rigidität in Assoziationsschemata und Unentscheidbarkeit des Quanten-Graphhomomorphismus

Problemstellung
Die Arbeit befasst sich mit der Komplexität des Problems des Quanten-Graphhomomorphismus, bezeichnet als $\text{CSP}_q(G')$. Gegeben sei ein fixer Zielgraph $G'$, und die Frage ist, ob ein Eingabegraph $G$ einen Quantenhomomorphismus zu $G'$ besitzt. Während die klassische Version dieses Problems gut verstanden ist (NP-vollständig für nicht-bipartite Ziele, polynomial für bipartite), ist die Quantenlandschaft weniger geklärt. Es ist bekannt, dass das Problem bei uneingeschränkten Quantenstrategien RE-vollständig (recursively enumerable complete) ist, aufgrund des $MIP^* = RE$-Theorems. Die Herausforderung besteht darin, die RE-Vollständigkeit für spezifische, nicht-uniforme Zielgraphen zu beweisen, was die Existenz von „Kommutativitäts-Gadgets“ erfordert – Strukturen, die erzwingen, dass Quantenstrategien sich klassisch (nicht-kontextuell) verhalten oder Reduktionen von bekannten schweren Problemen ermöglichen.

Die Autoren konzentrieren sich auf einen systematischen Ansatz zur Klassifizierung der Komplexität von $\text{CSP}_q(G)$ für spezifische Familien von Graphen, die aus Assoziationsschemata abgeleitet sind, einschließlich Kneser-Graphen, $q$-Kneser-Graphen und Komplementen von Johnson-, Grassmann- und Hamming-Graphen. Die zentrale Herausforderung besteht darin, zu bestimmen, wann diese Graphen Kommutativitäts-Gadgets besitzen, was laut der Theorie der Quanten-Polymorphismen äquivalent zum Beweis ist, dass alle Quanten-Polymorphismen des Graphen nicht-kontextuell sind.

Methodik
Die Arbeit entwickelt eine spektrale Methode, um die Nicht-Kontextualität von Quanten-Polymorphismen zu etablieren. Der Ansatz kombelt drei theoretische Säulen:

1. Schrijvers Theta und projektive Packungen: Die Autoren nutzen Schrijvers Parameter $\vartheta^-(G)$, eine Stärkung der Lovász-Theta-Funktion, die die Unabhängigkeitszahl $\alpha(G)$ nach oben begrenzt. Sie nutzen Roberts Ergebnis, dass $\vartheta^-(G)$ auch die projektive Packungszahl $\alpha_p(G)$ begrenzt, welche wiederum die Quanten-Unabhängigkeitszahl $\alpha_q(G)$ begrenzt. Der Kern ihrer Methode beruht auf dem Fall, in dem diese Schranken eng sind ($\alpha(G) = \alpha_p(G) = \vartheta^-(G)$).
2. Rigidität und Gleichheitsanalyse: Wenn die Schranke eng ist, analysieren die Autoren die Struktur der „Zertifikats“-Matrizen, die diese Gleichheit bezeugen. Sie beweisen, dass, falls ein Graph eine bestimmte Art von „Schrijver-rigider“ Repräsentation besitzt, die Projektoren, die eine perfekte Quantenstrategie definieren, in einem eingeschränkten Unterraum (dem Kern des Zertifikats) liegen müssen. Diese Einschränkung erzwingt lineare Identitäten unter den Projektoren.
3. Tame Disjointness Representations und Assoziationsschemata: Um das spektrale Kriterium in ein prüfbares Kriterium zu übersetzen, führen die Autoren „tame disjointness representations“ (zahme Disjunktheitsrepräsentationen) ein. Dies sind injektive Abbildungen von Graphknoten auf Mengen von Merkmalen, sodass benachbarte Knoten auf disjunkte Mengen abbilden. Sie definieren eine Repräsentation als Schrijver-rigid, wenn der Kern des optimalen Schrijver-Zertifikats mit dem Inzidenzraum der Repräsentation übereinstimmt.
   • Entscheidend ist, dass für Graphen, die aus Assoziationsschemata (Johnson, Grassmann, Hamming) abgeleitet sind, die Schrijver-Rigidität äquivalent zur Delsarte-Rigidität ist. Delsarte-Rigidität ist eine Bedingung, die vollständig innerhalb des linearen Programmierungsrahmens (LP) der Bose–Mesner-Algebra formuliert ist und unter Verwendung der Eigenwertmatrix des Schemas computergestützt verifizierbar ist.
   • Sie zeigen weiter, dass, falls ein Graph eine „zahme“ Schrijver-rigide Repräsentation besitzt, die aus den spektralen Beschränkungen abgeleiteten linearen Identitäten erzwingen, dass alle Projektoren in einem Quanten-Polymorphismus kommutieren (Nicht-Kontextualität).

Wesentliche Beiträge und Ergebnisse
Der primäre Beitrag ist der Beweis der RE-Vollständigkeit für das Quanten-Graphhomomorphismus-Problem, parametrisiert durch mehrere Familien von Graphen, die von klassischen metrischen Assoziationsschemata abgeleitet sind.

• Hauptsatz (Theorem 1.1): Die Autoren beweisen, dass die Bestimmung, ob ein Eingabegraph einen Quantenhomomorphismus zu einem der folgenden Graphen besitzt, RE-vollständig ist:

  • Kneser-Graphen $KG(n, k)$ mit $n > 2k \ge 2$.
  • Komplemente von Johnson-Graphen $\overline{J(n, k)}$ mit $n > 2k \ge 4$.
  • $q$-Kneser-Graphen $KG_q(n, k)$ mit $n > 2k \ge 2$ und $q$ einer Primzahlpotenz.
  • Komplemente von Grassmann-Graphen $\overline{J_q(n, k)}$ mit $n > 2k \ge 4$ und $q$ einer Primzahlpotenz.
  • Komplemente von Hamming-Graphen $\overline{H(d, q)}$ mit $d \ge 2$ und $q \ge 3$.

• Lösung offener Fragen: Dieses Ergebnis klärt die Komplexitätsfrage für „Odd Graphs“ ($O_n = KG(2n-1, n-1)$), eine Klasse von Graphen, für die die Existenz von Kommutativitäts-Gadgets zuvor ungelöst war. Die Autoren etablieren die RE-Vollständigkeit für diese Graphen sowohl im orakulären als auch im nicht-orakulären Setting.

• Technischer Rahmen: Das Paper schlägt eine Brücke zwischen der spektralen Graphentheorie (Schrijvers Schranke) und der algebraischen Theorie der Assoziationsschemata (Delsartes LP-Schranke). Es demonstriert, dass für diese symmetrischen Strukturen die komplexen SDP-Bedingungen, die für Nicht-Kontextualität erforderlich sind, auf die Prüfung von LP-Bedingungen auf den Eigenwerten des Schemas reduziert werden können.

Bedeutung und Ansprüche
Das Paper beansprucht, signifikante Fortschritte in Richtung einer „Quanten Hell–Nešetřil-Klassifizierung“ zu machen, die darauf abzielt, Graphhomomorphismus-Probleme in jene zu dikotomisieren, die in Polynomialzeit lösbar sind, und jene, die RE-vollständig sind. Durch die Bereitstellung eines spektralen Kriteriums (Schrijver-Rigidität), das RE-Vollständigkeit garantiert, bieten die Autoren ein systematisches Werkzeug zur Analyse neuer Graphfamilien.

Die Autoren sind jedoch bescheiden hinsichtlich des Umfangs ihrer Methode. Sie geben explizit an, dass ihr spektraler Ansatz nicht die gesamte Landschaft der RE-vollständigen Probleme erfasst. Sie liefern Gegenbeispiele:

• Einige Graphen (wie der Diamant-Graph oder der Moser-Spindel) sind RE-vollständig, besitzen aber keine Kommutativitäts-Gadgets (und scheitern somit an der Nicht-Kontextualitäts-Bedingung).
• Andere Graphen (wie ungerade Zyklen der Länge $\ge 5$) besitzen Kommutativitäts-Gadgets, erfüllen aber das spektrale Kriterium nicht, da die Schrijver-Schranke bei ihnen nicht eng ist.

Infolgedessen kommen die Autoren zu dem Schluss, dass eine vollständige Klassifizierung wahrscheinlich eine Kombination ihrer spektralen Argumente mit kombinatorischen Methoden (wie Kontextualitäts-Bifurkationen) erfordern wird, anstatt sich allein auf die spektrale Rigidität zu verlassen. Die Arbeit schlägt keine neuen experimentellen Protokolle vor, sondern bietet vielmehr einen rigorosen theoretischen Rahmen zum Verständnis der Rechenleistung von Verschränkung in spezifischen Quanten-Graphhomomorphismus-Spielen.