⚛️ quantum physics

Asymptotic yet practical optimization of quantum circuits implementing GF( $2^m$ ) multiplication and division operations

यह शोध पत्र GF( $2^m$ ) गुणन और विभाजन के लिए एसिम्प्टोटिकली (asymptotically) और व्यावहारिक रूप से अनुकूलित, एंसिला-मुक्त (ancilla-free) क्वांटम सर्किट प्रस्तुत करता है जो कुशल स्थिरांक बहुपद गुणन (constant polynomial multiplication) और अपरिमेय बहुपदों (irreducible polynomials) के रणनीतिक चयन के माध्यम से गेट गणना जटिलताओं को महत्वपूर्ण रूप से कम करते हैं और क्रिप्टोग्राफिक रूप से प्रासंगिक मापदंडों के लिए प्रदर्शन में सुधार करते हैं।

मूल लेखक: Noureldin Yosri, Dmytro Gavinsky, Dmitri Maslov

प्रकाशित 2026-03-25

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

CC BY 4.0

मूल लेखक: Noureldin Yosri, Dmytro Gavinsky, Dmitri Maslov

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

कल्पना कीजिए कि आप एक सुपर-फास्ट कैलकुलेटर बनाने की कोशिश कर रहे हैं, लेकिन इसमें आप संख्याओं को जोड़ने के बजाय, "पॉलीनोमियल" (जो कि $x^2 + 1$ जैसे फैंसी बीजगणितीय व्यंजक हैं) को गुणा और भाग कर रहे हैं, जो गैलोइस फील्ड $GF(2^m)$ नामक एक विशेष गणितीय दुनिया के भीतर है।

यह केवल गणित की क्लास के बारे में नहीं है; इस विशिष्ट प्रकार का गणित आधुनिक एन्क्रिप्शन (आपके बैंक डेटा को सुरक्षित रखने) और भविष्य के क्वांटम कंप्यूटरों के पीछे का गुप्त मंत्र है।

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

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

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

1. "गुणा" की समस्या: बाधा (The Bottleneck)

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

उपमा: इस असेंबली लाइन को एक राजमार्ग के रूप में सोचें। गुणा का चरण एक विशाल, 10-लेन का ट्रैफिक जाम था जहाँ कारों (डेटा) को एक-दूसरे के बीच से रास्ता बनाना पड़ता था। पुराने तरीके में "CNOT गेट्स" (बुनियादी स्विच जो डेटा को स्थानांतरित करते हैं) की संख्या क्वाड्रेटिक ( $m^2$ ) रूप से बढ़ती थी। यदि आप संख्या का आकार दोगुना कर देते, तो ट्रैफिक जाम चार गुना बदतर हो जाता।

नया समाधान:
लेखकों ने उस विशिष्ट ट्रैफिक जाम को ठीक करने का एक तरीका खोजा। उन्होंने एक विशेष प्रकार का "रोड लेआउट" (एक अपरिमेय बहुपद/irreducible polynomial) खोजा जो उस कॉन्स्टेंट गुणा चरण को एक सीधी रेखा में करने की अनुमति देता है।

परिणाम: उन्होंने उस 10-लेन के ट्रैफिक जाम को एक सिंगल-लेन हाईवे में बदल दिया। जटिलता क्वाड्रेटिक ( $m^2$ ) से घटकर लीनियरिथमिक ( $m \log m$ ) हो गई।
प्रभाव: वास्तविक दुनिया के एन्क्रिप्शन में उपयोग किए जाने वाले व्यावहारिक आकारों के लिए, यह केवल एक छोटा सुधार नहीं है; यह दक्षता में 100x से 350x की तेजी (speedup) है। उन्होंने हजारों "ब्रिक्स" (गेट्स) बचा लिए जो बर्बाद हो जाते।

2. "भाग" की समस्या: इनवर्स पहेली (The Inverse Puzzle)

पुराना तरीका:
इस गणित की दुनिया में भाग देना वास्तव में "इनवर्स" (जैसे कि 2 से भाग देने का मतलब 0.5 से गुणा करना है) से गुणा करने के समान है। इस इनवर्स को खोजने के लिए, पुराने तरीके ने "इतोह-त्सुजी एल्गोरिदम" नामक एक रेसिपी का उपयोग किया।

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

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

परिणाम: उन्होंने संख्याओं को विभाजित करने के लिए आवश्यक चरणों की संख्या को काफी कम कर दिया। कुछ आकारों के लिए, उन्होंने काम को 28% तक कम कर दिया। इसका मतलब है कि क्वांटम कंप्यूटर एन्क्रिप्शन कोड को बहुत तेज़ी से तोड़ (या सत्यापित) सकते हैं।

3. "स्क्वायर रूट" का आश्चर्य

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

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

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

क्वांटम कंप्यूटरों को एक नए प्रकार के इंजन के रूप में सोचें। लंबे समय तक, हम जानते थे कि इंजन कैसे बनाया जाता है, लेकिन ईंधन की खपत इतनी अधिक थी कि कार बहुत दूर तक नहीं जा सकती थी।

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

मुख्य बात:
उन्होंने केवल संख्याओं में बदलाव नहीं किया; उन्होंने गणित में एक मौलिक शॉर्टकट खोजा है जो क्वांटम कंप्यूटरों को जटिल क्रिप्टोग्राफिक कार्यों को 100 गुना कम प्रयास के साथ करने की अनुमति देता है। यह हमें क्वांटम कंप्यूटरों के करीब लाता है जो वास्तव में वास्तविक दुनिया की समस्याओं को हल कर सकें, जैसे कि अटूट कोड को तोड़ना या नई दवाओं को डिजाइन करना, बिना अपनी शक्ति खोए।

यहाँ शोध पत्र "Asymptotic yet practical optimization of quantum circuits implementing GF(2^m) multiplication and division operations" का विस्तृत तकनीकी सारांश दिया गया है।

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

गैलोइस फील्ड (Galois Field) अंकगणित, विशेष रूप से $GF(2^m)$ पर, विभिन्न क्वांटम एल्गोरिदम के लिए एक मौलिक प्रिमिटिव (primitive) है, जिसमें एलिप्टिक कर्व डिस्क्रीट लॉगरिदम समस्या (ECDLP), क्वांटमनेस के प्रमाण (proofs of quantumness), और डिकोडेड क्वांटम इंटरफेरोमेट्री शामिल हैं।

बाधा (The Bottleneck): $GF(2^m)$ गुणन (multiplication) के लिए मौजूदा अनसिलिया-मुक्त (ancilla-free) क्वांटम सर्किट (जो करात्सुबा एल्गोरिदम पर आधारित हैं) CNOT गेट्स के लिए $O(m^2)$ गेट काउंट जटिलता से ग्रस्त हैं। यह द्विघाती (quadratic) लागत मुख्य रूप से $1 + x^{\lceil m/2 \rceil}$ के बहुपद (constant polynomial) द्वारा गुणन को लागू करने के कारण होती है, जो वैन हूफ (Van Hoof) के निर्माण [46] में एक आवश्यक चरण है।
विभाजन जटिलता (Division Complexity): फील्ड डिवीजन (इनवर्जन) आमतौर पर इतो-सुजी (Itoh-Tsujii) एल्गोरिदम पर निर्भर करता है, जिसमें बार-बार स्क्वेयरिंग और मल्टीप्लिकेशन शामिल है। पिछले कार्यान्वयन अक्षम लीनियर रिवर्सिबल स्क्वेयरिंग सर्किट के कारण $O(m^2 \log m)$ CNOT जटिलता से ग्रस्त थे।
लक्ष्य: लेखकों का लक्ष्य इन ऑपरेशन्स की एसिम्प्टोटिक (asymptotic) जटिलता को गुणन के लिए $O(m \log_2 3)$ तक कम करने और विभाजन की जटिलता में सुधार करने का है, जबकि अनसिलिया-मुक्त (या कम अनसिलिया) बाधाओं को बनाए रखते हुए और क्रिप्टोग्राफिक रूप से प्रासंगिक फील्ड आकारों (जैसे, $m=163, 256, 1024$ ) के लिए व्यावहारिक सुधार सुनिश्चित करना है।

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

यह शोध पत्र बीजगणितीय संख्या सिद्धांत (algebraic number theory), रैखिक बीजगणित अनुकूलन (linear algebra optimization), और सर्किट संश्लेषण (circuit synthesis) तकनीकों को संयोजित करते हुए एक बहु-आयामी दृष्टिकोण अपनाता है।

A. कॉन्स्टेंट मल्टीप्लिकेशन ( $1 + x^{\lceil m/2 \rceil}$ ) का अनुकूलन

मुख्य नवाचार $1 + x^{\lceil m/2 \rceil}$ द्वारा गुणन की लागत को $O(m^2)$ से घटाकर $O(m)$ करना है।

मैट्रिक्स प्रतिनिधित्व (Matrix Representation): गुणन को एक रैखिक रिवर्सिबल ट्रांसफॉर्मेशन (एक $m \times m$ मैट्रिक्स $GF(2)$ पर) के रूप में देखा जाता है।
इर्रेड्यूसिबल बहुपद चयन (Irreducible Polynomial Selection): लेखक सिद्ध करते हैं कि किसी भी $m$ $m$ के लिए, ऐसे इर्रेड्यूसिबल बहुपद मौजूद हैं जहाँ मैट्रिक्स संरचना एक अत्यधिक कुशल CNOT सर्किट की अनुमति देती है।
- सम $m$ (Even $m$ ): वे ट्रिनोमियल ( $x^m + x^l + 1$ ) या सामान्य बहुपदों का उपयोग करते हैं जहाँ उच्चतम और निम्नतम गैर-तुच्छ पदों के बीच का अंतर छोटा है ( $l_1 - l_k \in O(1)$ )। वे $O(m)$ गेट्स वाले CNOT सर्किट का निर्माण करने के लिए एल्गोरिदम 1 और 2 विकसित करते हैं।
- विषम $m$ (Odd $m$ ): वे एक विशिष्ट वर्ग के बहुपदों को पेश करते हैं और एक विशिष्ट सर्कुलेंट मैट्रिक्स को सिंथेसाइज करने के लिए एल्गोरिदम 5 और 6 का उपयोग करते हैं, जिससे $O(m)$ जटिलता प्राप्त होती है।
परिणाम: यह द्विघाती बाधा को हटा देता है, जिससे समग्र करात्सुबा गुणन $O(m \log_2 3)$ CNOT जटिलता प्राप्त कर सकता है।

B. फील्ड डिवीजन का अनुकूलन

डिवीजन फर्माट के लिटिल थ्योरम (Fermat's Little Theorem) का उपयोग करके $b^{-1} = b^{2^m-2}$ के माध्यम से किया जाता है।

एडिशन चेन्स (Addition Chains): मानक इतो-सुजी एडिशन चेन के बजाय, लेखक गुणन की संख्या को कम करने के लिए अनुकूलित एडिशन चेन्स (डिमिट्रोव और जारविने [12] पर आधारित) का उपयोग करते हैं।
समकालिक अनुकूलन (Simultaneous Optimization): वे ऐसे इर्रेड्यूसिबल बहुपदों का चयन करते हैं जो एक साथ अनुकूलित करते हैं:
1. कॉन्स्टेंट मल्टीप्लिकेशन (जैसा कि ऊपर वर्णित है)।
2. फील्ड स्क्वेयरिंग: वे स्क्वेयरिंग ( $a \to a^2$ ) के लिए सर्किट डिजाइन करते हैं जो $O(m \log m)$ जटिलता में भी चलते हैं।
जटिलता में कमी: अनुकूलित स्क्वेयरिंग को एडिशन चेन्स के साथ जोड़कर, डिवीजन के लिए कुल CNOT जटिलता $O(m^2 \log m)$ से घटकर $O(m^2 \log \log m / \log m)$ हो जाती है।

C. टोफोली गेट रिडक्शन (Toffoli Gate Reduction)

करात्सुबा-जैसे फॉर्मूले (Karatsuba-like Formulas): लेखक गुणन की संख्या को कम करने के लिए "करात्सुबा-जैसे" फॉर्मूलों (इनपुट को $k$ टुकड़ों में विभाजित करना) का उपयोग करके करात्सुबा एल्गोरिदम का सामान्यीकरण करते हैं।
पैरिटी कंट्रोल्ड टोफोली (PCTOF): वे पैरिटी कंट्रोल्स के आधार पर टोफोली गेट्स को समूहबद्ध करने की एक तकनीक पेश करते हैं, जिससे कंट्रोल मैट्रिक्स के रैंक को कम करने में मदद मिलती है। यह गैर-पावर-ऑफ-2 $m$ के लिए टोफोली काउंट को 5% तक कम कर देता है।

D. सैद्धांतिक अंतर्दृष्टि: यूनिटरी के वर्गमूल (Square Roots of Unitities)

शोध पत्र में एक सैद्धांतिक लेम्मा शामिल है जो यह प्रदर्शित करता है कि कुछ रैखिक रिवर्सिबल यूनिटरी $U$ के लिए, वर्गमूल $\sqrt{U}$ को $U$ (जो कि कांस्टेंट डेप्थ हो सकता है) की तुलना में एसिम्प्टोटिक रूप से अधिक गहरी सर्किट ( $\Omega(\log n)$ ) की आवश्यकता हो सकती है, भले ही दोनों केवल CNOTs के साथ लागू करने योग्य हों।

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

एसिम्प्टोटिक सुधार (Asymptotic Improvement):
- गुणन (Multiplication): CNOT जटिलता को $O(m^2)$ से घटाकर $O(m \log_2 3)$ कर दिया गया।
- विभाजन (Division): CNOT जटिलता को $O(m^2 \log m)$ से घटाकर $O(m^2 \log \log m / \log m)$ कर दिया गया।
व्यावहारिक अनुकूलन (Practical Optimization):
- विशिष्ट वर्गों के इर्रेड्यूसिबल बहुपदों के लिए इन सीमाओं की गारंटी देने वाले रचनात्मक एल्गोरिदम (एल्गोरिदम 1-6) विकसित किए।
- सभी $m$ के लिए उपयुक्त इर्रेड्यूसिबल बहुपद मौजूद हैं, जो 10,000 तक के सभी प्रासंगिक क्रिप्टोग्राफिक आकार को कवर करते हैं।
गेट काउंट में कमी (Gate Count Reductions):
- कॉन्स्टेंट मल्टीप्लिकेशन चरण के लिए CNOT काउंट में 100x+ की कमी हासिल की (उदाहरण के लिए, $m=6159$ के लिए, ~2.2M से ~6k गेट्स तक की कमी)।
- टेबल I में गुणन के लिए CNOT काउंट में ~20.9% और टोफोली रिडक्शन में ~18% की कमी देखी गई।
- टेबल II में विभाजन के लिए CNOT और टोफोली दोनों गेट्स में ~28% तक की कमी।
अनसिलिया-मुक्त बाधा (Ancilla-Free Constraint): सभी अनुकूलन गुणन के लिए बिना किसी सहायक क्यूबिट (अनसिलिया) के, और विभाजन के लिए न्यूनतम अनसिलिया ओवरहेड के साथ प्राप्त किए गए हैं, जो उन्हें निकट-अवधि दोष-सहिष्णु (near-term fault-tolerant) क्वांटम कंप्यूटरों के लिए उपयुक्त बनाते हैं।

4. परिणाम (Results)

लेखक अपने अनुकूलित सर्किटों की तुलना अत्याधुनिक कार्यान्वयनों (वैन हूफ [46], पुत्रंतो एट अल. [37], और जेंग एट अल. [3]) से करते हुए व्यापक संख्यात्मक परिणाम प्रदान करते हैं।

गुणन (Table I):
- $m=163$ (एक मानक एलिप्टिक कर्व साइज) के लिए, CNOT काउंट 36,439 से घटकर 35,070 और टोफोली 4,387 से घटकर 3,605 हो जाता है।
- बड़े $m$ (जैसे, $m=1024$ ) के लिए, CNOT काउंट 591,942 से घटकर 525,140 हो जाता है।
- बेहतर एसिम्प्टोटिक स्केलिंग के कारण $m$ के साथ सुधार का कारक बढ़ता जाता है।
विभाजन (Table II):
- $m=64$ के लिए, CNOT काउंट 169,272 से घटकर 121,120 (~28% की कमी) हो जाता है।
- $m=1024$ के लिए, CNOT काउंट 28.3M से घटकर 22.9M, और टोफोली काउंट 2.18M से घटकर 1.59M हो जाता है।
- अनसिलिया रजिस्टर (AR) का उपयोग भी अनुकूलित किया गया है, जो कभी-कभी इसकी संख्या को 22% तक कम कर देता है।
टूम-कुक (Toom-Cook) (Appendix A): लेखकों ने टूम-कुक एल्गोरिदम का पता लगाया लेकिन पाया कि उच्च लीडिंग कांस्टेंट और रिकर्सन ओवरहेड के कारण वे परीक्षण किए गए रेंज के लिए अनुकूलित करात्सुबा-जैसे दृष्टिकोण से बेहतर प्रदर्शन नहीं करते हैं।

5. महत्व (Significance)

क्रिप्टोग्राफिक प्रभाव (Cryptographic Impact): गेट काउंट में कमी सीधे तौर पर शोर के एल्गोरिदम (Shor's algorithm) या संबंधित क्वांटम हमलों के माध्यम से एलिप्टिक कर्व क्रिप्टोग्राफी (ECC) को तोड़ने के लिए आवश्यक संसाधनों की आवश्यकताओं को कम करती है। यह "क्वांटम एडवांटेज" की समयसीमा के अनुमानों को परिष्कृत करता है।
एल्गोरिदमिक दक्षता (Algorithmic Efficiency): यह कार्य सिद्ध करता है कि करात्सुबा-आधारित क्वांटम सर्किटों में कॉन्स्टेंट मल्टीप्लिकेशन की "बाधा" को समाप्त किया जा सकता है, जिससे $O(m \log_2 3)$ केवल एक सैद्धांतिक सीमा के बजाय एक व्यावहारिक वास्तविकता बन जाता है।
हार्डवेयर प्रासंगिकता (Hardware Relevance): अनसिलिया-मुक्त और कम-अनसिलिया निर्माणों पर ध्यान केंद्रित करके, परिणाम तुरंत शुरुआती दोष-सहिष्णु क्वांटम कंप्यूटरों के लिए लागू होते हैं जहाँ क्यूबिट की संख्या प्राथमिक बाधा है।
लागत मॉडल संरेखण (Cost Model Alignment): अनुकूलन $10 \times \text{Toffoli} + \text{CNOT}$ लागत फलन को लक्षित करता है, जो आधुनिक त्रुटि सुधार मॉडलों को दर्शाता है जहाँ टोफोली गेट्स, CNOT की तुलना में काफी महंगे होते हैं, लेकिन CNOT भी नगण्य नहीं हैं।

संक्षेप में, यह शोध पत्र क्वांटम सर्किटों में $GF(2^m)$ अंकगणित को अनुकूलित करने के लिए एक व्यापक ढांचा प्रदान करता है, जो दोनों एसिम्प्टोटिक अनुकूलता और गेट काउंट में पर्याप्त व्यावहारिक कमी प्राप्त करता है, जो क्रिप्टोग्राफी और सिमुलेशन में क्वांटम एल्गोरिदम की व्यवहार्यता के लिए महत्वपूर्ण है।