⚛️ quantum physics

An Optimal Quantum Linear Systems Algorithm

यह शोध पत्र क्वांटम लीनियर सिस्टम्स प्रॉब्लम के लिए $\Theta(\kappa\sqrt d\log(1/\epsilon))$ की इष्टतम क्वेरी जटिलता स्थापित करता है और यह प्रदर्शित करके एक खुली समस्या को हल करता है कि किसी भी $N\times N$ यूनिटरी को $O(\sqrt N)$ क्वेरीज़ का उपयोग करके सीमित त्रुटि के साथ लागू किया जा सकता है।

मूल लेखक: Carlos Bravo-Prieto, Aram W. Harrow, Robin Kothari

प्रकाशित 2026-09-29

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

CC BY 4.0

मूल लेखक: Carlos Bravo-Prieto, Aram W. Harrow, Robin Kothari

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

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

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

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

यह सफलता समस्या के स्वयं के चतुर पुनर्गठन से आई। मूल प्रणाली को सीधे हल करने के बजाय, शोधकर्ताओं ने एक बहुत बड़ी, सहायक प्रणाली (auxiliary system) का निर्माण किया जिसमें मूल समाधान उसके भीतर छिपा हुआ था। इसे इस तरह सोचें जैसे कि एक एकल, कठिन समीकरण को सरल, परस्पर जुड़े चरणों की एक श्रृंखला में तोड़ना जो क्वांटंत कंप्यूटर के लिए नेविगेट करना आसान हो। मध्यवर्ती चरों (intermediate variables) को 'स्टेपिंग स्टोन्स' के रूप में पेश करके, वे मूल कठिन कार्य को एक नए कार्य में बदलने में सक्षम हुए जिसे एक क्वांटंत कंप्यूटर बहुत कम प्रश्नों के साथ संभाल सकता था। इस नए दृष्टिकोण ने उन्हें पिछली सीमाओं को पार करने की अनुमति दी, जिससे आवश्यक प्रश्नों की संख्या को विरलता कारक (sparsity factor) के वर्गमूल तक कम कर दिया गया, जो एक महत्वपूर्ण गणितीय छलांग थी जिसे पहले पहुंच से बाहर माना जाता था।

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

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

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

इस परिणाम तक पहुँचने का मार्ग सीधा नहीं था। इसके लिए शोधकर्ताओं को इस बात पर पुनर्विचार करने की आवश्यकता थी कि क्वांटंत एल्गोरिदम विरल डेटा (sparse data) के साथ कैसे अंतःक्रिया करते हैं। पिछले दृष्टिकोणों ने डेटा को एक कठोर संरचना के रूप में माना था, जिससे एल्गोरिदम को एक ऐसे तरीके से नेविगेट करने के लिए मजबूर होना पड़ा जो स्वाभाविक रूप से धीमा था। नया तरीका डेटा को अधिक लचीला बनाता है, जिससे एल्गोरिदम को संरचना का पता लगाने के लिए अधिक स्वतंत्र रूप से अन्वेषण करने की अनुमति मिलती है, जिससे समाधान अधिक सीधे प्रकट होता है। परिप्रेक्ष्य के इस बदलाव ने, कठोर गणितीय प्रमाण के साथ मिलकर, टीम को वह जो सोचा गया था और जो वास्तव में प्राप्त किया जा सकता है, उसके बीच के अंतर को पाटने में मदद की है।

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

तकनीकी सारांश: एक इष्टतम क्वांटम लीनियर सिस्टम्स एल्गोरिदम

समस्या विवरण

क्वांटम लीनियर सिस्टम्स प्रॉब्लम (QLSP) में एक इनवर्टिबल (invertible), $d$ -स्पार्स $N \times N$ मैट्रिक्स $A$ के साथ एक रैखिक समीकरण $A\vec{x} = \vec{b}$ को हल करना शामिल है, जहाँ $\vec{b}$ एक ज्ञात वेक्टर है और $\kappa$ कंडीशन नंबर है। लक्ष्य शास्त्रीय वेक्टर $\vec{x}$ को आउटपुट करना नहीं है, बल्कि एक सफलता फ्लैग (success flag) की स्थिति में, आदर्श अवस्था से अधिकतम $\epsilon$ ट्रेस डिस्टेंस (trace distance) के साथ एक क्वांटम अवस्था $|x\rangle$ तैयार करना है। यह एल्गोरिदम मानक स्पार्स-मैट्रिक्स ऑरेकल मॉडल के तहत कार्य करता है, जहाँ एक्सेस एक लोकेशन ऑरेकल (पंक्ति में गैर-शून्य प्रविष्टियों की पहचान करने के लिए) और एक वैल्यू ऑरेकल (प्रविष्टि मानों को वापस करने के लिए) के माध्यम से दिया जाता है।

इस कार्य से पूर्व, QLSP के लिए सर्वोत्तम ज्ञात क्वांटम एल्गोरिदम की क्वेरी जटिलता (query complexity) $O(\kappa d \log(1/\epsilon))$ [CAS+22] और $\kappa \sqrt{d} (\kappa d / \epsilon)^{o(1)}$ [Low19] थी। सर्वोत्तम ज्ञात लोअर बाउंड (lower bounds) क्रमशः $\Omega(\kappa \log(1/\epsilon))$ [CABB23] और $\Omega(\kappa \sqrt{d})$ [MKBR26] थे। ऊपरी और निचली सीमाओं के बीच एक अंतर मौजूद था, विशेष रूप से स्पर्सिटी $d$ पर निर्भरता के संबंध में।

कार्यप्रणाली

अपर बाउंड निर्माण (Upper Bound Construction)

लेखक सिद्ध करते हैं कि इष्टतम क्वेरी जटिलता $\Theta(\kappa \sqrt{d} \log(1/\epsilon))$ है, जिसके लिए एक नया एल्गोरिदम निर्मित किया गया है। मुख्य नवाचार एक रिडक्शन तकनीक है जो स्पार्स-मैट्रिक्स ब्लॉक एनकोडिंग में मानक बाधा से बचती है।

बाधा (The Obstruction): एक स्पार्स मैट्रिक्स $A$ का मानक ब्लॉक एनकोडिंग आमतौर पर $A = F^\dagger T$ के गुणनखंडन (factorization) पर निर्भर करता है। जबकि मैप $T$ (एम्प्लीट्यूड वितरित करना) को $O(1)$ क्वेरी के साथ लागू करना आसान है, मैप $F$ (पंक्ति मानों को लोड करना) को अनस्ट्रक्चर्ड सर्च समस्या को हल करने से बचने के लिए सामान्यतः $\Omega(\sqrt{d})$ क्वेरी की आवश्यकता होती है। यह पिछले एल्गोरिदम में उप-इष्टतम $O(\kappa d)$ निर्भरता का कारण बनता है।
रिडक्शन (The Reduction): $F$ को सीधे लागू करने के बजाय, लेखक समीकरण $F^\dagger T \vec{u} = \vec{b}$ को दो युग्मित समीकरणों $T \vec{u} = \vec{z}$ और $F^\dagger \vec{z} = \vec{b}$ में विभाजित करने के लिए एक मध्यवर्ती वेक्टर $\vec{z}$ का परिचय देते हैं।
बड़ा सिस्टम (Enlarged System): इन समीकरणों को एक बड़े लीनियर सिस्टम $L \begin{pmatrix} \vec{z} \\ \vec{u} \end{pmatrix} = \begin{pmatrix} 0 \\ \vec{b} \end{pmatrix}$ में संयोजित किया जाता है। मैट्रिक्स $L$ इस प्रकार बनाया गया है कि इसके समाधान में मूल समाधान $\vec{x}$ (स्केल किया हुआ) एक विशिष्ट ब्लॉक में होता है।
बढ़े हुए सिस्टम का ब्लॉक एनकोडिंग (Block Encoding the Enlarged System): लेखक केवल $O(1)$ $O (1)$ स्पार्स-मैट्रिक्स ऑरेकल क्वेरी का उपयोग करके $L$ $L$ के एक नॉर्मलाइज्ड संस्करण, जिसे $M$ $M$ कहा जाता है, का सटीक ब्लॉक एनकोडिंग निर्मित करते हैं। यह निम्नलिखित द्वारा प्राप्त किया जाता है:
- संपूर्ण पंक्तियों के बजाय व्यक्तिगत प्रविष्टियों को लोड करने वाले स्टेट प्रिपरेशन मैप्स को परिभाषित करना।
- प्रत्येक स्टेट प्रिपरेशन मैप को अलग से नॉर्मलाइज करना, जो महंगी $F$ मैप की आवश्यकता को दरकिनार करने की अनुमति देता है।
- यह सिद्ध करना कि नए मैट्रिक्स $M$ का कंडीशन नंबर $O(\kappa \sqrt{d})$ है।
समाधान (Solving): बढ़े हुए सिस्टम को कोस्टा एट अल. [CAS+22] द्वारा उपयोग किए गए मौजूदा ब्लॉक-एनकोडेड QLSP एल्गोरिदम का उपयोग करके हल किया जाता है। चूंकि $M$ का कंडीशन नंबर $O(\kappa \sqrt{d})$ है और इसे $O(1)$ क्वेरी के साथ एक्सेस किया जाता है, इसलिए कुल जटिलता $O(\kappa \sqrt{d} \log(1/\epsilon))$ हो जाती है।

लोअर बाउंड निर्माण (Lower Bound Construction)

लोअर बाउंड $\Omega(\kappa \sqrt{d} \log(1/\epsilon))$ को सिद्ध करने के लिए, लेखक कठिनाई के दो स्रोतों को जोड़ते हैं:

अनस्ट्रक्चर्ड सर्च (Unstructured Search): आकार $d$ की एक अनस्ट्रक्चर्ड सर्च समस्या को एम्बेड करने से $\Omega(\sqrt{d})$ का लोअर बाउंड मिलता है।
सर्किट हिस्ट्री/पैरिटी (Circuit History/Parity): एक सर्किट को एम्बेड करना जो $R$ बिट्स की पैरिटी की गणना करता है, $\Omega(R)$ का लोअर बाउंड देता है, जहाँ $R$ कंडीशन नंबर और प्रिसिजन (precision) से संबंधित है। विशेष रूप से, लीनियर सिस्टम निर्माण में "हिस्ट्री स्टेट" का क्षय (decay) कंडीशन नंबर $\kappa$ और प्रिसिजन $\epsilon$ को इस प्रकार जोड़ता है कि $R = \Theta(\kappa \log(1/\epsilon))$ होता है।
कंपोजिशन (Composition): लेखक एक ऐसी समस्या का निर्माण करते हैं जिसमें $R$ बिट्स की पैरिटी की गणना आवश्यक है, जहाँ प्रत्येक बिट $d$ आकार की एक स्वतंत्र अनस्ट्रक्चर्ड सर्च का आउटपुट है। ली और रोलैंड [LR12] के क्वांटम XOR लेम्मा का उपयोग करते हुए, वे दिखाते हैं कि इस कंपोज्ड समस्या की क्वेरी जटिलता $\Omega(R \sqrt{d})$ है, जो $\Omega(\kappa \sqrt{d} \log(1/\epsilon))$ में परिवर्तित होती है।

मुख्य परिणाम

प्रमेय 1 (इष्टतम क्वेरी जटिलता): QLSP की क्वेरी जटिलता $\Theta(\kappa \sqrt{d} \log(1/\epsilon))$ है। यह पिछले अपर और लोअर बाउंड के बीच के अंतर को समाप्त करता है।

प्रमेय 2 (स्क्वायर-रूट-स्पार्सिटी ब्लॉक एनकोडिंग): किसी भी हर्मिटियन (Hermitian) $d$ -स्पार्स मैट्रिक्स $H$ के लिए, जिसका $\|H\| \le 1$ है, $O(\sqrt{d} \log(1/\eta))$ स्पार्स-मैट्रिक्स ऑरेकल क्वेरी का उपयोग करके एक $(O(1), \eta)$ ब्लॉक एनकोडिंग निर्मित की जा सकती है। यह पिछले तरीकों में सुधार है जिन्हें निरंतर त्रुटि (constant error) के लिए $O(d)$ क्वेरी की आवश्यकता थी।

अनुषंगिक 3 (ब्लैक-बॉक्स यूनिटरी कार्यान्वयन): $N \times N$ यूनिटरी $U$ की प्रविष्टियों तक ऑरेकल एक्सेस दिए जाने पर, $U$ को $O(\sqrt{N} \log(1/\epsilon))$ क्वेरी का उपयोग करके त्रुटि $\epsilon$ के साथ लागू किया जा सकता है। यह बेरी और चाइल्ड्स [BC12] द्वारा उठाए गए एक खुले प्रश्न को हल करता है कि क्या अनस्ट्रक्चर्ड सर्च से प्राप्त $\Omega(\sqrt{N})$ लोअर बाउंड को यूनिटरी कार्यान्वयन के लिए मैच किया जा सकता है।

महत्व और दावे

यह शोध पत्र दावा करता है कि यह क्वांटम लीनियर सिस्टम्स प्रॉब्लम की क्वेरी जटिलता का पूर्ण लक्षण वर्णन प्रदान करता है। मिलान करने वाले अपर और लोअर बाउंड को सिद्ध करके, लेखक स्थापित करते हैं कि कंडीशन नंबर $\kappa$ , स्पर्सिटी $d$ , और प्रिसिजन $\epsilon$ पर निर्भरता इष्टतम है।

इस कार्य का महत्व निम्नलिखित में निहित है:

इष्टतमता (Optimality): यह QLSP के लिए क्वांटम एल्गोरिदम की सैद्धांतिक सीमाओं को निर्धारित करता है, यह दिखाते हुए कि पिछला $O(\kappa d)$ निर्भरता मौलिक नहीं थी बल्कि एक एल्गोरिद्मिक दृष्टिकोण का परिणाम थी।
पद्धतिगत प्रगति (Methodological Advancement): महंगी स्टेट प्रिपरेशन मैप्स से बचने के लिए बड़े लीनियर सिस्टम में मैट्रिक्स उत्पादों को विभाजित करने की तकनीक, क्वांटम एल्गोरिदम डिजाइन के लिए, विशेष रूप से स्पार्स मैट्रिक्स के लिए ब्लॉक एनकोडिंग हेतु एक नया उपकरण प्रदान करती है।
खुले प्रश्नों का समाधान (Resolution of Open Problems): ये परिणाम ब्लैक-बॉक्स यूनिटरीज को लागू करने के संबंध में खुले प्रश्न को सीधे हल करते हैं, यह पुष्टि करते हुए कि $\Omega(\sqrt{N})$ लोअर बाउंड टाइट (tight) है।

लेखक नोट करते हैं कि अपर बाउंड का प्रमाण स्वतंत्र रूप से विकसित किया गया था, हालांकि वे प्रमाणों को सरल बनाने और पांडुलिपि की तैयारी के लिए AI टूल्स के उपयोग को स्वीकार करते हैं। लोअर बाउंड प्रमाण स्थापित तकनीकों (हिस्ट्री स्टेट्स, XOR लेम्मा) पर निर्भर करता है जिन्हें एक नवीन कंपोजिट निर्माण में लागू किया गया है।