Polynomial-Space Quantum Algorithms from Classical Branching: Colouring, Domination and Monotone Local Search

एक ऐसी दुनिया की कल्पना करें जहाँ एक जटिल पहेली को हल करने के लिए टुकड़ों के हर एक संभावित विन्यास (arrangement) की एक-एक करके जाँच करनी पड़ती है। नेटवर्क, मानचित्रों या शेड्यूलों से जुड़ी कई समस्याओं के लिए, विन्यासों की संख्या इतनी विशाल होती है कि सबसे तेज़ सुपरकंप्यूटर को भी उत्तर खोजने में ब्रह्मांड की आयु से अधिक समय लग जाएगा। यह एक्सपोनेंशियल-टाइम (घातांकीय समय) समस्याओं का क्षेत्र है, जहाँ कठिनाई इतनी तेज़ी से बढ़ती है कि पहेली में बस कुछ और आइटम जोड़ने मात्र से कार्य अचानक असंभव हो जाता है। दशकों से, कंप्यूटर वैज्ञानिकों ने स्वीकार कर लिया है कि इनमें से कुछ समस्याएँ कितनी भी चतुर विधि अपना ली जाए, उन्हें जल्दी हल करना बहुत कठिन है। हालाँकि, एक नया दृष्टिकोण इस परिदृश्य को बदल रहा है, जो यह दिखा रहा है कि कैसे क्वांटम कंप्यूटर, जो उप-परमाणु दुनिया के अजीब नियमों पर काम करते हैं, मेमोरी में हर एक पथ को संग्रहीत किए बिना, इन संभावनाओं के विशाल जंगलों में शास्त्रीय मशीनों की तुलना में बहुत तेज़ी से नेविगेट कर सकते हैं।

इस चुनौती का मूल आधार यह है कि समाधानों की खोज कैसे की जाती है। एक क्लासिकल कंप्यूटर में, समाधान खोजना अक्सर एक विशाल, शाखाओं वाले भूलभुलैया (maze) में चलने जैसा महसूस होता है। आप एक रास्ता चुनते हैं, एक बंद रास्ते (dead end) पर पहुँचते हैं, और फिर एक अलग मार्ग आज़माने के लिए पिछले चुनाव तक वापस जाने के लिए मजबूर होते हैं। यदि भूलभुलैया में अरबों शाखाएँ हैं, तो यह प्रक्रिया बहुत अधिक समय लेती है। क्वांटम कंप्यूटर इस भूलभुलैया के माध्यम से आगे बढ़ने का एक अलग तरीका प्रदान करते हैं। एक समय में एक पथ पर चलने के बजाय, वे एक साथ कई पथों का पता लगा सकते हैं, जो एक ऐसी तकनीक का उपयोग करती है जिससे वे सही निकास को बहुत तेज़ी से "महसूस" कर सकते हैं। नया शोध यह प्रदर्शित करता है कि समस्याओं के एक विशिष्ट और महत्वपूर्ण वर्ग के लिए—जिनमें मानचित्रों को रंगना (coloring maps), नेटवर्क में कुशल नोड्स के समूह खोजना, या किसी संरचना को ठीक करने के लिए ग्राफ के विशिष्ट हिस्सों को हटाना शामिल है—यह क्वांटेंट स्पीडअप (quantum speedup) बहुत सीमित मेमोरी के साथ भी प्राप्त किया जा सकता है। शोधकर्ताओं ने ऐसे एल्गोरिदम बनाए हैं जो 'पॉलीनोमियल स्पेस' (polynomial space) में चलते हैं, जिसका अर्थ है कि उन्हें अपनी खोज का पूरा इतिहास संग्रहीत करने की आवश्यकता नहीं है, जो व्यावहारिक क्वांटम उपकरणों के लिए एक महत्वपूर्ण बाधा है।

यह शोध तीन मुख्य प्रकार की समस्याओं पर केंद्रित है जो कंप्यूटर विज्ञान और गणित में बार-बार आती हैं। पहला है ग्राफ कलरिंग, जो यह पूछता है कि क्या एक मानचित्र को सीमित रंगों के साथ इस तरह रंगा जा सकता है कि कोई भी दो छूते हुए क्षेत्र एक ही रंग के न हों। दूसरा डोमिनेशन (domination) समस्याओं से संबंधित है, जो यह पूछते हैं कि नेटवर्क में बिंदुओं का सबसे छोटा समूह कौन सा है जो अन्य प्रत्येक बिंदु की "निगरानी" कर सकता है या उनसे जुड़ सकता है। तीसरा वर्ग उन समस्याओं को शामिल करता है जहाँ आपको चक्रों (cycles) को तोड़ने या संरचनात्मक मुद्दों को ठीक करने के लिए कुछ विशिष्ट तत्वों को हटाना होता है, जैसे कि नेटवर्क में सभी लूप्स को समाप्त करने के लिए न्यूनतम कितने वर्टिसिस (शीर्षों) को हटाना होगा। प्रत्येक के लिए, शोधकर्ताओं ने सर्वोत्तम ज्ञात क्लासिकल एल्गोरिदम को लिया, जो पहले से ही काफी तेज़ हैं लेकिन फिर भी एक्सपोनेंशियल समय की आवश्यकता रखते हैं, और उन्हें क्वांटम कंप्यूटरों के लिए अनुकूलित किया। उन्होंने ऐसा इसलिए किया क्योंकि उन्होंने सिद्ध किया कि इन क्लासिकल एल्गोरिदम का चरण-दर-चरण तर्क एक विशिष्ट प्रकार की वृक्ष संरचना (tree structure) बनाता है। यह संरचना क्वांटम कंप्यूटर को समाधान खोजने के लिए लगभग उस समय के वर्गमूल (square root) में "क्वांटम वॉक" का उपयोग करने की अनुमति देती है, जो एक क्लासिकल कंप्यूटर को चाहिए होता।

परिणाम इन समस्याओं को हल करने के लिए आवश्यक समय में एक महत्वपूर्ण कमी लाते हैं। क्लासिक फोर-कलरिंग समस्या के लिए, नया क्वांटम एल्गोरिदम वर्टिसिस की संख्या के आधार पर 1.3032 की घात (power) के समान समय में समाधान पा सकता है। यह पिछले सर्वश्रेष्ठ क्वांटम अनुमान 1.3231 की तुलना में एक सार्थक सुधार है। अधिक रंगों वाली समस्याओं के लिए, जैसे कि पाँच या अठारह तक, नया तरीका लगातार पुराने सीमाओं को मात देता है, जिसमें रंगों की संख्या बढ़ने के साथ आवश्यक समय बहुत धीमी गति से बढ़ता है। डोमिनेशन समस्याओं के लिए, सुधार और भी आश्चर्यजनक हैं। डोमिनेटिंग सेट खोजने के लिए लगने वाला समय लगभग 1.4969 से घटकर 1.2235 रह जाता है, और इंडिपेंडेंट डोमिनेटिंग सेट के लिए यह 1.1583 तक गिर जाता है। ये संख्याएँ अमूर्त लग सकती हैं, लेकिन एक्सपोनेंशियल ग्रोथ की दुनिया में, आधार संख्या में एक छोटी सी कमी बड़े नेटवर्क के लिए वास्तविक कंप्यूटिंग समय की भारी बचत में बदल जाती है।

शोधकर्ताओं ने 'मोनोटोन लोकल सर्च' (monotone local search) नामक एक तकनीक पर भी इस तर्क को लागू किया है, जिसका उपयोग उन समस्याओं के लिए किया जाता है जहाँ आप एक आंशिक समाधान से शुरू करते हैं और उसे पूर्ण समाधान तक विस्तारित करने का प्रयास करते हैं। इसे क्वांटम सर्च के साथ जोड़कर, उन्होंने एक नई विधि बनाई है जो ग्राफ में सभी चक्रों को तोड़ने के लिए न्यूनतम वर्टिसिस को हटाने जैसी समस्याओं को हल करती है। इस विशिष्ट समस्या के लिए, नया क्वांटम समय वर्टिसिस की संख्या के आधार पर लगभग 1.3081 की घात है, जो इस दृष्टिकोण के लिए ज्ञात पहला क्वांटम बाउंड (सीमा) है, क्योंकि इससे पहले किसी भी क्वांटम मोनोटोन लोकल सर्च का उल्लेख नहीं किया गया था। शायद सबसे दिलचस्प बात यह है कि टीम ने दिखाया कि यह दृष्टिकोण न केवल सटीक समाधान खोजने के लिए, बल्कि "पर्याप्त अच्छे" सन्निकटन (approximations) खोजने के लिए भी काम करता है। उदाहरण के लिए, उन्होंने वर्टेक्स कवर समस्या के लिए एक ऐसा समाधान खोजने का तरीका प्रदर्शित किया जो सटीक उत्तर से केवल 10 प्रतिशत बड़ा है, लेकिन इसे वर्टिसिस की संख्या के आधार पर 1.0555 की घात के समान समय में पाया जा सकता है। यह सटीक समाधान खोजने की तुलना में तेज़ है, जो वास्तविक दुनिया के अनुप्रयोगों के लिए एक व्यावहारिक समझौता (trade-off) प्रदान करता है जहाँ पूर्ण समाधान के बजाय एक निकट-पूर्ण उत्तर ही पर्याप्त होता है।

मेमोरी पर सख्त सीमा इस कार्य का एक महत्वपूर्ण पहलू है। एल्गोरिदम को पॉलीनोमियल स्पेस के साथ चलाने के लिए डिज़ाइन किया गया है, जिसका अर्थ है कि जैसे-जैसे समस्या बड़ी होती है, उन्हें आवश्यक मेमोरी की मात्रा एक प्रबंधनीय दर से बढ़ती है। यह एक अत्यंत महत्वपूर्ण बाधा है क्योंकि वर्तमान और निकट भविष्य के क्वांटम कंप्यूटरों में उस विशाल मेमोरी क्षमता की कमी होगी जो अन्य सैद्धांतिक क्वांटम एल्गोरिदमों के लिए आवश्यक है जो "क्वांटम रैंडम एक्सेस मेमोरी" पर निर्भर करते हैं। इस आवश्यकता से बचकर, शोधकर्ताओं ने उस हार्डवेयर के लिए एक अधिक यथार्थवादी मार्ग बनाया है जो वास्तव में अस्तित्व में होगा। उन्होंने अपने परिणामों को गणितीय प्रमाणों और कंप्यूटर सिमुलेशन के संयोजन का उपयोग करके सत्यापित किया, यह जाँचते हुए कि एल्गोरिदम रैंडम ग्राफ पर सही ढंग से व्यवहार करते हैं और समय के अनुमान सटीक रहते हैं। यह कार्य इन समस्याओं को इस तरह से हल करने का दावा नहीं करता है कि वे किसी भी कंप्यूटर के लिए आसान हो जाएँ; बल्कि, इसने संभव की सीमाओं को आगे बढ़ाया है, यह दिखाते हुए कि क्वांटम मशीनें इन कठिन, एक्सपोनेंशियल-टाइम पहेलियों को दक्षता के एक ऐसे स्तर के साथ संभाल सकती हैं जिसे पहले से अधिक मेमोरी की आवश्यकता वाला माना जाता था।

इन निष्कर्षों के निहितार्थ विशिष्ट संख्याओं से परे हैं। यह शोध एक स्पष्ट ब्लूप्रिंट स्थापित करता है कि मौजूदा, अत्यधिक अनुकूलित क्लासिकल एल्गोरिदम को उनकी दक्षता खोए बिना या असंभव संसाधनों की मांग किए बिना क्वांटम क्षेत्र में कैसे अनुवादित किया जाए। यह सुझाव देता है कि कई कठिन समस्याओं के लिए, क्वांटम लाभ का मार्ग केवल नई गणितीय थ्योरी के आविष्कार में नहीं, बल्कि खोज स्थान (search space) को पार करने के तरीके को सावधानीपूर्वक पुन: इंजीनियर करने में निहित है। जैसे-जैसे क्वांटम हार्डवेयर विकसित होता जा रहा है, ये पॉलीनोमियल-स्पेस एल्गोरिदम एक ठोस लक्ष्य प्रदान करते हैं कि ये मशीनें क्या हासिल कर सकती हैं। यह कार्य पुष्टि करता है कि यह स्पीडअप वास्तविक और मापने योग्य है, जो एक ऐसे भविष्य की झलक देता है जहाँ वे समस्याएँ जो वर्तमान में क्लासिकल कंप्यूटरों के लिए दुर्गम हैं, हल की जा सकती हैं, बशर्ते हम इन विशिष्ट, मेमोरी-कुशल क्वांटम पथों को चलाने के लिए मशीनों का निर्माण कर सकें।