Quantum Superposition over Near Optimal Seeds for Maximum Independent Set on Dense Graphs
यह शोध पत्र एक क्वांटम वेरिएशनल एल्गोरिदम प्रस्तुत करता है जो कठिन इंस्टेंस (instances) पर जहाँ पिछले तरीके रुक जाते हैं, वहां 400 नोड्स तक के घने ग्राफों पर मैक्सिमम इंडिपेंडेंट सेट समस्याओं को हल करने के लिए निकट-इष्टतम बीजों (near-optimal seeds) के समान वितरण (uniform superpositions) और हस्तक्षेप-आधारित पोस्ट-सिलेक्शन (interference-based post-selection) का लाभ उठाता है, जो मानक VQE और क्लासिकल ह्यूरिस्टिक्स की तुलना में काफी बेहतर प्रदर्शन करता है।
मूल पेपर CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कंप्यूटर विज्ञान की दुनिया में, समस्याओं का एक वर्ग है जिसे कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन (combinatorial optimization) के रूप में जाना जाता है, जहाँ लक्ष्य विकल्पों की एक विशाल संख्या में से सबसे अच्छा संभव विन्यास खोजना होता है। इनमें से एक सबसे प्रसिद्ध 'मैक्सिमम इंडिपेंडेंट सेट' (Maximum Independent Set) समस्या है। कल्पना कीजिए कि एक पार्टी में लोगों का एक समूह है, जहाँ कुछ लोग एक-दूसरे को जानते हैं और अन्य नहीं। चुनौती मेहमानों की सबसे बड़ी संभव संख्या को एक निजी कमरे में आमंत्रित करने की है ताकि कमरे में मौजूद दो लोग एक-दूसरे को न जानते हों। यदि दो लोग एक-दूसरे को जानते हैं, तो उन दोनों को आमंत्रित नहीं किया जा सकता। हालांकि यह एक छोटे समूह के लिए सरल लगता है, लेकिन संभावित संयोजनों की संख्या इतनी तेज़ी से बढ़ती है कि कुछ सौ लोगों के समूह तक पहुँचते ही सबसे शक्तिशाली सुपरकंप्यूटर भी सटीक उत्तर खोजने के लिए संघर्ष करने लगते हैं। यह कठिनाई इस समस्या को नई कंप्यूटिंग तकनीकों, विशेष रूप से क्वांटम कंप्यूटरों के लिए एक मानक परीक्षण बनाती है, जो कई संभावनाओं को एक साथ तलाशने के लिए क्वांटम मैकेनिक्स के विचित्र नियमों का उपयोग करते हैं।
IBM रिसर्च के शोधकर्ताओं ने घने ग्राफ (dense graphs) पर इस समस्या से निपटने के लिए एक नई विधि विकसित की है, जहाँ लगभग हर कोई लगभग हर किसी को जानता है। इन भीड़भाड़ वाले परिदृश्यों में, पारंपरिक खोज विधियाँ अक्सर एक स्थानीय जाल (local trap) में फंस जाती हैं, जिससे वे एक अच्छा समाधान तो ढूंढ लेती हैं लेकिन पूर्ण समाधान को चूक जाती हैं क्योंकि सर्वोत्तम उत्तर तक पहुँचने का मार्ग ऐसे समन्वित परिवर्तनों की एक श्रृंखला की मांग करता है जो एक-एक करके करना असंभव लगता है। शोधकर्ताओं ने पाया कि कई "लगभग-पूर्ण" समाधानों को सुपरपोजिशन (superposition) की स्थिति में रखने के लिए क्वांटम कंप्यूटर का उपयोग करके—एक ऐसी स्थिति जहाँ कंप्यूटर एक साथ कई विकल्पों पर विचार करता है—वे इन जालों को तोड़ सकते हैं। 400 नोड्स तक के ग्राफ पर परीक्षण किए गए उनके कार्य से पता चलता है कि यह दृष्टिकोण गैर-समीपवर्ती वर्टिसिस (non-adjacent vertices) के सबसे बड़े समूहों को खोज सकता है, जिससे उन उदाहरणों को हल किया जा सका जिन्होंने मानक विधियों को विफल कर दिया था। महत्वपूर्ण रूप से, उन्होंने दिखाया कि यह सफलता क्वांटम कंप्यूटर की समाधान परिदृश्य (landscape of solutions) को समानांतर में तलाशने की क्षमता पर निर्भर करती है, न कि केवल एक शुरुआती बिंदु को सुधारने पर।
शोधकर्ताओं ने एक विशिष्ट कमजोरी को स्वीकार करते हुए शुरुआत की जो आमतौर पर क्वांटम कंप्यूटरों द्वारा इन समस्याओं के प्रति अपनाई जाती है। मानक विधियाँ अक्सर एक खाली स्लेट से शुरू होती हैं, क्वांटम मशीन को शून्य से पूरी संभावनाओं के ब्रह्मांड को खोजने के लिए कहती हैं। घने ग्राफ के लिए, सही उत्तर इतना दुर्लभ है कि यह समुद्र तट पर रेत के एक विशिष्ट कण को खोजने जैसा है; खाली स्लेट से शुरू करने का अर्थ है कि कंप्यूटर के पास कभी भी उस पर ठोकर खाने की बहुत कम संभावना है। इसके बजाय, टीम ने एक 'हेड स्टार्ट' (शुरुआती बढ़त) देने का निर्णय लिया। उन्होंने क्लासिकल कंप्यूटरों का उपयोग करके कई उच्च-गुणवत्ता वाले, हालांकि पूर्ण नहीं, समाधान खोजे। ये खोज के "बीज" (seeds) थे। फिर उन्होंने इन बीजों को क्वांटम कंप्यूटर में एनकोड किया, एक-एक करके नहीं, बल्कि एक साथ, एक समान सुपरपोजिशन बनाकर। इस अवस्था में, क्वांटम कंप्यूटर प्रभावी रूप से इन सभी लगभग-इष्टतम समाधानों को अपने मन में एक साथ रख रहा था, उन्हें एक एकल, जटिल शुरुआती बिंदु के रूप में मान रहा था।
यह सुनिश्चित करने के लिए कि खोज सही दिशा में रहे, टीम ने एक विशेष प्रकार के क्वांटम सर्किट का उपयोग किया जिसे "एक्साइटेशन" (excitation) गणना को संरक्षित करने के लिए डिज़ाइन किया गया था। समस्या की भाषा में, इसका मतलब था कि सर्किट को सख्ती से आमंत्रित किए गए लोगों की कुल संख्या को बदलने से रोका गया था। यदि बीजों में 14 लोग थे, तो क्वांटम विकास केवल उन 14 लोगों को इधर-उधर घुमा सकता था, एक अतिथि को दूसरे से बदलकर, लेकिन वह गलती से 15वें व्यक्ति को आमंत्रित नहीं कर सकता था या संख्या को 13 तक नहीं गिरा सकता था। यह प्रतिबंध अत्यंत महत्वपूर्ण था। इसने खोज को समाधान स्थान के सबसे आशाजनक क्षेत्र पर केंद्रित रखा, जिससे कंप्यूटर को असंभव या स्पष्ट रूप से निम्न स्तर के विन्यासों की खोज में समय बर्बाद करने से रोका जा सके। आमंत्रित मेहमानों की संख्या को स्थिर रखकर, सर्किट 14 के विभिन्न समूहों के बीच सूक्ष्म अंतर कर सकता था, और उस विशिष्ट व्यवस्था की तलाश कर सकता था जो पूर्ण उत्तर के सबसे करीब थी।
टीम ने इस पाइपलाइन का परीक्षण कई कठिन ग्राफों पर किया, जिसमें एक चुनौतीपूर्ण 180-नोड वाला उदाहरण शामिल था जहाँ पूर्ण समाधान में 15 लोग शामिल थे। जब उन्होंने एक एकल बीज का उपयोग करके इसे हल करने का प्रयास किया, तो सिस्टम लगातार 14 लोगों पर अटक गया, 15वें व्यक्ति तक पहुँचने का मार्ग खोजने में असमर्थ रहा। हालाँकि, जब उन्होंने चार अलग-अलग 14-व्यक्ति वाले बीजों के सुपरपोजिशन का उपयोग किया, तो सिस्टम ने इस बाधा को पार कर लिया। क्वांटम कंप्यूटर ने, सभी चार बीजों को नियमों के एक ही सेट के तहत एक साथ विकसित करके, एक ऐसा विन्यास खोज निकाला जिसे कोई भी व्यक्तिगत बीज अकेले नहीं खोज सकता था। अंतिम चरण में एक क्लासिकल कंप्यूटर द्वारा क्वांटम आउटपुट लेना और एक त्वरित, स्मार्ट जांच करना शामिल था कि क्या समूह को 15 तक बढ़ाया जा सकता है। इस हाइब्रिड दृष्टिकोण ने सफलतापूर्वक 15 लोगों के प्रमाणित अधिकतम समूह को पुनः प्राप्त किया, जो एक परिणाम था जिसे न तो क्लासिकल पोस्ट-प्रोसेसिंग और न ही मानक क्वांटम विधि अकेले प्राप्त कर सकती थी।
यह समझने के लिए कि यह क्यों काम कर रहा था, शोधकर्ताओं ने अन्य स्पष्टीकरणों को खारिज करने के लिए कई जाँच कीं। उन्होंने परीक्षण किया कि क्या क्लासिकल पोस्ट-प्रोसेसिंग अकेले उत्तर पा सकती थी यदि उसे केवल एक बीज दिया जाता, लेकिन वह हर बार विफल रही। उन्होंने यह भी परीक्षण किया कि क्या क्वांटम सर्किट संरचना स्वयं जादुई तत्व थी, इसके लिए सिंगल सीड्स पर इसे चलाया, लेकिन वह भी अटक गया। एकमात्र तरीका स्थानीय जाल से बचने के लिए सभी बीजों पर एक साथ अनुकूलन करना था। इसने पुष्टि की कि शक्ति समानांतर खोज से आई थी: क्वांटम कंप्यूटर ने ऐसे मापदंडों का एक सेट खोजा जिसने सभी चार शुरुआती बिंदुओं को एक साथ सुधारा, प्रभावी रूप से एक ऐसे पथ का नेविगेशन किया जो किसी भी एकल शुरुआती बिंदु के लिए अदृश्य था।
शोधकर्ताओं ने यह भी पता लगाया कि क्या सुपरपोजिशन की विभिन्न शाखाएं एक-दूसरे के साथ हस्तक्षेप (interfere) कर सकती हैं ताकि सर्वश्रेष्ठ उत्तरों को बढ़ाया जा सके, जो एक ऐसी घटना है जहाँ क्वांटम तरंगें मिलकर सिग्नल को मजबूत बनाती हैं। उन्होंने हस्तक्षेप पैदा करने के लिए डिज़ाइन किया गया एक विशिष्ट लेयर जोड़ा और फिर परिणामों को मापा। हालांकि वे इन क्वांटम क्रॉस-टर्म्स की उपस्थिति का पता लगा सकते थे, लेकिन प्रभाव वर्तमान सिमुलेशन में छोटा था। शोधकर्ताओं ने नोट किया कि इस हस्तक्षेप को अधिक शक्तिशाली होने के लिए, विभिन्न समाधानों को संरचना में बहुत समान होना होगा, या क्वांटम सर्किट को बहुत गहरा होना चाहिए। उन्होंने पाया कि उनके द्वारा सिम्युलेट किया जा सकने वाला सर्किट का डेप्थ (गहराई), एंटैंगलमेंट की जटिलता द्वारा सीमित था, जो सुझाव देता है कि इस हस्तक्षेप प्रभाव का पूर्ण लाभ उठाने के लिए अधिक क्वबिट्स और बेहतर स्थिरता वाले भविष्य के हार्डवेयर की आवश्यकता होगी।
टीम ने छोटे ग्राफों के लिए वास्तविक क्वांटम हार्डवेयर पर अपने निष्कर्षों को मान्य किया, एक 156 क्वबिट वाले IBM प्रोसेसर पर अपने एल्गोरिदम चलाए। वर्तमान मशीनों में अंतर्निहित शोर और त्रुटियों के बावजूद, पद्धति ने 64, 99 और 125 नोड्स वाले ग्राफ के लिए इष्टतम समाधानों को सफलतापूर्वक पुनः प्राप्त किया। इससे सिद्ध हुआ कि यह पाइपलाइन वास्तविक उपकरणों पर काम करने के लिए पर्याप्त मजबूत है, न कि केवल आदर्श सिमुलेशन में। बड़े ग्राफों के लिए, जैसे कि 400-नोड वाला उदाहरण, टीम ने हाई-फिडेलिटी सिमुलेशन पर भरोसा किया क्योंकि समस्या का आकार वर्तमान क्वांटम हार्डवेयर की क्षमता से अधिक था। इन सिमुलेशन में, उन्होंने पाया कि क्वांटम सर्किट की गहराई बढ़ाने से उन्हें बड़े इंडिपेंडेंट सेट्स खोजने में मदद मिली, जिससे एक ऐसे ग्राफ पर 25 की संख्या तक पहुँचा जहाँ पूर्ण उत्तर 27 है। यह सुझाव देता है कि जैसे-जैसे क्वांटम कंप्यूटर अधिक शक्तिशाली होते जाएंगे, यह विधि स्केल (scale) करती रहेगी।
यह कार्य इस बात पर प्रकाश डालता है कि कठिन समस्याओं के लिए क्वांटम एल्गोरिदम को कैसे डिज़ाइन किया जा सकता है। उत्तर को शून्य से खोजने के बजाय, सबसे प्रभावी रणनीति यह हो सकती है कि क्लासिकल कंप्यूटरों का उपयोग अच्छे शुरुआती बिंदु खोजने के लिए किया जाए और फिर क्वांटम कंप्यूटरों का उपयोग उनके बीच के स्थान को तलाशने के लिए किया जाए। शोधकर्ताओं ने दिखाया कि दोनों की शक्तियों को जोड़कर—बीजों को खोजने के लिए क्लासिकल ह्यूरिस्टिक्स और उनके बीच के संबंधों को तलाशने के लिए क्वांटम सुपरपोजिशन—वे उन समस्याओं को हल कर सकते थे जो पहले पहुंच से बाहर थीं। हालांकि उन्होंने सभी संभावित ग्राफों के लिए मैक्सिमम इंडिपेंडेंट सेट समस्या को हल करने का दावा नहीं किया, लेकिन उन्होंने घने ग्राफों के सबसे कठिन उदाहरणों को हल करने के लिए एक स्पष्ट और पुनरुत्पादनीय पथ प्रदर्शित किया, जो भविष्य के क्वांटम कंप्यूटरों के लिए जटिल कॉम्बिनेटोरियल चुनौतियों से निपटने के लिए एक ब्लूप्रिंट प्रदान करता है।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।