Hybrid quantum-classical end-to-end pipeline for solving MILPs: a vehicle routing case study

तकनीकी सारांश: MILPs को हल करने के लिए हाइब्रिड क्वांटम-क्लासिकल एंड-टू-एंड पाइपलाइन

समस्या विवरण
मिक्सड-इंटीजर लीनियर प्रोग्रामिंग (MILP) समस्याएँ लॉजिस्टिक्स और आपूर्ति श्रृंखला प्रबंधन जैसे उद्योगों में उच्च-प्रभाव वाले निर्णय लेने के लिए केंद्रीय हैं, लेकिन अपने कॉम्बिनेटोरियल स्वभाव के कारण ये गणनात्मक रूप से चुनौतीपूर्ण होती हैं। जबकि बेंडर्स डिकंपोजिशन (BD) जैसी अपघटन तकनीकें बड़े पैमाने की MILPs को मास्टर प्रॉब्लम (MP) और सबप्रॉब्लम्स (SP) में विभाजित करके हल करने के लिए व्यापक रूप से उपयोग की जाती हैं, वे अक्सर धीमी अभिसरण (convergence) से ग्रस्त होती हैं। यह अभिसरण मास्टर प्रॉब्लम में जोड़ने के लिए सूचनात्मक "कट्स" (constraints) के चयन पर महत्वपूर्ण रूप से निर्भर करता है। पूर्ववर्ती कार्य द्वारा पटेराकिस [1] ने इस प्रक्रिया को तेज करने के लिए कट सिलेक्शन स्टेप को—जिसे मिनिमम सेट कवर समस्या के रूप में तैयार किया गया है—क्वांटम एनीलिंग का उपयोग करने का प्रस्ताव दिया था। हालांकि, क्वांटम एनीलिंग के लिए महंगी माइनर-एम्बेडिंग प्रक्रियाओं की आवश्यकता होती है जो स्केलिंग के दौरान महत्वपूर्ण ओवरहेड उत्पन्न करती है।

कार्यप्रणाली
यह शोध पत्र एक एंड-टू-एंड हाइब्रिड क्वांटम-क्लासिकल ऑप्टिमाइज़ेशन फ्रेमवर्क प्रस्तुत करता है जो मल्टीपल कट्स वाया मल्टीपल सॉल्यूशंस (MCMS) बेंडर्स डिकंपोजिशन दृष्टिकोण का विस्तार करता है। मुख्य नवाचार क्वांटम एनीलिंग स्टेप को गेट-आधारित क्वांटम एप्रोक्सिमेट ऑप्टिमाइज़ेशन एल्गोरिदम (QAOA) कार्यान्वयन के साथ बदलना है।

फ्रेमवर्क इस प्रकार कार्य करता है:

1. MCMS बेंडर्स डिकंपोजिशन: एल्गोरिदम प्रत्येक इटरेशन में कई संभावित समाधान उत्पन्न करता है, जो संभावित कट्स का एक पूल बनाने के लिए समानांतर में कई सबप्रॉब्लम्स को हल करता है।
2. QUBO के रूप में कट सिलेक्शन: अत्यधिक संख्या में कट्स के कारण मास्टर प्रॉब्लम को गणनात्मक रूप से महंगा होने से रोकने के लिए, सूचनात्मक कट्स के एक उपसमुच्चय (subset) का चयन किया जाता है। इसे मिनिमम सेट कवर समस्या के रूप में तैयार किया गया है, जिसे फिर क्वाड्रेटिक अनकन्स्ट्रेंड बाइनरी ऑप्टिमाइज़ेशन (QUBO) इंस्टेंस में मैप किया जाता है।
3. QAOA एकीकरण: एनीलिंग-आधारित दृष्टिकोण के विपरीत, यह फ्रेमवर्क QUBO को QAOA का उपयोग करके हल करता है। पाइपलाइन तीन अलग-अलग सॉल्वर के साथ इंटरफेस करती है:
   • फर्मियोनिक (Fermioniq) का एवा (Ava): एक टेंसर नेटवर्क सर्किट एमुलेटर।
   • MPS-JuliQAOA: जूलिया (Julia) में निर्मित एक ओपन-सोर्स मैट्रिक्स प्रोडक्ट स्टेट (MPS) एमुलेटर।
   • IBM क्वांटम: सुपरकंडक्टिंग क्वांटम हार्डवेयर (IBM Eagle प्रोसेसर) पर सीधा निष्पादन।
4. केस स्टडी: फ्रेमवर्क का मूल्यांकन व्हीकल राउटिंग प्रॉब्लम (VRP) पर किया जाता है, जो एक मानक लॉजिस्टिक्स ऑप्टिमाइज़ेशन समस्या है। पाइपलाइन की व्यवहार्यता का परीक्षण करने के लिए QOptLib (20 ग्राहक, 4 वाहन) के एक मानकीकृत बेंचमार्क और रैंडम टॉय इंस्टेंस (5 ग्राहक) का उपयोग किया गया है।

मुख्य योगदान

• गेट-आधारित विस्तार: यह शोध पत्र मौजूदा HQC-MCMS फ्रेमवर्क को क्वांटम एनीलिंग से गेट-आधारित क्वांटम कंप्यूटिंग तक विस्तारित करता है, जिससे टेंसर नेटवर्क एमुलेटर्स और सुपरकंडक्टिंग क्वांटम प्रोसेसर दोनों पर निष्पादन संभव होता है।
• एंड-टू-एंड कार्यान्वयन: लेखकों ने सफलतापूर्वक एक पूर्ण कार्यात्मक पाइपलाइन का प्रदर्शन किया है जो क्लासिकल बेंडर्स डिकंपोजिशन लूप में QAOA सबरूटीन को एकीकृत करती है।
• अनुभवजन्य बेंचमार्किंग: अध्ययन VRP इंस्टेंस पर विभिन्न सॉल्वर बैकएंड (क्लासिकल Cbc, MPS-JuliQAOA, Fermioniq, और IBM Quantum) पर पाइपलाइन के प्रदर्शन का तुलनात्मक विश्लेषण प्रदान करता है।

परिणाम
प्रायोगिक परिणाम इस विशिष्ट संदर्भ में क्वांटम लाभ की वर्तमान व्यवहार्यता के संबंध में कई महत्वपूर्ण अंतर्दृष्टि प्रदान करते हैं:

• क्लासिकल प्रदर्शन: पूरी तरह से क्लासिकल सेटिंग (कट सिलेक्शन के लिए Cbc का उपयोग करते हुए) में, पाइपलाइन 20-ग्राहक VRP इंस्टेंस के लिए व्यवहार्य समाधान खोजने में सफल रहती है, जिसमें ऑप्टिमलिटी गैप इटरेशन के साथ घटता जाता है। मल्टी-कट दृष्टिकोण (अधिक सबप्रॉब्लम्स का उपयोग करके) कम इटरेशन में व्यवहार्य समाधानों की ओर ले जाता है।
• रनटाइम बॉटलनैक्स: क्लासिकल पाइपलाइन का विश्लेषण प्रकट करता है कि कट सिलेक्शन स्टेप कुल इटरेशन समय का केवल एक छोटा हिस्सा लेता है। अधिकांश कम्प्यूटेशनल समय मास्टर प्रॉब्लम को हल करने में खर्च होता है।
• क्वांटम प्रदर्शन: जब टॉय प्रॉब्लम पर कट सिलेक्शन स्टेप को QAOA (MPS-JuliQAOA का उपयोग करके) द्वारा प्रतिस्थापित किया जाता है, तो क्लासिकल दृष्टिकोण की तुलना में कुल रनटाइम काफी बढ़ जाता है। अध्ययन नोट करता है कि MPS-JuliQAOA इस स्केल पर मिनिमम सेट कवर समस्या के लिए क्लासिकल सॉल्वर Cbc की तुलना में बहुत कम कुशल है।
• QAOA आउटपुट: हार्डवेयर और एमुलेटर्स पर प्रयोगों से पता चलता है कि परीक्षण किए गए कॉन्फ़िगरेशन के लिए, अधिकांश QAOA सैंपल या तो अमान्य (infeasible) समाधान परिणाम देते हैं (अर्थात, वे वैध सेट कवर नहीं बनाते हैं)। जबकि गहरे सर्किट्स ($p=3$) ने उथले सर्किट्स ($p=1$) की तुलना में अधिक अनुकूल लागत (optimal cost) वाले सैंपल दिए, समग्र प्रदर्शन क्लासिकल तरीकों से बेहतर नहीं रहा।

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

1. कट सिलेक्शन स्टेप, जो क्वांटम त्वरण का लक्ष्य है, वर्तमान क्लासिकल MCMS पाइपलाइन में कम्प्यूटेशनल बॉटलनैक नहीं है; मास्टर प्रॉब्लम को हल करने में लगने वाला समय रनटाइम पर हावी है।
2. क्लासिकल सॉल्वर (Cbc) इस स्तर पर उत्पन्न विशिष्ट मिनिमम सेट कवर इंस्टेंस के लिए QAOA कार्यान्वयन की तुलना में कहीं अधिक बेहतर प्रदर्शन करता है।

लेखक इस बात पर जोर देते हैं कि हालांकि पाइपलाइन तकनीकी रूप से कार्यात्मक है और क्वांटम-एन्हांस्ड ऑप्टिमाइज़ेशन की दिशा में एक पुनरुत्पादित (reproducible) कदम प्रदर्शित करती है, लेकिन सेट कवर समस्या को QUBO में बदलने से पर्याप्त ओवरहेड उत्पन्न होता है। उनका तर्क है कि भविष्य के शोध को बड़े पैमाने के बेंचमार्किंग पर ध्यान केंद्रित करना चाहिए जहाँ कट सिलेक्शन स्टेप अधिक महत्वपूर्ण बॉटलनैक बन सकता है, और जहाँ अधिक शक्तिशाली क्वांटम प्रोसेसिंग यूनिट्स (QPUs) संभावित रूप से मूल्य प्रदान कर सकती हैं। यह अध्ययन एक चेतावनीपूर्ण अनुभवजन्य विश्लेषण के रूप में कार्य करता है, जो यह रेखांकित करता है कि वर्तमान क्वांटम विधियाँ अभी भी इस विशिष्ट अपघटन चरण के लिए व्यावहारिक, छोटे-से-मध्यम पैमाने के इंस्टेंस में स्पीडअप प्रदान नहीं करती हैं।