Proven optimality for LABS with quantum-classical branch and bound
यह शोध पत्र एक क्वांटम-क्लासिकल ब्रांच एंड बाउंड एल्गोरिदम पेश करता है जो लो ऑटोकोरिलेशन बाइनरी सीक्वेंस (LABS) अनुकूलन समस्या को हल करने के लिए फिक्स्ड-एंगल QAOA सैंपलिंग का लाभ उठाता है, जो क्वांटम स्पीडअप पर निर्भर किए बिना 30 तक की अनुक्रम लंबाई के लिए वैश्विक इष्टतमता को सफलतापूर्वक सिद्ध करता है और प्रमाणित निचले स्तर के बाउंड तथा अभिसरण मेट्रिक्स प्रदान करता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखक ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
आधुनिक तकनीक की छिपी हुई वास्तुकला में, गणितीय पहेलियों का एक वर्ग मौजूद है जिसे 'लो ऑटोकोरिलेशन बाइनरी सीक्वेंस' (low autocorrelation binary sequences) के रूप में जाना जाता है। ये केवल अमूर्त जिज्ञासाएँ नहीं हैं, बल्कि वे मौलिक निर्माण खंड हैं जिनसे हम संचार करते हैं और दुनिया को महसूस करते हैं। जब एक रडार प्रणाली किसी विमान का पता लगाने के लिए एक पल्स भेजती है, या जब एक डिजिटल सिग्नल मोबाइल फोन कनेक्शन को सिंक्रोनाइज़ करता है, तो वह धनात्मक और ऋणात्मक मानों के एक विशिष्ट पैटर्न पर निर्भर करता है। इस पैटर्न की गुणवत्ता यह निर्धारित करती है कि सिस्टम एक स्पष्ट लक्ष्य देखेगा या गलत प्रतिध्वनियों का एक भ्रमित करने वाला ढेर। लक्ष्य एक ऐसा अनुक्रम खोजने का है जहाँ आंतरिक ओवरलैप, या सहसंबंध (correlations), यथासंभव कम हों। यह एक अत्यंत कठिन समस्या है, जो अरबों ऊबड़-खाबड़ सुइयों के ढेर में से एक अकेली, बिल्कुल चिकनी सुई खोजने के समान है। दशकों से, कंप्यूटर यह सिद्ध करने के लिए संघर्ष कर रहे हैं कि उन्होंने सबसे अच्छा पैटर्न खोज लिया है, और अक्सर वे बिना यह जाने कि क्या कोई बेहतर विकल्प मौजूद है, बहुत अच्छे अनुमानों पर ही संतोष कर लेते हैं।
एक शोधकर्ता, एंड्रास ज़ेगेल (András Czégel) ने अब एक तरीका प्रदर्शित किया है जिससे इस समस्या को पूर्ण निश्चितता के साथ हल किया जा सकता है, जो शास्त्रीय कंप्यूटिंग और क्वांटम सैंपलिंग के मिश्रण का उपयोग करता है। यह कार्य यह दावा नहीं करता कि यह सर्वोत्तम पारंपरिक तरीकों से तेज़ है; वास्तव में, लेखक स्पष्ट रूप से कहता है कि इसमें कोई गति वृद्धि (speedup) नहीं है। इसके बजाय, उपलब्धि प्रमाण (proof) में निहित है। एक कठोर शास्त्रीय खोज ढांचे के भीतर एक क्वांटम एल्गोरिदम को समाहित करके, टीम ने लंबाई 2 से लंबाई 30 तक के अनुक्रमों के लिए इष्टतम समाधानों को सिद्ध किया। यह एक महत्वपूर्ण मील का पत्थर है क्योंकि इस समस्या पर पिछले क्वांटम प्रयासों में केवल अच्छे अनुक्रम मिल सकते थे, लेकिन वे कभी भी यह गारंटी नहीं दे सके कि वे सर्वश्रेष्ठ हैं, न ही वे यह माप सके कि कोई अनुमान पूर्णता से कितना दूर हो सकता है। यह विधि अनुकूलता का एक प्रमाण (certificate of optimality) प्रदान करती है—एक गणितीय गारंटी कि कोई बेहतर अनुक्रम मौजूद नहीं है—साथ ही यह भी बताती है कि खोज समय के साथ कैसे अभिसरित (converged) हुई।
इस पद्धति का मूल एक "ब्रांच एंड बाउंड" (branch and bound) रणनीति है, जो संभावनाओं को तलाशने का एक व्यवस्थित तरीका है जिसमें मृत अंत (dead ends) को काट दिया जाता है। एक बढ़ते हुए पेड़ की कल्पना करें जो हर दिशा में बढ़ रहा है, जहाँ प्रत्येक शाखा अनुक्रम में एक मान निर्धारित करने के निर्णय का प्रतिनिधित्व करती है। एक शास्त्रीय कंप्यूटर आमतौर पर इस पेड़ पर चलता है, सीमाओं (bounds) की जाँच करता है कि क्या कोई शाखा बेहतर समाधान की ओर ले जा सकती है। यदि कोई शाखा बहुत महंगी दिखती है, तो उसे काट दिया जाता है। ज़ेगेल का नवाचार एक फिक्स्ड-एंगल क्वांटम एल्गोरिदम (fixed-angle quantum algorithm) को इस शास्त्रीय पेड़ के भीतर रखने में था। प्रत्येक नोड पर जहाँ एक निर्णय लिया जाना होता है, क्वांटम सैंपलर संभावनाओं के परिदृश्य की एक त्वरित झलक लेता है। यह पूरे समस्या को हल नहीं करता है; यह केवल अब तक पाए गए सर्वश्रेष्ठ समाधान के लिए एक उम्मीदवार पेश करता है और यह सुझाव देता है कि किस पथ का अन्वेषण करना चाहिए। फिर शास्त्रीय कंप्यूटर इन सुझावों का उपयोग खोज को निर्देशित करने के लिए करता है, जबकि उसके अपने सख्त गणितीय नियम पेड़ को काटते हैं और अंतिम परिणाम को सत्यापित करते हैं।
इस हाइब्रिड दृष्टिकोण के परिणाम लंबाई 30 तक के अनुक्रमों पर मापे गए। इस सीमा में प्रत्येक लंबाई के लिए, एल्गोरिदम ने सफल रूप से इष्टतम ऊर्जा मान (optimal energy value) को सिद्ध किया, जिसका अर्थ है कि इसने पुष्टि की कि किसी अन्य अनुक्रम का वर्ग सहसंबंधों (squared correlations) का योग कम नहीं हो सकता। प्रक्रिया का परीक्षण विभिन्न सेटिंग्स के साथ किया गया था, जिसमें क्वांटम सैंपलर की गहराई 12 और एक उथली गहराई 1 शामिल थी। गहरे सेटिंग में, क्वांटम सैंपलर ने कई मामलों में तुरंत सबसे अच्छा समाधान ढूंढ लिया, जिससे शास्त्रीय भाग को यह सिद्ध करने पर ध्यान केंद्रित करने की अनुमति मिली कि कोई बेहतर समाधान मौजूद नहीं है। लंबे अनुक्रमों के लिए, विशेष रूप से लंबाई 27 और उससे ऊपर के लिए, शोधकर्ताओं ने पाया कि मुख्य समस्या इतनी बड़ी थी कि क्वांटम सैंपलर इसे सीधे संभाल नहीं सका, इसलिए उन्होंने सैंपलिंग से पहले समरूपता (symmetry) के आधार पर समस्या को छोटे, प्रबंधनीय टुकड़ों में विभाजित किया। इन जटिल मामलों में भी, सिस्टम ने अनुकूलता का एक प्रमाणित प्रमाण लौटाया।
अध्ययन ने सावधानीपूर्वक यह भी जांचा कि क्वांटम सैंपलर की सफलता में वास्तव में क्या योगदान था। यह पता चला कि सैंपलर का प्राथमिक मूल्य प्रक्रिया के शुरुआती चरण में ही सर्वश्रेष्ठ समाधान खोजने में था। एक बार जब सर्वश्रेष्ठ समाधान मिल गया, तो क्वांटम सैंपलर के सुझाव कि आगे किस पथ पर जाना चाहिए, हमेशा खोज में सुधार नहीं करते थे; कुछ मामलों में, एक सरल यादृच्छिक चयन (random choice) या एक निश्चित नियम उतना ही अच्छा या उससे भी बेहतर प्रदर्शन करता था। यह सुझाव देता है कि क्वांटम सैंपलर कोई जादुई छड़ी नहीं है जो पहेली को तुरंत हल कर देती है, बल्कि यह एक उपकरण है जो शास्त्रीय कंप्यूटर को लक्ष्य खोजने में तेज़ी से मदद करता है, जिससे कठोर प्रमाण तंत्र कार्यभार संभाल सके। शोधकर्ताओं ने शोर रहित (noiseless) कंप्यूटरों पर सिमुलेशन चलाया और यह भी मॉडल किया कि वास्तविक क्वांटम हार्डवेयर, जैसे कि IBM और क्वांटिनियम (Quantinuum) के उपकरणों पर यह प्रणाली कैसे व्यवहार करेगी। उन्होंने पाया कि हालांकि वर्तमान हार्डवेयर अभी तक बड़े कार्यों को उच्च निष्ठा (fidelity) के साथ संभालने के लिए पर्याप्त शक्तिशाली नहीं है, फिर भी यह विधि शोर (noise) के साथ भी वैध बनी रहती है, क्योंकि शास्त्रीय भाग शुद्धता का अंतिम प्रमाण प्रदान करता है।
यह कार्य क्वांटम एल्गोरिदम के मूल्यांकन के तरीके में एक बदलाव का प्रतिनिधित्व करता है। केवल एक अच्छा उत्तर जितनी जल्दी हो सके खोजने की दौड़ में भाग लेने के बजाय, यहाँ ध्यान एक सत्यापित, प्रमाणित उत्तर प्रदान करने पर है। शोधकर्ताओं ने संपूर्ण खोज प्रक्रिया को रिकॉर्ड किया, प्रत्येक क्षण में सर्वश्रेष्ठ समाधान और सैद्धांतिक निचली सीमा (theoretical lower bound) के बीच के अंतर को मापा। यह "प्राइमल-ड्यूल इंटीग्रल" (primal-dual integral) एल्गोरिदम की दक्षता के लिए एक स्कोरकार्ड के रूप में कार्य करता है, जो सटीक रूप से दिखाता है कि इसने संभावनाओं को कितनी तेज़ी से सीमित किया। अध्ययन पुष्टि करता है कि क्वांटम सैंपलिंग को सटीक एल्गोरिदम में एकीकृत किया जा सकता है ताकि उन समस्याओं के लिए अनुकूलता के प्रमाण प्रदान किए जा सकें जो पहले केवल ह्यूरिस्टिक्स (heuristics) या उन शास्त्रीय तरीकों द्वारा हल की जा सकती थीं जिन्हें क्वांटम माध्यमों द्वारा सत्यापित नहीं किया जा सकता था। हालाँकि हल की गई समस्याओं की सीमा वर्तमान में लंबाई 30 तक सीमित है, जो सर्वोत्तम शास्त्रीय विधियों द्वारा प्राप्त 66 से बहुत कम है, फिर भी अवधारणा का प्रमाण स्पष्ट है: एक क्वांटम एल्गोरिदम अब केवल एक अनुमान नहीं, बल्कि सत्य का प्रमाण (certificate of truth) दे सकता है।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।