The Kikuchi Hierarchy is Sharp for $k$XOR

कल्पना कीजिए कि आप एक जासूस हैं जो एक विशाल, अराजक शोर मशीन के भीतर छिपे रहस्य को सुलझाने की कोशिश कर रहे हैं। यह मशीन लाखों यादृच्छिक (random) सुराग उगलती है, लेकिन उस स्टेटिक (static) के बहुत गहरे भीतर एक गुप्त संदेश छिपा है—एक विशिष्ट पैटर्न या "सिग्नल" जिसे किसी ने वहां प्लांट किया है। सबसे बड़ा सवाल कंप्यूटर विज्ञान और गणित के इस कोने में यह है: आप कितना शोर झेल सकते हैं इससे पहले कि वह रहस्य ढूँढना असंभव हो जाए? कभी-कभी सिग्नल इतना कमजोर होता है कि उसे खोजने के लिए आपको एक मिलियन वर्षों तक चलने वाले सुपरकंप्यूटर की आवश्यकता होती है, भले ही एक इंसान पेंसिल लेकर इसे सिद्धांत रूप रूप में हल कर सकता हो यदि उसके पास अनंत समय होता। सिद्धांत में जो संभव है और वास्तविकता में जो व्यावहारिक है, उनके बीच के इस अंतर को "सांख्यिकीय-संगणकीय अंतराल" (statistical-computational gap) कहा जाता है। वैज्ञानिकों को लंबे समय से संदेह था कि एक सहज ट्रेड-ऑफ मौजूद है: यदि आप एक एल्गोरिदम को अधिक समय देते हैं, तो वह कमजोर और कमजोर होते सिग्नलों को खोजने में सक्षम होना चाहिए। लेकिन "kXOR" नामक एक विशिष्ट प्रकार की पहेली के लिए (जहाँ सुराग इस बारे में होते हैं कि कुछ संख्याओं का योग सम है या विषम), उन स्मार्ट, धीमे एल्गोरिदम को बनाने के हर प्रयास में एक दोष था। वे हमेशा थोड़े बहुत अनाड़ी थे, उन्हें सिद्धांत के अनुसार आवश्यक डेटा से थोड़ा अधिक डेटा की आवश्यकता थी, और उस मामूली सी अनाड़ीपन ने आवश्यक समय को असंभव स्तर तक बढ़ा दिया।

यह पेपर उस अनाड़ीपन को ठीक करने के बारे में है। लेखकों, अलेक्जेंडर श्मिडहुबर और मैथ्यू बी. हेस्टिंग्स ने "किकुची पदानुक्रम" (Kikuchi hierarchy) नामक एक जासूसी उपकरण का एक नया संस्करण बनाया है। पुराने उपकरणों को कल्पना करें कि वे तूफान में फुसफुसाहट सुनने की कोशिश कर रहे हैं; वे केवल वॉल्यूम बढ़ा देते हैं; तूफान (शोर) भी तेज हो जाता है, जिससे फुसफुसाहट दब जाती है। लेखकों ने महसूस किया कि पुराने उपकरण "अननॉर्मलाइज्ड" (unnormalized) थे, जिसका अर्थ है कि उन्होंने शोर मशीन के हर हिस्से के साथ समान व्यवहार किया, यहाँ तक कि उन हिस्सों के साथ भी जो जोर से चिल्ला रहे थे और उन हिस्सों के साथ भी जो शायद ही फुसफुसा रहे थे। उनका नया उपकरण "नॉर्मलाइज्ड" (normalized) है, जो ऐसा है जैसे जासूस के पास स्मार्ट हेडफ़ोन का एक जोड़ा हो जो स्वचालित रूप से चिल्लाने वाले हिस्सों को कम कर देता है और शांत हिस्सों को बढ़ा देता है, जिससे वॉल्यूम पूरी तरह संतुलित हो जाता है। ऐसा करके, उन्होंने सिद्ध किया कि उनका नया एल्गोरिदम ठीक उसी सैद्धांतिक सीमा तक पहुँचता है जिसकी भौतिकविदों ने वर्षों पहले भविष्यवाणी की थी, कॉन्स्टेंट फैक्टर्स (constant factors) तक। यह न्यूनतम डेटा के साथ सिग्नल को खोज लेता है (फिक्स्ड मल्टीप्लायर्स को छोड़कर), बिना किसी बर्बाद समय या अतिरिक्त "लॉगारिदमिक" बोझ के जो पहले इसे धीमा कर देता था। उन्होंने यह भी दिखाया कि इसी प्रकार का कोई अन्य तरीका इससे बेहतर नहीं कर सकता है, और उन्होंने यहाँ तक कि अपने इस जासूसी टूल का एक क्वांटम संस्करण भी बनाया है जो सर्वश्रेष्ठ क्लासिकल स्पेक्ट्रल एल्गोरिदम की तुलना में क्वाटिकली (quartically) तेज़ है।

फुसफुसाते सुरागों का रहस्य

पेपर को समझने के लिए, हमें पहले यह समझना होगा कि यहाँ कौन सा खेल खेला जा रहा है। कल्पना कीजिए कि आपके पास $n$ लाइट स्विचों वाला एक विशाल बोर्ड है, जिनमें से प्रत्येक या तो चालू (ON) है या बंद (OFF)। कोई गुप्त रूप से स्विचों का एक विशिष्ट पैटर्न (सिग्नल) चुनता है और फिर यादृच्छिक सुराग उत्पन्न करना शुरू करता है। प्रत्येक सुराग कहता है, "स्विचों के इस विशिष्ट समूह के $n$ स्विचों में से कितने चालू (even/odd) हैं।" लेकिन पेच यह है कि सुराग शोर भरे (noisy) हैं। कभी-कभी सुराग लिखने वाला व्यक्ति गलती करता है, या सिग्नल बहुत धुंधला होता है। यह "प्लांटेड नॉइज़ी kXOR" समस्या है।

लक्ष्य केवल इन शोर भरे सुरागों को देखकर मूल पैटर्न का पता लगाना है। यदि आपके पास दस लाख सुराग हैं, तो यह आसान है। यदि आपके पास केवल कुछ ही हैं, तो यह असंभव है। बड़ा सवाल यह है कि: आपको इसे हल करने के लिए ठीक कितने सुरागों की आवश्यकता है?

लंबे समय से वैज्ञानिक एक "जादुई वक्र" (magic curve) में विश्वास करते रहे हैं। यह वक्र कहता है कि यदि आप अधिक समय देने के लिए तैयार हैं (अधिक समय), तो आप कम सुरागों के साथ पहेली को हल कर सकते हैं। यह संबंध एक सूत्र द्वारा नियंत्रित होता है जिसमें चरों की संख्या ($n$), समूहों का आकार ($k$), और सिग्नल की शक्ति ($\rho$) शामिल है। सूत्र बताता है कि यदि आपके पास $m$ सुराग हैं, तो आप इसे हल कर सकते हैं यदि $m$ लगभग $1/\rho^2$ के समानुपाती है और इसमें $n$ और एल्गोरिदम के "स्तर" ($\ell$) से संबंधित एक विशिष्ट कारक शामिल है।

हालाँकि, जब भी शोधकर्ताओं ने इस वक्र का अनुसरण करने के लिए एक एल्गोरिदम बनाने की कोशिश की, तो वे एक दीवार से टकरा गए। उनके एल्गोरिदम काम तो करते थे, लेकिन उन्हें कुछ अतिरिक्त सुरागों की आवश्यकता थी—विशेष रूपकर, एक "पॉलीलॉगारिदमिक" (polylogarithmic) कारक अधिक। कंप्यूटर विज्ञान की दुनिया में, "पॉलीलॉगारिदमिक" छोटा लगता है (जैसे $\log n$ या $(\log n)^2$), लेकिन जब यह कारक रनिंग टाइम के एक्सपोनेंट (exponent) में फंस जाता है, तो यह एक ऐसी समस्या में बदल जाता है जिसे हल करने में कुछ घंटे लगने चाहिए थे, लेकिन अब इसमें ब्रह्मांड की आयु से भी अधिक समय लग सकता है। यह एक ऐसी कार चलानेने जैसा है जहाँ गति सीमा 60 मील प्रति घंटा है, लेकिन हर बार जब आप और तेज़ जाने की कोशिश करते हैं, तो इंजन लड़खड़ा जाता है और थोड़ा सा खिंचाव पैदा करता है जो अंततः आपकी कार को पूरी तरह रोक देता है।

"नॉर्मलाइजेशन" की सफलता

इस पेपर के लेखकों ने महसूस किया कि "खिंचाव" (drag) इस बात से आ रहा था कि एल्गोरिदम कैसे बनाए गए थे। उन्होंने "किकुची मैट्रिक्स" (Kikuchi matrix) नामक एक संरचना का उपयोग किया। कल्पना कीजिए कि यह मैट्रिक्स एक विशाल स्प्रेडशीट है जहाँ पंक्तियाँ और कॉलम स्विचों के विभिन्न समूहों का प्रतिनिधित्व करते हैं। एल्गोरिदम इस स्प्रेडशीट में पैटर्न की तलाश करता है ताकि गुप्त सिग्नल को खोजा जा सके।

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

लेखकों का समाधान मैट्रिक्स को "नॉर्मलाइज" करना था। उन्होंने केवल कच्चे कनेक्शनों को नहीं देखा; उन्होंने नंबरों को इस आधार पर समायोजित किया कि प्रत्येक पंक्ति कितनी तेज़ या शांत थी।

• "तेज़" पंक्तियाँ: उन्होंने उन पंक्तियों की आवाज़ कम कर दी जिनमें बहुत अधिक कनेक्शन थे ताकि वे बाकी हिस्सों को दबा न दें।
• "शांत" पंक्तियाँ: उन्होंने उन पंक्तियों को थोड़ा बढ़ावा दिया जिनमें बहुत कम कनेक्शन थे ताकि उन्हें अनदेखा न किया जाए।

वे इसे "डिग्री-प्लस-फ्लोर" (degree-plus-floor) नॉर्मलाइजेशन कहते हैं। यह एक साउंड इंजीनियर की तरह है जो एक कंप्रेसर का उपयोग करता है ताकि यह सुनिश्चित हो सके कि सबसे तेज़ वाद्य यंत्र दूसरों पर हावी न हों, जिससे यह सुनिश्चित होता है कि पूरा बैंड स्पष्ट रूप से सुनाई दे।

ऐसा करके, उन्होंने सिद्ध किया कि उनका नया एल्गोरिदम "शार्प" (sharp) ट्रेड-ऑफ प्राप्त करता है। इसका मतलब है कि यह कॉन्स्टेंट फैक्टर्स तक सटीक रूप से सैद्धांतिक सीमा तक पहुँचता है। यदि गणित कहता है कि आपको 1 घंटे में हल करने के लिए 100 सुरागों की आवश्यकता है, तो उनका एल्गोरिदम लगभग 100 सुरागों के साथ 1 घंटे में इसे करता है (शायद विशिष्ट स्थिरांकों के आधार पर 105 या 95, लेकिन 100 गुना 100 नहीं)। यह केवल अनुमान नहीं है; उन्होंने एक कठोर गणितीय प्रमाण प्रदान किया है कि उनकी विधि काम करती है और इसी प्रकार का कोई अन्य तरीका इससे बेहतर नहीं कर सकता है।

क्वांटम छलांग

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

इसे समझने के लिए: यदि एक क्लासिकल कंप्यूटर पहेली को हल करने के लिए 10,000 स्टेप्स लेता है, तो क्वांटम संस्करण को केवल 10 स्टेप्स की आवश्यकता होगी (क्योंकि $10^4 = 10,000$)। यह एक विशाल सुधार है। लेखकों ने सिद्ध किया कि यह स्पीडअप इन सभी प्रकार की पहेलियों के लिए काम करता है, न कि केवल सम-संख्या वाले (even-numbered) वाले, और यह उनके क्लासिकल संस्करण की तरह ही पूर्ण दक्षता (बिना किसी अतिरिक्त शोर के) के साथ काम करता है।

यह क्यों महत्वपूर्ण है

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

लेखकों ने यह भी दिखाया कि उनकी विधि केवल विशिष्ट "kXOR" गेम से परे अन्य प्रकार की पहेलियों के लिए भी काम करती है। उन्होंने प्रदर्शित किया कि वही तर्क कई प्रकार के "बुलियन CSPs" (Constraint Satisfaction Problems) पर लागू होता है, जो शेड्यूलिंग, क्रिप्टोग्राफी और डेटा ट्रांसमिशन में त्रुटि सुधार (error correction) जैसे कई वास्तविक दुनिया के कार्यों की रीढ़ हैं।

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