⚛️ quantum physics

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth

यह शोध पत्र एक संक्षिप्त क्वांटम सर्किट प्रस्तुत करता है जो जैकोबी प्रतीक (Jacobi symbol) की गणना करने के लिए एक नवीन स्थान-कुशल एल्गोरिदम के माध्यम से, उप-रैखिक (sublinear) स्थान और गहराई का उपयोग करके, शास्त्रीय रूप से कठिन पूर्णांकों के एक विशिष्ट वर्ग को बहुपद समय (polynomial time) में गुणनखंडित करता है।

मूल लेखक: Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, Katherine Van Kirk

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

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

CC BY 4.0

मूल लेखक: Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, Katherine Van Kirk

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

कल्पना कीजिए कि आपके पास एक विशाल, लॉक वाली तिजोरी (एक बड़ी संख्या) है और आप इसका संयोजन (इसके अभाज्य गुणनखंड/prime factors) खोजना चाहते हैं। दशकों तक, इसे करने का सबसे अच्छा तरीका शोर का एल्गोरिदम (Shor's Algorithm) था, जो एक प्रसिद्ध क्वांटम विधि है। लेकिन शोर का एल्गोरिदम एक विशाल, औद्योगिक आकार के रोबोटिक हाथ से उस तिजोरी को तोड़ने जैसा है। इसके लिए बहुत अधिक स्थान की आवश्यकता होती है, इसे घुमाने में बहुत समय लगता है, और यह बहुत अधिक ऊर्जा का उपयोग करता है। यह शक्तिशाली तो है, लेकिन वर्तमान में हमारे पास इतना बड़ा रोबोट बनाने के लिए हार्डवेयर नहीं है।

यह शोध पत्र एक नया उपकरण पेश करता है जिसे जैकोबी फैक्टरिंग सर्किट (Jacobi Factoring Circuit) कहा जाता है। इसे एक विशाल रोबोट के रूप में न देखें, बल्कि एक चिकने, जेब के आकार के लॉकपिक (lockpick) के रूप में देखें। इसे एक विशिष्ट प्रकार की तिजोरी खोलने के लिए डिज़ाइन किया गया है जो क्रिप्टोग्राफी में बहुत आम है लेकिन इसकी संरचना में एक विशेष "कमजोरी" है।

यहाँ शोध पत्र को सरल उपमाओं का उपयोग करके विभाजित किया गया है:

1. लक्ष्य: एक विशिष्ट प्रकार की तिजोरी

लेखक हर तरह की तिजोरी को तोड़ने की कोशिश नहीं कर रहे हैं (जैसे कि आज इंटरनेट पर उपयोग किए जाने वाले मानक RSA लॉक)। इसके बजाय, वे एक विशिष्ट आकार की तिजोरियों को लक्षित कर रहे हैं: $N = P^2 \times Q$ ।

कल्पना कीजिए कि एक तिजोरी दो भागों से बनी है: एक भारी, वर्गाकार ब्लॉक ( $P^2$ ) और एक छोटा, अनियमित ब्लॉक ( $Q$ )।
शोध पत्र उन मामलों पर ध्यान केंद्रित करता है जहाँ छोटा ब्लॉक ( $Q$ ), पूरी तिजोरी की तुलना में काफी छोटा है, लेकिन इतना छोटा भी नहीं है कि क्लासिकल कंप्यूटर इसे आसानी से तोड़ सकें।
पेंच (The Catch): यदि छोटा ब्लॉक बहुत छोटा है, तो क्लासिकल कंप्यूटर इसे पहले ही तोड़ सकते हैं। यदि यह बहुत बड़ा है, तो यह नई विधि काम नहीं आती। लेकिन "गोल्डिलॉक्स ज़ोन" (जहाँ $Q$ बिल्कुल सही है) में, यह नई क्वांटम विधि चमकती है।

2. पुराना तरीका बनाम नया तरीका

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

नया तरीका (यह शोध पत्र):
लेखकों ने महसूस किया कि उन्हें पूरी तिजोरी को देखने की आवश्यकता नहीं है। उन्हें केवल छोटे, अनियमित ब्लॉक ( $Q$ ) को देखने की आवश्यकता है।

उपमा: कल्पना कीजिए कि आप एक विशाल पुस्तकालय में एक विशिष्ट कुंजी खोजने की कोशिश कर रहे हैं। पुराने तरीके ने कहा, "पुस्तकालय की हर किताब को खोजें।" नए तरीके ने कहा, "वास्तव में, कुंजी पुस्तकालय के उस छोटे हिस्से में छिपी है जहाँ अनियमित ब्लॉक रहते हैं। आइए बस उस छोटे हिस्से को खोजें।"
परिणाम: केवल छोटे हिस्से पर ध्यान केंद्रित करके, उन्होंने आवश्यक स्थान (qubits) और गहराई (समय/चरणों) को पहले की तुलना में बहुत कम कर दिया। उन्होंने सबलीनियर स्पेस (sublinear space) प्राप्त किया, जिसका अर्थ है कि आवश्यक मेमोरी संख्या के आकार की तुलना में बहुत धीमी गति से बढ़ती है।

3. गुप्त उपकरण: "जैकोबी सिंबल" (The Jacobi Symbol)

वे केवल छोटे हिस्से को कैसे देख पाए? उन्होंने जैकोबी सिंबल नामक एक गणितीय उपकरण का उपयोग किया।

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

4. यह वास्तव में क्या करता है?

यह शोध पत्र दावा करता है कि यह सर्किट:

इन विशिष्ट प्रकार की संख्याओं ( $P^2Q$ ) को नियर-लीनियर गेट्स (near-linear gates) (अत्यंत कुशल चरणों) का उपयोग करके फैक्टर (factor) कर सकता है।
सबलीनियर स्पेस (sublinear space) (संख्या के आकार से कम मेमोरी) का उपयोग करता है।
सबलीनियर डेप्थ (sublinear depth) (पिछले तरीकों की तुलना में काम को तेजी से पूरा करना) का उपयोग करता है।

महत्वपूर्ण सीमा: शोध पत्र स्पष्ट रूप से कहता है कि यह मानक RSA एन्क्रिप्शन को नहीं तोड़ता है (जो $N = P \times Q$ , दो अलग-अलग अभाज्य संख्याओं का उपयोग करता है)। यह केवल उन संख्याओं को तोड़ता है जिनमें एक विशिष्ट "वर्ग" (square) संरचना होती है। हालाँकि, लेखकों ने नोट किया है कि इस विशिष्ट संरचना का उपयोग अन्य क्रिप्टोग्राफिक प्रणालियों में भी किया गया है, इसलिए यह उस क्षेत्र के लिए एक महत्वपूर्ण खोज है।

5. "क्वांटमनेस का प्रमाण" (The Proof of Quantumness)

शोध पत्र सुझाव देता है कि इस नए सर्किट का उपयोग यह साबित करने के लिए किया जा सकता है कि कोई कंप्यूटर वास्तव में क्वांटम है।

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

सारांश

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

तकनीकी सारांश: जैकोबी फैक्टरिंग सर्किट (The Jacobi Factoring Circuit)

समस्या विवरण (Problem Statement)
वर्तमान क्वांटम फैक्टिंग एल्गोरिदम, जैसे कि शोर का एल्गोरिदम (Shor's algorithm) और रेगेव के हालिया सुधार, निकट-अवधि के उपकरणों (near-term devices) पर व्यावहारिक कार्यान्वयन के लिए उच्च संसाधन आवश्यकताओं के कारण महत्वपूर्ण बाधाओं का सामना करते हैं। विशेष रूप से, एक $n$ -बिट पूर्णांक को फैक्टर करने के लिए आमतौर पर $\tilde{O}(n^2)$ या $\tilde{O}(n^{3/2})$ गेट्स और $\tilde{O}(n)$ क्यूबिट्स की आवश्यकता होती है। जबकि स्पेस कॉम्प्लेक्सिटी (space complexity) को $\tilde{O}(n)$ या यहाँ तक कि $O(n)$ तक कम किया गया है, क्लासिकली कठिन (classically hard) फैक्टिंग समस्याओं के लिए सबलीनियर (sublinear) स्पेस और डेप्थ प्राप्त करना एक खुला प्रश्न बना हुआ है। इसके अलावा, मौजूदा क्वांटम एल्गोरिदम इनपुट पूर्णांक के विशिष्ट संरचनात्मक गुणों (जैसे, छोटे स्क्वायरफ्री पार्ट्स) से पोलीनोमियल रूप से लाभान्वित होते प्रतीत नहीं होते हैं, जैसा कि कुछ क्लासिकल एल्गोरिदम में होता है।

यह शोध पत्र इस प्रश्न को संबोधित करता है कि क्या क्वांटम सर्किट फैक्टरिंग के लिए (लगभग) लीनियर गेट काउंट प्राप्त कर सकते हैं, जबकि विशेष रूप से उन पूर्णांकों के वर्ग (class of integers) के लिए काम कर सकते हैं जहाँ कठिनाई RSA के समकक्ष होने की अपेक्षा की जाती है (यद्यपि इसमें RSA पूर्णांक शामिल नहीं हैं)।

कार्यप्रणाली (Methodology)
लेखक "जैकोबी फैक्टरिंग सर्किट" का प्रस्ताव करते हैं, जो ली, पेंग, डू और सुटर (LPDS) [LPDS12] के स्क्वायरफ्री डिकम्पोजिशन एल्गोरिदम पर आधारित है। कार्यप्रणाली में तीन प्राथमिक तकनीकी घटक शामिल हैं:

LPDS का परिष्कृत विश्लेषण (अनुभाग 3): मूल LPDS सर्किट एक पूर्णांक $N = A^2 B$ का स्क्वायरफ्री डिकम्पोजिशन करने के लिए $x \in [1, N]$ के ऊपर एक यूनिफॉर्म सुपरपोजिशन बनाता है और जैकोबी सिंबल $(\frac{x}{N})$ की गणना करता है। लेखक प्रदर्शित करते हैं कि पूरे रेंज $[1, N]$ पर सुपरपोजिशन अनावश्यक है। शोर के पीरियड-फाइंडिंग विश्लेषण और गॉस सम बाउंड्स (Gauss sum bounds) को मिलाकर, वे सिद्ध करते हैं कि एक बहुत छोटे रेंज $[1, \text{poly}(B_{\max})]$ पर सुपरपोजिशन, जहाँ $B_{\max}$ स्क्वायरफ्री भाग $B$ का ऊपरी स्तर (upper bound) है, $B$ (या एक अभाज्य गुणनखंड) को निरंतर प्रायिकता (constant probability) के साथ रिकवर करने के लिए पर्याप्त है। यह कमी सर्किट को $\log N$ के बजाय $\log B$ के अनुपात में स्पेस के साथ संचालित करने की अनुमति देती है।
सबलीनियर स्पेस जैकोबी सिंबल कंप्यूटेशन (अनुभाग 4): LPDS दृष्टिकोण में कम्प्यूटेशनल बॉटलनेक $(\frac{x}{N})$ की गणना करना है जहाँ $x$ सुपरपोजिशन में है और $N$ एक बड़ा क्लासिकल पूर्णांक है। मानक एल्गोरिदम (एक्सटेंडेड यूक्लिडियन, बाइनरी GCD) $\log N$ के रैखिक (linear) स्पेस की आवश्यकता रखते हैं।
लेखक एक नया क्वांटम एल्गोरिदम पेश करते हैं जो $(\frac{x}{N})$ की गणना तब करता है जब $\log x \ll \log N$ हो। मुख्य नवाचार मोंटगोमरी रिडक्शन (Montgomery reduction) और बाइनरी GCD एल्गोरिदम से प्रेरित "रिवर्स" लॉन्ग डिवीजन का एक संस्करण है।

तंत्र (Mechanism): $N$ के मोस्ट सिग्निफिकेंट बिट्स (MSBs) से मेल खाने वाले $x$ के गुणज (multiple) को खोजने के बजाय (मानक लॉन्ग डिवीजन), यह एल्गोरिदम एक ऐसा गुणज $kx $खोजता है जिससे$ N - kx$ के लीस्ट सिग्निफिकेंट बिट्स (LSBs) $N$ से मेल खाते हों (प्रभावी रूप से उन्हें शून्य कर देता है)।
स्पेस दक्षता (Space Efficiency): $N$ को $m$ आकार के ब्लॉक्स में प्रोसेस करके (जहाँ $m \approx \log x$ ), यह एल्गोरिदम केवल रनिंग सम के लीडिंग $O(m)$ बिट्स को क्वांटम रूप से स्टोर करने की आवश्यकता रखता है। लोअर-ऑर्डर बिट्स क्लासिकली ज्ञात होते हैं और उन्हें अनकंप्यूट (uncompute) या रीसायकल किया जा सकता है।
जटिलता (Complexity): इससे $\tilde{O}(n)$ गेट काउंट, $\tilde{O}(m)$ स्पेस, और $\tilde{O}(n/m + m)$ डेप्थ वाला एक सर्किट प्राप्त होता है।

विशेष पूर्णांकों का पूर्ण गुणनखंड (अनुभाग 5): यह शोध पत्र एक ब्लैक-बॉक्स रिडक्शन प्रदान करता है जो उन पूर्णांकों को पूरी तरह से फैक्टर करने का तरीका दिखाता है जिनमें उनके अभाज्य गुणनखंडन में विशिष्ट घातांक (distinct exponents) होते हैं (जिन्हें "विशेष पूर्णांक" कहा जाता है, $N = p_1^{\alpha_1} \dots p_r^{\alpha_r}$ जहाँ सभी $\alpha_i$ भिन्न हैं)।

विधि: एल्गोरिदम विषम घातांकों वाले अभाज्य संख्याओं के उत्पाद को अलग करने के लिए स्क्वायरफ्री डिकम्पोजिशन का पुनरावृत्ति (recursively) उपयोग करता है। मूल संख्या और एक व्युत्पन्न मान के बीच GCD की गणना करके, यह एक एकल अभाज्य गुणनखंड को अलग करता है। यह प्रक्रिया पूर्ण गुणनखंड प्राप्त होने तक दोहराई जाती है। यह दृष्टिकोण बहुपद गुणनखंडन (polynomial factorization) के लिए यून के एल्गोरिदम के समान है।

मुख्य योगदान और परिणाम (Key Contributions and Results)

प्रमेय 1.1 (अनौपचारिक): एक क्वांटम सर्किट मौजूद है जो किसी भी $n$ $n$ -बिट पूर्णांक $N = P^2 Q$ $N = P^{2} Q$ (जहाँ $P, Q$ $P, Q$ अभाज्य हैं और $\log Q = \Theta(n^a)$ $lo g Q = Θ (n^{a})$ जहाँ $a \in (2/3, 1)$ $a \in (2/3, 1)$ ) को निम्नलिखित का उपयोग करके फैक्टर करता है:
- गेट्स: $\tilde{O}(n)$
- क्यूबिट्स: $\tilde{O}(m)$ (जहाँ $m = \log Q$ )
- डेप्थ: $\tilde{O}(m + n/m)$
  जब $m = \Theta(n^a)$ है $a \in (0, 1)$ के साथ, तो स्पेस और डेप्थ दोनों $n$ में सबलीनियर होते हैं।
प्रथम सबलीनियर स्पेस फैक्टरिंग: लेखकों की जानकारी के अनुसार, यह एक क्लासिकली कठिन फैक्टिंग समस्या के लिए सबलीनियर क्यूबिट काउंट प्राप्त करने वाला पहला बहुपद-समय (polynomial-time) क्वांटम सर्किट है।
क्लासिकल हार्डनेस के साथ तुलना: $N = P^2 Q$ के रूप में पूर्णांकों के लिए जहाँ $\log Q \ge \tilde{\Omega}((\log N)^{2/3})$ , कोई भी ज्ञात क्लासिकल स्पेशल-परपज एल्गोरिदम (जैसे लेन्स्ट्रा का एलिप्टिक कर्व मेथड) जनरल-परपज फैक्टरिंग (नंबर फील्ड सीव) पर एसिम्प्टोटिक स्पीडअप नहीं देते हैं। अतः, यहाँ क्वांटम लाभ केवल एक क्लासिकल कमजोरी का फायदा उठाना नहीं है, बल्कि एक संसाधन कमी (resource reduction) प्राप्त करना है जो इस शासन (regime) में क्लासिकल एल्गोरिदम के लिए असंभव है।
क्वांटमनेस का प्रमाण: यह सर्किट सबलीनियर स्पेस कॉम्प्लेक्सिटी के साथ एक फैक्टरिंग-आधारित क्वांटमनेस प्रूफ सक्षम करता है। $N = P^2 Q$ के लिए जहाँ $\log Q \approx n^{2/3}$ , सर्किट $\tilde{O}(n)$ गेट्स, $\tilde{O}(n^{2/3})$ डेप्थ, और $\tilde{O}(n^{2/3})$ क्यूबिट्स का उपयोग करता है। यह क्यूबिट काउंट और डेप्थ/गेट्स के गुणनफल के मामले में शोर के एल्गोरिदम और रेगेव के एल्गोरिदम से बेहतर प्रदर्शन करता है।

महत्व और दावे (Significance and Claims)
शोध पत्र का दावा है कि जैकोबी फैक्टरिंग सर्किट स्पेस और डेप्थ की आवश्यकताओं को भारी रूप से कम करके, निकट- या मध्यम-अवधि के क्वांटम उपकरणों पर पूर्णांक गुणनखंडन को साकार करने की दिशा में एक महत्वपूर्ण कदम है।

स्वतंत्रता: सबलीनियर स्पेस में जैकोबी सिंबल की गणना करने की तकनीक स्वतंत्र रूप से भी दिलचस्प है और GCD तथा मॉड्यूलर इनवर्स की गणना के लिए सामान्यीकृत की जा सकती है।
सीमाएँ: लेखक स्पष्ट रूप से कहते हैं कि उनकी विधि सीधे RSA पूर्णांकों (समान आकार के दो अभाज्य संख्याओं के गुणनफल) को फैक्टर नहीं करती है, क्योंकि RSA में स्क्वायरफ्री भाग $B = 1$ होता है। यह विधि उन पूर्णांकों पर लागू होती है जहाँ स्क्वायरफ्री भाग छोटा लेकिन गैर-तुच्छ (non-trivial) है।
विनम्रता: लेखक नोट करते हैं कि जबकि एसिम्प्टोटिक स्केलिंग में सुधार किया गया है, ठोस लागतों (गेट काउंट, एरर करेक्शन ओवरहेड) का गहराई से विश्लेषण नहीं किया गया है, और 2048-बिट पूर्णांकों को फैक्टर करने का व्यावहारिक कार्यान्वयन भविष्य के कार्य के लिए एक विषय बना हुआ है। वे यह भी स्वीकार करते हैं कि एल्गोरिदम वर्तमान में सामान्य स्क्वायरफ्री पूर्णांकों को फैक्टर करने तक विस्तारित नहीं है, जो कि एक खुला प्रश्न बना हुआ है।

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