A Quantum-Inspired Algorithm for Graph Isomorphism

तकनीकी सारांश: ग्राफ आइसोमोर्फिज्म (Graph Isomorphism) के लिए एक क्वांटम-प्रेरित एल्गोरिदम

समस्या विवरण
यह शोध पत्र ग्राफ आइसोमोर्फिज्म (GI) समस्या को संबोधित करता है: यह निर्धारित करना कि क्या दो असतत (discrete) ग्राफ उनके शीर्ष लेबल (vertex labels) के क्रमपरिवर्तन (permutation) के आधार पर संरचनात्मक रूप से समान हैं। हालांकि यह समस्या NP-पूर्ण (NP-complete) होने के रूप में ज्ञात नहीं है, लेकिन एक सामान्य बहुपद-समय (polynomial-time) एल्गोरिदम खोजना सैद्धांतिक कंप्यूटर विज्ञान में एक महत्वपूर्ण चुनौती बनी हुई है। अत्याधुनिक शास्त्रीय दृष्टिकोण, बाबाई का एल्गोरिदम (2015), अर्ध-बहुपद समय (quasi-polynomial time, $2^{O(\log V)^3}$) में कार्य करता है। लेखक इस बात की जांच करते हैं कि क्या नॉइजी इंटरमीडिएट-स्केल क्वांटम (NISQ) युग, विशेष रूप से गाऊसी बोसन सैंपलिंग (GBS), अधिक कुशल समाधान के लिए एक मार्ग प्रदान कर सकता है। वे ब्रैडलर एट अल. [13] द्वारा प्रस्तावित एक क्वांटम एल्गोरिदम का आलोचनात्मक मूल्यांकन करते हैं और उसके अंतर्निहित सिद्धांतों से प्रेरित एक शास्त्रीय विकल्प का प्रस्ताव करते हैं।

कार्यप्रणाली
लेखक एक शास्त्रीय एल्गोरिदम विकसित करते हैं जो भौतिक क्वांटम उपकरण की आवश्यकता के बिना, ग्राफ आइसोमोर्फिज्म का परीक्षण करने के लिए GBS प्रणाली के सांख्यिकीय गुणों का उपयोग करता है।

1. एन्कोडिंग (Encoding): ग्राफ को एडजेसेंसी मैट्रिक्स (adjacency matrix) $A$ के ऑटोन-टाकी अपघटन (Autonne-Takagi decomposition, $A = UDU^T$) का उपयोग करके एक GBS सिस्टम में एनकोड किया जाता है। यूनिटरी मैट्रिक्स $U$ इंटरफेरोमीटर को परिभाषित करता है, और विकर्ण मैट्रिक्स $D$ (जिसमें आइगेनवैल्यू होते हैं) इनपुट स्क्वीजिंग मापदंडों को निर्धारित करता है। यह एन्कोडिंग सुनिश्चित करती है कि सैंपलर का संभाव्यता वितरण (probability distribution) ग्राफ की संरचना को दर्शाता है।
2. सांख्यिकीय इनवेरियंट्स (Statistical Invariants): भौतिक नमूने एकत्र करने के बजाय (जो सटीक वितरण सन्निकटन के लिए अक्षम है), एल्गोरिदम सैंपलर के आउटपुट वितरण के मोड सहसंबंधों (mode correlations/cumulants) की गणना करता है।
   • GBS में एक आउटपुट पैटर्न की संभावना एक उप-मैट्रिक्स के हाफनियन (Hafnian) द्वारा नियंत्रित होती है, जो क्लासिकली कंप्यूट करने में कठिन है।
   • हालांकि, निम्न-क्रम के क्युमुलेट्स (lower-order cumulants/correlations) को कुशलतापूर्वक गणना किया जा सकता है। लेखक $k$ मोड के बीच सहसंबंध का वर्णन करने वाले उर्सल फंक्शन्स (Ursell functions) का उपयोग करके $k$-क्रम के सहसंबंध $C^{(k)}$ को परिभाषित करते हैं।
   • महत्वपूर्ण रूप से, लेखक समान स्क्वीजिंग (uniform squeezing) का अनुमान नहीं लगाते हैं; वे गैर-समान इनपुट स्क्वीजिंग निर्धारित करने के लिए ग्राफ के विशिष्ट आइगेनवैल्यू का उपयोग करते हैं, जिससे आइसोस्पेक्ट्रैलिटी (isospectrality) की अग्रिम जांच संभव होती है (जो आइसोमोर्फिज्म के लिए एक आवश्यक शर्त है)।
3. एल्गोरिदम प्रक्रिया:
   • अपघटन (Decomposition): दोनों ग्राफों के एडजेसेंसी मैट्रिसेस को $U$ और $D$ में विघटित किया जाता है।
   • पुनरावृत्त सहसंबंध गणना (Iterative Correlation Calculation): एल्गोरिदम बढ़ते क्रम $k$ (1 से $M$ शीर्षों तक) के लिए सहसंबंध मानों की गणना करता है।
   • परम्यूटेशन फ़िल्टरिंग (Permutation Filtering): प्रत्येक क्रम $k$ के लिए, एल्गोरिदम दो ग्राफों के बीच सहसंबंध मानों के सेट की तुलना करता है। यह एक संभावित क्रमपरिवर्तन मैट्रिक्स $\sigma$ (प्रारंभिक रूप से सभी एकों के साथ) बनाए रखता है। यदि ग्राफ 1 के किसी शीर्ष के लिए कोई सहसंबंध मान मौजूद है लेकिन ग्राफ 2 में नहीं है, तो $\sigma$ में संबंधित मैपिंग को समाप्त (शून्य पर सेट) कर दिया जाता है।
   • समाप्ति (Termination):
     • यदि $\sigma$ अमान्य हो जाता है (खाली पंक्ति/स्तंभ), तो ग्राफों को गैर-आइसोमॉर्फिक (non-isomorphic) घोषित किया जाता है।
     • यदि $\sigma$ एक अद्वितीय क्रमपरिवर्तन मैट्रिक्स में बदल जाता है, तो ग्राफों को आइसोमॉर्फिक के रूप में सत्यापित किया जाता है।
     • यदि $\sigma$ अनिश्चित रहता है (कई मैपिंग संभव हैं), तो एल्गोरिदम अगले उच्च क्रम $k+1$ पर आगे बढ़ता है।
   • ट्रंकेशन (Truncation): यदि गणनात्मक लागत अत्यधिक हो जाती है, तो प्रक्रिया को अधिकतम क्रम $k_{max}$ पर रोका जा सकता है।

प्रमुख योगदान

• आवश्यक शर्त का सूत्रकरण (Necessary Condition Formulation): लेखक सैंपलर-एनकोडेड ग्राफों के $k$-क्रम के मोड सहसंबंधों की समानता के आधार पर ग्राफ आइसोमोर्फिज्म के लिए एक आवश्यक शर्त तैयार करते हैं। वे सिद्ध करते हैं कि यदि दो ग्राफ आइसोमॉर्फिक हैं, तो उनके सहसंबंध सेट सभी $k$ के लिए क्रमपरिवर्तनीय रूप से समान (permutationally equivalent) होने चाहिए।
• शास्त्रीय एल्गोरिदम: वे इस आवश्यक शर्त का परीक्षण करने के लिए एक शास्त्रीय एल्गोरिदम पेश करते हैं। यह एल्गोरिदम ग्राफ के एडजेसेंसी मैट्रिक्स से प्राप्त कुशलतापूर्वक गणना योग्य सांख्यिकीय गुणों (सहसंबंधों) का उपयोग करके गैर-आइसोमॉर्फिक ग्राफों के बीच अंतर करता है।
• जटिलता विश्लेषण: शोध पत्र प्रदर्शित करता है कि प्रस्तावित शास्त्रीय एल्गोरिदम की गणना जटिलता और ग्राफ अंतर करने की शक्ति, ब्रैडलर एट अल. [13] के क्वांटम-प्रेरित सैंपलिंग एल्गोरिदम और क्लासिकल कलर रिफाइनमेंट (Weisfeiler-Leman) एल्गोरिदम [23] के तुल्य है।
• मौजूदा विधियों से भिन्नता: लेखक स्पष्ट करते हैं कि हालांकि उनकी विधि कलर रिफाइनमेंट एल्गोरिदम (विशेष रूप से वेइल्सिलर-लेमैन टेस्ट) के साथ जटिलता विशेषताओं को साझा करती है, लेकिन यह अलग जानकारी का आकलन करती है (सैंपलर मोड सहसंबंध बनाम पड़ोस रंग गणना)। वे नोट करते कि यह एक खुला प्रश्न है कि क्या उनकी विधि सीआई-फुरर-इमरमैन (Cai-Fürer-Immerman) ग्राफों जैसे विशिष्ट ग्राफ परिवारों के संबंध में वेइल्सिलर-लेमैन टेस्ट की समान सीमाओं से ग्रस्त है।

परिणाम और सीमाएं

• दक्षता: सहसंबंध मानों की गणना $M$ शीर्षों के संदर्भ में बहुपद (polynomial) है लेकिन सहसंबंध क्रम $k$ के साथ तेजी से (exponentially) बढ़ती है।
• भेद करने की शक्ति (Distinguishing Power): एल्गोरिदम गैर-आइसोमॉर्फिक ग्राफों की पहचान करने में सफल रहता है, यह दिखाकर कि आवश्यक शर्त का उल्लंघन होता है। हालांकि, कलर रिफाइनमेंट एल्गोरिदम की तरह, यह अत्यधिक सममित ग्राफों (जैसे रेगुलर ग्राफ) के साथ संघर्ष करता है जहाँ निम्न-क्रम के सहसंबंध समान होते हैं।
• पूर्णता (Completeness): लेखक कहते हैं कि अधिकतम क्रम ($k=M$) पर, यह विधि प्रासंगिक संभाव्यता वितरणों को पुनः प्राप्त करती है और आइसोमोर्फिज्म का परीक्षण करने के लिए सैद्धांतिक रूप से पर्याप्त है। हालांकि, यह कुशल नहीं है, क्योंकि गणनात्मक लागत अत्यधिक हो जाती है।
• अत्याधुनिक (State-of-the-Art) से तुलना: शोध पत्र स्पष्ट रूप से दावा करता है कि उनकी विधि बाबाई के अत्याधुनिक अर्ध-बहुपद एल्गोरिदम की तुलना में श्रेणीबद्ध रूप से कम कुशल है। यह सामान्य ग्राफ आइसोमोर्फिज्म समस्या के लिए बहुपद-समय समाधान प्रदान नहीं करती है।

महत्व और दावे
यह शोध पत्र NISQ युग में क्वांटम लाभ के दावों के एक महत्वपूर्ण मूल्यांकन के रूप में स्वयं को स्थापित करता है। इसका प्राथमिक महत्व निम्नलिखित में निहित है:

1. क्वांटम दावों का निराकरण: यह दिखाता है कि ब्रैडलर एट अल. के एल्गोरिदम के लिए प्रस्तावित "क्वांटम लाभ" को भौतिक क्वांटम उपकरण के बिना, समान सांख्यिकीय गुणों की गणना करके शास्त्रीय रूप से दोहराया जा सकता है।
2. सीमाओं को परिभाषित करना: यह इस विचार को पुख्ता करता है कि वर्तमान में लीनियर ऑप्टिकल क्वांटम कंप्यूटरों का उपयोग करके ग्राफ आइसोमोर्फिज्म के लिए कोई सामान्य कुशल क्वांटम एल्गोरिदम उपलब्ध नहीं है।
3. पद्धतिगत भिन्नता: यह गैर-आइसोमोर्फिज्म के परीक्षण के लिए एक नया, विशिष्ट ह्यूरिस्टिक (heuristic) स्थापित करता है जो GBS सांख्यिकी पर आधारित है, जो मानक कलर रिफाइनमेंट के विपरीत, अधिकतम क्रम पर पर्याप्त स्थिति (sufficient condition) को पुनः प्राप्त करने में सैद्धांतिक रूप से सक्षम है।

लेखक निष्कर्ष निकालते हैं कि हालांकि उनकी विधि गैर-आइसोमॉर्फिक ग्राफों को अलग करने के लिए एक उपयोगी ह्यूरिस्टिक है, लेकिन यह वर्तमान में सर्वोत्तम शास्त्रीय दृष्टिकोणों पर कार्यात्मक क्वांटम लाभ प्रदर्शित नहीं करती है।