QAOA Inside ADMM: Subproblem Wins Do Not Become Decomposition Wins at Matched Budgets
यह शोध पत्र मिश्रित-बाइनरी समस्याओं के लिए एक ADMM ढांचे के भीतर एक उप-समस्या समाधानकर्ता (subproblem solver) के रूप में क्वांटम एप्रोक्सिमेट ऑप्टिमाइज़ेशन एल्गोरिदम (QAOA) का बेंचमार्किंग करता है, जिसमें यह पाया गया है कि हालांकि QAOA विशिष्ट मूल्यांकन मानदंडों के तहत शोर रहित सिमुलेशन (noiseless simulations) में शास्त्रीय स्थानीय अनुमानी (classical local heuristics) से बेहतर प्रदर्शन कर सकता है, लेकिन अंततः यह परीक्षण किए गए समस्या परिवारों में सर्वश्रेष्ठ शास्त्रीय सॉल्वर की तुलना में बेहतर समग्र समाधान देने में विफल रहता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखक ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
जटिल निर्णय लेने की दुनिया में, कंप्यूटर अक्सर उन समस्याओं का सामना करते हैं जहाँ लाखों संभावित उत्तर होते हैं, जहाँ एक एकल सर्वोत्तम उत्तर खोजना एक ऐसे घास के ढेर में सुई खोजने जैसा है जो अपना आकार बदलता रहता है। इससे निपटने के लिए, वैज्ञानिक 'डिकम्पोज़िशन' (decomposition) नामक एक रणनीति का उपयोग करते हैं, जो एक विशाल, उलझी हुई समस्या को छोटे, प्रबंधनीय टुकड़ों में तोड़ देता है जिन्हें अलग से हल किया जा सकता है। इसे करने के लिए एक लोकप्रिय विधि 'अल्टरनेटिंग डायरेक्शन मेथड ऑफ मल्टीप्लायर्स' (ADMM) है। यह समस्या के निरंतर (continuous) भागों और असतत (discrete), ऑन-ऑफ़ भागों के बीच बारी-बारी से काम करता है, और टुकड़ों को आपस में जोड़ने तक सूचनाओं का आदान-प्रदान करता है। वर्षों से, शोधकर्ता यह जानना चाहते थे कि क्या क्वांटम कंप्यूटर, जो क्वांटम यांत्रिकी के विचित्र नियमों पर काम करते हैं, इन असतत टुकड़ों को शास्त्रीय (classical) कंप्यूटरों की तुलना में तेज़ी से हल कर सकते हैं। इस काम के लिए सबसे प्रमुख उम्मीदवार 'क्वांटम एप्रोक्सीमेट ऑप्टिमाइज़ेशन एल्गोरिदम' (QAOA) नामक एक एल्गोरिदम है, जिसे कई संभावनाओं को एक साथ तलाशकर अच्छे समाधान खोजने के लिए डिज़ाइन किया गया है। बड़ा सवाल यह रहा है कि क्या यह क्वांटम दृष्टिकोण हमारे पास मौजूद बहुत मजबूत शास्त्रीय तरीकों की तुलना में वास्तव में लागत और प्रयास के लायक है।
शोधकर्ताओं की एक टीम ने एक क्वांटम एल्गोरिदम को ADMM ढांचे के भीतर एक कठोर परीक्षण के माध्यम से इस प्रश्न का उत्तर देने के लिए हाथ आजमाया। उन्होंने केवल क्वांटम कंप्यूटर को नहीं चलाया और बेहतर परिणाम की उम्मीद नहीं की; बल्कि उन्होंने एक निष्पक्ष तुलना बनाई जहाँ दोनों क्वांटम और शास्त्रीय सॉल्वर को पहेली के छोटे टुकड़ों को हल करने के लिए बिल्कुल समान मात्रा में कम्प्यूटेशनल प्रयास, या "बजट" दिया गया था। अध्ययन एक विशिष्ट प्रकार की समस्या पर केंद्रित था जहाँ चर (variables) बाइनरी हैं, जिसका अर्थ है कि वे केवल शून्य या एक हो सकते हैं। शोधकर्ताओं ने एक बारह-क्यूबिट (twelve-qubit) क्वांटम कंप्यूटर के शोर रहित, आदर्श संस्करण पर सिमुलेशन चलाया ताकि यह देखा जा सके कि क्वांटम सॉल्वर, रैंडम सर्च, सिम्युलेटेड एनीलिंग और टैबू सर्च (tabu search) जैसी उन्नत तकनीकों सहित सॉल्वर के एक समूह के मुकाबले कैसा प्रदर्शन करता है। उन्होंने सिस्टम का परीक्षण दो अलग-अलग प्रकार के समस्या परिवारों पर किया: एक जो अपेक्षाकृत सुचारू और आसान था, और दूसरा जो ऊबड़-खाबड़ और कठिन था, जिसे वास्तविक दुनिया के अनुप्रयोगों में पाए जाने वाले जटिल परिदृश्यों की नकल करने के लिए डिज़ाइन किया गया था।
सबसे आश्चर्यजनक खोज इस बात से आई कि परिणामों को कैसे गिना गया। क्वांटम कंप्यूटिंग की दुनिया में, एक एल्गोरिदम का एक एकल रन संभावित उत्तरों, या बिटस्ट्रिंग्स (bitstrings) की एक धारा उत्पन्न करता है, और एल्गोरिदम अपना अधिकांश समय इन उत्तरों को सुधारने के लिए अपनी आंतरिक सेटिंग्स को समायोजित करने में बिताता है। शोधकर्ताओं ने पाया कि अंतिम निर्णय पूरी तरह से इस बात पर निर्भर था कि रन का प्रतिनिधित्व करने के लिए किस उत्तर को चुना गया। यदि शोधकर्ताओं ने क्वांटम कंप्यूटर को केवल उसके अंतिम सेट के उत्तरों के लिए श्रेय दिया, जैसा कि कुछ मानक सॉफ्टवेयर ट्यूटोरियलों में सामान्य है, तो क्वांटम सॉल्वर एक साधारण रैंडम सर्च की तुलना में भी खराब प्रदर्शन करता था। यह उस कंप्यूटर की तुलना में अधिक बार सर्वोत्तम समाधान खोजने में विफल रहा जिसने केवल अंदाज़ा लगाया था। हालाँकि, जब शोधकर्ताओं ने क्वांटम सॉल्वर को उसके पूरे रन के दौरान मिले किसी भी बिंदु पर मिले एकल सर्वोत्तम उत्तर के लिए श्रेय दिया, तो कहानी पूरी तरह बदल गई। इस "बेस्ट-सैंपल" (best-sample) स्कोरिंग के तहत, क्वांटम सॉल्वर ने रैंडम सर्च को पछाड़ दिया और यहाँ तक कि कठिन, ऊबड़-खाबड़ समस्याओं पर उप-समस्या स्तर पर कई परिष्कृत शास्त्रीय तरीकों को भी मात दी। इसने खुलासा किया कि क्वांटम दृष्टिकोण की कथित विफलता अक्सर डेटा को स्कोर करने के तरीके का एक परिणाम थी, न कि स्वयं भौतिकी की विफलता।
जब शोधकर्ताओं ने 'ट्रांसफर्ड एंगल्स' (transferred angles) के रूप में ज्ञात पूर्व-प्रशिक्षित सेटिंग्स का उपयोग करने वाले क्वांटम एल्गोरिदम के एक विशिष्ट संस्करण के प्रदर्शन को गहराई से देखा, तो उन्होंने पाया कि यह कठिन उप-समस्याओं को उल्लेखनीय सटीकता के साथ हल कर सकता है। ऊबड़-खाबड़ समस्या परिवार पर, इस क्वांटम दृष्टिकोण ने ट्यून्ड लोकल सर्च विधियों (मजबूत स्थानीय अनुमानी विधियों के लिए 97.3% बनाम 67.4%) की तुलना में अधिक बार सटीक सर्वोत्तम समाधान खोजा, हालांकि इसने सेमीडेफिनेट प्रोग्रामिंग (SDP+LS) पर आधारित एक शास्त्रीय तकनीक को नहीं पछाड़ा। हालाँकि, यह लाभ समग्र समस्या के अंतिम परिणाम में नहीं आया। अध्ययन में पाया गया कि किसी भी समस्या परिवार ने QAOA को सर्वश्रेष्ठ शास्त्रीय सॉल्वर और पेनल्टी (penalty) की तुलना में बेहतर अंतिम ADMM परिणाम नहीं दिया। शोधकर्ताओं ने गणना की कि समान समस्या आकार के लिए, क्वांटम दृष्टिकोण को टैबू सर्च नामक शास्त्रीय विधि की तुलना में सेकंडों में लगभग पचास गुना अधिक समय लगा। इसके अलावा, क्वांटम पद्धति का प्रदर्शन शास्त्रीय पद्धतियों की तरह अच्छी तरह से स्केल नहीं हुआ; जैसे-जैसे समस्याएँ बड़ी होती गईं, क्वांटम सॉल्वर का लाभ प्रयासों की संख्या में गायब हो गया, और वह सेमीडेफिनेट प्रोग्रामिंग पर आधारित एक शास्त्रीय तकनीक से पीछे रह गया।
अध्ययन ने यह भी उजागर किया कि डिकम्पोज़िशन विधि स्वयं कैसे काम करती है, इसमें एक सूक्ष्म लेकिन महत्वपूर्ण दोष है। शोधकर्ताओं ने पाया कि कुछ प्रकार की समस्याओं के लिए, टुकड़ों को फिर से जोड़ने का तरीका 'पेनल्टी' नामक एक पैरामीटर पर बहुत अधिक निर्भर करता है। जब इस पेनल्टी को एक विशिष्ट मान पर सेट किया गया, तो डिकम्पोज़िशन विधि ने अनिवार्य रूप से पूरी समस्या को सीधे हल कर दिया, जिससे उप-सॉल्वर की गुणवत्ता अप्रासंगिक हो गई। लेकिन जब पेनल्टी अधिक थी, तो विधि कभी-कभी एक उप-इष्टतम (sub-optimal) समाधान पर अटक जाती थी, और बेहतर समाधान मौजूद होने पर भी आगे बढ़ने से इनकार कर देती थी। इन मामलों में, क्वांटम सॉल्वर की "नॉइजी" (noisy) प्रकृति, जो अपने उत्तरों को बदलती रहती थी, वास्तव में सिस्टम को इन जालों से बाहर निकलने और एक बेहतर समग्र समाधान खोजने में मदद करती थी। इसने सुझाव दिया कि क्वांटम सॉल्वर की सफलता हमेशा उसके क्वांटम स्वभाव के कारण नहीं थी, बल्कि कभी-कभी इसलिए थी क्योंकि वह एक रैंडम सर्च की तरह व्यवहार कर रहा था, जो कठिन अनुकूलन परिदृश्यों में स्थानीय जाल से बचने का एक ज्ञात तरीका है।
अंततः, शोध पत्र यह निष्कर्ष निकालता है कि जबकि क्वांटम एल्गोरिदम उच्च सटीकता के साथ विशिष्ट उप-समस्याओं को हल करने में आशाजनक दिखते हैं, उन्होंने अभी तक पूरे सिस्टम पर विचार किए जाने पर सर्वश्रेष्ठ शास्त्रीय तरीकों पर कोई स्पष्ट लाभ प्रदर्शित नहीं किया है। क्वांटम सॉल्वर ने वह अंतिम परिणाम प्रदान नहीं किया जो सर्वश्रेष्ठ शास्त्रीय सॉल्वर सही सेटिंग्स के साथ प्राप्त कर सकता था। यह अध्ययन इस बात पर प्रकाश डालता है कि इन हाइब्रिड सिस्टमों में क्वांटम कंप्यूटिंग को वास्तव में उपयोगी होने के लिए, इसे न केवल अच्छे उत्तर खोजने चाहिए, बल्कि शास्त्रीय विकल्पों की तुलना में कम समय में और बेहतर स्केलिंग के साथ ऐसा करना चाहिए। शोधकर्ताओं ने पाया कि जबकि क्वांटम दृष्टिकोण विशिष्ट स्थितियों में शास्त्रीय सॉल्वरों की सटीकता का मुकाबला कर सकता था, यह काफी धीमा था और उतनी कुशलता से स्केल नहीं हुआ। यह कार्य एक आवश्यक वास्तविकता की जाँच के रूप में कार्य करता है, जो दिखाता है कि क्वांटडम एडवांटेज का मार्ग केवल बेहतर क्वांटम हार्डवेयर बनाने के बारे में नहीं है, बल्कि यह भी है कि इन मशीनों का बड़े, शास्त्रीय ढाँचों के भीतर उपयोग कैसे किया जाता है।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।