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

तकनीकी सारांश: एसोसिएशन स्कीम्स में श्राइवर-डेल्सार्ट रिजिडिटी (Schrijver–Delsarte Rigidity) और क्वांटम ग्राफ होमोरफिज्म की अनडिसाइडेबिलिटी (Undecidability)

समस्या विवरण
यह शोध पत्र क्वांटम ग्राफ होमोरफिज्म समस्या, जिसे $\text{CSP}_q(G')$ द्वारा दर्शाया गया है, की कम्प्यूटेशनल जटिलता को संबोधित करता है। दिए गए लक्ष्य ग्राफ (target graph) $G'$ के लिए, यह समस्या पूछती है कि क्या एक इनपुट ग्राफ $G$, $G'$ में एक क्वांटम होमोरफिज्म स्वीकार करता है। जबकि इस समस्या का शास्त्रीय (classical) संस्करण अच्छी तरह से समझ लिया गया है (गैर-बाइपार्टाइट लक्ष्यों के लिए NP-कम्प्लीट और बाइपार्टाइट के लिए बहुपद समय/polynomial), क्वांटम परिदृश्य कम स्पष्ट है। यह ज्ञात है कि अनियंत्रित क्वांटम रणनीतियों के लिए, समस्या RE-कम्प्लीट (रिकर्सिवली एन्यूमेरेबल कम्प्लीट) है, जो $MIP^* = RE$ प्रमेय के कारण है। हालांकि, विशिष्ट, गैर-समान (non-uniform) लक्ष्य ग्राफों के लिए RE-कỀ-कम्प्लीट होने को स्थापित करने के लिए "कम्यूटेटिविटी गैजेट्स" (commutativity gadgets)—ऐसी संरचनाएं जो क्वांटम रणनीतियों को शास्त्रीय (गैर-संदर्भगत/non-contextual) व्यवहार करने के लिए मजबूर करती हैं या ज्ञात कठिन समस्याओं से रिडक्शन की अनुमति देती हैं—के अस्तित्व को सिद्ध करना आवश्यक है।

लेखक एसोसिएशन स्कीम्स (जैसे किनेसर ग्राफ, $q$-किनेसर ग्राफ, और जॉनसन, ग्रासमैन और हैमिंग ग्राफ के पूरक) से प्राप्त विशिष्ट ग्राफ परिवारों के लिए $\text{CSP}_q(G)$ की जटिलता को वर्गीकृत करने के लिए एक व्यवस्थित दृष्टिकोण पर ध्यान केंद्रित करते हैं। केंद्रीय चुनौती यह निर्धारित करना है कि कब ये ग्राफ कम्यूटेटिविटी गैजेट्स को स्वीकार करते हैं, जो क्वांटम पॉलीमॉर्फिज्म के सिद्धांत के अनुसार, यह सिद्ध करने के समतुल्य है कि सभी क्वांटम पॉलीमॉर्फिज्म गैर-संदर्भगत (non-contextual) हैं।

कार्यप्रणाली (Methodology)
यह शोध पत्र क्वांटम पॉलीमॉर्फिज्म की गैर-संदर्भगतता (non-contextuality) को स्थापित करने के लिए एक स्पेक्ट्रल विधि विकसित करता है। यह दृष्टिकोण तीन सैद्धांतिक स्तंभों को जोड़ता है:

1. श्राइवर का थीटा ($\vartheta$) और प्रोजेक्टिव पैकिंग: लेखक श्राइवर के पैरामीटर $\vartheta^-(G)$ का उपयोग करते हैं, जो लोवाज़ थेटा फंक्शन ($\vartheta$) का एक सुदृढ़ीकरण है और इंडिपेंडेंस नंबर $\alpha(G)$ को ऊपरी सीमा प्रदान करता है। वे रोबर्सन के इस परिणाम का लाभ उठाते हैं कि $\vartheta^-(G)$, प्रोजेक्टिव पैकिंग संख्या $\alpha_p(G)$ को भी सीमित करता है, जो बदले में क्वांटम इंडिपेंडेंस नंबर $\alpha_q(G)$ को सीमित करता है। उनकी विधि का मूल मामला वह है जहाँ ये सीमाएँ सटीक ($\alpha(G) = \alpha_p(G) = \vartheta^-(G)$) होती हैं।
2. रिजिडिटी (Rigidity) और समानता विश्लेषण: जब सीमा सटीक होती है, तो लेखक इस समानता को प्रमाणित करने वाले "सर्टिफिकेट" मैट्रिसेस की संरचना का विश्लेषण करते हैं। वे सिद्ध करते हैं कि यदि कोई ग्राफ एक विशिष्ट प्रकार का "श्राइवर-रिजिड" प्रतिनिधित्व स्वीकार करता है, तो किसी भी परफेक्ट क्वांटम रणनीति को परिभाषित करने वाले प्रोजेक्टर एक प्रतिबंधित उप-स्थान (सर्टिफिकेट के कर्नेल) में होने चाहिए। यह प्रतिबंध प्रोजेक्टरों के बीच रैखिक पहचान (linear identities) को अनिवार्य करता है।
3. टेम डिस्पोजिटनेस रिप्रेजेंटेशन (Tame Disjointness Representations) और एसोसिएशन स्कीम्स: स्पेक्ट्रल स्थिति को एक जांच योग्य मानदंड में अनुवादित करने के लिए, लेखक "टेम डिस्पोजिटनेस रिप्रेजेंटेशन" पेश करते हैं। ये ग्राफ के शीर्षों (vertices) से विशेषताओं (features) के सेट में इनजेक्टिव मैप्स हैं ताकि आसन्न शीर्ष (adjacent vertices) विलगित (disjoint) सेटों को मैप करें। वे एक प्रतिनिधित्व को तब श्राइवर-रिजिड कहते हैं यदि अनुकूलतम श्राइवर सर्टिफिकेट का कर्नेल, प्रतिनिधित्व के इंसिडेंस स्पेस के साथ मेल खाता हो।
   • महत्वपूर्ण रूप से, एसोसिएशन स्कीम्स (जॉनसन, ग्रासमैन, हैमिंग) से प्राप्त ग्राफों के लिए, लेखक सिद्ध करते हैं कि श्राइवर-रिजिडिटी, डेल्सार्ट-रिजिडिटी के समतुल्य है। डेल्सार्ट-रिजिडिटी एक ऐसी स्थिति है जिसे बोस-मेसनर बीजगणित (Bose–Mesner algebra) के लीनियर प्रोग्रामिंग (LP) ढांचे के भीतर पूरी तरह से तैयार किया गया है, जिससे इसे स्कीम के आइगेनवैल्यू मैट्रिक्स का उपयोग करके कम्प्यूटेशनल रूप से सत्यापित किया जा सकता है।
   • वे आगे दिखाते हैं कि यदि किसी ग्राफ में "टेम" श्राइवर-रिजिड प्रतिनिधित्व है, तो स्पेक्ट्रल बाधाओं से प्राप्त रैखिक पहचान यह सुनिश्चित करती है कि क्वांटम पॉलीमॉर्फिज्म में सभी प्रोजेक्टर कम्यूट (commute) होते हैं (अर्थात, वे गैर-संदर्भगत हैं)।

मुख्य योगदान और परिणाम
प्राथमिक योगदान क्लासिक मेट्रिक एसोसिएशन स्कीम्स से प्राप्त कई ग्राफ परिवारों द्वारा पैरामीटराइज्ड क्वांटम होमोरफिज्म समस्या के लिए RE-कỀ-कम्प्लीट होने का प्रमाण है।

• मुख्य प्रमेय (Theorem 1.1): लेखक सिद्ध करते हैं कि निम्नलिखित में से किसी भी ग्राफ में इनपुट ग्राफ के क्वांटम होमोरफिज्म को निर्धारित करना RE-कỀ-कम्प्लीट है:

  • किनेसर ग्राफ $KG(n, k)$ जहाँ $n > 2k \ge 2$।
  • जॉनसन ग्राफ के पूरक $\overline{J(n, k)}$ जहाँ $n > 2k \ge 4$।
  • $q$-किनेसर ग्राफ $KG_q(n, k)$ जहाँ $n > 2k \ge 2$ और $q$ एक प्राइम पावर है।
  • ग्रासमैन ग्राफ के पूरक $\overline{J_q(n, k)}$ जहाँ $n > 2k \ge 4$ और $q$ एक प्राइम पावर है।
  • हैमिंग ग्राफ के पूरक $\overline{H(d, q)}$ जहाँ $d \ge 2$ और $q \ge 3$।

• खुले प्रश्नों का समाधान: यह परिणाम "ऑड ग्राफ्स" ($O_n = KG(2n-1, n-1)$) के लिए जटिलता प्रश्न को हल करता है, जो ग्राफों का एक ऐसा वर्ग है जिनके लिए कम्यूटेटिविटी गैजेट्स का अस्तित्व पहले अनसुलझा था। लेखक इन ग्राफों के लिए ओरैकुलर (oracular) और गैर-ओरैकुलर (non-oracular) दोनों सेटिंग्स में RE-कỀ-कम्प्लीट होने की स्थापना करते हैं।

• तकनीकी ढांचा: यह शोध पत्र स्पेक्ट्रल ग्राफ थ्योरी (श्राइवर बाउंड) और एसोसिएशन स्कीम्स के बीजगणितीय सिद्धांत (डेल्सार्ट LP बाउंड) के बीच एक सेतु स्थापित करता है। यह प्रदर्शित करता है कि इन सममित संरचनाओं के लिए, गैर-संदर्भगतता के लिए आवश्यक जटिल SDP स्थितियों को स्कीम के आइगेनवैलियम्स पर LP स्थितियों की जाँच करके कम किया जा सकता है।

महत्व और दावे
यह शोध पत्र एक "क्वांटम हेल-नेशेट्रिल वर्गीकरण" (quantum Hell–Nešetřil classification) की दिशा में महत्वपूर्ण प्रगति का दावा करता है, जिसका लक्ष्य ग्राफ होमोरफिज्म समस्याओं को बहुपद समय में हल होने वाली समस्याओं और RE-कỀ-कम्प्लीट समस्याओं में विभाजित करना है। एक स्पेक्ट्रल मानदंड (श्राइवर-रिजिडिटी) प्रदान करके जो RE-कỀ-कम्प्लीट होने की गारंटी देता है, लेखक नए ग्राफ परिवारों के विश्लेषण के लिए एक व्यवस्थित उपकरण प्रदान करते हैं।

हालाँकि, लेखक अपने तरीके के दायरे के बारे में विनम्र हैं। वे स्पष्ट रूप से बताते हैं कि उनका स्पेक्ट्रल दृष्टिकोण सभी RE-कỀ-कम्प्लीट समस्याओं के परिदृश्य को कैप्चर नहीं करता है:

• कुछ ग्राफ (जैसे डायमंड ग्राफ या मोसर स्पिंडल) RE-कỀ-कम्प्लीट हैं लेकिन उनमें कम्यूटेटिविटी गैजेट्स नहीं होते (और इस प्रकार वे गैर-संदर्भगतता की शर्त को विफल कर देते हैं)।
• अन्य ग्राफ (जैसे लंबाई $\ge 5$ के विषम चक्र/odd cycles) कम्यूटेटिविटी गैजेट्स रखते हैं लेकिन स्पेक्ट्रल मानदंड में विफल रहते हैं क्योंकि उन पर श्राइवर का बाउंड सटीक नहीं है।

परिणामतः, लेखक निष्कर्ष निकालते हैं कि एक पूर्ण वर्गीकरण के लिए संभवतः केवल स्पेक्ट्रल रिजिडिटी पर निर्भर रहने के बजाय उनके स्पेक्ट्रल तर्कों को कॉम्बिनेटोरियल विधियों (जैसे संदर्भगत द्विभाजन/contextuality bifurcations) के साथ जोड़ने की आवश्यकता होगी। यह कार्य नए प्रयोगात्मक प्रोटोकॉल का प्रस्ताव नहीं करता है, बल्कि विशिष्ट ग्राफ होमोरफिज्म गेम्स में एंटैंगलमेंट की कम्प्यूटेशनल शक्ति को समझने के लिए एक कठोर सैद्धांतिक ढांचा प्रदान करता है।