⚛️ quantum physics

An almost-linear time decoding algorithm for quantum LDPC codes under circuit-level noise

यह शोध पत्र BP+OTF एल्गोरिदम प्रस्तुत करता है, जो सर्किट-स्तरीय शोर के तहत क्वांटम LDPC कोड्स के लिए एक लगभग-रैखिक समय वाला डिकोडर है, जो अत्याधुनिक डिकोडर्स के तुलनीय लॉजिकल एरर सप्रेशन प्राप्त करने के लिए डिटेक्टर एरर मॉडल स्पारसिफिकेशन तकनीक और बिलीफ प्रोपेगेशन को एक ऑर्डर्ड टैनर फॉरेस्ट पोस्ट-प्रोसेसिंग स्टेज के साथ जोड़ता है, जबकि कुशल रनटाइम बनाए रखता है।

मूल लेखक: Antonio deMarti iOlius, Imanol Etxezarreta Martinez, Joschka Roffe, Josu Etxezarreta Martinez

प्रकाशित 2026-07-01

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Antonio deMarti iOlius, Imanol Etxezarreta Martinez, Joschka Roffe, Josu Etxezarreta Martinez

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक विशाल, अविश्वसनीय रूप से जटिल जिग्सॉ पहेली (jigsaw puzzle) को सुलझाने की कोशिश कर रहे हैं। लेकिन एक पेच है: पहेली के टुकड़े लगातार अपना आकार बदल रहे हैं, तस्वीर धुंधली है, और आपको इसे पलक झपकते ही हल करना है। यह क्वांटम एरर करेक्शन (QEC) की चुनौती है। क्वांटम कंप्यूटर शक्तिशाली होते हैं, लेकिन वे नाजुक होते; छोटी सी गड़बड़ी (शोर/noise) भी उनकी गणनाओं को बर्बाद कर सकती है। उन्हें ठीक करने के लिए, हमें एक "डिकोडर" की आवश्यकता है जो सुरागों (जिन्हें 'सिंड्रोम' कहा जाता है) को देखे और यह पता लगाए कि वास्तव में कौन से टुकड़े टूटे हुए हैं, और वह भी वास्तविक समय (real-time) में।

यह शोध पत्र एक नया, सुपर-फास्ट डिकोडर पेश करता है जिसे BP+BP+OTF कहा जाता है। यह कैसे काम करता है, यहाँ सरल अवधारणाओं में दिया गया है:

1. समस्या: "शोर वाला" पहेली (The "Noisy" Puzzle)

एक क्वांटम कंप्यूटर में, हम केवल अंतिम तस्वीर ही नहीं देखते; हम यह देखने के लिए समय-समय पर पहेली की जाँच करते हैं कि क्या टुकड़े खिसक गए हैं। हालाँकि, जिन उपकरणों का हम जाँच के लिए उपयोग करते हैं, वे भी शोर वाले होते हैं। यह एक "सर्किट-लेवल" का उलझाव पैदा करता है जहाँ एक एकल गलती गलत सूचनाओं की एक श्रृंखला को ट्रिगर कर सकती है।

इनसे निपटने के पारंपरिक तरीके इस बात की तरह हैं जैसे आप पहेली के हर एक संभावित संयोजन की जाँच करके उसे हल करने की कोशिश कर रहे हों। यह सटीक तो है, लेकिन धीमा है। यदि आपके पास हजारों टुकड़ों वाली पहेली है, तो ये धीमे तरीके बहुत अधिक समय ले लेंगे, और इससे पहले कि आप समाधान निकाल पाएं, क्वांटम कंप्यूटर क्रैश हो जाएगा।

2. पहला चरण: "अंतर्ज्ञान" या सहज अहसास (Belief Propagation)

लेखक बलीफ प्रोपेगेशन (BP) नामक एक विधि से शुरुआत करते हैं। इसे जासूसों की एक टीम के रूप में सोचें जो एक कमरे में आपस में नोट्स साझा कर रहे हैं।

प्रत्येक जासूस एक सुराग देखता है और फुसफुसाता है, "मुझे लगता है कि यह टुकड़ा टूटा हुआ है।"
वे यह जानकारी अपने पड़ोसियों को देते हैं।
यदि पर्याप्त पड़ोसी सहमत होते हैं, तो वे आश्वस्त हो जाते हैं।

यह तेज़ है (एक फुसफुसाहट नेटवर्क की तरह), लेकिन कभी-कभी जासूस एक लूप (loop) में फंस जाते हैं। वे शायद एक ही गलत विचार को बार-बार आपस में साझा करते रह सकते हैं, और कभी भी समाधान पर सहमत नहीं हो पाते। गणितीय शब्दों में, सुरागों का ग्राफ "लूप्स" बनाता है जो सिस्टम को भ्रमित कर देते हैं।

3. दूसरा चरण: "स्पारसिफिकेशन" (नक्शे को सरल बनाना)

शोध पत्र एक चतुर तकनीक पेश करता है जिसे स्पारसिफिकेशन (Sparsification) कहा जाता है।

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

4. तीसरा चरण: "ट्री कटर" (Ordered Tanner Forest)

यदि जासूस अभी भी फंसे हुए हैं, तो लेखक एक विशेष उपकरण लाते हैं जिसे OTF (Ordered Tanner Forest) कहा जाता है।

फिर से उस उलझे हुए जंगल की कल्पना करें। OTF एल्गोरिदम एक माली की तरह है जिसके पास एक बहुत ही विशिष्ट नियम है: "किसी भी ऐसे पेड़ की शाखा को काट दें जो एक लूप बनाती है।"
यह सुरागों को देखता है, उन्हें अपराधी होने की संभावना के आधार पर रैंक करता है (पहले चरण के "अंतर्ज्ञान" के आधार पर), और काटना शुरू करता है।
यह तब तक काटता रहता है जब तक कि शेष संरचना एक परफेक्ट ट्री (या पेड़ों का एक जंगल) न बन जाए। एक ट्री संरचना में, कोई लूप नहीं होते।
इससे क्या फर्क पड़ता है? एक लूप-मुक्त ट्री में, "फुसफुसाहट नेटवर्क" (Belief Propagation) गारंटी के साथ पूरी तरह से काम करता है। यह तुरंत समाधान पा सकता है क्योंकि इसमें उलझाने वाले घेरे नहीं हैं जिनमें फंसने का डर हो।

5. परिणाम: तेज़ और सटीक

शोध पत्र ने इस BP+BP+OTF विधि का परीक्षण दो प्रकार के क्वांटम पहेलियों पर किया:

बायवेरिएट बाइसिकल कोड्स (Bivariate Bicycle Codes): एक जटिल, आधुनिक प्रकार का क्वांटम कोड।
सरफेस कोड्स (Surface Codes): आज कई प्रयोगशालाओं द्वारा उपयोग किया जाने वाला मानक प्रकार।

निष्कर्ष:

गति: नया डिकोडर लगभग लीनियर (linear) गति में है। इसका मतलब है कि यदि आप पहेली का आकार दोगुना करते हैं, तो इसमें लगने वाला समय भी लगभग दोगुना ही होगा (बजना के बजाय, जहाँ समय तेजी से बढ़ता है)। कुछ कोड्स के लिए यह वर्तमान सर्वोत्तम मानक तरीकों की तुलना में 10 गुना तेज़ पाया गया।
सटीकता: इतनी तेज़ होने के बावजूद, यह धीमे और भारी-भरकम तरीकों जितना ही सटीक है। इसने त्रुटियों को "गोल्ड स्टैंडर्ड" डिकोडर्स के समान स्तर तक सफलतापूर्वक कम किया।

बड़ी तस्वीर का उदाहरण (The Big Picture Analogy)

डीकोडिंग के पुराने तरीके को एक धीमे, सूक्ष्म जासूस के रूप में सोचें जो सुराग खोजने के लिए एक विशाल पुस्तकालय की हर एक फाइल की जांच करता है। यह सटीक है, लेकिन इसमें घंटों लग जाते हैं।

नया BP+BP+OTF तरीका एक स्मार्ट, तेज़ जासूस की तरह है जो:

एक पूर्वाभास प्राप्त करने के लिए पुस्तकालय को जल्दी से स्कैन करता है (BP)।
एक लाइब्रेरियन से पूछता है कि सभी अप्रासंगिक, भ्रमित करने वाली किताबों को हटा दे और उसे एक सुव्यवस्थित सूची दे (Sparsification)।
यदि वे अभी भी फंसे हुए हैं, तो वे किसी भी भ्रमित करने वाले कनेक्शन को काटने के लिए लेजर कटर का उपयोग करते हैं जब तक कि केवल एक सीधा, स्पष्ट रास्ता शेष न रह जाए (OTF)।
वे फिर तुरंत उत्तर खोजने के लिए उस सीधे रास्ते पर चलते हैं।

शोध पत्र का दावा है कि यह विधि क्वांटम कंप्यूटरों को वास्तविक समय (real-time) में अपनी गलतियों को ठीक करने की अनुमति देती है, जो उपयोगी, फॉल्ट-टोलरेंट क्वांटम मशीनों के निर्माण की दिशा में एक महत्वपूर्ण कदम है।

तकनीकी सारांश: सर्किट-लेवल नॉइज़ के तहत क्वांटम LDPC कोड के लिए एक लगभग-रैखिक समय डिकोडिंग एल्गोरिदम

समस्या विवरण
फॉल्ट-टोलरेंट क्वांटम कंप्यूटिंग के व्यावहारिक कार्यान्वयन के लिए, क्वांटम एरर करेक्शन (QEC) सिंड्रोम का वास्तविक समय में डिकोडिंग करना आवश्यक है, जो अक्सर माइक्रोसेकंड के समयावधि के भीतर होना चाहिए। जबकि बेलिफ प्रोपेगेशन (BP) एक तेज़, रैखिक-समय ( $O(n)$ ) डिकोडिंग दृष्टिकोण प्रदान करता है जो लो-डेंसिटी पैरिटी-चेक (LDPC) कोड के लिए उपयुक्त है, यह अक्सर क्वांटम LDPC (QLDPC) कोड पर डिजेनरेट त्रुटियों और ट्रैपिंग सेट्स के कारण विफल हो जाता है। मौजूदा उच्च-प्रदर्शन डिकोडर, जैसे कि ऑर्डर्ड स्टैटिस्टिक्स डिकोडिंग (BP+OSD) या मैचिंग-आधारित डिकोडर, अक्सर मैट्रिक्स इनवर्जन तकनीकों पर निर्भर करते हैं जो वर्स्ट-केस रनटाइम कॉम्प्लेक्सिटी को बढ़ाकर $O(n^3)$ कर देते हैं, जिससे वास्तविक समय के हार्डवेयर कार्यान्वयन में एक बाधा उत्पन्न होती है। इसके अतिरिक्त, सर्किट-लेवल शोर (फेनोमेनोलॉजिकल शोर के बजाय) के तहत डिकोडिंग करने से जटिल एरर प्रोपेगेशन मैकेनिज्म पेश होते हैं जिन्हें मानक BP के साथ संभालना कठिन होता है, विशेष रूप से जब डिटेक्टर एरर मॉडल (DEM) में उच्च-वेट कॉलम और छोटे लूप होते हैं जो पोस्ट-प्रोसेसिंग रणनीतियों में बाधा डालते हैं।

कार्यप्रणाली
लेखक एक हाइब्रिड डिकोडिंग फ्रेमवर्क, BP+BP+OTF का प्रस्ताव करते हैं, जिसे सर्किट-लेवल शोर के तहत उच्च त्रुटि दमन बनाए रखते हुए लगभग-रैखिक समय जटिलता प्राप्त करने के लिए डिज़ाइन किया गया है। कार्यप्रणाली में तीन प्राथमिक चरण शामिल हैं:

डिटेक्टर ग्राफ स्पारसिफिकेशन (Sparsification):
लेखक पूर्ण डिटेक्टर एरर मॉडल ( $H_{dem}$ ), जो सर्किट फॉल्ट तंत्र को सिंड्रोम माप से जोड़ता है, को एक स्पारसिफाइड डिटेक्टर ग्राफ ( $H_{sdem}$ ) में मैप करने की एक तकनीक पेश करते हैं। इस स्पारसिफाइड ग्राफ का अधिकतम कॉलम वेट कोड के पैरिटी-चेक मैट्रिसेस के तुलनीय होता है (आमतौर पर सरफेस कोड के लिए $\leq 2$ या QLDPC के लिए कम स्थिरांक)।

एक ट्रांसफर मैट्रिक्स ( $A_{tr}$ ) का निर्माण किया जाता है जो पूर्ण DEM को स्पारसिफाइड DEM में मैप करता है। यह ट्रांसफर मैट्रिक्स सुनिश्चित करता है कि त्रुटियों का लॉजिकल एक्शन संरक्षित रहे और पूर्ण ग्राफ से स्पारसिफाइड ग्राफ में सॉफ्ट सूचना (त्रुटि संभावनाओं) का अनुवाद संभव हो सके।
स्पारसिफिकेशन कॉलम की संख्या को कम करता है और छोटे लूप्स को समाप्त करता है, जिससे ग्राफ ट्री-आधारित पोस्ट-प्रोसेसिंग के लिए अधिक अनुकूल हो जाता है।

दो-चरणीय बेलिफ प्रोपेगेशन (BP+BP):

चरण 1: त्रुटि संभावनाओं के संबंध में प्रारंभिक सॉफ्ट सूचना निकालने के लिए पूर्ण डिटेक्टर ग्राफ पर मानक BP लागू किया जाता है।
चरण 2: चरण 1 से प्राप्त सॉफ्ट सूचना को ट्रांसफर मैट्रिक्स का उपयोग करके स्पारसिफाइड डिटेक्टर ग्राफ पर मैप किया जाता है। स्पारसिफाइड ग्राफ पर BP का दूसरा दौर निष्पादित किया जाता है। यह चरण पहले दौर से प्राप्त नॉन-यूनिफॉर्म एरर चैनल का लाभ उठाता है, जो अभिसरण (convergence) को तेज करता है।

ऑर्डर्ड टैनर फॉरेस्ट (OTF) पोस्ट-प्रोसेसिंग:
यदि BP चरण सिंड्रोम को संतुष्ट करने में विफल रहते हैं, तो स्पारसिफाइड ग्राफ पर OTF एल्गोरिदम को बुलाया जाता है।

तंत्र: OTF एल्गोरिदम एक ऑर्डर्ड स्पैनिंग फॉरेस्ट बनाने के लिए संशोधित क्रुस्कल (Kruskal) एल्गोरिदम का उपयोग करता है। यह क्वबिट्स (पैरिटी चेक मैट्रिक्स के कॉलम) को उनके पोस्टीरियर एरर प्रोबेबिलिटीज (BP आउटपुट से) के आधार पर सॉर्ट करता है और उन्हें ग्राफ में पुनरावृत्ति से जोड़ता है, और किसी भी ऐसे कॉलम को हटा देता है जो लूप पेश करेगा।
अभिसरण: परिणामी ग्राफ एक फॉरेस्ट (वृक्षों का संग्रह) है। चूंकि BP ट्री जैसी संरचनाओं पर अभिसरण की गारंटी देता है, इसलिए ऑर्डर्ड फॉरेस्ट पर अंतिम दौर का BP, यदि सिंड्रोम कम किए गए मैट्रिक्स के इमेज के भीतर है, तो समाधान खोजने की गारंटी देता है।
जटिलता: सॉर्टिंग और फॉरेस्ट निर्माण चरणों की जटिलता $O(n \log n)$ है, और अंतिम BP चरण $O(n)$ है, जिसके परिणामस्वरूप कुल लगभग-रैखिक समय जटिलता प्राप्त होती है।

प्रमुख योगदान

OTF पोस्ट-प्रोसेसर: $O(n^3)$ इनवर्जन-आधारित विधियों जैसे BP+OSD के विकल्प के रूप में, मैट्रिक्स इनवर्जन से बचने वाले एक ऑर्डर्ड टैनर फॉरेस्ट एल्गोरिदम का परिचय।
ट्रांसफर मैट्रिसेस के साथ स्पारसिफिकेशन: एक नवीन प्रक्रिया जो महत्वपूर्ण एरर प्रोपेगेशन जानकारी को ट्रांसफर मैट्रिक्स के माध्यम से संरक्षित करते हुए, सर्किट-लेवल डिटेक्टर एरर मॉडल्स को स्पार्सर ग्राफ में मैप करती है। यह डिकोडर को पूर्ण सर्किट शोर मॉडल की जटिलता से बाधित हुए बिना उसके पूर्ण संरचना का लाभ उठाने की अनुमति देता है।
BP+BP+OTF आर्किटेक्चर: एक एकीकृत डिकोडर जो मानक BP, स्पारसिफाइड BP और OTF पोस्ट-प्रोसेसिंग को जोड़ता है, जो विशेष रूप से सर्किट-लेवल शोर के लिए अनुकूलित है।
हार्डवेयर व्यवहार्यता: एल्गोरिदम मानक BP और क्रुस्कल के एल्गोरिदम पर निर्भर करता है, जो दोनों ही ऑफ-द-शेल्फ एप्लीकेशन-स्पेसिफिक इंटीग्रेटेड सर्किट्स (ASICs) या फील्ड-प्रोग्रामेबल गेट एरेज़ (FPGAs) पर कार्यान्वयन के लिए अत्यधिक उपयुक्त हैं।

परिणाम
लेखकों ने डिपोलराइजिंग सर्किट-लेवल शोर के तहत बाइवेरिएट बाइसिकल कोड्स और रोटेटेड सरफेस कोड्स पर मोंटे कार्लो सिमुलेशन का उपयोग करके BP+BP+OTF डिकोडर का बेंचमार्किंग किया।

प्रदर्शन: डिकोडर स्टेट-ऑफ-द-आर्ट डिकोर्स के समान लॉजिकल एरर सप्रेशन प्राप्त करता है। बाइवैरिएट बाइसिकल कोड्स के लिए, यह BP+OSD-0 के प्रदर्शन से मेल खाता है। सरफेस कोड्स के लिए, यह MWPM के प्रदर्शन के समान उपलब्धि प्राप्त करता है और BP+OSD-0 से काफी बेहतर प्रदर्शन करता है।
गति: कार्यान्वयन बाइसिकल बाइसिकल कोड्स को डिकोड करते समय एक मानक BP+OSD कार्यान्वयन (विशेष रूप से [27] में कार्यान्वयन का संदर्भ देते हुए) की तुलना में 10 गुना से अधिक की गति वृद्धि प्रदर्शित करता है।
दक्षता: सरफेस कोड्स के लिए, डिकोडर एक बहुत ही कम संख्या में इटरेशन (जैसे, डिस्टेंस-17 कोड के लिए 107 कुल BP इटरेशन) के साथ विश्वसनीय डिकोडिंग प्राप्त करता है।
स्पारसिफिकेशन प्रभावकारिता: प्रयोगों ने दिखाया कि प्रारंभिक फुल-ग्राफ राउंड के बिना सीधे स्पारसिफाइड मॉडल पर BP लागू करने से प्रदर्शन में गिरावट आती है, लेकिन हाइब्रिड BP+BP दृष्टिकोण पूर्ण-मॉडल डिकोडर के प्रदर्शन को पुनः प्राप्त करता है और औसत डिकोडिंग समय को तीन गुना कम कर देता है।

महत्व
यह पेपर दावा करता है कि BP+BP+OTF, फॉल्ट-टोलरेंट क्वांटम कंप्यूटरों की वास्तविक समय की डिकोडिंग आवश्यकताओं की ओर एक महत्वपूर्ण कदम है। धीमी, इनवर्जन-आधारित विधियों के एरर थ्रेशोल्ड से समझौता किए बिना लगभग-रैखिक समय जटिलता ( $O(n \log n)$ ) प्राप्त करके, यह एल्गोरिदम डिकोडिंग लेटेंसी की महत्वपूर्ण बाधा को संबोधित करता है। लेखक इस बात पर जोर देते हैं कि डिकोडर की मानक, अच्छी तरह से समझ में आने वाले एल्गोरिदम (BP और क्रुस्कल) पर निर्भरता इसे हार्डवेयर त्वरण के लिए एक अत्यधिक आकर्षक उम्मीदवार बनाती है, जो जटिल, विशिष्ट डिकोडर की तुलना में कम विकास लागत और उच्च स्केलेबिलिटी के साथ फॉल्ट-टोलरेंट सिस्टम के निर्माण को सक्षम कर सकती है। यह कार्य यह भी सुझाव देता है कि स्पारसिफिकेशन तकनीक प्रस्तावित विशिष्ट BP+BP+OTF आर्किटेक्चर के अलावा अन्य डिकोडर परिवारों को भी लाभान्वित कर सकती है।