Linear-depth quantum oracles for clique problems from edge colorings and graph states, with linear non-Clifford cost and a provably bounded-error k-clique search

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

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

समस्या का मूल यह है कि क्वांटम कंप्यूटर ग्राफ को कैसे "देखते" हैं। क्लिक खोजने के लिए, एक क्वांटम एल्गोरिदम को यह जांचना होगा कि क्या बिंदुओं का एक विशिष्ट सेट आपस में जुड़ा हुआ है। पिछले तरीकों ने नेटवर्क में प्रत्येक कनेक्शन को एक अलग गेट के रूप में माना जिसे सक्रिय करना आवश्यक था। यदि एक नेटवर्क में हजारों कनेक्शन थे, तो सर्किट को हजारों ऐसे महंगे गेटों की आवश्यकता थी, जिससे प्रक्रिया धीमी और त्रुटियों के प्रति संवेदनशील हो जाती थी। नया कार्य 'एज कलरिंग' (edge coloring) के विचार पर आधारित एक चतुर शेड्यूलिंग तकनीक पेश करता है। एक व्यस्त चौराहे की कल्पना करें जहाँ विभिन्न दिशाओं से आने वाली कारों को बिना टकराए गुजरने की आवश्यकता होती है। यदि आप कारों को रंग के आधार पर समूहबद्ध करते हैं, तो आप सभी लाल कारों को एक साथ, फिर सभी नीली कारों को, और इसी तरह, बिना किसी टकराव के जाने दे सकते हैं। शोधकर्ताओं ने ग्राफ में कनेक्शनों पर यही तर्क लागू किया। कनेक्शनों को जो आपस में कोई बिंदु साझा नहीं करते, उन्हें समूहबद्ध करके, वे उन्हें समानांतर परतों (parallel layers) में एक साथ संसाधित कर सकते हैं। यह सर्किट की गहराई को—इसे चलाने में लगने वाले चरणों की संख्या को—आकार के साथ तेजी से बढ़ने वाले द्विघातीय (quadratic) विकास से घटाकर एक रैखिक (linear) विकास में बदल देता है जो बहुत धीरे-धीरे बढ़ता है।

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

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

शोधकर्ताओं ने अपने सिद्धांत का परीक्षण केवल रैंडम नंबरों पर नहीं, बल्कि वास्तविक डेटा पर किया। उन्होंने दो वास्तविक जैविक नेटवर्क से प्रेरित सबग्राफ लिए: मकाक बंदर का सेरेब्रल कॉर्टेक्स और चूहे का रेटिना। ये जटिल, अव्यवस्थित, वास्तविक दुनिया की संरचनाएं हैं, आदर्श गणितीय आकार नहीं। उन्होंने अपने एल्गोरिदम को सैकड़ों इन सबग्राफ पर चलाया, जो क्वांटम सर्किट के सटीक व्यवहार का अनुकरण करता है। परिणाम आश्चर्यजनक थे। जब उन्होंने नए फ़िल्टर्ड ऑरेकल का उपयोग किया, तो सही क्लिक खोजने की सफलता दर लगातार उच्च रही, जो अक्सर 90 प्रतिशत से अधिक थी और कई मामलों में लगभग 100 प्रतिशत तक पहुँच गई। इसके विपरीत, जब उन्होंने अपने नए सर्किट के पुराने, अनफ़िल्टर्ड संस्करण का उपयोग करने का प्रयास किया, तो सफलता दर काफी गिर गई, और एल्गोरिदम अक्सर समाधान खोजने में विफल रहा या गलत समाधान पाया। सिमुलेशन ने पुष्टि की कि सैद्धांतिक गारंटी वास्तविक अभ्यास में भी सत्य रही, यहाँ तक कि क्वांटम अवस्था की खामियों के बावजूद।

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

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