⚛️ quantum physics

On the Quantum Equivalence between $S|LWE\rangle$ and $ISIS$

यह शोध पत्र इनहोमोजेनियस शॉर्ट इंटीजर सॉल्यूशन ($ISIS $) समस्या से क्वांटम$ S|LWE\rangle$ समस्या तक पहला पूर्णतः जेनेरिक रिडक्शन स्थापित करता है और एक सशर्त रिवर्स रिडक्शन को प्रदर्शित करता है, जिससे इन दोनों मौलिक क्वांटम क्रिप्टोग्राफिक समस्याओं के बीच तुल्यता परिदृश्य स्पष्ट होता है और शेष बाधाओं की पहचान होती है।

मूल लेखक: André Chailloux, Paul Hermouet

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

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

CC BY 4.0

मूल लेखक: André Chailloux, Paul Hermouet

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

कल्पना कीजिए कि आप एक विशाल, जटिल पहेली को हल करने की कोशिश कर रहे हैं। क्रिप्टोग्राफी की दुनिया में, दो बहुत प्रसिद्ध प्रकार की पहेलियाँ हैं: ISIS और S|LWE⟩।

ISIS एक "सर्च" (खोज) पहेली की तरह है। आपको एक उलझी हुई समीकरण दी जाती है और एक लक्ष्य संख्या दी जाती है, और आपको संख्याओं का एक विशिष्ट सेट खोजना होता है जो उस समीकरण को सही साबित करे।
S|LWE⟩ एक "क्वांटम" पहेली है। केवल संख्याएँ देने के बजाय, कोई आपको एक विशेष, धुंधला क्वांटम सिक्का (एक सुपरपोजिशन) थमाता है जिसमें छिपी हुई जानकारी होती है। आपका काम उस धुंधले सिक्के के भीतर छिपे गुप्त कोड को समझना है।

लंबे समय तक, शोधकर्ताओं को पता था कि ये दोनों पहेलियाँ आपस में जुड़ी हुई हैं, लेकिन यह संबंध बहुत उलझा हुआ था। कुछ लोग एक पहेली के समाधान को दूसरी में बदल सकते थे, लेकिन केवल तभी जब समाधान एकदम सटीक हो। यदि समाधान में थोड़ा सा भी "शोर" (noise) या त्रुटि होती, तो वह पुल ढह जाता।

आंद्रे चैलौक्स (André Chailloux) और पॉल हर्मोएट (Paul Hermouet) द्वारा लिखित यह शोध पत्र इन दोनों पहेलियों के बीच एक मजबूत, सुदृढ़ पुल बनाता है। उन्होंने इसे कैसे किया, इसके लिए यहाँ कुछ रोजमर्रा के उदाहरण दिए गए हैं:

1. एकतरफा पुल (ISIS से S|LWE⟩ तक)

समस्या: "सर्च" पहेली (ISIS) के समाधान को "क्वांटम" पहेली (S|LWE⟩) में बदलने के पिछले प्रयास नाजुक थे। यदि सर्च एल्गोरिदम में कोई गलती होती या वह पूर्ण नहीं होता, तो क्वांटम समाधान विफल हो जाता।

शोध पत्र का समाधान: लेखकों ने एक नया पुल बनाया जो त्रुटियों के प्रति लचीला (robust to errors) है।

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

2. दोतरफा पुल (S|LWE⟩ से वापस ISIS तक)

समस्या: विपरीत दिशा और भी कठिन थी। क्या आप एक क्वांटम सिक्के (S|LWE⟩) को लेकर वापस एक मानक खोज पहेली (ISIS) में बदल सकते हैं?

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

शोध पत्र का समाधान: उन्होंने एक बिचौलिया पेश किया, एक "सहायक पहेली" जिसे IC|LWE⟩ कहा जाता है।

उदाहरण: क्वांटम सिक्के को एक ताले लगे सेफ (तिजोरी) के रूप में सोचें। आप इसे सीधे नहीं खोल सकते। लेकिन, यदि आपके पास एक विशिष्ट प्रकार की चाबी (IC|LWE⟩ समस्या) है, तो आप सेफ को खोल सकते हैं।
शर्त: इस चाबी का उपयोग करने के लिए, "सर्च" एल्गोरिदम (ISIS) को बहुत ईमानदार होना चाहिए। उसे न केवल उत्तर खोजना चाहिए, बल्कि यह भी बताने में सक्षम होना चाहिए कि उसने वह उत्तर कैसे पाया (वह "रैंडमनेस" या चरण जो उसने लिए)। यदि एल्गोरिदम एक "ब्लैक बॉक्स" है जो बिना अपने चरणों को समझाए उत्तर देता है, तो यह पुल अभी काम नहीं करेगा।
परिणाम: उन्होंने सिद्ध किया कि यदि आपके पास एक "ईमानदार" सर्च एल्गोरिदम है, तो आप निश्चित रूप से क्वांटम सिक्का बना सकते हैं।

3. "दो की शक्ति" (Power of Two) वाला तरीका

लेखकों ने एक विशिष्ट प्रकार की पहेली के साथ अपने सिद्धांत का परीक्षण किया जहाँ संख्याएँ 2 की घातें (जैसे 2, 4, 8, 16...) हैं।

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

4. यह क्यों महत्वपूर्ण है (बड़ी तस्वीर)

इस शोध पत्र से पहले, इन पहेलियों के बीच का संबंध एक ऐसे एकतरफा रास्ते जैसा था जिसके बीच में एक टूटा हुआ पुल था।

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

मुख्य निष्कर्ष (The Bottom Line):
यह शोध पत्र केवल यह नहीं कहता कि "ये संबंधित हैं।" यह उनके बीच रूपांतरण करने के लिए वास्तविक मशीनरी का निर्माण करता है। यह स्पष्ट करता है कि क्वांटम पहेली की कठिनाई कोई जादुई, अ объясने योग्य (unexplainable) शक्ति नहीं है; यह मानक सर्च पहेली की कठिनाई से गहराई से जुड़ी हुई है। यदि हम सर्च पहेली को कुशलतापूर्वक हल कर सकते हैं, तो हमारे पास क्वांटम पहेली को भी हल करने के उपकरण होने की संभावना है, बशर्ते हम अपने एल्गोरिदम को "ईमानदार" बनाने में सक्षम हों ताकि वे पुल के नियमों का पालन कर सकें।

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

तकनीकी सारांश: S|LWE⟩ और ISIS के बीच क्वांटम तुल्यता पर

1. समस्या विवरण और संदर्भ

यह शोध पत्र लैटिस-आधारित क्रिप्टोग्राफी की दो मौलिक समस्याओं: इनहोमोजेनियस शॉर्ट इंटीजर सॉल्यूशन (ISIS) और क्वांटम सर्च-LWE (S|LWE⟩) के बीच कम्प्यूटेशनल संबंध की जांच करता है।

ISIS: एक मैट्रिक्स $A \in \mathbb{Z}_q^{n \times m}$ और एक लक्ष्य वेक्टर $y \in \mathbb{Z}_q^n$ दिया गया है, एक विशिष्ट सेट $T$ में एक लघु वेक्टर $x$ खोजें ताकि $Ax = y \pmod q$ हो।
S|LWE⟩: एक क्वांटम अवस्था $|\psi_s\rangle = \sum_{e} f(e) |A^T s + e\rangle$ दी गई है, जहाँ $s$ एक गुप्त वेक्टर है और $f$ एक एम्प्लीट्यूड फंक्शन है, जिससे गुप्त $s$ को रिकवर किया जाता है। यह समस्या त्रुटियों (errors) के साथ क्वांटम सुपरपोजिशन में LWE का प्रतिनिधित्व करती है।

चेन, लियू और ज़ैंडरी [CLZ22] द्वारा पूर्व कार्य में ISIS के लिए क्वांटम एल्गोरिदम बनाने हेतु S|LWE⟩ को पेश किया गया था। हालांकि विशिष्ट रिडक्शन मौजूद थे (जैसे, प्रतिबंधात्मक धारणाओं के तहत ISIS से S|LWE⟩ तक, या मध्यवर्ती कोडिंग समस्याओं के माध्यम से), सामान्य तुल्यता और एल्गोरिदम संबंधी त्रुटियों की उपस्थिति में इन रिडक्शन की मजबूती स्पष्ट नहीं थी। विशेष रूप से, दो खुले प्रश्न रखे गए थे:

क्या ISIS से S|LWE⟩ तक एक पूर्णतः जेनेरिक रिडक्शन है जो S|LWE⟩ सॉल्वर में त्रुटियों के प्रति सुदृढ़ (robust) हो?
क्या ISIS के एल्गोरिदम से S|LWE⟩ के लिए एल्गोरिदम का निर्माण किया जा सकता है, जो कि एक प्रकार की तुल्यता का संकेत देता है?

2. कार्यप्रणाली और मुख्य योगदान

लेखक ISIS और S|LWE⟩ के बीच एक द्विदिश (bidirectional) रिडक्शन फ्रेमवर्क स्थापित करते हैं, जिसमें रिवर्स दिशा को सुगम बनाने के लिए एक मध्यवर्ती समस्या IC|LWE⟩ (इनहोमोजेनियस कंस्ट्रक्ट-LWE) को पेश किया गया है।

2.1 फॉरवर्ड रिडक्शन: ISIS $\to$ S|LWE⟩

यह शोध पत्र ISIS से S|LWE⟩ तक का पहला पूर्णतः जेनेरिक रिडक्शन प्रस्तुत करता है।

[CT25] में सुधार: पिछले रिडक्शन के लिए S|LWE⟩ सॉल्वर के बारे में विशिष्ट धारणाओं की आवश्यकता थी (जैसे, वे स्थितियाँ जो क्लासिकल एल्गोरिदम द्वारा संतुष्ट की जाती हैं लेकिन आवश्यक रूप से क्वांटम द्वारा नहीं)। यह कार्य उन बाधाओं को हटाता है, जिससे यह रिडक्शन किसी भी क्वांटम एल्गोरिदम के लिए वैध हो जाता है जो S|LWE⟩ को हल करता है, भले ही उसमें गैर-नगण्य (non-negligible) त्रुटियां हों।
त्रुटि विश्लेषण (Error Analysis): लेखक त्रुटियों का अधिक सटीक विश्लेषण करते हैं। केवल सफलता की संभावना पर निर्भर त्रुटि पद जोड़ने के बजाय, वे अंतिम सफलता संभावना सीमा में त्रुटि वेक्टर्स की संरचना को एकीकृत करते हैं।
परिणाम: यदि एक कुशल क्वांटम एल्गोरिदम सफलता की संभावना $p$ के साथ S|LWE⟩ $(A, f)$ को हल करता है और $f$ के फूरियर ट्रांसफॉर्म का सपोर्ट $T$ (एक छोटी त्रुटि $\eta$ तक) के भीतर समाहित है, तो ISIS $(A, T)$ के लिए एक कुशल एल्गोरिदम बनाया जा सकता है। सफलता की संभावना $p(1-\eta) - 2\sqrt{p(1-p)\eta}$ द्वारा सीमित है।

2.2 रिवर्स रिडक्शन: S|LWE⟩ $\to$ ISIS

रिवर्स दिशा अधिक जटिल है और इसे IC|LWE⟩ नामक मध्यवर्ती समस्या के माध्यम से एक सशर्त रिडक्शन द्वारा प्राप्त किया जाता है।

IC|LWE⟩ की परिभाषा: एक वेक्टर $y$ दिया गया है, यूनिटरी अवस्था $|y\rangle|0\rangle \to |y\rangle|W_y\rangle$ का निर्माण करें, जहाँ $|W_y\rangle$ एम्प्लीट्यूड फंक्शन के फूरियर ट्रांसफॉर्म द्वारा भारित (weighted) $Ax=y$ के समाधानों का एक सुपरपोजिशन है।
चरण 1: S|LWE⟩ $\to$ IC|LWE⟩: लेखक सिद्ध करते हैं कि IC|LWE⟩ के लिए एक कुशल एल्गोरिदम, S|LWE⟩ के लिए एक कुशल एल्गोरिदम की ओर ले जाता है। यह रिडक्शन IC|LWE⟩ सॉल्वर में त्रुटियों के प्रति सुदृढ़ है और इसके लिए एल्गोरिदम के विशिष्ट गुणों की आवश्यकता नहीं है।
चरण 2: IC|LWE⟩ $\to$ ISIS (सशर्त): IC|LWE⟩ को ISIS तक कम करने के लिए, लेखक फुल-सपोर्ट रैंडमनेस-रिकवरेबल एल्गोरिदम की अवधारणा पेश करते हैं। एक ISIS एल्गोरिदम "रैंडमनेस-रिकवरेबल" है यदि समाधान उत्पन्न करने के लिए उपयोग किए गए आंतरिक रैंडम टेप को स्वयं समाधान से रिकवर किया जा सकता है। यह "फुल-सपोर्ट" है यदि आउटपुट वितरण सभी वैध समाधानों पर यूनिफॉर्म है।
प्रमेय: यदि ISIS के लिए एक कुशल क्लासिकल एल्गोरिदम मौजूद है जो पूर्णतः फुल-सपोर्ट और रैंडमनेस-रिकवरेबल दोनों है, तो IC|LWE⟩ (और फलस्वरूप S|LWE⟩) के लिए एक कुशल क्वांटम एल्गोरिदम मौजूद है।

2.3 इंस्टेंटिएशन और मौजूदा परिणामों की रिकवरी

रिवर्स रिडक्शन की व्यावहारिकता को प्रदर्शित करने के लिए, लेखक (रेगेव के कार्य और [CLZ22] से अनुकूलित) के एक ज्ञात क्लासिकल ISIS एल्गोरिदम के संशोधित संस्करण के साथ इसे इंस्टेंटिएट करते हैं।

संशोधन: वे क्लासिकल एल्गोरिदम को यह सुनिश्चित करने के लिए टवीक (tweak) करते हैं कि वह सख्त "रैंडमनेस-रिकवरेबल" और "फुल-सपोर्ट" शर्तों को पूरा करे।
पैरामीटर्स: यह इंस्टेंटिएशन विशेष रूप से तब काम करता है जब मोडुलस $q$ 2 की एक छोटी पावर ( $q=2^l$ ) हो।
परिणाम: अपने रिडक्शन चेन में इस संशोधित ISIS सॉल्वर को डालकर, वे बाई एट अल. [BJK+25] के परिणामों को रिकवर करते हैं, जिन्होंने $q=2^l$ के लिए सब-एक्सपोनेंशियल समय में चलने वाले S|LWE⟩ (EDCP समस्या के रूप में फ्रेम किया गया) के लिए एक क्वांटम एल्गोरिदम प्रस्तुत किया था।
तुलना: लेखक नोट करते हैं कि उनका दृष्टिकोण [BJK+25] की तुलना में संरचनात्मक रूप से सरल है, जो कई क्वांटम अवस्थाओं के पुनरावृत्त पेयरिंग और सीविंग (sieving) के बजाय, एक एकल ग्लोबल क्वांटम फूरियर ट्रांसफॉर्म (QFT) और ISIS सॉल्वर के कोहेरेंट अनुप्रयोग पर निर्भर करता है।

3. मुख्य परिणाम

जेनेरिक फॉरवर्ड रिडक्शन: ISIS से S|LWE⟩ तक एक सुदृढ़, त्रुटि-सहिष्णु (error-tolerant) रिडक्शन स्थापित किया गया है, जो किसी भी क्वांटम S|LWE⟩ सॉल्वर के लिए वैध है।
कंडीशनल रिवर्स रिडक्शन: एक रैंडमनेस-रिकवरेबल, फुल-सपोर्ट ISIS सॉल्वर के अस्तित्व पर निर्भर करते हुए, ISIS से S|LWE⟩ तक एक रिडक्शन सिद्ध किया गया है।
विशिष्ट मामलों के लिए तुल्यता: $q$ के 2 की पावर होने के मामले में, पेपर यह प्रदर्शित करता है कि S|LWE⟩ की हार्डनेस, ISIS की हार्डness से मजबूती से जुड़ी हुई है, क्योंकि एक के लिए मौजूद एल्गोरिदम को दूसरे में बदला जा सकता है।
मध्यवर्ती समस्या: IC|LWE⟩ की भूमिका को एक महत्वपूर्ण वैचारिक सेतु (conceptual bridge) के रूप में दिखाया गया है, जो इनहोमोजेनियस लैटिस समस्या और क्वांटम स्टेट कंस्ट्रक्शन समस्या के बीच संबंध को स्पष्ट करता है।

4. महत्व और दावे

यह पेपर S|LWE⟩ और ISIS के बीच "रिडक्शन के परिदृश्य" (landscape of reductions) को स्पष्ट करने का दावा करता है।

मजबूत संबंध: यह स्थापित करता है कि दोनों समस्याएं मजबूती से जुड़ी हुई हैं; विशेष रूप से, एक को हल करना (निर्धारित स्थितियों के तहत) दूसरे को हल करने की अनुमति देता है।
पूर्ण तुल्यता की बाधाएं: लेखक विनम्रतापूर्वक नोट करते हैं कि सभी मामलों के लिए पूर्ण तुल्यता अभी तक सिद्ध नहीं हुई है। रिवर्स रिडक्शन "रैंडमनेस-रिकवरेबल" ISIS एल्गोरिदम के अस्तित्व पर निर्भर है, जो एक सख्त गुण है और वर्तमान में केवल विशिष्ट पैरामीटर व्यवस्था (जैसे, $q=2^l$ ) के लिए प्रदर्शित किया गया है।
लॉसलेस रिडक्शन: पिछले रिडक्शन चेन्स (जैसे, S|LWE⟩ $\to$ LWE $\to$ SIS $\to$ ISIS) के विपरीत जो लॉसों (lossy) और वन-वे होते हैं, यहाँ प्रस्तुत रिडक्शन "लॉसलेस" हैं इस अर्थ में कि मैट्रिक्स $A$ अपरिवर्तित रहता है, और विशिष्ट व्यवस्थाओं में, फॉरवर्ड और रिवर्स रिडक्शन को मूल समस्या को पैरामीटर गिरावट के बिना रिकवर करने के लिए संयोजित किया जा सकता है।
भविवी दिशाएं: लेखक सुझाव देते हैं कि इन रिडक्शन को कोडिंग थ्योरी (लैटिस से परे) तक विस्तारित करना 'डिकोडेड क्वांटम इंटरफेरोमेट्री' से संबंधित खुले प्रश्नों को संबोधित कर सकता है। वे यह भी मानते हैं कि ISIS के लिए नए एल्गोरिदम खोजना उनके फ्रेमवर्क के माध्यम से सीधे S|LWE⟩ के लिए नए क्वांटम एल्गोरिदम प्रदान कर सकता है।

संक्षेप में, यह पेपर एक कठोर सैद्धांतिक ढांचा प्रदान करता है जो क्वांटम सुपरपोजिशन-आधारित LWE वेरिएंट को क्लासिकल लैटिस समस्याओं से जोड़ता है, यह प्रदर्शित करते हुए कि विशिष्ट रिकवरेबिलिटी स्थितियों के तहत, वे कम्प्यूटेशनल रूप से तुल्य हैं, जबकि सामान्य मामले में इस तुल्यता को सिद्ध करने के लिए शेष बाधाओं को भी उजागर करते हैं।