⚛️ क्वांटम भौतिकी

Improved Exact and Approximate Quantum Fourier Transforms from Multiplication

यह शोध पत्र सटीक और अनुमानित क्वांटम फूरियर ट्रांसफॉर्म्स के लिए बेहतर क्वांटम सर्किट निर्माण प्रस्तुत करता है जो पूर्णांक गुणन एल्गोरिदम में प्रगति का लाभ उठाकर गेट जटिलता को क्रमशः $O(q (\log q)^{\alpha+1})$ और $O(q (\log \log(q/\varepsilon))^{\alpha+1})$ से घटाकर $O(q (\log q)^{\alpha})$ और $O(q (\log \log(q/\varepsilon))^{\alpha})$ कर देता है।

मूल लेखक: Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh

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

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

CC BY 4.0

मूल लेखक: Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh

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

क्वांटम कंप्यूटिंग के क्षेत्र में, मशीनें उस सरल और रैखिक तरीके से सूचना को संसाधित नहीं करती हैं जैसा कि हम अपने रोजमर्रा के लैपटॉप और स्मार्टफोन में देखते हैं। इसके बजाय, वे पदार्थ की उन नाजुक अवस्थाओं का हेरफेर करती हैं जो एक साथ कई विन्यासों (configurations) में मौजूद हो सकती हैं। इन मशीनों को जटिल समस्याओं को हल करने के योग्य बनाने के लिए, वैज्ञानिक 'क्वांटम फूरियर ट्रांसफॉर्म' नामक एक विशिष्ट गणितीय ऑपरेशन पर निर्भर करते हैं। इस ऑपरेशन को एक शक्तिशाली लेंस के रूप में समझें जो संभावनाओं के एक उलझे हुए मिश्रण को लेता है और उन्हें एक स्पष्ट पैटर्न में व्यवस्थित करता है, जिससे डेटा के भीतर छिपी संरचनाओं का पता चलता है। यह छँटाई प्रक्रिया उन सबसे प्रसिद्ध क्वांटम एल्गोरिदम के पीछे का इंजन है, जिनमें आधुनिक एन्क्रिप्शन कोड को तोड़ने या रासायनिक प्रतिक्रियाओं का अनुकरण करने के लिए डिज़ाइन किए गए एल्गोरिदम शामिल हैं। दशकों से, क्वांटम सर्किट में इस लेंस को बनाने का मानक तरीका भौतिक घटकों की एक ऐसी संख्या की मांग करता था जो समस्या का आकार बढ़ने के साथ बहुत तेजी से बढ़ती थी, जिससे बड़े पैमाने पर अनुप्रयोगों को साकार करना कठिन हो गया था।

शोधकर्ताओं के एक दल ने अब इस आवश्यक लेंस को बहुत अधिक कुशलता से बनाने का एक तरीका प्रस्तावित किया है। इस ऑपरेशन के निर्माण के तरीके पर पुनर्विचार करके, उन्होंने प्रदर्शित किया है कि भौतिक घटकों की संख्या को काफी कम किया जा सकता है, बशर्ते कि संख्याओं को गुणा करने के लिए एक विशिष्ट विधि का उपयोग किया जाए। उनका कार्य दिखाता है कि यदि कोई एक निश्चित कुशल विधि का उपयोग करके बड़ी संख्याओं को गुणा कर सकता है, तो क्वांटम फूरियर ट्रांसफॉर्म को पहले की तुलना में बहुत कम चरणों के साथ बनाया जा सकता है। यह सुधार इस ऑपरेशन के पूर्ण, सटीक संस्करण और थोड़े अनुमानित (approximate) संस्करण, जिसका उपयोग अक्सर व्यवहार में किया जाता है, दोनों पर लागू होता है। शोधकर्ताओं ने मौजूदा तकनीकों को क्वांटम अवस्थाओं की प्रतिलिपि (copying) बनाने की एक चतुर युक्ति और एक अंतिम जांच के साथ जोड़कर यह उपलब्धि हासिल की, जो सुनिश्चित करती है कि उत्तर हर बार सही हो।

मुख्य चुनौती इस ट्रांसफॉर्म को करने के लिए आवश्यक गेट्स (gates) की भारी संख्या है। मानक दृष्टिकोण में, गेट्स की संख्या शामिल बिट्स की संख्या के वर्ग के साथ बढ़ती है, जो बड़े कार्यों के लिए अव्यवहार्य हो जाती है। शोधकर्ताओं की एक पिछली पीढ़ी ने इस ट्रांसफॉर्म को पूर्णांक गुणन (integer multiplication) की समस्या से जोड़कर इसमें सुधार किया था, जिससे विकास दर को लघुगणक (logarithm) से जुड़ी स्तर तक कम कर दिया गया। हालांकि, नया अध्ययन इस सीमा को और आगे बढ़ाता है। लेखक दिखाते हैं कि गेट्स की संख्या को स्वयं गुणन विधि की दक्षता के अनुरूप कम किया जा सकता है, न कि उससे एक कदम धीमा। यदि गुणन विधि अत्यधिक कुशल है, तो क्वांटम फूरियर ट्रांसफॉर्म भी तदनुरूप कुशल हो जाता है।

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

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

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

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

तकनीकी सारांश: गुणन (Multiplication) से बेहतर सटीक और अनुमानित क्वांटम फूरियर ट्रांसफॉर्म

समस्या विवरण

क्वांटम फूरियर ट्रांसफॉर्म (QFT) एक मौलिक सबरूटीन है, जो मुख्य रूप से शोर के फैक्टिंग एल्गोरिदम (Shor's factoring algorithm) और क्वांटम फेज एस्टीमेशन (quantum phase estimation) जैसे क्वांटम एल्गोरिदम में उपयोग किया जाता है। $F_{2^q}$ पर मानक सर्किट कार्यान्वयन के लिए QFT में $O(q^2)$ गेट्स की आवश्यकता होती है। जबकि क्लेव और वाट्रस (Cleve and Watrous, 2000) ने पूर्णांक गुणन (integer multiplication) एल्गोरिदम का लाभ उठाकर सटीक QFT के लिए गेट काउंट को $O(q(\log q)^2 \log \log q)$ तक कम कर दिया, और अहोकास, क्लेव और हेल्स (Ahokas, Cleve, and Hales, 2003) ने अनुमानित (approximate) QFT के लिए और अधिक अनुकूलन प्रदान किए, लेखकों ने पूर्णांक गुणन की जटिलता और परिणामी QFT सर्किट जटिलता के बीच एक अंतर की पहचान की है।

विशेष रूप से, यदि $n$ -बिट संख्याओं के पूर्णांक गुणन को $M(n) = O(n(\log n)^\alpha)$ गेट्स के साथ किया जा सकता है, तो क्लेव-वाट्रस निर्माण $O(q(\log q)^{\alpha+1})$ गेट्स के साथ एक सटीक QFT प्रदान करता है। यह शोध पत्र इस प्रश्न को संबोधित करता है कि क्या इस ओवरहेड को कम किया जा सकता है, जिसका लक्ष्य गुणन जटिलता के साथ अधिक निकटता से मेल खाना है (अर्थात, सटीक और अनुमानित दोनों QFT के लिए $O(q(\log q)^\alpha)$ प्राप्त करना)।

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

लेखक QFT निर्माण की गेट जटिलता में सुधार के लिए दोहरे दृष्टिकोण का प्रस्ताव करते हैं:

1. सटीक QFT निर्माण (Exact QFT Construction)

लेखक मॉस्का और ज़ालका (Mosca and Zalka, 2003) की "एक्ज़ैक्टिफिकेशन" (exactification) विधि को क्लेव-वाट्रस (2000) के गुणन-आधारित कार्यान्वयन के साथ जोड़ते हैं।

एम्प्लीट्यूड एम्प्लीफिकेशन (Amplitude Amplification): वे एक अनुमानित QFT सर्किट (सफलता की संभावना $p \geq 3/4$ $p \geq 3/4$ के साथ) को सटीक सर्किट में बदलने की एक तकनीक का उपयोग करते हैं। इसमें शामिल है:
1. फूरियर स्टेट की प्रतिलिपि बनाना: फूरियर स्टेट को डुप्लिकेट करने के लिए क्लेव-वाट्रस कॉपीइंग सर्किट का उपयोग करना, जिससे मूल अवस्था को सत्यापन के लिए सुरक्षित रखा जा सके।
2. संभावना समायोजन (Probability Adjustment): एक सहायक क्यूबिट (auxiliary qubit) पेश करना और सही उत्तर और सहायक क्यूबिट अवस्था की संयुक्त सफलता संभावना को ठीक $1/4$ करने के लिए एक विशिष्ट सिंगल-क्यूबिट रोटेशन $B(\theta_q)$ लागू करना।
3. ग्रोवर इटरेशन (Grover Iteration): सफलता की संभावना को बढ़ाकर 1 करने के लिए एम्प्लीट्यूड एम्प्लीफिकेशन (एक ग्रोवर इटरेशन) का एक एकल चरण लागू करना।
गेट सेट: निर्माण में मानक गेट्स (Hadamard, CNOT, Phase gates) साथ ही एक विशिष्ट सिंगल-क्यूबिट रोटेशन $B(\theta_q)$ का उपयोग किया जाता है जिसका कोण $q$ पर निर्भर करता है। एम्प्लीफिकेशन चरण के लिए प्रारंभिक आयाम (amplitude) निर्धारित करने के लिए यह गैर-मानक गेट आवश्यक है।

2. अनुमानित QFT निर्माण (Approximate QFT Construction)

अनुमानित QFT के लिए, लेखक अहोकास, क्लेव और हेल्स (ACH) के रिकर्सिव निर्माण को अनुकूलित करते हैं।

रिकर्सिव स्प्लिटिंग (Recursive Splitting): इनपुट रजिस्टर को पुनरावर्ती रूप से ऊपरी और निचले हिस्सों में विभाजित किया जाता है। निर्माण ऊपरी रजिस्टर पर एक रिकर्सिव QFT लागू करता है, रजिस्टरों के बीच एक "प्रोडक्ट-फेज" ऑपरेशन करता है, निचले रजिस्टर पर एक रिकर्सिव QFT लागू करता है, और रजिस्टरों को स्वैप करता है।
ट्रंकेशन (Truncation): प्रोडक्ट-फेज ऑपरेशन में, केवल इनपुट्स के $k = \Theta(\log(q/\varepsilon))$ सबसे महत्वपूर्ण बिट्स का उपयोग किया जाता है, जहाँ $\varepsilon$ अनुमान त्रुटि (approximation error) है।
बेस केसेस (Base Cases): पुनरावृत्ति (recursion) तब रुक जाती है जब रजिस्टर का आकार $2k$ से कम हो जाता है। इन बेस केसेस के लिए मानक क्लेव-वाट्रस सटीक QFT (लागत $O(k(\log k)^{\alpha+1})$ ) के बजाय, लेखक अपने बेहतर सटीक QFT (लागत $O(k(\log k)^\alpha)$ ) का उपयोग करते हैं।
रोटेशन एप्रोक्सिमेशन (Rotation Approximation): चूंकि बेहतर सटीक QFT के लिए गैर-मानक रोटेशन $B(\theta_q)$ की आवश्यकता होती है, लेखक दिखाते हैं कि इन रोटेशन्स को मानक फेज गेट्स $P(2\pi a/2^d)$ का उपयोग करके कुशलतापूर्वक अनुमानित किया जा सकता है, जिससे गेट काउंट या सहायक स्पेस (auxiliary space) में बिना किसी एसिम्प्टोटिक वृद्धि के इसे किया जा सकता है। परिणामस्वरूप, $\varepsilon$ -अनुमानित QFT के लिए अंतिम निर्माण क्लेव और वाट्रस (Hadamard, controlled-NOT, और सटीक फेज गेट्स) के समान गेट सेट का उपयोग करता है।

मुख्य योगदान और परिणाम

1. बेहतर गेट जटिलता (Improved Gate Complexity)

मुख्य योगदान सटीक और अनुमानित दोनों QFT के लिए गेट काउंट में एसिम्प्टोटिक कमी है, जो सीधे पूर्णांक गुणन $M(n) = O(n(\log n)^\alpha)$ की जटिलता से जुड़ा हुआ है।

सटीक QFT (Theorem 1.1): लेखक $q$ $q$ क्यूबिट्स पर एक सटीक QFT का निर्माण $O(q(\log q)^\alpha)$ गेट्स का उपयोग करके करते हैं। यह क्लेव और वाट्रस द्वारा दिए गए पिछले सर्वोत्तम $O(q(\log q)^{\alpha+1})$ $O (q (lo g q)^{α + 1})$ के ऊपर सुधार है।
- नोट: इस निर्माण के लिए $q$ पर निर्भर एक अतिरिक्त सिंगल-क्यूबिट रोटेशन $B(\theta_q)$ की आवश्यकता होती है।
अनुमानित QFT (Theorem 1.2): एक अनुमानित त्रुटि $\varepsilon$ $ε$ के लिए, लेखक $O(q(\log \log(q/\varepsilon))^\alpha)$ गेट्स का उपयोग करके एक सर्किट का निर्माण करते हैं। यह अहोकास, क्लेव और हेल्स द्वारा दिए गए पिछले $O(q(\log \log(q/\varepsilon))^{\alpha+1})$ $O (q (lo g lo g (q / ε))^{α + 1})$ के ऊपर सुधार है।
- नोट: यह निर्माण आवश्यक रोटेशन्स को अनुमानित करके क्लेव और वाट्रस (Hadamard, controlled-NOT, और सटीक फेज गेट्स) के समान गेट सेट का उपयोग करता है।

2. हालिया गुणन दावों के निहितार्थ

यह शोध पत्र पूर्णांक गुणन की जटिलता $O(n(\log n)^{1-\kappa})$ (जहाँ $0 < \kappa < 1$ एक स्थिरांक है) के संबंध में OpenAI के एक हालिया दावे के संभावित प्रभाव को रेखांकित करता है।

यदि यह दावा Boolean सर्किट के लिए सत्य होता है, तो $\alpha = 1-\kappa$ सेट करने पर एक सटीक QFT के लिए $o(q \log q)$ गेट्स और एक अनुमानित QFT के लिए $o(q \log \log q)$ गेट्स प्राप्त होंगे।
यह ऐसे QFT सर्किट की ओर संकेत करता है जो मानक $O(q^2)$ या यहाँ तक कि $O(q \log q)$ सीमाओं से भी काफी अधिक कुशल हो सकते हैं।

3. संसाधन सीमाएँ (Resource Bounds)

सहायक क्यूबिट्स (Auxiliary Qubits): सटीक निर्माण $O(a(q) + M(q))$ सहायक क्यूबिट्स का उपयोग करता है (जहाँ $a(q)$ अनुमानित सर्किट का सहायक काउंट है)। अनुमानित निर्माण $O(L(\log L)^\alpha)$ सहायक क्यूबिट्स का उपयोग करता है, जहाँ $L = \log(q/\varepsilon)$ है।
यूनिफॉर्मिटी (Uniformity): लेखक स्पष्ट रूप से कहते हैं कि उनके सर्किट परिवार नॉन-यूनिफॉर्म (non-uniform) हैं। ऐसा इसलिए है क्योंकि रोटेशन $B(\theta_q)$ के लिए कोण $\theta_q$ को वर्तमान में एक क्लासिकल एल्गोरिदम द्वारा कुशलतापूर्वक नहीं निकाला जा सकता है। वे इन कोणों के कुशल उत्पादन को एक स्वाभाविक खुला प्रश्न (open question) बताते हैं।

महत्व और दावे

यह शोध पत्र पूर्णांक गुणन की लागत और क्वांटम फूरियर ट्रांसफॉर्म की लागत के बीच के सैद्धांतिक संबंध को कड़ा करने का दावा करता है। गेट जटिलता में एक अतिरिक्त लॉगरिदमिक कारक को हटाकर, लेखक प्रदर्शित करते हैं कि QFT को अंतर्निहित गुणन एल्गोरिदम जितना कुशल बनाया जा सकता है।

लेखक अपने सर्किट की यूनिफॉर्मिटी के संबंध में विनम्र हैं, और स्वीकार करते हैं कि एक विशिष्ट रोटेशन कोण पर निर्भरता वर्तमान ज्ञान के अनुसार निर्माण को यूनिफॉर्म होने से रोकती है। वे आरून (Aaronson, 2025) द्वारा उठाए गए इस प्रश्न को भी दोहराते हैं कि क्या $q$ क्यूबिट्स पर एक सटीक QFT को $O(q)$ गेट्स के साथ लागू किया जा सकता है, यह नोट करते हुए कि उनके परिणाम एक्सपोनेंट (exponent) में सुधार करते हैं लेकिन अभी तक लीनियर साइज (linear size) तक नहीं पहुँचते हैं।

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