The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem

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

द दशकों से, शोधकर्ता एक विशिष्ट प्रकार की समरूपता समस्या पर ध्यान केंद्रित कर रहे हैं जिसे 'हिडन सबग्रुप प्रॉब्लम' (hidden subgroup problem) कहा जाता है। इस परिदृश्य में, कंप्यूटर को एक ऐसा फलन (function) दिया जाता है जो इनपुट के एक छिपे हुए समूह के लिए समान व्यवहार करता है, लेकिन बाकी सब के लिए अलग होता है। लक्ष्य उस छिपे हुए समूह को खोजना है। जबकि इसे सरल, व्यवस्थित समूहों के लिए हल किया जा चुका है, एक अधिक हालिया और चुनौतीपूर्ण संस्करण सामने आया है: 'स्टेट हिडन सबग्रुप प्रॉब्लम' (state hidden subgroup problem)। यहाँ, किसी गणितीय फलन के बजाय, कंप्यूटर को एक रहस्यमय क्वांटम अवस्था (quantum state) दी जाती है—कणों का एक नाजुक विन्यास। कार्य यह पता लगाना है कि कौन से ऑपरेशन्स इस अवस्था को अपरिवर्तित छोड़ देते हैं। इस कार्य की कठिनाई इस बात पर बहुत अधिक निर्भर करती है कि कंप्यूटर को उस अवस्था के साथ बातचीत करने की अनुमति कैसे दी जाती है। यदि कंप्यूटर केवल अवस्था की स्थिर प्रतियां प्राप्त कर सकता है, जैसे कि एक तस्वीर देखना, तो प्रक्रिया धीमी होती है। लेकिन यदि कंप्यूटर के पास उस मशीन तक पहुंच हो जिसने उस अवस्था का निर्माण किया है, जिससे वह निर्माण प्रक्रिया को आगे और पीछे चला सके, तो खेल के नियम पूरी तरह से बदल जाते हैं।

मैक्स प्लैंक इंस्टीट्यूट फॉर क्वांटम ऑप्टिक्स और फ्री यूनिवर्सिटी ऑफ बर्लिन के शोधकर्ताओं द्वारा किए गए एक नए अध्ययन ने अंततः इस प्रश्न को सुलझा लिया है कि इन विभिन्न स्थितियों के तहत इस समस्या को कितनी तेजी से हल किया जा सकता है। टीम ने सिद्ध किया कि पहुंच का तरीका केवल एक मामूली तकनीकी विवरण नहीं है; यह मौलिक रूप से समाधान की गति को निर्धारित करता है। उन्होंने प्रदर्शित किया कि यदि एक क्वांटम कंप्यूटर केवल अज्ञात अवस्था की प्रतियों को देख सकता है, तो उसे प्रतियों की संख्या उस 'गैप' (gap) के व्युत्क्रमानुपाती (inversely) बढ़नी चाहिए जो सही समरूपता और गलतों के बीच होता है। सरल शब्दों में, यदि संकेत धुंधला है, तो कंप्यूटर को इसे स्पष्ट रूप से सुनने के लिए बहुत सारी प्रतियों की आवश्यकता होगी। हालाँकि, यदि कंप्यूटर के पास 'प्रिपरेशन यूनिटरी' (preparation unitary)—वह वास्तविक सर्किट जो अवस्था का निर्माण करता है—तक पहुंच है, तो वह प्रक्रिया को उल्टा चला सकता है। अवस्था को सुसंगत रूप से (coherently) हेरफेर करने की यह क्षमता कंप्यूटर को 'एम्प्लीट्यूड एम्प्लीफिकेशन' (amplitude amplification) नामक तकनीक का उपयोग करने की अनुमति देती है, जो एक शक्तिशाली आवर्धक लेंस की तरह कार्य करता है। इस उपकरण के साथ, आवश्यक इंटरैक्शन की संख्या नाटकीय रूप से गिर जाती है, जिससे गति पिछले आवश्यकता के वर्गमूल (square root) के कारक से सुधर जाती है।

शोधकर्ताओं ने न केवल तेज़ तरीका नहीं खोजा; उन्होंने यह भी सिद्ध किया कि यह गति वास्तव में सर्वोत्तम संभव है। उन्होंने एक कठोर गणितीय तर्क बनाया जिससे पता चलता है कि कोई भी एल्गोरिदम, चाहे वह कितना भी चतुर क्यों न हो, इन सीमाओं को मात नहीं दे सकता। भले ही कंप्यूटर को प्रतियों पर सबसे जटिल माप करने की अनुमति दी जाए, या यदि उसे तैयारी मशीन के और भी शक्तिशाली संस्करणों तक पहुंच दी जाए, मौलिक बाधा बनी रहती है। यह अध्ययन स्थापित करता है कि 'कोहेरेंट कंट्रोल' (coherent control) के माध्यम से प्राप्त की गई द्विघातीय सुधार (quadratic improvement) एक विशिष्ट एल्गोरिदम का परिणाम नहीं है, बल्कि अवस्था के निर्माण पर नियंत्रण रखने का एक वास्तविक गुण है। यह खोज इन लर्निंग कार्यों में क्वांटम लाभ के सटीक स्रोत को स्पष्ट करती है, जो प्रक्रिया को उलटने और उसके आउटपुट को केवल देखने के बीच के अंतर को अलग करती है।

इस कार्य के निहितार्थ अमूर्त सिद्धांत से परे आधुनिक भौतिकी के केंद्र तक विस्तृत हैं। जटिल सामग्रियों को समझने और क्वांटम उपकरणों को सत्यापित करने के लिए क्वांटम अवस्थाओं में छिपी समरूपताओं को कुशलतापूर्वक पहचानना महत्वपूर्ण है। उदाहरण के लिए, नए एल्गोरिदम का उपयोग यह पता लगाने के लिए किया जा सकता है कि एक बड़ा क्वांटम सिस्टम स्वतंत्र, असंबद्ध भागों में कहाँ टूट जाता है, जो यह समझने के लिए एक महत्वपूर्ण कार्य है कि क्वांटम सूचना कैसे फैलती है। वे 'स्टेबलाइजर ग्रुप्स' (stabilizer groups) की पहचान करने के तेज़ तरीके भी प्रदान करते हैं जो क्वांटम सूचना को त्रुटियों से बचाते हैं, जो विश्वसनीय क्वांटम कंप्यूटर बनाने का एक आधार स्तंभ है। इसके अलावा, ये विधियाँ कई-शरीर प्रणालियों (many-body systems) में छिपी अनुवाद संबंधी समरूपताओं (translation symmetries) का पता लगा सकती हैं, जिससे भौतिकविदों को जटिल क्वांटम पदार्थ में अंतर्निहित व्यवस्था को मैप करने में मदद मिलती है। प्रत्येक अनुप्रयोग में, अध्ययन दिखाता है कि यदि तैयारी सर्किट उपलब्ध है, तो छिपी संरचना को खोजने के लिए आवश्यक समय काफी कम हो जाता है, जिससे पहले अगम्य समस्याएं सुलभ हो जाती हैं।

इस खोज का मार्ग दो प्रतिस्पर्धी एक्सेस मॉडलों के बीच एक सावधानीपूर्वक संतुलन बनाकर प्रशस्त हुआ। पहले मॉडल, "सैंपल" (sample) मॉडल में, एल्गोरिदम को एक निष्क्रिय पर्यवेक्षक माना जाता है, जिसे समान क्वांटम अवस्थाओं का ढेर थमाया जाता है। शोधकर्ताओं ने दिखाया कि इस परिदृश्य में, छिपी समरूपता को खोजने के लिए आवश्यक अवस्थाओं की संख्या 'प्रॉमिस गैप' (promise gap) के व्युत्क्रम द्वारा निर्धारित होती है। यदि गैप छोटा है, जिसका अर्थ है कि सही समरूपता और गलतों के बीच का अंतर सूक्ष्म है, तो एल्गोरिदम को उन्हें पहचानने के लिए बड़ी संख्या में नमूनों की आवश्यकता होगी। टीम ने सिद्ध किया कि सबसे उन्नत सामूहिक मापों (collective measurements) के साथ भी, जहाँ सभी प्रतियों को एक एकल, जटिल ऑपरेशन में एक साथ मापा जाता है, इस सीमा को तोड़ा नहीं जा सकता। जानकारी बस प्रतियों में इतनी नहीं होती कि उसे इससे तेज़ निकाला जा सके।

इसके विपरीत, दूसरा मॉडल, "क्वेरी" (query) मॉडल, एल्गोरिदम को सक्रिय नियंत्रण प्रदान करता है। यहाँ, कंप्यूटर एक यूनिटरी ऑपरेटर को कॉल कर सकता है जो अवस्था को तैयार करता है और उसका व्युत्क्रम (inverse), जो तैयारी को पूर्ववत करता है। यह पहुंच एल्गोरिदम को अवस्था के साथ हस्तक्षेप करने की अनुमति देती है, प्रभावी रूप से सही उत्तर को बढ़ाती है और गलत उत्तरों को रद्द करती है। शोधकर्ताओं ने एक नया एल्गोरिदम विकसित किया जो इस क्षमता का उपयोग करके गैप के व्युत्क्रम वर्गमूल (inverse square root) के पैमाने पर छिपी समरूपता को खोजने के लिए करता है। यह आवश्यक संसाधनों में भारी कमी को दर्शाता है। यह सुनिश्चित करने के लिए कि यह केवल एक भाग्यशाली सफलता नहीं थी, उन्होंने 'साइमन के प्रॉब्लम' (Simon's problem) के रूप में ज्ञात एक क्लासिक चुनौती पर आधारित कठिन समस्याओं का एक परिवार बनाया। इस समस्या को पैडिंग देकर और इसके 'फ्रैक्शनल ऑरेकल' (fractional oracle) का परिचय देकर, उन्होंने दिखाया कि क्वेरी मॉडल के लिए निचली सीमा (lower bound) उनकी ऊपरी सीमा (upper bound) से बिल्कुल मेल खाती है। यह सटीक मिलान सिद्ध करता है कि एल्गोरिदम इष्टतम है और गति में सुधार अवस्था की तैयारी को पीछे चलाने की क्षमता का स्वाभाविक परिणाम है।

इस कार्य के सबसे महत्वपूर्ण योगदानों में से एक छिपे हुए सबग्रुप के आकार के बारे में लंबे समय से चली आ रही अनिश्चितता का समाधान करना है। पिछले एल्गोरिदम अक्सर एक ऐसी 'वर्स्ट-केस' (worst-case) स्थिति मान लेते थे जहाँ छिपा हुआ समूह बहुत छोटा होता था, जिससे संसाधन अनुमान पूरे समूह के कुल आकार पर निर्भर करते थे। नया अध्ययन एक 'एडेप्टिव स्ट्रैटेजी' (adaptive strategy) पेश करता है जो एल्गोरिदम को पर्याप्त जानकारी मिलते ही रुकने की अनुमति देता है, चाहे समूह का आकार कुछ भी हो। इसका अर्थ है कि जटिलता अब 'कोटिएंट' (quotient) के आकार पर निर्भर करती है, या कुल समूह और छिपे हुए सबग्रुप के अनुपात पर। यदि छिपा हुआ सबग्रुप बड़ा है, तो समस्या बहुत आसान हो जाती है, और एल्गोरिदम इसे कम संसाधनों की आवश्यकता के साथ दर्शाता है। यह एडेप्टिव स्टॉपिंग नियम बिना यह जाने कि छिपे हुए समूह का आकार क्या है, प्रभावी ढंग से काम करता है, जिससे समाधान कुशल और व्यावहारिक बनता है।

अध्ययन 'कंट्रोल्ड क्वेरीज' (controlled queries) और 'कंजुगेट एक्सेस' (conjugate access) जैसी उन्नत क्वांटम विशेषताओं की भूमिका को भी संबोधित करता है। कुछ सैद्धांतिक मॉडलों में, किसी ऑपरेटर के कॉम्प्लेक्स कंजुगेट तक पहुंच होना या एक क्वांटम बिट के साथ ऑरेकल को नियंत्रित करने की क्षमता होना संभावित रूप से और अधिक लाभ दे सकता है। शोधकर्ताओं ने इन संभावनाओं का परीक्षण किया और पाया कि उनके द्वारा निर्मित वर्स्ट-केस परिदृश्यों के लिए, इन अतिरिक्त शक्तियों ने कोई अतिरिक्त लाभ नहीं दिया। तैयारी यूनिटरी के व्युत्क्रम तक पहुँच से प्राप्त द्विघातीय गति (quadratic speedup) अधिकतम संभव लाभ था। यह परिणाम महत्वपूर्ण है क्योंकि यह सुझाव देता है कि लर्निंग कार्यों के एक व्यापक वर्ग के लिए, अवस्था की तैयारी को उलटने की क्षमता ही मुख्य घटक है, और अधिक जटिल नियंत्रण तंत्र जोड़ने से भविष्य में कोई अतिरिक्त 'एसिम्टोटिक' (asymptotic) सुधार नहीं मिलता है।

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

अंततः, यह कार्य 'एबेलियन स्टेट हिडन सबग्रुप प्रॉब्लम' (abelian state hidden subgroup problem) के परिदृश्य का एक निश्चित मानचित्र प्रदान करता है। यह निष्क्रिय अवलोकन और सक्रिय नियंत्रण के बीच एक स्पष्ट रेखा खींचता है। शोधकर्ताओं ने दिखाया है कि इस क्षेत्र में क्वांटम एल्गोरिदम की शक्ति एक अस्पष्ट क्षमता नहीं है, बल्कि एक सटीक रूप से मापने योग्य लाभ है जो अवस्था की तैयारी को सुसंगत रूप से हेरफेर करने की क्षमता से उत्पन्न होता है। यह सिद्ध करके कि उनके एल्गोरिदम इष्टतम हैं और कोई भी बेहतर विधि मौजूद नहीं है, उन्होंने इस मौलिक समस्या की जटिलता पर विराम लगा दिया है। परिणाम भविष्य के अनुसंधान के लिए एक ठोस आधार प्रदान करते हैं, जो ऐसे क्वांटम एल्गोरिदम के विकास का मार्गदर्शन करते हैं जो भौतिकी और कंप्यूटर विज्ञान की सबसे चुनौतीपूर्ण समरूपता समस्याओं को अधिकतम संभव दक्षता के साथ हल कर सकें।