⚛️ quantum physics

Parallel Spooky Pebbling Makes Regev Factoring More Practical

यह शोध पत्र "पैरेलल स्पूकी पेबल गेम्स" पेश करता है, जो रेगेव के गुणनखंड एल्गोरिदम (Regev's factoring algorithm) के लिए आवश्यक गुणन गहराई (multiplication depth) को काफी कम करने के लिए समानांतरता (parallelism) और हैडामार्ड बेसिस मेजरमेंट्स (Hadamard basis measurements) को संयोजित करने वाली एक तकनीक है, जो यह प्रदर्शित करता है कि 4096-बिट पूर्णांकों को 193 की गहराई के साथ गुणनखंडित किया जा सकता है, जबकि पिछले वेरिएंट्स के लिए 444 या 680 की आवश्यकता थी।

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

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

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

CC BY 4.0

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

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

कल्पना कीजिए कि आप एक बहुत ही विशाल और अविश्वसनीय रूप से जटिल पहेली को हल करने की कोशिश कर रहे हैं। इसे करने के लिए, आपको एक के बाद एक, कई चरणों में गणनाओं की एक लंबी श्रृंखला करनी होगी। शास्त्रीय कंप्यूटरों (classical computers) की दुनिया में, यह एक लंबे गलियारे में चलने जैसा है, जहाँ आप हर दरवाजे पर एक नोट उठाते हैं, उसे पढ़ते हैं, और फिर अगले दरवाजे की ओर बढ़ जाते हैं। आप चरणों को छोड़ नहीं सकते, और आपको वह सब कुछ याद रखना होगा जो आपने अब तक देखा है।

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

यह समस्या रेगेव के फैक्टरिंग एल्गोरिदम (Regev's Factoring Algorithm) की है। यह एन्क्रिप्शन कोड को तोड़ने का एक नया, आशाजनक तरीका है, लेकिन माना जाता था कि यह बहुत अधिक "स्थान-खर्ची" (space-hungry) है। इसे सभी मध्यवर्ती चरणों (intermediate steps) को रखने के लिए बहुत अधिक मेमोरी (qubits) की आवश्यकता थी।

यह शोध पत्र एक चतुर ट्रिक पेश करता है जिसे "पैरेलल स्पूकी पेबलिंग" (Parallel Spooky Pebbling) कहा जाता है। यह कैसे काम करता है, इसके लिए यहाँ कुछ मजेदार उपमाएँ दी गई हैं:

1. कंकड़ का खेल (सेटअप)

कल्पना कीजिए कि गणना कदमों के पत्थरों (stepping stones) की एक लंबी रेखा है। शुरुआत से अंत तक पहुँचने के लिए, आपको प्रत्येक पत्थर पर एक "कंकड़" (मार्कर) रखना होगा।

पुराना तरीका: आप पत्थर 1 पर एक कंकड़ रखते हैं, फिर पत्थर 2 पर, फिर पत्थर 3... अंत तक। वापस आने और सफाई करने के लिए, आपको उन्हें उल्टे क्रम में उठाना पड़ता है। आपको उन सभी पत्थरों के लिए एक कंकड़ चाहिए जिन्हें आपने छुआ है। यह "स्पेस" (स्थान) की समस्या है।
"स्पूकी" ट्रिक: लेखक एक क्वांटम जादू का उपयोग करते हैं जिसे मिड-सर्किट मेजरमेंट (mid-circuit measurement) कहा जाता है। कल्पना कीजिए कि पत्थर पर कंकड़ रखने के बजाय, आप उसकी एक फोटो लेते हैं, और फिर कंकड़ को मिटा देते हैं।
- सावधानी: फोटो लेने से पीछे एक छोटा सा "भूत" (फेज एरर/phase error) रह जाता है। यह ऐसा है जैसे किसी पत्थर पर इत्र की हल्की खुशबू छोड़ देना। पत्थर खाली है, लेकिन वह अभी भी "याद" रखता है कि आप वहाँ थे।
- लाभ: अब आपको भारी कंकड़ ढोने की ज़रूरत नहीं है! आपको बस बाद में उस "भूत" को बाहर निकालने (exorcise) का ध्यान रखना होगा। इससे बहुत सारा स्थान बचता है।

2. पैरेलल ट्रिक (गति बढ़ाना)

मूल "स्पूकी" तरीके में, आप एक समय में केवल एक ही काम कर सकते थे। आप एक कंकड़ रखते, उसकी फोटो लेते, उसे मिटाते और फिर अगले की ओर बढ़ते।

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

3. परिणाम: एक हल्का और तेज़ एल्गोरिदम

"स्पूकीनेस" (जगह बचाने के लिए कंकड़ मिटाना) को "पैरेललिज्म" (एक साथ कई काम करना) के साथ जोड़कर, उन्होंने एक बड़ी सफलता हासिल की:

पहले: रेगेव के तरीके का उपयोग करके 2048-बिट कोड को तोड़ने के लिए, आपको बहुत अधिक मेमोरी (स्पेस) और लंबे समय (डेप्थ) वाले क्वांटम कंप्यूटर की आवश्यकता थी।
अब: उन्होंने दिखाया कि आप बहुत कम मेमोरी (संख्या के आकार के लॉगरिदम का लगभग 2.5 गुना) और पिछले प्रयासों की तुलना में आधे समय में यह कर सकते हैं।

"अहा!" क्षण (The "Aha!" Moment):
इसे यात्रा के लिए पैकिंग करने जैसा समझें।

शोर का एल्गोरिदम (Shor's Algorithm) (पुराना चैंपियन) एक बैकपैकर की तरह है: बहुत हल्का, बहुत कुशल, लेकिन शायद मंजिल तक पहुँचने में थोड़ा धीमा।
रेगेव का एल्गोरिदम (नया दावेदार) एक मूविंग ट्रक की तरह था: यह अधिक सामान ले जा सकता था, लेकिन यह इतना भारी था कि चल नहीं सकता था।
यह शोध पत्र रेगेव के मूविंग ट्रक को एक साइडकार वाली मोटरसाइकिल में बदल देता है। यह अब बैकपैकर जितना ही हल्का है और फिर भी वह विशेष सामान ले जा सकता है जिसकी रेगेव को आवश्यकता है।

यह क्यों महत्वपूर्ण है?

वर्षों से, विशेषज्ञों का मानना था कि शोर का एल्गोरिदम ही कोड तोड़ने का एकमात्र वास्तविक तरीका है क्योंकि रेगेव का तरीका बहुत भारी था।

यह शोध पत्र कहता है: "रुको जरा! हम रेगेव के तरीके को बहुत हल्का बना सकते हैं।"

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

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

यहाँ Kahanamoku-Meyer, Ragavan, और Van Kirk के शोध पत्र "Parallel Spooky Pebbling Makes Regev Factoring More Practical" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र क्वांटम कंप्यूटरों पर अंतर्निहित रूप से क्रमिक गणनाओं (inherently sequential computations) को कुशलतापूर्वक लागू करने की चुनौती को संबोधित करता है, जो विशेष रूप से रेगेव के फैक्टिंग एल्गोरिदम (Regev's factoring algorithm) (JACM 2025) के लिए आवश्यक मॉड्यूलर एक्सपोनेंटिएशन (modular exponentiation) पर केंद्रित है।

बाधा (The Bottleneck): रेगेव का एल्गोरिदम शोर (Shor) के एल्गोरिदम की तुलना में क्वांटम गुणन (quantum multiplications) की संख्या में एक बहुपद कमी (polynomial reduction) प्रदान करता है ( $O(\sqrt{n})$ बनाम $O(n)$ )। हालांकि, पिछले कार्यान्वयन उच्च स्पेस कॉम्प्लेक्सिटी ( $O(n^{3/2})$ क्यूबिट्स) से ग्रस्त थे क्योंकि एक्सपोनेंटिएशन के लिए उपयोग की जाने वाली "स्क्वायर-एंड-मल्टीप्लाई" विधि प्रतिवर्ती (reversible) नहीं है, जिसके लिए प्रत्येक चरण के लिए नए रजिस्टरों की आवश्यकता होती है।
मौजूदा समाधान और सीमाएँ (Existing Solutions & Limitations):
- फाइबोनैकी-आधारित रिवर्सिबल अरिथमेटिक: स्पेस-एफिशिएंट वेरिएंट (जैसे कि रागावन और वैकुंतनाथन द्वारा) में उपयोग किया जाता है, लेकिन यह मध्यवर्ती मानों को संग्रहीत करने और उन्हें उलटने (invert) की आवश्यकता के कारण भारी स्थिरांक-कारक ओवरहेड (constant-factor overheads) उत्पन्न करता है।
- गिडनी का "स्पूकी पेबलिंग" (Gidney's "Spooky Pebbling"): मिड-सर्किट मेजरमेंट का उपयोग करके रजिस्टरों को "घोस्ट" (discard) करने के लिए किया जाता है, जिससे केवल फेज एरर (phase errors) बचते हैं। यह स्पेस को लॉगरिदमिक तक कम कर देता है लेकिन सर्किट डेप्थ (circuit depth) को बढ़ा देता है।
- पैरेलल पेबलिंग (Parallel Pebbling): समानांतर संचालन (simultaneous operations) की अनुमति देता है ताकि डेप्थ को कम किया जा सके, लेकिन इसे पहले बिना "स्पूकीनेस" के अध्ययन किया गया था, जिसके परिणामस्वरूप उप-इष्टतम (sub-optimal) स्पेस उपयोग हुआ।
अंतराल (The Gap): कोई भी मौजूदा विधि क्रमिक क्वांटम गणनाओं के लिए एक साथ इष्टतम डेप्थ (optimal depth) (चरणों की संख्या में रैखिक) और लॉगरिदमिक स्पेस (logarithmic space) प्राप्त नहीं कर सकती। लेखक पूछते हैं: क्या पैरेललिज्म और स्पूकीनेस को जोड़कर रेगेव के एल्गोरिदम को 2048-बिट पूर्णांकों के लिए व्यावहारिक रूप से कुशल बनाया जा सकता है?

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

लेखक "पैरेलल स्पूकी पेबलिंग गेम्स" (Parallel Spooky Pebbling Games) का परिचय देते हैं और उसका विश्लेषण करते हैं, जो दो संसाधनों को संयोजित करने वाला एक एब्स्ट्रैक्शन है:

स्पूकीनेस (Spookiness): रजिस्टरों को अनकंप्यूट (uncompute) करने के लिए हाडामाड बेसिस मेजरमेंट्स (Hadamard basis measurements) का उपयोग करना (जो "घोस्ट्स" या फेज एरर छोड़ते हैं जिन्हें बाद में ठीक किया जाना चाहिए)।
पैरेललिज्म (Parallelism): कई पेबलिंग (गणना) और अनपेबलिंग (अनकंप्यूटेशन) चरणों को एक साथ निष्पादित करना।

A. सैद्धांतिक ढांचा (Theoretical Framework)

परिभाषाएँ: वे लंबाई $\ell$ वाले एक लाइन ग्राफ पर पेबलिंग गेम को परिभाषित करते हैं। एक "पेबल" (pebble) एक संगणित मान का प्रतिनिधित्व करता है। "घोस्टिंग" (Ghosting) एक पेबल को हटा देता है लेकिन एक फेज छोड़ देता है। "अनपेबलिंग" (Unpebbling) गणना को उलट देती है।
इष्टतम डेप्थ निर्माण: वे एक विशिष्ट अनुक्रम $\{A_k\}$ ${A_{k}}$ (परिभाषित $A_k = A_{k-2} + A_{k-3}$ $A_{k} = A_{k - 2} + A_{k - 3}$ , जो ट्राइबोनैकी अनुक्रम से संबंधित है) का उपयोग करके एक रिकर्सिव एल्गोरिदम का निर्माण करते हैं।
- रणनीति: एक "ब्लास्टिंग" (blasting) चरण एक मार्कर और घोस्ट छोड़ते हुए अंत तक एक पेबल को ले जाता है। एक समानांतर "अनब्लास्टिंग" (unblasting) चरण बाएं हिस्से को रिकर्सिवली ब्लास्ट करते हुए दाएं हिस्से को साफ करता है।
- परिणाम: वे सिद्ध करते हैं कि लंबाई $\ell$ वाले लाइन ग्राफ को केवल $\approx 2.47 \log \ell$ पेबल्स (क्यूबिट्स) का उपयोग करके डेप्थ $2\ell$ (सैद्धांतिक न्यूनतम) में पेबल किया जा सकता है। यह स्थिरांक कारकों तक एसिम्प्टोटिक रूप से इष्टतम है।

B. एल्गोरिद्मिक अनुकूलन (A* Search)

ठोस, गैर-एसिम्प्टोटिक मामलों को संभालने के लिए, उन्होंने जूलिया (Julia) में एक अत्यधिक अनुकूलित $A^*$ सर्च को लागू किया।
यह सर्च विशिष्ट ग्राफ लंबाई ( $\ell$ ) और निश्चित पेबल्स की संख्या ( $s$ ) के लिए सटीक इष्टतम-डेप्थ पेबलिंग स्कीम पाता है।
भारित लागत (Weighted Costs): सर्च विभिन्न भारित लागत मेट्रिक्स को शामिल करता है, यह स्वीकार करते हुए कि विभिन्न पेबलिंग चरणों (जैसे स्क्वेरिंग बनाम बेस के उत्पाद के साथ गुणा करना) के लिए अलग-अलग सहायक स्थान (ancillary space) की आवश्यकता होती है।

C. रेगेव फैक्टरिंग पर अनुप्रयोग (Application to Regev Factoring)

लेखक रेगेव के मॉड्यूलर एक्सपोनेंटिएशन सर्किट को पेबलिंग गेम में मैप करते हैं:

विंडोइंग (Windowing): वे पेबलिंग गेम की कुल लंबाई को कम करने के लिए "विंडोइंग" तकनीक लागू करते हैं (गुणा को एमोर्टाइज करना)।
इंटरमीडिएट प्रोडक्ट्स को घोस्ट करना: बड़े उत्पाद टर्म $\prod a_j^{z_j}$ को स्पष्ट रूप से अनकंप्यूट करने के बजाय, वे स्पेस बचाने के लिए मेजरमेंट-बेस्ड अनकंप्यूटेशन का उपयोग करते हैं।
इन-प्लेस मल्टीप्लिकेशन: वे प्रोडक्ट ट्री को क्रमिक इन-प्लेस क्लासिकल-क्वांटम मल्टीप्लिकेशन्स से बदलते हैं, जिससे क्यूबिट ओवरहेड काफी कम हो जाता है।
एंसिला जागरूकता (Ancilla Awareness): पेबलिंग रणनीति को विभिन्न अंकगणितीय ऑपरेशन्स की अलग-अलग एन्सिला आवश्यकताओं को ध्यान में रखते हुए संख्यात्मक रूप से अनुकूलित किया गया है।

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

पैरेलल स्पूकी पेबलिंग थ्योरी: पैरेललिज्म और मिड-सर्किट मेजरमेंट्स दोनों का उपयोग करने वाले पेबलिंग गेम्स की पहली कठोर परिभाषा और विश्लेषण।
इष्टतम डेप्थ/स्पेस ट्रेड-ऑफ: प्रमाण कि इष्टतम डेप्थ ( $2\ell$ ) लॉगरिदमिक स्पेस ( $\approx 2.47 \log \ell$ ) के साथ प्राप्त किया जा सकता है, जो पैरेललिज्म या स्पूकीनेस के लिए पिछले अलग-अलग बाउंड्स में सुधार करता है।
ठोस संसाधन अनुमान (Concrete Resource Estimates): इन नई तकनीकों के साथ अनुकूलित, इन तकनीकों का उपयोग करके रेगेव के एल्गोरिदम का उपयोग करके 2048-बिट और 4096-बिट पूर्णांकों को फैक्टर करने के लिए एक विस्तृत संसाधन अनुमान।
ओपन सोर्स टूलिंग: किसी भी पैरामीटर के लिए इष्टतम पेबलिंग स्कीम्स खोजने के लिए $A^*$ सर्च हेतु जूलिया कोड का रिलीज।

4. परिणाम (Results)

पेपर $N$ (2048-बिट और 4096-बिट) को फैक्टर करने के लिए विभिन्न एल्गोरिदम के बीच ठोस तुलना प्रदान करता है:

मेट्रिक	शोर का एल्गोरिदम (पैरेललाइज्ड)	रेगेव (फाइबोनैकी/पिछला)	रेगेव (यह कार्य: पैरेलल स्पूकी)
2048-बिट डेप्थ	~100 (उच्च स्पेस के साथ) / 230 (मानक)	~580	157 (12 पेबल्स के साथ)
4096-बिट डेप्थ	~444	~680	193 (12 पेबल्स के साथ)
क्यूबिट काउंट	$\approx 2n$ (बहुत कम)	$\ge 13n$ (बहुत अधिक)	$\approx 7n - 15n$ (मध्यम)
कुल ऑप्स (सभी रन)	सर्वश्रेष्ठ	सबसे खराब	फाइबोनैकी से बेहतर, शोर से बदतर

डेप्थ सुधार: नया तरीका 2048-बिट पूर्णांकों के लिए मल्टीप्लिकेशन डेप्थ को 580 (पिछले रेगेव वेरिएंट) से घटाकर 157 और 4096-बिट के लिए 680 से 193 कर देता है।
शोर के साथ तुलना: जबकि शोर का एल्गोरिदम सभी रन में कुल स्पेस (क्यूबिट्स) और कुल गेट काउंट में श्रेष्ठ बना हुआ है, अनुकूलित रेगेव एल्गोरिदम की डेप्थ प्रति शॉट (depth per shot) अब पैरेललाइज्ड शोर के प्रतिस्पर्धी है, और कुछ पैरामीटर व्यवस्थाओं में उससे बेहतर भी है।
लैटिस पोस्ट-प्रोसेसिंग: अध्ययन से पता चलता है कि क्लासिकल लैटिस रिडक्शन पावर (BKZ ब्लॉक साइज) बढ़ाने का क्वांटम सर्किट डेप्थ पर मामूली प्रभाव पड़ता है, जिससे पता चलता है कि क्वांटम बॉटलनेक अंकगणित है, न कि क्लासिकल पोस्ट-प्रोसेसिंग बाधाएं।

5. महत्व (Significance)

रेगेव की व्यावहारिक व्यवहार्यता: परिणाम दर्शाते हैं कि रेगेव का एल्गोरिदम पूरी तरह से अनुकूलित नहीं है। इन तकनीकों के साथ, यह निकट-अवधि (near-term) क्वांटम फैक्टिंग के लिए एक व्यवहार्य उम्मीदवार बन जाता है, विशेष रूप से उन परिदृश्यों में जहाँ सर्किट डेप्थ सीमित कारक है (जैसे, सीमित कोहेरेंस समय), न कि कुल क्यूबिट काउंट।
समानांतर निष्पादन (Parallel Execution): क्योंकि रेगेव के एल्गोरिदम के लिए कई स्वतंत्र सर्किट रन की आवश्यकता होती है, इसलिए प्रति शॉट कम डेप्थ मध्यम-स्तर के क्वांटम कंप्यूटरों पर व्यापक समानांतरकरण (massive parallelization) की अनुमति देता है, जिसमें उपकरणों के बीच क्वांटम संचार की आवश्यकता नहीं होती है।
व्यापक प्रभाव: "पैरेलल स्पूकी पेबलिंग" फ्रेमवर्क एक सामान्य टूल है जिसे क्वांटम सर्किट कंपाइलेशन में उपयोग किया जा सकता है। इसे किसी भी अंतर्निहित क्रमिक क्वांटम कार्य पर लागू किया जा सकता है, जिसमें प्रूफ ऑफ वर्क, टाइम-लॉक पज़ल्स और पूर्णांक गुणनखंडन से परे अन्य क्रिप्टानलिटिक अनुप्रयोग शामिल हैं।
भविष्य का दृष्टिकोण: लेखक तर्क देते हैं कि चूंकि शोर के एल्गोरिदम को दशकों के अनुकूलन का लाभ मिला है जबकि रेगेव का अस्तित्व केवल दो वर्ष है, इसलिए रेगेव के सर्किट के निरंतर अनुकूलन से अंततः इसे विशिष्ट हार्डवेयर आर्किटेक्चर के लिए पसंदीदा तरीका बनाया जा सकता है।