Motzkin-Straus Optimization on an Entropy-Computing Platform
यह शोध पत्र एक ऐसे ढांचे को प्रस्तुत करता है जो QCi के Dirac-3S फोटोनिक एंट्रॉपी कंप्यूटर पर कॉम्बिनेटरियल ऑप्टिमाइज़ेशन समस्याओं को हल करने के लिए मोट्ज़किन-स्ट्रॉस प्रमेय का लाभ उठाता है, जो यह प्रदर्शित करता है कि यह एनालॉग प्लेटफॉर्म अधिकांश बेंचमार्क इंस्टेंस पर शास्त्रीय सॉल्वर के बराबर या उनसे बेहतर प्रदर्शन करता है और साथ ही गैर-उत्तल (non-convex) परिदृश्यों में नेविगेट करने के लिए एंट्रॉपी कंप्यूटिंग को एक प्रतिस्पर्धी दृष्टिकोण के रूप में स्थापित करता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
आधुनिक कंप्यूटिंग के विशाल परिदृश्य में, कुछ समस्याएँ इतनी जटिल होती हैं कि वे गति और मेमोरी की सीमाओं को चुनौती देती हुई प्रतीत होती हैं। इन्हें कॉम्बिनेटरियल ऑप्टिमाइज़ेशन (combinatorial optimization) समस्याएं कहा जाता है, जो चुनौतियों का एक वर्ग है जहाँ लक्ष्य उपलब्ध असंख्य संभावनाओं में से एकल सर्वोत्तम व्यवस्था को खोजना होता है। कल्पना कीजिए कि आप एक विशाल पार्टी आयोजित करने की कोशिश कर रहे हैं जहाँ आपको मेहमानों का एक ऐसा समूह चुनना है जो सभी एक-दूसरे को जानते हों, लेकिन आप सबसे बड़ा संभव समूह चाहते हैं। जैसे-जैसे मेहमानों की सूची बढ़ती है, इस समूह को बनाने के तरीके विस्फोट की तरह बढ़ते जाते हैं, जिससे पारंपरिक कंप्यूटरों के लिए हर विकल्प की जाँच करना लगभग असंभव हो जाता है। यह विशिष्ट पहेली, जिसे "मैक्सिमम क्लिक" (maximum clique) खोजने के रूप में जाना जाता है, केवल एक गणितीय जिज्ञासा नहीं है; यह उड़ान भरने के शेड्यूलिंग, संसाधनों के आवंटन और सामाजिक नेटवर्क के विश्लेषण जैसे वास्तविक दुनिया के कार्यों का आधार है। दशकों से, वैज्ञानिक इन समस्याओं को कुशलतापूर्वक हल करने के लिए संघर्ष करते रहे हैं, और अक्सर उन्हें पूर्ण उत्तर के बजाय 'पर्याप्त अच्छे' उत्तरों से संतोष करना पड़ता है।
हाल ही में, शोधकर्ताओं की एक टीम ने एक अलग तरह की मशीन की ओर मुड़कर इन पहेलियों से निपटने का एक नया तरीका खोजा है। साधारण कंप्यूटरों में पाए जाने वाले मानक लॉजिक गेट्स पर निर्भर रहने के बजाय, उन्होंने एक 'एन्ट्रॉपी कंप्यूटर' (entropy computer) नामक उपकरण का उपयोग किया। यह मशीन एक ऐसे सिद्धांत पर काम करती है जो विरोधाभासी लग सकता है: यह प्रकाश के प्राकृतिक, यादृच्छिक उतार-चढ़ाव का उपयोग करती है—विशेष रूप से इस बात का कि फोटॉन, या प्रकाश के कण, एक धारा में कैसे आते हैं—ताकि यह गतिरोध (dead ends) से बाहर निकल सके। ऑप्टिमाइज़ेशन की दुनिया में, एक "लोकल मिनिमम" (local minimum) में फंसना एक पहाड़ी श्रृंखला में एक छोटी घाटी खोजने और यह सोचने जैसा है कि यह दुनिया का निचला हिस्सा है, जबकि अगली पहाड़ी के ठीक पार एक बहुत गहरी घाटी स्थित है। पारंपरिक कंप्यूटर अक्सर इन छोटी घाटियों में फंस जाते हैं। हालाँकि, एन्ट्रॉपी कंप्यूटर क्वांटम दुनिया के अंतर्निहित शोर (noise) का उपयोग सिस्टम को थोड़ा धकेलने के लिए करता है, जिससे इसे बाधाओं के ऊपर से कूदने और अधिक स्वतंत्र रूप से परिदृश्य का अन्वेषण करने में मदद मिलती है, ताकि वह वास्तविक निम्नतम बिंदु को खोज सके।
शोधकर्ताओं ने, 'डायरैक-3S' (Dirac-3S) नामक एक उपकरण के साथ काम करते हुए, यह देखने के लिए प्रयास किया कि क्या यह दृष्टिकोण मानक कंप्यूटरों पर उपलब्ध सर्वोत्तम विधियों की तुलना में मैक्सिमम क्लिक समस्या को बेहतर ढंग से हल कर सकता है। उन्होंने इस समस्या को उस प्रारूप में जबरदस्ती नहीं डाला जिसे मशीन स्वाभाविक रूप से नहीं समझती थी। इसके बजाय, उन्होंने 1960 के दशक के एक गणितीय अंतर्दृष्टि का उपयोग किया जो जुड़े हुए समूहों की गिनती करने की असतत (discrete) समस्या को एक सुचारू, निरंतर आकार (smooth, continuous shape) में बदल देता है। यह अनुवाद महत्वपूर्ण था क्योंकि डायरैक-3S स्वाभाविक रूप से सुचारू आकारों और बाधाओं को संभालने के लिए बनाया गया है। मशीन समय अंतराल में फोटॉन की गिनती करती है, और चूंकि आप फोटॉन की ऋणात्मक संख्या नहीं रख सकते, इसलिए उपकरण स्वतः ही इस नियम का पालन करता है कि सभी मान धनात्मक होने चाहिए। इसके अलावा, मशीन के डिज़ाइन द्वारा फोटॉन की कुल संख्या निर्धारित होती है, जो स्वतः ही इस आवश्यकता को पूरा करती है कि मानों का योग एक विशिष्ट कुल तक होना चाहिए। इसका अर्थ था कि शोधकर्ता अपने प्रश्न को बिना किसी जटिल वर्कअराउंड या अतिरिक्त चरणों के, जो अन्य क्वांटम सिस्टम को धीमा कर देते हैं, सीधे हार्डवेयर पर मैप कर सके।
अपने सिस्टम का परीक्षण करने के लिए, टीम ने 75 कठिन ग्राफ समस्याओं के एक मानक सेट पर डायरैक-3S को दो अत्यधिक परिष्कृत क्लासिकल कंप्यूटर प्रोग्रामों के विरुद्ध चलाया। इन समस्याओं में 28 नोड्स वाले छोटे नेटवर्क से लेकर 4,000 नोड्स वाली विशाल संरचनाएं शामिल थीं। परिणाम आश्चर्यजनक थे। चार-पത്തിലों से अधिक परीक्षण मामलों में, एन्ट्रॉपी कंप्यूटर ने क्लासिकल प्रोग्रामों के प्रदर्शन की बराबरी की या उससे बेहतर प्रदर्शन किया। कई सबसे बड़े और सबसे जटिल उदाहरणों में, डायरैक-3S ने दोनों क्लासिकल प्रतिद्वंद्वियों से बेहतर समाधान खोजे, और अक्सर उन सर्वोत्तम-ज्ञात उत्तरों तक पहुँच गया जो पिछले वर्षों के शोध द्वारा स्थापित किए गए थे। मशीन इन समस्याओं के ऊबड़-खाबड़ और ऊबड़-खाबड़ इलाके में नेविगेट करने में विशेष रूप से कुशल लग रही थी, और इसने अपने खोज प्रयासों को सर्वोत्तम समाधानों के पास बहुत अधिक प्रभावी ढंग से केंद्रित किया, जबकि क्लासिकल विधियाँ अक्सर कई कम आशाजनक क्षेत्रों में अपने प्रयासों को बिखेर देती थीं।
हालाँकि, यह कहानी पूर्ण विजय की नहीं है। शोधकर्ताओं ने पाया कि एक विशिष्ट प्रकार की कठिन समस्या, जिसे "प्लांटेड क्लिक" (planted clique) उदाहरण कहा जाता है जहाँ शोर के समुद्र के भीतर एक समाधान छिपा होता है, वहाँ क्लासिकल कंप्यूटर प्रोग्राम अभी भी बढ़त बनाए रखते हैं। ये प्रोग्राम, जो विभिन्न शुरुआती बिंदुओं से खोज को कई बार फिर से शुरू करने की रणनीति का उपयोग करते हैं, इन विशिष्ट मामलों में छिपे हुए समाधान को खोजने में बेहतर थे। यह सुझाव देता है कि जबकि एन्ट्रॉपी कंप्यूटर जटिल परिदृश्यों का पता लगाने का एक शक्तिशाली नया तरीका प्रदान करता है, यह अभी तक हर मामले को पूरी तरह से हल करने वाला कोई जादुई हथियार नहीं है। शोधकर्ताओं ने नोट किया कि प्रदर्शन का अंतर अक्सर छोटा था, कभी-कभी समूह में केवल एक नोड का, लेकिन तथ्य यह है कि एन्ट्रॉपी कंप्यूटर विविध समस्याओं की एक विस्तृत श्रृंखला पर सर्वोत्तम क्लासिकल एल्गोरिदम के साथ इतनी निकटता से प्रतिस्पर्धा कर सका, यह एक महत्वपूर्ण प्रगति है।
यह कार्य कंप्यूटिंग के भविष्य के लिए एक आशाजनक मार्ग को रेखांकित करता है। पारंपरिक मशीनों के लिए कठिन समस्याओं को हल करने के लिए प्रकाश के प्राकृतिक व्यवहार का उपयोग करके, एन्ट्रॉपी कंप्यूटर प्रदर्शित करता है कि अपरंपरागत हार्डवेयर एक गंभीर प्रतिस्पर्धी हो सकता है। शोधकर्ता सुझाव देते हैं कि भविष्य में सबसे शक्तिशाली दृष्टिकोण यह नहीं होगा कि क्लासिकल और क्वांटम विधियों के बीच चयन किया जाए, बल्कि उन्हें मिलाया जाए। वे एक हाइब्रिड सिस्टम की कल्पना करते हैं जहाँ एन्ट्रोपी कंप्यूटर तेजी से परिदृश्य को स्कैन करके आशाजनक क्षेत्रों को खोजता है, और फिर एक क्लासिकल कंप्यूटर सटीक शिखर खोजने के लिए उत्तर को परिष्कृत करता है। यह अध्ययन स्थापित करता है कि एन्ट्रॉपी कंप्यूटिंग वास्तविक दुनिया के अनुकूलन के कठिन, नॉन-कॉन्वेक्स (non-convex) परिदृश्यों में नेविगेट करने के लिए एक व्यवहार्य और प्रतिस्पर्धी दृष्टिकोण है, जो उन वैज्ञानिकों और इंजीनियरों को एक नया उपकरण प्रदान करता है जिन्हें हमारे समय की सबसे कठिन पहेलियों को हल करने की आवश्यकता है।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।