⚛️ quantum physics

On the practicality of quantum sieving algorithms for the shortest vector problem

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

मूल लेखक: Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia

प्रकाशित 2026-04-13

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

CC BY 4.0

मूल लेखक: Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia

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

द ग्रेट क्वांटम सीव (The Great Quantum Sieve): भविष्य के कोड तोड़ने पर एक वास्तविकता की जाँच

कल्पना कीजिए कि आप एक विशाल, उलझे हुए ऊन के गोले में से सबसे छोटा धागा खोजने की कोशिश कर रहे हैं, जो एक आकाशगंगा (galaxy) के आकार का है। यह मूल रूप से शॉर्टेस्ट वेक्टर प्रॉब्लम (SVP) है। क्रिप्टोग्राफी की दुनिया में, यह "ऊन का गोला" एक गणितीय संरचना है जिसे लैटिस (lattice) कहा जाता है, और उस सबसे छोटे धागे को खोजना आज के हमारे सबसे सुरक्षित डिजिटल तालों को तोड़ने की कुंजी है।

दशकों से, वैज्ञानिक पूछ रहे हैं: "क्या एक क्वांटम कंप्यूटर इस धागे को एक सामान्य कंप्यूटर की तुलना में बहुत तेज़ी से खोज सकता है?"

शोधकर्ताओं की एक टीम द्वारा लिखा गया यह शोध पत्र कहता है: "शायद नहीं, कम से कम निकट भविष्य में तो बिल्कुल नहीं।"

यहाँ उनके निष्कर्षों का सरल उपमाओं (analogies) के माध्यम से विवरण दिया गया है।

1. सेटअप: क्वांटम रेस (The Quantum Race)

आधुनिक एन्क्रिप्शन (वह प्रकार जो क्वांटम कंप्यूटरों के आने के बाद हमारे डेटा की रक्षा करेगा) को तोड़ने के लिए, हैकर्स को लगभग 400 आयाम (dimension) वाले लैटिस पर SVP को हल करने की आवश्यकता होगी। इसे एक 400-आयामी भूलभुलैया के रूप में समझें।

शोधकर्ता काफी समय से जानते हैं कि ग्रोवर का एल्गोरिदम (Grover's Algorithm) (एक प्रसिद्ध क्वांटम सर्च ट्रिक) सैद्धांतिक रूप से इस खोज को तेज़ कर सकता है। यह एक जादुई टॉर्च होने जैसा है जो आपको एक बार में एक के बजाय दो कमरों की जांच करने की अनुमति देती है। सैद्धांतिक रूप से, यह खोज को बहुत तेज़ बना देना चाहिए।

हालाँकि, यह शोध पत्र एक बहुत ही व्यावहारिक प्रश्न पूछता है: "उस जादुई टॉर्च को बनाने की वास्तविक लागत क्या है?"

2. छिपी हुई लागतें: "जादू" मुफ़्त नहीं है

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

उन्होंने पूरा बिल गणना करने का निर्णय लिया, जिसमें शामिल हैं:

कार (हार्डवेयर): एक क्वांटम कंप्यूटर बनाने के लिए लाखों सूक्ष्म भागों की आवश्यकता होती है।
ड्राइवर (एरर करेक्शन): क्वांटम बिट्स (qubits) अविश्वसनीय रूप से नाजुक होते हैं, जैसे ऊबड़-खाबड़ सड़क पर कांच की मार्बल्स। उन्हें टूटने से बचाने के लिए, आपको हर एक "उपयोगी" मार्बल को हजारों अन्य मार्बल्स से बनी एक सुरक्षात्मक परत (bubble) में लपेटना होगा। इसे क्वांटम एरर करेक्शन (Quantum Error Correction) कहा जाता है।
मेमोरी (QRAM): ऊन के गोले को खोजने के लिए, कंप्यूटर को याद रखना होगा कि हर धागा कहाँ है। शोध पत्र एक विशाल "क्वांटम लाइब्रेरी" (QRAM) बनाने की लागत की गणना करता है जिसे तुरंत एक्सेस किया जा सके।
ईंधन (समय): इंजन को चलने में कितना समय लगता है?

3. बड़ा खुलासा: आंकड़े चौंकाने वाले हैं

जब लेखकों ने 400 आयाम के लैटिस (वर्तमान "पोस्ट-क्वांटम" सुरक्षा मानकों को तोड़ने के लिए आवश्यक आकार) के लिए आंकड़ों की गणना की, तो परिणाम विनम्र करने वाले थे:

क्विबिट काउंट (Qubit Count): इस एल्गोरिदम को चलाने के लिए, आपको लगभग 10 ट्रिलियन (10¹³) फिजिकल क्विबिट्स की आवश्यकता होगी।
- उपमा: यदि मानव शरीर का प्रत्येक परमाणु एक क्विबिट है, तो इस कंप्यूटर को बनाने के लिए आपको अरबों मनुष्यों के परमाणुओं को एक साथ रखने की आवश्यकता होगी।
समय: इस विशाल मशीन के साथ भी, इस समस्या को हल करने में लगभग 10³¹ वर्ष लगेंगे।
- उपमा: ब्रह्मांड केवल लगभग 13.8 बिलियन वर्ष पुराना है (10¹⁰)। इस कंप्यूटर को ब्रह्मांड की आयु से 1,000,000,000,000,000,000,000,000,000,000 गुना अधिक समय लगेगा।

4. "क्लासिकल" सरप्राइज (The "Classical" Surprise)

यहाँ एक मोड़ है: लेखकों ने यह भी गणना की कि एक सामान्य, सिंगल-कोर क्लासिकल कंप्यूटर (जैसे आपके लैपटॉप में होता है, लेकिन बहुत तेज़ गति पर चल रहा हो) को वही काम करने में कितना समय लगेगा।

इसे भी लगभग उतना ही समय लगेगा: 10³¹ वर्ष।

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

5. यह इतना कठिन क्यों है? (The "QRAM" Bottleneck)

इस भारी लागत के लिए सबसे बड़ा अपराधी QRAM (क्वांटम रैंडम एक्सेस मेमोरी) है।

उपमा: कल्पना कीजिए कि आप घास के ढेर में सुई ढूंढ रहे हैं। एक क्वांटम कंप्यूटर पूरे घास के ढेर को एक साथ देखना चाहता है। लेकिन ऐसा करने के लिए, उसे घास के हर एक टुकड़े के लिए एक लाइब्रेरी कार्ड की आवश्यकता होती है। आकाशगंगा के आकार के घास के ढेर के लिए लाइब्रेरी कार्ड सिस्टम बनाने के लिए खुद उस घास के ढेर से भी अधिक संसाधनों की आवश्यकता होती है!
शोध पत्र दिखाता है कि खोज के लिए डेटा रखने के लिए आवश्यक मेमोरी इतनी विशाल है कि वह क्वांटम स्पीडअप के सभी लाभों को निगल लेती है।

6. निष्कर्ष: घबराएं नहीं (अभी नहीं)

लेखक निष्कर्ष निकालते हैं कि:

वर्तमान मानक सुरक्षित हैं: NIST द्वारा मानकीकृत किया जा रहा लैटिस-आधारित क्रिप्टोग्राफी (जैसे Kyber और Dilithium) निकट भविष्य के लिए क्वांटम हमलों से सुरक्षित है।
कोई जादुई समाधान नहीं: केवल एक क्वांटम कंप्यूटर को जोड़ने से ये कोड अपने आप नहीं टूट जाते। हार्डवेयर की आवश्यकताएं वर्तमान में असंभव हैं।
भविष्य की उम्मीद? क्वांटम कंप्यूटरों द्वारा वास्तव में इन कोडों को तोड़ने के लिए, हमें दो क्षेत्रों में बड़े ब्रेकथ्रू की आवश्यकता होगी:
- हार्डवेयर: ऐसे क्वांटम कंप्यूटर बनाना जिन्हें हर क्विबिट के लिए लाखों सुरक्षात्मक "बबल्स" की आवश्यकता न हो।
- मेमोरी: ऐसी क्वांटम मेमोरी (QRAM) बनाने का तरीका खोजना जिसके लिए आकाशगंगा के आकार के स्थान की आवश्यकता न हो।

सारांश

इस शोध पत्र को "क्वांटम एपोकैलिप्स" (Quantum Apocalypse) के लिए एक वास्तविकता की जाँच के रूप में देखें। हालांकि क्वांटम कंप्यूटर अद्भुत हैं और अंततः कई समस्याओं को हल करेंगे, लेकिन वे कोई जादुई छड़ी नहीं हैं जो तुरंत सभी एन्क्रिप्शन को तोड़ देती है।

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

यहाँ शोध पत्र "On the practicality of quantum sieving algorithms for the shortest vector problem" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

पोस्ट-क्वांटम क्रिप्टोग्राफी (PQC) की सुरक्षा, विशेष रूप से NIST द्वारा मानकीकृत जाली-आधारित (lattice-based) योजनाओं (जैसे कि Kyber, Dilithium) की सुरक्षा, शॉर्टेस्ट वेक्टर प्रॉब्लम (SVP) की कम्प्यूटेशनल कठिनाई पर निर्भर करती है। SVP एक पूर्णांक जाली (integer lattice) में सबसे छोटे गैर-शून्य वेक्टर (non-zero vector) को खोजने के लिए कहता है। जबकि शास्त्रीय एल्गोरिदम (एन््युमरेशन और सीविंग) को जाली आयाम $D$ में घातांकीय (exponential) माना जाता है, यह व्यापक रूप से माना जाता है कि क्वांटम कंप्यूटर, मुख्य रूप से ग्रोवर के सर्च एल्गोरिदम (Grover's search algorithm) के माध्यम से, एक गति प्रदान कर सकते हैं, जो अनस्ट्रक्चर्ड सर्च के लिए द्विघात गति (quadratic speedup) ( $O(\sqrt{N})$ बनाम $O(N)$ ) प्रदान करता है।

पिछले सैद्धांतिक विश्लेषणों ने सुझाव दिया था कि क्वांटम सीविंग एल्गोरिदम लगभग $2^{0.267D}$ (लोकेलिटी सेंसिटिव हैशिंग/फिल्टरिंग के साथ सीव्स पर ग्रोवर का उपयोग करके) की जटिलता के साथ SVP को हल कर सकते हैं, जो सर्वोत्तम शास्त्रीय जटिलताओं ( $2^{0.292D}$ ) से काफी कम है। हालाँकि, इन एसिम्प्टोटिक (asymptotic) विश्लेषणों ने अक्सर महत्वपूर्ण ओवरहेड्स की अनदेखी की है:

क्वांटम रैंडम एक्सेस मेमोरी (QRAM) की लागत।
क्वांटम एरर करेक्शन (QEC) का ओवरहेड।
क्वांटम हार्डवेयर पर फिक्स्ड-पॉइंट अंकगणित (fixed-point arithmetic) की लागत।
गैर-एसिम्प्टोटिक (Non-asymptotic) बाधाएं (जैसे, समाधानों की अज्ञात संख्या)।

यह शोध पत्र वर्तमान क्रिप्टोग्राफिक मानकों (विशेष रूप से $D=400$ ) के लिए प्रासंगिक आयामों में SVP को हल करने के लिए एक कठोर संसाधन अनुमान (resource estimation) करके, सैद्धांतिक विश्लेषण और व्यावहारिक व्यवहार्यता के बीच के अंतर को संबोधित करता है।

2. कार्यप्रणाली (Methodology)

लेखकों ने आठ प्रकार के सीविंग एल्गोरिदम के लिए एक व्यापक संसाधन अनुमान विश्लेषण किया:

NVSieve (नेग्वेन-विडिक) और GaussSieve (मिकियानसिओ-वुलगारिस)।
लोकेलिटी सेंसिटिव हैशिंग (LSH) के साथ उन्नत वेरिएंट: एंगुलर LSH और स्फेरिकल LSH।
लोकेलिटी सेंसिटिव फिल्टरिंग (LSF) के साथ उन्नत वेरिएंट: स्फेरिकल LSF।

विश्लेषण ने निम्नलिखित घटकों को एकीकृत किया:

क्वांटम अंकगणित (Quantum Arithmetic): 32-बिट परिशुद्धता ( $\kappa=32$ ) के साथ फिक्स्ड-पॉइंट अंकगणित (जोड़, तुलना, गुणा) के लिए अत्याधुनिक सर्किट का उपयोग किया गया। उन्होंने टोफोली काउंट (Toffoli count) को न्यूनतम रखने के लिए गिडनी के आउट-ऑफ-प्लेस एडर (Gidney's out-of-place adder) और एक स्कूलबुक-शैली के मल्टीप्लायर का उपयोग किया।
ग्रोवर सर्च (Grover's Search): गैर-एसिम्प्टोटिक ग्रोवर सर्च (एक्सपोनेंशियल सर्च वेरिएंट का उपयोग करके) को लागू किया गया क्योंकि सीविंग चरणों में समाधानों की संख्या पहले से ज्ञात नहीं होती है।
QRAM: क्लासिकल डेटाबेस तक पहुँचने के लिए बकेट-ब्रिगेड QRAM (अरुणाचलम एट अल. का डिज़ाइन) के मॉडल का उपयोग किया गया। यह एक प्रमुख केंद्र था, क्योंकि QRAM के लिए आवश्यक लॉजिकल क्यूबिट्स की संख्या डेटाबेस के आकार के लगभग समान होती है।
एरर करेक्शन (Error Correction): $p_{phy} = 10^{-5}$ के भौतिक त्रुटि दर के साथ एक सरफेस कोड (surface code) आर्किटेक्चर को माना गया। आवश्यक विशाल संख्या में टोफोली गेट्स के लिए $10^{-40}$ से कम लॉजिकल एरर रेट प्राप्त करने के लिए उन्होंने मल्टी-लेवल मैजिक स्टेट डिस्टिलेशन (magic state distillation) (3 स्तरों तक) का उपयोग किया।
आर्किटेक्चर (Architectures): दो भौतिक आर्किटेक्चर का मूल्यांकन किया गया:
- बेसलाइन: निकटतम-पड़ोसी इंटरैक्शन के साथ 2D ग्रिड (जैसे गूगल साइकामोर स्टाइल)।
- एक्टिव-वॉल्यूम (Active-Volume): एक अधिक कुशल आर्किटेक्चर (लिटिंस्की/निकर्सन) जो गैर-स्थानीय कनेक्शनों और आइडल क्यूबिट लागत को कम करने के लिए "वर्कस्पेस" मॉड्यूल का उपयोग करता है।
क्लासिकल बेसलाइन (Classical Baseline): क्वांटम निष्पादन समय की तुलना अनुक्रमिक खोज (sequential searches) और हैशिंग करने वाले एकल-कोर क्लासिकल कंप्यूटर (6 GHz) से की गई।

3. मुख्य योगदान (Key Contributions)

प्रथम व्यापक संसाधन अनुमान: पिछले कार्यों के विपरीत जो केवल गेट काउंट पर ध्यान केंद्रित करते थे या QRAM/QEC की अनदेखी करते थे, यह शोध पत्र भौतिक क्यूबिट्स, समय और एरर करेक्शन ओवरहेड्स सहित एक पूर्ण-स्टैक संसाधन अनुमान प्रदान करता है।
QRAM का प्रभुत्व (QRAM Dominance): लेखक प्रदर्शित करते हैं कि QRAM की लागत प्राथमिक बाधा है। सीविंग एल्गोरिदम में, QRAM के माध्यम से वेक्टरों की घातांकीय बड़ी सूचियों तक पहुँचने की आवश्यकता अधिकांश भौतिक क्यूबिट्स का उपभोग करती है।
गैर-एसिम्प्टोटिक विश्लेषण: उन्होंने ग्रोवर सर्च में "समाधानों की अज्ञात संख्या" की समस्या को शामिल किया, जो आदर्श $O(\sqrt{N/M})$ मामले की तुलना में क्वेरी जटिलता को बढ़ाता है।
हार्डवेयर यथार्थवाद (Hardware Realism): रिएक्शन टाइम (1 $\mu$ s), कोड साइकिल (100 ns), और मल्टी-लेवल मैजिक स्टेट डिस्टिलेशन जैसे वास्तविक मापदंडों को शामिल करके, यह अध्ययन सैद्धांतिक "टॉय" मॉडलों से आगे बढ़ता है।

4. मुख्य परिणाम (Key Results)

महत्वपूर्ण आयाम $D=400$ (NIST लेवल 1 सुरक्षा मानकों को तोड़ने के लिए आवश्यक) के लिए परिणाम स्पष्ट हैं:

भौतिक क्यूबिट्स (Physical Qubits): आशावादी धारणाओं के तहत भी, सर्वोत्तम क्वांटम सीविंग एल्गोरिदम (Spherical LSF के साथ GaussSieve) को लगभग $10^{13}$ भौतिक क्यूबिट्स की आवश्यकता होती है।
- ब्रेकडाउन: इनमें से अधिकांश क्यूबिट्स उम्मीदवार वेक्टर सूचियों को संग्रहीत करने के लिए आवश्यक QRAM इंफ्रास्ट्रक्चर के लिए समर्पित हैं।
निष्पादन समय (Execution Time): $D=400$ $D = 400$ पर SVP को हल करने के लिए अनुमानित समय लगभग $10^{31}$ वर्ष है।
- यह अवधि ब्रह्मांड की आयु ( $\approx 1.38 \times 10^{10}$ वर्ष) से कहीं अधिक लंबी है।
क्लासिकल से तुलना: समान कार्य (अनुक्रमिक खोज) करने वाला एक एकल-कोर क्लासिकल कंप्यूटर (6 GHz) भी लगभग $10^{31}$ वर्ष ही लेगा।
- निष्कर्ष: क्रिप्टोग्राफिक आयामों पर कोई व्यावहारिक क्वांटम गति (practical quantum speedup) नहीं है। ग्रोवर के एल्गोरिदम से मिलने वाली द्विघात गति, QRAM, एरर करेक्शन और अंकगणित के ओवरहेड द्वारा पूरी तरह से समाप्त हो जाती है।
स्केलिंग (Scaling): क्वांटम लाभ (जहाँ क्वांटम समय < क्लासिकल समय) केवल $D=1000$ से परे के आयामों में दिखाई देता है, जहाँ क्वांटम स्पीडअप फैक्टर $\approx 10^5$ तक पहुँच जाता है, लेकिन पूर्ण समय अभी भी खगोलीय बना रहता है और क्यूबिट की आवश्यकताएं अव्यवहारिक रहती हैं।
डेप्थ बाधाएं (Depth Constraints): NIST द्वारा प्रस्तावित डेप्थ सीमाओं (जैसे, $2^{40}$ गेट्स) द्वारा सीमित होने पर, भौतिक क्यूबिट्स की संख्या कम हो जाती है, लेकिन निष्पादन समय और बढ़ जाता है, जो लाभ की कमी को पुष्ट करता है।

5. महत्व और निहितार्थ (Significance and Implications)

लैटिस क्रिप्टोग्राफी की सुरक्षा: यह शोध पत्र इस बात का पुख्ता प्रमाण प्रदान करता है कि लैटिस-आधारित क्रिप्टोग्राफी (विशेष रूप से SVP-आधारित योजनाएं) वर्तमान और निकट भविष्य की क्वांटम तकनीकों के खिलाफ सुरक्षित है। इन मानकों के लिए "क्वांटम खतरा" शास्त्रीय खतरों की तुलना में नगण्य है।
QRAM बाधा: अध्ययन इस बात पर प्रकाश डालता है कि जब तक QRAM आर्किटेक्चर में कोई बड़ी सफलता (इसे क्यूबिट्स और डेप्थ के मामले में काफी सस्ता बनाना) नहीं आती, तब तक बड़े डेटाबेस लुकअप (जैसे सीविंग) पर निर्भर क्वांटम एल्गोरिदम व्यावहारिक नहीं होंगे।
संसाधन अनुमान मानक: यह शोध पत्र सरल गेट काउंट से हटकर एरर करेक्शन और मेमोरी लागत सहित पूर्ण-स्टैक भौतिक संसाधन मॉडलिंग की ओर बढ़ते हुए, क्वांटम क्रिप्टोएनालिसिस में संसाधन अनुमान के लिए एक नया मानक स्थापित करता है।
भविष्य की दिशाएं: लेखक नोट करते हैं कि हालांकि उनका विश्लेषण वर्तमान प्रोटोकॉल के संबंध में निराशावादी है, क्वांटम रैंडम वॉक या नए हार्डवेयर आर्किटेक्चर में महत्वपूर्ण सैद्धांतिक सफलताएं परिदृश्य को बदल सकती हैं। हालाँकि, ऐसी सफलताओं को $10^{13}$ क्यूबिट बाधा को पार करने के लिए बहुत बड़ा होना होगा।

संक्षेप में, शोध पत्र यह निष्कर्ष निकालता है कि क्रिप्टोग्राफिक रूप से प्रासंगिक आयामों में SVP को हल करने के लिए ग्रोवर का सर्च व्यावहारिक लाभ बहुत कम या बिल्कुल नहीं देता है, क्योंकि एरर करेक्शन और QRAM की अत्यधिक लागत है, जो यह सुझाव देती है कि लैटिस-आधारित क्रिप्टोग्राफी भविष्य के क्वांटम हमलों के खिलाफ मजबूत है।