Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization

ऊर्जा परिदृश्य संरचना: लघु ग्राफ समरूपता (Graph Isomorphism) का वैचारिक अनुकूलन

समस्या विवरण

यह शोध पत्र ग्राफ समरूपता (Graph Isomorphism - GI) समस्या को संबोधित करता है, जो एक ऐसी गणनात्मक कार्य है जिसमें यह निर्धारित किया जाता है कि क्या दो परिमित ग्राफ संरचनात्मक रूप से समान हैं। हालांकि यह समस्या जटिलता सिद्धांत (complexity theory) में एक अद्वितीय स्थिति रखती है (न तो सिद्ध रूप से NP-complete है और न ही बहुपद समय (polynomial time) में हल करने योग्य), इसके रसायन विज्ञान, जीव विज्ञान और सामाजिक नेटवर्क में महत्वपूर्ण व्यावहारिक अनुप्रयोग हैं।

लेखक वैरिएशनल क्वांटम एल्गोरिदम (VQAs)—विशेष रूप से क्वांटम एप्रोक्सिमेट ऑप्टिमाइजेशन एल्गोरिदम (QAOA) और वैरिएशनल क्वांटम आइजनसॉल्वर (VQE)—का उपयोग करके GI को हल करने के अनुप्रयोग की जांच करते हैं। मुख्य चुनौती GI समस्या को एक क्वाड्रेटिक अनकन्स्ट्रेंड बाइनरी ऑप्टिमाइजेशन (QUBO) फॉर्मूलेशन (या आइसिंग हैमिल्टोनियन) में एनकोड करने की है, जहाँ वैध ग्राफ समरूपता (isomorphisms) ग्राउंड स्टेट (शून्य ऊर्जा) के अनुरूप होती है। यह अध्ययन इस बात पर केंद्रित है कि क्या वैरीयेशनल अनुकूलन नॉइजी इंटरमीडिएट स्केल क्वांटम (NISQ) युग में, विशेष रूप से छोटे ग्राफ उदाहरणों और सीमित क्वबिट संख्या की बाधाओं के बीच, समरूप (isomorphic) और गैर-समरूप (non-isomorphic) ग्राफ युग्मों के बीच प्रभावी ढंग से अंतर कर सकता है।

कार्यप्रणाली

यह शोध NISQ स्थितियों का अनुकरण करने के लिए छोटे पैमाने के ग्राफ उदाहरणों (4 और 5 नोड्स) का उपयोग करते हुए एक हाइब्रिड क्वांटम-क्लासिकल दृष्टिकोण अपनाता है।

1. समस्या का निर्धारण (Problem Formulation):

   • लेखक पूर्व कार्यों (लुकास, ज़िक एट अल., और कैलुडे एट अल.) से प्राप्त QUBO फॉर्मूलेशन का उपयोग करते हैं।
   • हैमिल्टोनियन में बाइजेक्शन बाधाओं (bijection constraints) (शीर्षों के बीच एक-से-एक मैपिंग सुनिश्चित करना) और एज प्रिजर्वेशन (edge preservation) (यह सुनिश्चित करना कि आसन्नता बनी रहे) को लागू करने के लिए दंड पद (penalty terms) शामिल हैं।
   • आवश्यक तार्किक क्वबिट्स की संख्या $n$ क्रम के ग्राफों के लिए $O(n^2)$ के अनुपात में बढ़ती है, जो वर्तमान हार्डवेयर और सिमुलेशन सीमाओं के कारण अध्ययन को छोटे $n$ तक सीमित करती है।

2. एल्गोरिदम:

   • QAOA: इसे उथले सर्किट डेप्थ ($p=1$) के साथ लागू किया गया है ताकि यह NISQ-प्रासंगिक क्षेत्र के भीतर रहे। यह QUBO से प्राप्त कॉस्ट हैमिल्टोनियन और एक मिक्सर हैमिल्टोनियन का उपयोग करता है।
   • VQE: इसे एक गहरे, अधिक अभिव्यंजक एंसेट (5 पुनरावृत्तियों के साथ TwoLocal सर्किट) के साथ लागू किया गया है और SPSA ऑप्टिमाइज़र का उपयोग किया गया है। यह यह पुष्टि करने के लिए एक उच्च-विश्वसनीयता वाला चेक है कि क्या हैमिल्टोनियन समस्या की संरचना को सही ढंग से एनकोड करता है।

3. विश्लेषण ढांचा (Analysis Framework):

   • केवल अंतिम ऊर्जा मानों पर निर्भर रहने के बजाय, लेखक अनुकूलन प्रक्षेपवक्र (optimization trajectories) का विश्लेषण करते हैं।
   • वे एक फीचर वेक्टर का निर्माण करते जिसमें नोड्स की संख्या ($N$), अंतिम वैरीयेशनल ऊर्जा ($E_{final}$), अनुकूलन चरण (optimization steps), और कुल ऊर्जा में कमी ($\Delta E$) शामिल है।
   • इन फीचर्स को शास्त्रीय मशीन लर्निंग क्लासिफायर (लॉजिस्टिक्स रिग्रेशन, SVM, रैंडम फॉरेस्ट, ग्रेडिएंट बूस्टिंग, XGBoost, LightGBM, MLP) के एक समूह में फीड किया जाता है ताकि यह परीक्षण किया जा सके कि क्या प्रक्षेपवक्र-स्तरीय डेटा समरूप और गैर-समरूप युग्मों के बीच भेदभाव में सुधार करता है।

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

1. समरूप युग्मों का ऊर्जा क्लस्टरिंग (Energy Clustering of Isomorphic Pairs)
अध्ययन यह देखता है कि समरूप ग्राफ युग्म अपने वैरीयेशनल ऊर्जा परिदृश्यों में सुसंगत क्लस्टरिंग (consistent clustering) प्रदर्शित करते हैं।

• QAOA: छोटे सिस्टम ($N=4$) के लिए, समरूप युग्म निम्न ऊर्जा मानों के आसपास केंद्रित होते हैं। हालांकि, जैसे-जैसे $N$ बढ़कर 5 होता है, केवल न्यूनतम ऊर्जा के आधार पर भेदभाव करने की क्षमता तेजी से घट जाती है।
• VQE: यह उच्च विश्वसनीयता के साथ क्लस्टरिंग घटना की पुष्टि करता है, यह दिखाते हुए कि समरूप युग्म शून्य के करीब ऊर्जा की ओर अभिसरित (converge) होते हैं जबकि गैर-समरूप युग्म धनात्मक मानों की ओर अभिसरित होते हैं। यह प्रमाणित करता है कि हैमिल्टोनियन संरचनात्मक विशेषताओं को सही ढंग से एनकोड करता है।
• नियंत्रित एब्लेशन (Controlled Ablation): समरूपता को स्थिर रखते हुए ग्राफ टोपोलॉजी (एज हटाना) को बदलने वाले प्रयोगों ने प्रदर्शित किया कि ऊर्जा परिवर्तन ग्राफ की संरचना द्वारा संचालित होते हैं, न कि लेबलिंग आर्टिफैक्ट्स द्वारा, जो हैमिल्टोनियन एनकोडिंग की स्थिरता की पुष्टि करता है।

2. प्रमाणक के रूप में निम्न ऊर्जा की सीमाएं (Limitations of Low Energy as a Certifier)
एक महत्वपूर्ण निष्कर्ष यह है कि निम्न वैरीयेशनल ऊर्जा, समरूपता का एक अविश्वसनीय प्रमाणक (certifier) है।

• असंभव अवस्थाएं (Infeasible States): अनुकूलन अक्सर ऐसी निम्न-ऊर्जा अवस्थाओं की ओर अभिसरित होता है जो बाइजेक्शन बाधाओं (परम्यूटेशन बाधाओं) का उल्लंघन करती हैं।
• स्पेक्ट्रल ओवरलैप (Spectral Overlap): समरूप और गैर-समरूप उदाहरणों के निम्न-ऊर्जा स्पेक्ट्रा के बीच पर्याप्त ओवरलैप है। कई गैर-समरूप ग्राफ ऐसे ऊर्जा स्तर देते हैं जो समरूप ग्राफ के समान होते हैं, विशेष रूप से उथले सर्किट डेप्थ पर।
• अपभ्रष्टता (Degeneracy): वैध परम्यूटेशन का व्यवहार्य सेट (feasible set) कुल हिल्बर्ट स्पेस ($N! / 2^{N^2} \to 0$) की तुलना में अत्यंत छोटा है, जिससे एक ऐसा परिदृश्य बनता है जो असंभव सुपरपोजिशन (infeasible superpositions) द्वारा हावी है।

3. प्रक्षेपवक्र-आधारित वर्गीकरण का प्रदर्शन (Performance of Trajectory-Based Classification)
लेखकों ने यह परीक्षण किया कि क्या केवल अंतिम ऊर्जा के बजाय अनुकूलन पथ (प्रक्षेपवक्र) का विश्लेषण करने से वर्गीकरण में सुधार हो सकता है।

• परिणाम: जबकि गैर-रेखीय एन्सेम्बल विधियों (रैंडम फॉरेस्ट, ग्रेडिएंट बूस्टिंग) ने रैखिक क्लासिफायर की तुलना में बेहतर प्रदर्शन किया, समग्र सटीकता मध्यम रही (सर्वश्रेष्ठ सटीकता $\approx 75\%$)।
• निष्कर्ष: इन मॉडलों की विश्वसनीय पृथक्करण करने में विफलता यह संकेत देती है कि वैरीयेशनल सिग्नल स्वयं पर्याप्त विभेदक जानकारी की कमी रखता है, न कि क्लासिफायर अपर्याप्त अभिव्यंजक हैं। निम्न-ऊर्जा स्पेक्ट्रा में ओवरलैप एक अंतर्निहित सीमा है।

महत्व और दावे

यह शोध पत्र अपने निष्कर्षों को ग्राफ समरूपता समस्या के स्केलेबल समाधान के बजाय एक सिद्धांत-प्रमाण जांच (proof-of-principle investigation) के रूप में प्रस्तुत करता है।

• नैदानिक उपकरण बनाम सॉल्वर (Diagnostic Tool vs. Solver): लेखक तर्क देते हैं कि NISQ युग में GI के लिए वैरीयेशनल एल्गोरिदम को 'सॉल्वर' के रूप में नहीं, बल्कि हैमिल्टोनियन एनकोडिंग की संरचना की जांच करने के लिए नैदानिक उपकरणों (diagnostic tools) के रूप में देखा जाना चाहिए। देखी गई ऊर्जा क्लस्टरिंग दर्शाती है कि हैमिल्टोनियन संरचनात्मक विशेषताओं को सफलतापूर्वक एनकोड करता है, लेकिन ऊर्जा के आधार पर वर्गों को अलग करने में असमर्थता शुद्ध ऊर्जात्मक ह्यूरिस्टिक्स (energetic heuristics) की सीमाओं को उजागर करती है।
• वर्तमान दृष्टिकोणों की सीमाएं: अध्ययन इस बात पर जोर देता है कि वैश्विक परम्यूटेशन बाधाओं को स्पष्ट रूप से लागू करने वाले तंत्र या उन्नत एंसेट के बिना, वैरीयेशनल एल्गोरिदम असंभव निम्न-ऊर्जा अवस्थाओं की व्यापकता के कारण समरूप और गैर-समरूप ग्राफों के बीच अंतर करने में संघर्ष करेंगे।
• भावी दिशा: कार्य यह सुझाव देता है कि प्रगति के लिए कॉम्पैक्ट QUBO एनकोडिंग, समस्या-अनुकूलित एंसेट और बाधा-जागरूक मिक्सर की आवश्यकता है। यह भी उल्लेख करता है कि सिमुलेशन और प्रयोगात्मक व्यवहार्यता के बीच के अंतर को पाटने के लिए बड़े ग्राफ (6-8 नोड्स) तक विस्तार करना और त्रुटि न्यूनीकरण (error mitigation) के साथ वास्तविक हार्डवेयर पर परीक्षण करना आवश्यक अगला कदम है।

संक्षेप में, यह शोध पत्र प्रदर्शित करता है कि हालांकि वैरीयेशनल क्वांटम एल्गोरिदम ग्राफ संरचनाओं के अनुरूप निम्न-ऊर्जा बेसिन की पहचान कर सकते हैं, लेकिन ऊर्जा न्यूनीकरण अकेले स्केलेबल ग्राफ समरूपता भेदभाव के लिए पर्याप्त नहीं है, क्योंकि असंभव अवस्थाओं में अभिसरण होने की उच्च संभावना और ग्राफ वर्गों के बीच स्पेक्ट्रल ओवरलैप मौजूद है।