⚛️ quantum physics

Quantum algorithm for Discrete Gaussian Sampling

यह शोध पत्र डिस्क्रीट गॉसियन सैंपलिंग के लिए एक क्वांटम एल्गोरिदम प्रस्तुत करता है जो शास्त्रीय विधियों पर एसिम्प्टोटिक क्वाड्रेटिक स्पीडअप (asymptotic quadratic speedup) प्राप्त करता है, जिससे बेहतर क्वांटम ड्यूल हमलों को सक्षम बनाया जा सके और शॉर्ट इंटीजर सॉल्यूशन समस्या के समाधानों में तेजी लाई जा सके।

मूल लेखक: Clémence Chevignard, Yixin Shen, André Schrottenloher

प्रकाशित 2026-05-20

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

CC BY 4.0

मूल लेखक: Clémence Chevignard, Yixin Shen, André Schrottenloher

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

एक बड़ी तस्वीर: क्वांटम घास के ढेर में सुई ढूँढना

कल्पना कीजिए कि आप एक बहुत ही कठिन पहेली को हल करने की कोशिश कर रहे हैं जिसमें एक विशाल, बहु-आयामी ग्रिड (जिसे लैटिस/lattice कहा जाता है) शामिल है। आधुनिक क्रिप्टोग्राफी की दुनिया में, इन ग्रिडों का उपयोग रहस्यों को लॉक करने के लिए किया जाता है। इन तालों को तोड़ने के लिए (या नए बनाने के लिए), आपको ग्रिड पर विशिष्ट बिंदुओं को खोजना होता है जो एक लक्ष्य स्थान के बहुत करीब हों।

समस्या यह है कि आप जिन बिंदुओं को खोज रहे हैं वे बेतरतीब ढंग से बिखरे हुए नहीं हैं। वे एक विशिष्ट पैटर्न का पालन करते हैं जिसे डिस्क्रीट गॉसियन डिस्ट्रीब्यूशन (Discrete Gaussian distribution) कहा जाता है। इसे एक 'बेल कर्व' (bell curve) की तरह समझें: केंद्र में स्थित बिंदु बहुत आम होते हैं, लेकिन जैसे-जैसे आप दूर जाते हैं, वे अविश्वसनीय रूप से दुर्लभ होते जाते हैं।

चुनौती:
इन दुर्लभ बिंदुओं को खोजना समुद्र तट से रेत का एक विशिष्ट कण चुनने जैसा है, लेकिन वह समुद्र तट एक पहाड़ के आकार का है, और आप केवल उन कणों को चाहते हैं जो बिल्कुल शिखर पर हैं।

क्लासिकल कंप्यूटर: वर्तमान में इसे करने का सबसे अच्छा तरीका समुद्र तट के चारों ओर घूमना और रेत के हर कण की एक-एक करके जांच करना है। यह धीमा है। यदि आप बहुत सटीक होना चाहते हैं, तो इसमें बहुत अधिक समय लगता है।
लेखकों का लक्ष्य: वे एक "क्वांटम जादुई छड़ी" बनाना चाहते थे जो इन कणों को बहुत तेज़ी से खोज सके।

समाधान: एक क्वांटम "रिजेक्शन सैंपलिंग" ट्रिक

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

1. शुरुआती बिंदु: "क्लेन सैंपलर" (The Klein Sampler)

सबसे पहले, उन्होंने उन्हें आवश्यक बिंदुओं का एक "रफ ड्राफ्ट" तैयार करने के लिए एक मौजूदा विधि (क्लेन सैंपलर) का उपयोग किया।

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

2. क्वांटम फ़िल्टर: "रिजेक्शन सैंपलिंग" (Rejection Sampling)

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

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

हमले (और बचाव) के दो नए तरीके

लेखकों ने न केवल उपकरण बनाया; उन्होंने यह भी दिखाया कि इस उपकरण का उपयोग क्रिप्टोग्राफिक पहेलियों (LWE और SIS) के दो विशिष्ट प्रकारों को तोड़ने के लिए कैसे किया जा सकता है। उन्होंने अपने नए इंजन का उपयोग करके दो अलग-अलग "वाहन" बनाए:

वाहन 1: स्पीड डेमन (Speed Demon - गति का दैत्य) (इसके लिए "क्वांटम RAM" की आवश्यकता है)

यह कैसे काम करता है: यह संस्करण हमले के पहले चरण को तेज करने के लिए नए क्वांटम सैंपलर का उपयोग करता है।
कैच (शर्त): इसके लिए एक विशाल मात्रा में "क्वांटम RAM" (एक सैद्धांतिक मेमोरी बैंक जो डेटा की विशाल मात्रा को रख सकता है और जिसे क्वांटम कंप्यूटर द्वारा तुरंत एक्सेस किया जा सकता है) की आवश्यकता होती है।
उपमा: यह एक फॉर्मूला 1 कार की तरह है। यह अविश्वसनीय रूप से तेज़ है, लेकिन इसे चलाने के लिए एक बहुत ही महंगी, हाई-टेक ट्रैक (क्वांटम RAM) की आवश्यकता होती है। यदि आपके पास ट्रैक नहीं है, तो आप इसे चला नहीं सकते।

वाहन 2: एफिशिएंट हाइकर (Efficient Hiker - कुशल पदयात्री) (इसमें क्वांटम RAM की आवश्यकता नहीं है)

यह कैसे काम करता है: यह संस्करण अधिक चतुर है। एक विशाल मेमोरी बैंक में सारा डेटा स्टोर करने के बजाय, यह क्वांटम सैंपलर और एक "मीन एस्टिमेशन" (mean estimation) ट्रिक का उपयोग करके डेटा की गणना ऑन-द-फ्लाई (on the fly) करता है।
लाभ: इसे केवल बहुत कम मेमोरी (पॉलीनोमियल मेमोरी) की आवश्यकता होती है, जो भविष्य के क्वांटम कंप्यूटरों के लिए बहुत अधिक वास्तविक है।
समझौता: यह स्पीड डेमन की तुलना में थोड़ा धीमा है, लेकिन इसे उस असंभव क्वांटम RAM की आवश्यकता नहीं है जिसे बनाना बहुत कठिन है।
उपमा: यह एक हाई-टेक माउंटेन बाइक की तरह है। यह फॉर्मूला 1 कार जितनी तेज़ नहीं है, लेकिन आप इसे लगभग किसी भी रास्ते पर चला सकते हैं, और आपको किसी विशेष ट्रैक की आवश्यकता नहीं है।

यह क्यों मायने रखता है?

यह शोध पत्र सैद्धांतिक गति (theoretical speedups) पर केंद्रित है। लेखक यह नहीं कह रहे हैं कि "हमने आज इंटरनेट की सुरक्षा को तोड़ दिया है।" इसके बजाय, वे कह रहे हैं:

हमने गणित करने का एक तेज़ तरीका खोजा है: उन्होंने सिद्ध किया कि इन विशिष्ट लैटिस समस्याओं के लिए, एक क्वांटम कंप्यूटर क्लासिकल कंप्यूटर की तुलना में लगभग $\sqrt{N}$ गुना तेज़ी से काम कर सकता है (जहाँ $N$ आवश्यक कार्य है)।
हमारे पास विकल्प हैं: उन्होंने इस गति को लागू करने के दो अलग-अलग तरीके दिखाए। एक तेज़ है लेकिन मेमोरी-गहन (memory-hungry) है; दूसरा मेमोरी-कुशल है लेकिन थोड़ा धीमा है।
भविष्य के लिए तैयारी (Future Proofing): क्रिप्टोग्राफर्स को यह जानने की ज़रूरत है कि भविष्य के क्वांटम कंप्यूटरों के खिलाफ उनके ताले कितने मजबूत हैं। यह शोध पत्र उन्हें एक बेहतर "तनाव परीक्षण" (stress test) प्रदान करता है ताकि वे देख सकें कि उनका एन्क्रिप्शन कितने समय तक सुरक्षित रहेगा।

एक वाक्य में सारांश

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

तकनीकी सारांश: डिस्क्रीट गॉसियन सैंपलिंग के लिए क्वांटम एल्गोरिदम

समस्या विवरण
लैटिस पर डिस्क्रीट गॉसियन सैंपलिंग (DGS) लैटिस-आधारित क्रिप्टोग्राफी में एक मौलिक समस्या है, जो दोनों क्रिप्टोग्राफिक प्रिमिटिव्स (जैसे, "हैश-एंड-साइन" डिजिटल सिग्नेचर) और क्रिप्टोएनालिसिस (जैसे, शॉर्टेस्ट वेक्टर प्रॉब्लम, लर्निंग विद एरर्स (LWE), और शॉर्ट इंटीजर सॉल्यूशन (SIS) को हल करना) के लिए एक मुख्य घटक के रूप में कार्य करती है। कार्य में एक लैटिस वेक्टर $x$ को इस प्रकार सैंपल करना शामिल है जिसकी प्रायिकता $e^{-\pi\|x-c\|^2/\sigma^2}$ के समानुपाती हो। जैसे-जैसे चौड़ाई पैरामीटर $\sigma$ घटता है, विशेष रूप से "स्मूथिंग पैरामीटर" से नीचे, सैंपलिंग की कठिनाई बढ़ती जाती है।

मौजूदा शास्त्रीय एल्गोरिदम महत्वपूर्ण ट्रेड-ऑफ का सामना करते हैं:

क्लेन सैंपलर (Klein Sampler): कुशल (पॉलीनोमियल समय) है लेकिन बड़े $\sigma$ मानों तक सीमित है जो इनपुट बेसिस की गुणवत्ता पर निर्भर करता है।
मार्कोव चेन मोंटे कार्लो (MCMC) [49]: किसी भी $\sigma$ के लिए काम करता है लेकिन उच्च समय जटिलता (time complexity) से ग्रस्त है, जो एक पैरामीटर $\Delta$ (गॉसियन द्रव्यमान के अनुपात से संबंधित) के व्युत्क्रमानुपाती स्केल करता है, जिससे यह सबसे खराब स्थिति में घातांकीय (exponential) हो जाता है।
घातांकीय मेमोरी एल्गोरिदम (Exponential Memory Algorithms): [3] जैसे एल्गोरिदम किसी भी $\sigma$ के लिए सैंपल कर सकते हैं लेकिन उन्हें घातांकीय मेमोरी की आवश्यकता होती है, जिससे वे क्रिप्टोएनालिसिस के लिए अव्यवहारिक हो जाते हैं।

वर्तमान में, कोई ज्ञात क्वांटम एल्गोरिदम इन सैंपलिंग विधियों के लिए स्पीडअप प्रदान नहीं करता है जो अनैतिक संसाधनों जैसे कि क्वांटम रैंडम एक्सेस मेमोरी (qRAM) पर निर्भर न हो, या वे MCMC दृष्टिकोण की एसिम्प्टोटिक जटिलता में सुधार करने में विफल रहते हैं।

कार्यप्रणाली (Methodology)
लेखक क्वांटम रिजेक्शन सैंपलिंग [41] पर आधारित DGS के लिए एक क्वांटम एल्गोरिदम प्रस्तावित करते हैं। मुख्य रणनीति एक ज्ञात वितरण द्वारा तैयार की गई क्वांटम अवस्था को एम्प्लीट्यूड एम्प्लीफिकेशन के माध्यम से लक्षित वितरण में बदलना है।

प्रारंभिक अवस्था तैयारी (क्वांटम क्लाइन सैंपलर): एल्गोरिदम क्लाइन वितरण के एक संस्करण के अनुरूप एक क्वांटम अवस्था $|q\rangle$ तैयार करके शुरू होता है। इसे शास्त्रीय क्लाइन सैंपलिंग एल्गोरिदम (एल्गोरिदम 1) को क्वांटम सर्किट (एल्गोरिदम 2) में अनुकूलित करके प्राप्त किया जाता है, जैसा कि [11] में विस्तृत है। यह चरण लैटिस वेक्टर्स का एक सुपरपोजिशन बनाता है जहाँ एम्प्लीट्यूड क्लाइन वितरण के सन्निकटन (approximate) करते हैं।
एम्प्लीट्यूड ट्रांसडक्शन (Amplitude Transduction): एल्गोरिदम अवस्था $|q\rangle$ के एम्प्लीट्यूड को संशोधित करने के लिए एक यूनिटरी ऑपरेशन का उपयोग करता है। यह लक्षित डिस्क्रीट गॉसियन वितरण $D_{\Omega, \sigma}$ और प्रारंभिक क्लाइन वितरण $q$ के बीच के अनुपात की गणना करता है। इसमें Kitaev और Webb [31] तथा de Boer [10] की तकनीकों का उपयोग करके परिमित अंतराल पर गॉसियन द्रव्यमान का अनुमान लगाना शामिल है।
क्वांटम रिजेक्शन सैंपलिंग: गणना किए गए अनुपात का उपयोग करते हुए, एल्गोरिदम एक एंसिलर क्यूबिट (ancilla qubit) पर एम्प्लीट्यूड ट्रांसडक्शन लागू करता है। इसके बाद अवस्था को क्वांटम एम्प्लीट्यूड एम्प्लीफिकेशन (QAA) [17] का उपयोग करके "एक्सेप्ट" सबस्पेस पर प्रोजेक्ट किया जाता है। आवश्यक पुनरावृत्तियों (iterations) की संख्या रिजेक्शन रेशियो $w = \max_x (D_2(x)/D_1(x))$ के वर्गमूल के समानुपाती है।
परिशुद्धता और सन्निकटन (Precision and Approximation): एल्गोरिदम अनुमानित वितरण अवस्थाओं $|D \pm 2^{-\nu}\rangle$ के साथ काम करता है। लेखक आदर्श डिस्क्रीट गॉसियन वितरण और आउटपुट अवस्था के बीच टोटल वेरिएशन डिस्टेंस को कड़ाई से बांधते (bound) हैं, यह सुनिश्चित करते हुए कि परिमित डोमेन आकार $M$ और परिशुद्धता $\nu$ को चुनकर त्रुटि नगण्य हो।

मुख्य योगदान
पेपर तीन प्राथमिक योगदान प्रस्तुत करता है:

DGS जटिलता में एक द्विघातीय (Quadratic) स्पीडअप: लेखक एक क्वांटम एल्गोरिदम प्रदर्शित करते हैं जो एक डिस्क्रीट गॉसियन वितरण से सैंपल करता है और शास्त्रीय MCMC एल्गोरिदम [49] पर एक एसिम्प्टोटिक द्विघातीय स्पीडअप प्रदान करता है। जबकि शास्त्रीय जटिलता $O(1/\Delta)$ के रूप में स्केल करती है, क्वांटम जटिलता $O(1/\sqrt{\Delta})$ के रूप में स्केल करती है, जहाँ $\Delta$ गॉसियन द्रव्यमान का अनुपात है। यह स्पीडअप बिना किसी घातांकीय क्वांट मेमोरी की आवश्यकता के प्राप्त किया गया है, केवल पॉलीनोमियल क्यूबिट्स का उपयोग करके (हालांकि विशिष्ट हमलों के लिए शास्त्रीय मेमोरी एक्सेस के लिए qRAM पर निर्भर हो सकता है)।
LWE पर क्वांटम डुअल हमलों के दो वेरिएंट: लेखक अपने सैंपलर को LWE पर "आधुनिक" डुअल अटैक फ्रेमवर्क [42] पर लागू करते हैं, दो अलग-अलग क्वांटम संस्करण प्रस्तावित करते हैं:
- वेरिएंट 1 (qRAM के साथ): हमले के पहले चरण में शास्त्रीय MCMC सैंपलिंग चरण को क्वांटम सैंपलर से बदल देता है। यह सैंपलिंग चरण में द्विघातीय स्पीडअप देता है, लेकिन दूसरे चरण (FFT-आधारित डिस्टिंग्विशर) में qRAM की आवश्यकता को बरकरार रखता है।
- वेरिएंट 2 (बिना qRAM के): एक अभिनव दृष्टिकोण जो हमले के दूसरे चरण में सीधे क्वांटम सैंपलर को एकीकृत करता है। क्वांटम मीन एस्टीमेशन एल्गोरिदम (अनुवर्ती 1) के साथ सैंपलर को जोड़कर, यह वेरिएंट पूरी तरह से qRAM की आवश्यकता को समाप्त करता है, जिसमें केवल पॉलीनोमियल क्लासिकल और क्वांटम मेमोरी की आवश्यकता होती है। हालांकि इसमें वेरिएंट 1 की तुलना में उच्च समय जटिलता है, यह मेमोरी बाधाओं के मामले में एक अलग लाभ प्रदान करता है।
SIS के लिए क्वांटम स्पीडअप: लेखक किसी भी नॉर्म (norm) के लिए SIS समस्या को हल करने वाले एल्गोरिदम [12] पर अपने सैंपलर को लागू करते हैं। शॉर्ट वेक्टर्स को फिल्टर करने के लिए सैंपलिंग स्टेप को क्वांटाइज करके और एम्प्लीट्यूड एम्प्लीफिकेशन लागू करके, वे शास्त्रीय समकक्ष (BKZ प्रीप्रोसेसिंग स्टेप को छोड़कर) पर द्विघातीय स्पीडअप प्राप्त करते हैं।

परिणाम और जटिलता विश्लेषण

सैंपलिंग जटिलता: प्रस्तावित क्वांटम सैंपलर लगभग $\tilde{O}(mM(\nu + mM + m^2r)^2)$ गेट काउंट और $\tilde{O}(m(\nu + mM + m^2r))$ क्यूबिट काउंट प्राप्त करता है, जहाँ $m$ लैटिस डायमेंशन है। जटिलता शास्त्रीय MCMC लागत के वर्गमूल द्वारा संचालित होती है।
LWE डुअल अटैक्स:
- qRAM-आधारित वेरिएंट शास्त्रीय MCMC-आधारित हमले की तुलना में हमले की जटिलता में $\sqrt{\Delta}$ के कारक से सुधार करता है।
- qRAM-मुक्त वेरिएंट एक मेमोरी-कुशल विकल्प प्रदान करता है, जो घातांकीय शास्त्रीय मेमोरी आवश्यकताओं को समाप्त करने के लिए समय (time) का व्यापार करता है।
Dilithium पर SIS: पेपर Dilithium सिग्नेचर स्कीम में SIS समस्या पर हमला करने की क्वांटम जटिलता के लिए मोटे अनुमान प्रदान करता है। परिणाम (तालिका 2) दर्शाते हैं कि जबकि क्वांटम हमला शास्त्रीय हमलों की तुलना में समय जटिलता को काफी कम कर देता है (उदाहरण के लिए, NIST लेवल 2 के लिए $\log_2 T_{attack}$ को 202 से घटाकर 146 करना), जटिलता अभी भी BKZ बेसिस रिडक्शन प्रीप्रोसेसिंग स्टेप द्वारा भारी रूप से बाधित है।

महत्व और दावे
लेखक इस कार्य को "क्वांटम क्रिप्टोएनालिसिस टूलबॉक्स" के विस्तार के रूप में देखते हैं। वे स्पष्ट रूप से स्वीकार करते हैं कि qRAM बनाए रखने की अंतर्निहित लागत और ग्रोवर सर्च की क्रमिक प्रकृति के कारण प्रस्तुत एसिम्प्टोटिक स्पीडअप को व्यवहार में लागू करना कठिन हो सकता है। पेपर किसी विशिष्ट NIST मानक को तुरंत तोड़ने का दावा नहीं करता है, बल्कि सैद्धांतिक सीमाएं और एल्गोरिथम सुधार प्रदान करता है।

महत्व इस प्रकार है:

लागू होने योग्य मापदंडों के शासन (regimes) में डिस्क्रीट गॉसियन सैंपलिंग के लिए पहला ज्ञात क्वांटम स्पीडअप प्रदान करना जो लैटिस-आधारित क्रिप्टोएनालिसिस में उपयोग किए जाते हैं।
यह प्रदर्शित करना कि क्वांटम तकनीकों को डुअल हमलों में मेमोरी आवश्यकताओं को कम करने के लिए अनुकूलित किया जा सकता है, जो मेमोरी बनाम समय के क्रिप्टोएनालिटिक ट्रेड-ऑफ के लिए एक नया आयाम प्रदान करता है।
उन एल्गोरिदम को क्वांटाइज करने के लिए एक ढांचा स्थापित करना जो MCMC सैंपलिंग पर निर्भर करते हैं, जो LWE और SIS के अलावा अन्य लैटिस समस्याओं के लिए भी लागू हो सकता है।

लेखक निष्कर्ष निकालते हैं कि हालांकि व्यावहारिक कार्यान्वयन विवरण (डेप्थ, गैर-एसिम्प्टोटिक गेट काउंट) भविष्य के कार्य के लिए छोड़ दिए गए हैं, फिर भी सैद्धांतिक परिणाम लैटिस समस्याओं की क्वांटम कठोरता (hardness) को समझने के लिए एक कठोर आधार प्रदान करते हैं।