⚛️ quantum physics

An efficient Pauli decomposition algorithm for structured matrices

यह शोध पत्र एक यादृच्छिक शास्त्रीय एल्गोरिदम प्रस्तुत करता है जो संरचित मैट्रिसेस (structured matrices) के लिए वादे की गई विरलता (promised sparsity) के साथ सटीक पाउली अपघटन (Pauli decomposition) को बहुपद समय (polynomial time) में कुशलतापूर्वक पुनर्प्राप्त करता है, जो सामान्य सघन मैट्रिसेस (generic dense matrices) के लिए डिज़ाइन की गई मौजूदा विधियों की घातीय जटिलता (exponential complexity) पर विजय प्राप्त करता है।

मूल लेखक: Daniel J. Spencer, Kishor Bharti, Alexey V. Gorshkov

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

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

CC BY 4.0

मूल लेखक: Daniel J. Spencer, Kishor Bharti, Alexey V. Gorshkov

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

यहाँ इस शोध पत्र का सरल भाषा और रोज़मर्रा के उदाहरणों के साथ विवरण दिया गया है।

बड़ी समस्या: "पॉली पहेली" (The Pauli Puzzle)

कल्पना कीजिए कि आपके पास एक क्वांटम कंप्यूटर के लिए एक विशाल, जटिल निर्देश पुस्तिका (instruction manual) है। यह मैनुअल एक विशेष कोड में लिखा गया है जिसे पॉली स्ट्रिंग्स (Pauli strings) कहते हैं। एक क्वांटम एल्गोरिदम चलाने के लिए, आपको इस मैनुअल को उसके व्यक्तिगत वाक्यों (पॉली स्ट्रिंग्स) में तोड़ना होगा और यह जानना होगा कि प्रत्येक वाक्य क्या कहता है।

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

मौजूदा तरीके पूरे समुद्र तट को पढ़ने की कोशिश करते हैं। वे संपूर्ण हैं, लेकिन वे उन क्वांटम कंप्यूटरों के लिए बहुत धीमे हैं जिन्हें हम अभी बना रहे हैं (जिन्हें NISQ डिवाइस कहा जाता है)।

वादा: एक विरल समुद्र तट (A Sparse Beach)

इस शोध पत्र के लेखक कहते हैं: "रुकिए। क्या होगा अगर हमारे पास रेत से भरा समुद्र तट न हो? क्या होगा अगर हमें यह आश्वासन दिया जाए कि पूरे मैनुअल में केवल कुछ ही रेत के कण छिपे हुए हैं?"

तकनीकी शब्दों में, वे मानते हैं कि मैट्रिक्स स्पार्स (sparse/विरल) है। इसका मतलब है कि अरबों संभावित पॉली स्ट्रिंग्स में से, केवल एक छोटा, प्रबंधनीय संख्या (मान लीजिए $k$ ) ही वास्तव में उपयोग की जा रही है।

शोध पत्र पूछता है: यदि हमें पता है कि पहेली सरल है (स्पार्स है), तो क्या हम पूरे समुद्र तट को पढ़े बिना इसे जल्दी हल कर सकते हैं?

समाधान: एक चतुर जासूस

लेखकों ने एक नया, रैंडमाइज्ड (यादृच्छिक) एल्गोरिदम बनाया है जो एक चतुर जासूस की तरह काम करता है। मैनुअल के हर एक पन्ने को पढ़ने के बजाय, जासूस छिपे हुए रेत के कणों को खोजने के लिए कुछ स्मार्ट ट्रिक्स का उपयोग करता है।

यहाँ बताया गया है कि जासूस कैसे काम करता है, जिसे तीन चरणों में विभाजित किया गया है:

1. "फ्लैशलाइट" स्कैन (स्थानों का पता लगाना)

कल्पना कीजिए कि पॉली स्ट्रिंग्स के दो भाग हैं: एक "लोकेशन" वाला भाग (जहाँ क्रिया होती है) और एक "साइन" वाला भाग (कि वह सकारात्मक है या नकारात्मक)।

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

2. "यूनिक" बनाम "भीड़भाड़ वाले" कमरे

एक बार जब जासूस को लोकेशन मिल जाती है, तो वह जाँचता है कि वह एक "यूनिक" (अद्वितीय) कमरा है या "क्राउडेड" (भीड़भाड़ वाला) कमरा।

यूनिक कमरे: कभी-कभी, एक लोकेशन में केवल एक मोमबत्ती (एक पॉली स्ट्रिंग) होती है। यह आसान है। जासूस बस मोमबत्ती का लेबल पढ़ता है और आगे बढ़ जाता है।
भीड़भाड़ वाले कमरे: कभी-कभी, एक ही स्थान पर कई मोमबत्तियाँ एक के ऊपर एक रखी होती हैं, और उनकी रोशनी एक-दूसरे को रद्द कर सकती है या आपस में मिल सकती है। यह कठिन हिस्सा है।

3. "फोल्डिंग" ट्रिक (भीड़भाड़ वाले कमरों को हल करना)

जब जासूस को भीड़भाड़ वाला कमरा मिलता है, तो वह लेबल नहीं पढ़ सकता क्योंकि वे आपस में मिल गए होते हैं।

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

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

यह शोध पत्र सिद्ध करता है कि यह जासूस विधि तेज़ है।

पुराना तरीका: इसमें समय एक्सपोनेंशियल रूप से बढ़ता है (जैसे $2^{100}$ )। बड़े कार्यों के लिए असंभव।
नया तरीका: इसमें समय पॉलिनोमियल रूप से बढ़ता है (जैसे $n^3$ )। यह वास्तविक दुनिया के उपयोग के लिए पर्याप्त तेज़ है।

एल्गोरिदम केवल अनुमान नहीं लगाता है; इसमें "प्रमाणन" (certification) चरण भी शामिल हैं। यह सुनिश्चित करने के लिए कि इसने कोई गलती नहीं की है, यह अपने स्वयं के काम की जाँच करता है। यदि इसे कोई गलती मिलती है, तो यह कहता है "Fail" और रुक जाता है, बजाय इसके कि आपको गलत उत्तर दे।

निष्कर्ष (The Bottom Line)

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

संक्षेप में: उन्होंने यह जानकर एक विशाल पहेली को हल करने का तरीका खोजा है कि आपको हर टुकड़े को देखने की ज़रूरत नहीं है—आपको बस सही टुकड़ों को, यादृच्छिक रूप से, देखना है, और बाकी को तब तक मोड़ना है जब तक कि वे खुद को प्रकट न कर दें।

तकनीकी सारांश: संरचित मैट्रिसेस के लिए एक कुशल पाउली अपघटन एल्गोरिदम (An Efficient Pauli Decomposition Algorithm for Structured Matrices)

समस्या विवरण (Problem Statement)
क्लासिकल $2^n \times 2^n$ मैट्रिसेस को पाउली स्ट्रिंग्स के रैखिक संयोजन (linear combinations) में विघटित करना निकट-अवधि (near-term) क्वांटम एल्गोरिदम के एंड-टू-एंड कार्यान्वयन के लिए एक महत्वपूर्ण बाधा है, विशेष रूप से रसायन विज्ञान, मशीन लर्निंग और वित्त में। कई एल्गोरिदम, जैसे कि वेरिएशनल क्वांटम आइजनवैल्यू सॉल्वर (VQE) और लीनियर अलजेब्रा सॉल्वर, यह मान लेते हैं कि इनपुट डेटा पाउली स्ट्रिंग्स के 'लीनियर कॉम्बिनेशन ऑफ यूनिटरीज' (LCU) के रूप में प्रदान किया गया है। हालांकि, सामान्य क्लासिकली-निर्धारित मैट्रिसेस के लिए, यह अपघटन (decomposition) पूर्व में ज्ञात नहीं होता है।

मौजूदा एल्गोरिदम सामान्य, सघन (dense) मैट्रिसेस के लिए $n$ क्वबिट्स की संख्या के साथ चरघातांकीय (exponentially) रूप से स्केल करते हैं। सबसे सीधा दृष्टिकोण $O(32^n)$ समय की आवश्यकता रखता है, जबकि मौजूदा सर्वोत्तम विधियों (जैसे कि PennyLane में) का स्केल $O(n4^n)$ है। यह चरघातांकीय लागत इसलिए उत्पन्न होती है क्योंकि, सबसे खराब स्थिति में, एक मैट्रिक्स का सभी $4^n$ पाउली बेस तत्वों पर समर्थन (support) हो सकता है, जिसके लिए सभी गुणांकों (coefficients) को पुनः प्राप्त करने की आवश्यकता होती है।

यह शोध पत्र पाउली अपघटन समस्या के एक प्रॉमिस वर्जन (promise version) को संबोधित करता है। यह मानता है कि इनपुट मैट्रिक्स $M$ का समर्थन केवल $k = \text{poly}(n)$ पाउली स्ट्रिंग्स पर होने की गारंटी है। इसके अतिरिक्त, मैट्रिक्स को एक क्लासिकल स्पार्स क्वेरी मॉडल के माध्यम से एक्सेस किया जाता है, जहाँ एक एल्गोरिदम पूर्ण $2^n \times 2^n$ मैट्रिक्स को मेमोरी में बनाए बिना किसी विशिष्ट पंक्ति या कॉलम के गैर-शून्य (non-zero) प्रविष्टियों को प्राप्त कर सकता है। लक्ष्य $n, k,$ और $\log(1/\delta)$ के बहुपद (polynomial) संसाधनों का उपयोग करके उच्च प्रायिकता के साथ सटीक पाउली अपघटन (पाउली स्ट्रिंग्स और उनके गुणांकों का सेट) को प्राप्त करना है।

कार्यप्रणाली (Methodology)
लेखक एक रैंडमाइज्ड क्लासिकल एल्गोरिदम प्रस्तावित करते हैं जो प्रॉमिस की गई स्पर्सिटी ( $k$ ) और पाउली स्ट्रिंग्स के बाइनरी सिम्प्लेक्टिक रूप (binary symplectic form) के ढांचे का लाभ उठाता है। एल्गोरिदम समस्या को तीन मुख्य चरणों में विभाजित करता है:

सक्रिय पाउली-X भागों ( $x$ ) की खोज (Discovery of Active Pauli-X Parts):
लेम्मा 1 का उपयोग करते हुए, जो पंक्ति सूचकांक $v$ , कॉलम सूचकांक $u$ , और पाउली-X भाग $x$ के बीच संबंध स्थापित करता है ( $x = u \oplus v$ ), एल्गोरिदम मैट्रिक्स की यादृच्छिक पंक्तियों (random rows) को क्वेरी करता है। गैर-शून्य प्रविष्टियों के कॉलम सूचकांकों को एकत्र करके और उन्हें पंक्ति सूचकांकों के साथ XOR करके, एल्गोरिदम अपघटन में मौजूद विशिष्ट $x$ बिट स्ट्रिंग्स के सेट $X$ की पहचान करता है। यह चरण 'बुलियन अनसर्टेन्टी प्रिंसिपल' (तथ्य 1) पर निर्भर करता है ताकि यह सुनिश्चित किया जा सके कि रैंडम क्वेरीज़ उच्च प्रायिकता के साथ सक्रिय $x$ स्ट्रिंग्स को प्रकट करती हैं।
अद्वितीय $x$ स्ट्रिंग्स का डिकोडिंग (Decoding Unique $x$ Strings):
प्रत्येक खोजे गए $x$ के लिए, एल्गोरिदम जाँच करता है कि क्या वह "अद्वितीय" है (अर्थात, ठीक एक पाउली स्ट्रिंग से जुड़ा है, इसलिए $p_x = 1$ )। यदि अद्वितीय है, तो क्वेरी फंक्शन $b_x(u) = M_{x \oplus u, u}$ एकल वाल्श कैरेक्टर $\beta_x(z)(-1)^{z \cdot u}$ में बदल जाता है। एल्गोरिदम शून्य वेक्टर और मानक आधार वेक्टर्स (standard basis vectors) का मूल्यांकन करके संबंधित पाउली-Z भाग $z$ और गुणांक $\beta$ को पुनः प्राप्त करता है। एक प्रमाणन चरण (certification step) रैंडम इनपुट्स का उपयोग करके यह सत्यापित करता है कि समाधान कोई डिजेनरेट केस नहीं है जो संयोगवश क्वेरी किए गए बिंदुओं से मेल खाता हो।
डिकजेनरेट $x$ स्ट्रिंग्स का डिकोडिंग (Decoding Degenerate $x$ Strings):
यदि कोई $x$ "डिजेनरेट" है (अर्थात $\geq 2$ पाउली स्ट्रिंग्स से जुड़ा है), तो समस्या एक स्पार्स वाल्श-हाडामार्ड स्पेक्ट्रम को पुनः प्राप्त करने में बदल जाती है। एल्गोरिदम एक रैंडम फोल्डिंग (random folding) तकनीक का उपयोग करता है:
- यह $n$ -बिट स्पेक्ट्रल इंडेक्स ( $z$ ) को एक रैंडम बाइनरी मैट्रिक्स $R$ का उपयोग करके $m$ -बिट बिन्स (bins) में मैप करता है, जहाँ $m \ll n$ ।
- यह "फोल्डिंग" उच्च प्रायिकता के साथ व्यक्तिगत $z$ स्ट्रिंग्स को "सिंगलटन बिन्स" (singleton bins) में अलग कर देती है।
- एक सिंगलटन बिन के लिए, एल्गोरिदम $z$ स्ट्रिंग के बिट्स और उसके गुणांक को निर्धारित करने के लिए शिफ्टेड क्वेरीज़ का उपयोग करता है।
- पुनः प्राप्त किए गए पदों को अवशिष्ट फलन (residual function) से घटाया जाता है, और प्रक्रिया तब तक दोहराई जाती है जब तक कि $x$ के लिए सभी पद न मिल जाएं।
- एक अंतिम रैंडमाइज्ड वेरिफिकेशन यह सुनिश्चित करता है कि कोई भी पद छूटा नहीं है।

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

एल्गोरिदम डिज़ाइन: पेपर एक रैंडमाइज्ड क्लासिकल एल्गोरिदम (एल्गोरिदम 1) प्रस्तुत करता है जो $k$ -स्पर्सिटी और स्पार्स क्वेरी एक्सेस के प्रॉमिस के तहत पाउली अपघटन समस्या को हल करता है।
जटिलता में सुधार (Complexity Improvement): मौजूदा विधियों के विपरीत, जो $n$ में चरघातांकीय रूप से स्केल करती हैं, प्रस्तावित एल्गोरिदम क्वेरी और रनटाइम जटिलता को $n, k,$ और $\log(1/\delta)$ के बहुपद (polynomial) में प्राप्त करता है।
सैद्धांतिक गारंटी: एल्गोरिदम किसी भी उपयोगकर्ता द्वारा चुने गए $\delta \in (0, 1)$ के लिए कम से कम $1-\delta$ की प्रायिकता के साथ सफल होता है। लेखक प्रत्येक चरण (डिस्कवरी, यूनिक डिकोडिंग, और डिजेनरेट डिकोडिंग) के लिए विफलता की प्रायिकता के कठोरतम (rigorous) बाउंड्स प्रदान करते हैं।
स्पार्स वाल्श-हाडामार्ड तकनीकें: यह कार्य बाउलियन क्यूब (विशेष रूप से स्पार्स वाल्श-हाडामार्ड डिकोडिंग) से स्पार्स रिकवरी तकनीकों को पाउली अपघटन के संदर्भ में अनुकूलित करता है, जिसमें रैंडम फोल्डिंग और शिफ्ट-आधारित बिट रिकवरी का उपयोग किया गया है।

परिणाम (Results)

संख्यात्मक बेंचमार्क (Numerical Benchmarks): लेखकों ने $n = 2$ $n = 2$ से $30 $और$ $और$ k = 2^n$ के लिए रैंडम इंस्टेंस पर एल्गोरिदम का परीक्षण किया।
- छोटे $n$ ( $n < 10$ ) के लिए, रैंडमाइज्ड एल्गोरिदम का ओवरहेड मौजूदा PennyLane PauliDecompose रूटीन की तुलना में इसे धीमा बनाता है।
- $n=10$ के आसपास एक क्रॉसओवर होता है। $n > 10$ के लिए, प्रस्तावित एल्गोरिदम घातांकीय-समय बेसलाइन की तुलना में काफी बेहतर प्रदर्शन करता है।
- देखा गया रनटाइम और क्वेरी काउंट $n$ के साथ बहुपद रूप से स्केल करता है, जो सैद्धांतिक बाउंड्स के अनुरूप है।
- सभी परीक्षण किए गए रन में, एल्गोरिदम बिना किसी विफलता के पूर्ण अपघटन को सफलतापूर्वक पुनः प्राप्त करने में सफल रहा।
स्केलेबिलिटी (Scalability): एल्गोरिदम ने $n=30$ तक के इंस्टेंस को सफलतापूर्वक संभाला, जो वह क्षेत्र है जहाँ पूर्ण मैट्रिक्स का निर्माण करना या सघन अपघटन एल्गोरिदम चलाना कम्प्यूटेशनल रूप से अव्यवहार्य हो जाता है।

महत्व और दावे (Significance and Claims)
पेपर दावा करता है कि जबकि सामान्य मैट्रिसेस के लिए पाउली अपघटन खोजना चरघातांकीय रूप से कठिन है, यह उन मैट्रिसेस के लिए कुशल रूप से हल करने योग्य हो जाता है जो पाउली बेस में स्पार्स होने का वादा (promise) करते हैं। यह क्षेत्र निकट-अवधि क्वांटम एल्गोरिदम के लिए अत्यधिक प्रासंगिक है जो संरचित क्लासिकल इनपुट डेटा पर कार्य करते हैं।

लेखक इस बात पर जोर देते हैं कि उनका एल्गोरिदम विशेष रूप से उस प्रॉमिस समस्या के लिए डिज़ाइन किया गया है जहाँ $k = \text{poly}(n)$ है। वे सामान्य सघन (dense) मामले को हल करने का दावा नहीं करते हैं। इसका महत्व पाउली अपघटन की आवश्यकता वाले क्वांटम एल्गोरिदम के लिए कुशल क्लासिकल प्रीप्रोसेसिंग को सक्षम करने में निहित है, जो संभावित रूप से एंड-टू-एंड क्वांटम वर्कफ़्लो में एक प्रमुख बाधा को दूर कर सकता है। यह कार्य विशिष्ट अनुप्रयोग संदर्भों को भी उजागर करता है, जैसे कि संक्षिप्त क्लासिकल नियमों द्वारा परिभाषित मैट्रिसेस या डेटा जो अनट्रस्टेड सर्वर के पास है जहाँ केवल क्वेरी एक्सेस उपलब्ध है।

पेपर विनम्रतापूर्वक समाप्त होता है, यह नोट करते हुए कि प्राप्त ऊपरी सीमाएँ (upper bounds) ढीली (loose) हो सकती हैं और भविष्य के कार्य अधिक सटीक (tighter) बाउंड्स, लोअर बाउंड्स और लगभग स्पार्स (approximately sparse) मैट्रिसेस के विस्तार की खोज कर सकते हैं।