A quantum lower bound for path finding in welded trees

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

इस प्रश्न ने वैज्ञानिकों को 'वेल्डेड ट्री' (welded tree) नामक एक विशिष्ट पहेली की ओर अग्रसर किया। कल्पना कीजिए कि दो ऊंचे, पूरी तरह से सममित पेड़ उल्टे उग रहे हैं, उनकी शाखाएं जमीन की ओर बढ़ रही हैं। बिल्कुल नीचे, बाएं पेड़ की पत्तियां दाएं पेड़ की पत्तियों से पुलों के एक यादृच्छिक, उलझे हुए जाल द्वारा जुड़ी हुई हैं। लक्ष्य सरल है: बाएं पेड़ के शीर्ष से शुरू करें और दाएं पेड़ के शीर्ष को खोजें। एक क्लासिकल कंप्यूटर, इस भूलभुलैया में रास्ता खोजने की कोशिश करते समय, संभावनाओं की तेजी से बढ़ती संख्या की जांच करने के लिए मजबूर होगा, और अंततः पेड़ों के ऊंचे होने पर हार मान लेगा। हालाँकि, एक क्वांटम कंप्यूटर पूरे ढांचे के माध्यम से एक संभाव्यता की लहर (wave of probability) भेज सकता है, और पेड़ों की ऊंचाई के साथ रैखिक (linearly) रूप से बढ़ते समय में निकास खोज सकता है। यह एक ज्ञात परिणाम था, क्वांटम गति का एक प्रतिष्ठित उदाहरण। लेकिन एक अनसुलझा रहस्य बना हुआ था: जबकि क्वांटम लहर निकास को खोज सकती थी, क्या वह उस विशिष्ट मार्ग को भी रिकॉर्ड कर सकती थी जिस पर उसने यात्रा की थी? यदि कंप्यूटर प्रत्येक चरण का लॉग रखने की कोशिश करता ताकि पथ को पुनर्गठित किया जा सके, तो नाजुक क्वांटम लहर ढह जाएगी, जिससे गति का लाभ समाप्त हो जाएगा और कंप्यूटर क्लासिकल मशीन से बेहतर नहीं रह जाएगा। वर्षों तक, यह एक खुला प्रश्न था कि क्या कोई चतुर क्वांटम एल्गोरिदम इस सीमा को किसी तरह पार कर सकता है और अपनी शक्ति खोए बिना पथ खोज सकता है।

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

शोधकर्ताओं ने पाया कि एक सफल पथ आउटपुट करने के लिए क्वांटम कंप्यूटर को क्वेरी की एक ऐसी संख्या की आवश्यकता होगी जो पेड़ों के आकार के साथ तेजी से (exponentially) बढ़ती है। यह वही घातांकीय प्रयास है जो एक क्लासical कंप्यूटर द्वारा आवश्यक होता है, जिसका अर्थ है कि क्वांटम स्पीडअप लुप्त हो जाता है क्षण भर में जब एल्गोरिदम को पथ प्रकट करने के लिए मजबूर किया जाता है। यह प्रमाण यह दिखाने पर आधारित है कि क्वांटम अवस्था, कई क्वेरी के बाद भी, अत्यधिक संभावना के साथ एक "पथ-रहित" (path-free) स्थिति में रहती है। कंप्यूटर कई अलग-अलग संभावित मार्गों के सुपरपोजिशन में अस्तित्व में हो सकता है, लेकिन ये मार्ग कभी भी एक एकल, रिकॉर्ड करने योग्य पगडंडी में विलीन नहीं होते। यदि एल्गोरिदम पथ को अस्तित्व में लाने के लिए मजबूर करने का प्रयास करता है, तो यह प्रभावी रूप से उन हस्तक्षेप पैटर्न (interference patterns) को नष्ट कर देता है जो क्वांटम खोज को तेज़ बनाते हैं। परिणाम एक स्पष्ट अलगाव है: एक क्वांटम मशीन नेविगेशन समस्या को किसी भी क्लासिकल मशीन की तुलना में घातांकीय रूप से तेज़ी से हल कर सकती है, फिर भी यह प्रमाणित रूप से असंभव है कि वही मशीन आपको बताएगी कि उसने यह कैसे किया।

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

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

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