Improved quantum volume estimation with transducers and amortized quantum walks

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

हाल ही में, शोधकर्ताओं की एक टीम ने इस क्लासिक समस्या पर क्वांटम कंप्यूटिंग के सिद्धांतों को लागू करके एक महत्वपूर्ण प्रगति की है। उन्होंने इस जटिल आकृतियों के आयतन का अनुमान लगाने के लिए एक नई विधि विकसित की है जो सर्वोत्तम शास्त्रीय (classical) विधियों की तुलना में बहुत कम चरणों का उपयोग करती है। उनका कार्य केवल एक मौजूदा सूत्र में सुधार नहीं है; यह मौलिक रूप से इस बात पर पुनर्विचार करता है कि एक कंप्यूटर उच्च-आयामी स्थान के माध्यम से अपने आकार को खोजने के लिए कैसे चल सकता है। "क्वांटम वॉक" नामक तकनीक को "ट्रांसड्यूसर" (transducer) के एक नए तरीके के साथ जोड़कर, उन्होंने एक ऐसा एल्गोरिदम बनाया है जो पहले से ज्ञात किसी भी विधि की तुलना में प्रमाणित रूप से तेज़ है। परिणाम एक जटिल ज्यामिति की समस्या को हल करने के लिए एक अधिक कुशल मार्ग है, जो लंबे समय से कम्प्यूटेशनल ज्योमेट्री में एक बाधा बनी हुई थी।

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

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

इस ढांचे का उपयोग करते हुए, टीम ने स्पीडी वॉक का एक क्वांटम संस्करण बनाया। उन्होंने एक विशिष्ट प्रकार का ट्रांसड्यूसर डिजाइन किया जो वॉक के क्वांटत अवस्था (quantum state) को उसके स्थिर वितरण (stationary distribution)—वह अवस्था जहाँ वॉक एक स्थिर पैटर्न में सेट हो जाता है—के चारों ओर प्रतिबिंबित कर सकता है। यह प्रतिबिंब क्वांटम वॉक का मुख्य इंजन है। आकार की ज्यामिति और वॉक के गुणों का सावधानीपूर्वक विश्लेषण करके, उन्होंने सिद्ध किया कि इन प्रतिबिंबों की लागत को एमोर्टाइज किया जा सकता है। इसका मतलब था कि भले ही क्वांटम वॉक में कुछ चरण सैद्धांतिक रूप से महंगे थे, फिर भी प्रति चरण औसत लागत कम रही। उन्होंने इसे अन्य क्वांटम तकनीकों के साथ जोड़ा, जैसे कि "क्वांटम एनीलिंग" (quantum annealing), जो सिस्टम को एक अवस्था से दूसरी अवस्था में सुचारू रूप से जाने में मदद करती है, और "क्वांटम मीन एस्टिमेशन" (quantum mean estimation), जो मानों के सटीक औसत की अनुमति देता है। परिणाम एक पूर्ण एल्गोरिदम है जो उच्च-आयामी स्थान में एक उत्तल पिंड (convex body) के आयतन का अनुमान लगाता है।

इस नए एल्गोरिदम का प्रदर्शन अत्याधुनिक (state of the art) तकनीकों से काफी बेहतर है। सबसे अच्छे शास्त्रीय रैंडमाइज्ड एल्गोरिदम को चरणों की एक संख्या की आवश्यकता होती है जो अंतरिक्ष के आयाम की लगभग 3.5 की घात (power) के साथ बढ़ती है, साथ ही वांछित सटीकता से संबंधित एक पद भी होता है। पिछला सर्वश्रेष्ठ क्वांटम एल्गोरिदम इसमें थोड़ा सुधार करता था, लेकिन इस शोध पत्र में प्रस्तुत नई विधि जटिलता को काफी कम कर देती है। विशेष रूप से, नया क्वांटम एल्गोरिदम आयाम की घात 3.5 के साथ बढ़ता है, लेकिन सटीकता से संबंधित पद 2.25 की घात से घटकर 1.75 रह जाता है। व्यावहारिक शब्दों में, इसका अर्थ है कि सटीकता के एक निश्चित स्तर के लिए, क्वांटम कंप्यूटर पिछले किसी भी तरीके की तुलना में आकार के बहुत कम प्रश्नों (queries) के साथ समस्या को हल कर सकता है। शोधकर्ताओं ने केवल यह विचार प्रस्तावित नहीं किया; उन्होंने एक कठोर गणितीय प्रमाण प्रदान किया कि उनका एल्गोरिदम काम करता है और लागत विश्लेषण सही है। उन्होंने इस निरंतर प्रकृति (continuous nature) को संभालने के व्यावहारिक मुद्दे को भी संबोधित किया कि कैसे वॉक के आवश्यक गुणों को खोए बिना समस्या को विविक्त (discretize) किया जा सकता है।

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

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