Counting anticommuting Pauli pairs in linear time

तकनीकी सारांश: रैखिक समय में एंटीकम्यूटिंग पाउली युग्मों की गणना (Counting Anticommuting Pauli Pairs in Linear Time)

समस्या का निरूपण (Problem Formulation)
यह शोध पत्र क्वांटम कंप्यूटिंग वर्कफ़्लो में आवश्यक एक मौलिक शास्त्रीय सबरूटीन (classical subroutine) को संबोधित करता है: $m$ स्पार्स (sparse) $n$-qubit पाउली स्ट्रिंग्स, $P^{(1)}, \dots, P^{(m)}$ की एक सूची को प्रोसेस करना, जहाँ प्रत्येक स्ट्रिंग का भार (weight/locality) $k$ सीमित है (अर्थात, यह अधिकतम $k$ क्वबिट्स पर गैर-तत्काल प्रभाव डालती है)। इसका उद्देश्य इन स्ट्रिंग्स के युग्मवार कम्यूटेशन गुणों (pairwise commutation properties) को निर्धारित करना है। विशेष रूप से, एल्गोरिदम को निम्नलिखित तीन में से एक कार्य करना चाहिए:

1. सटीक गणना (Exact Counting): अनियंत्रित एंटीकम्यूटिंग युग्मों $\{i, j\}$ की सटीक संख्या की गणना करना ताकि $P^{(i)}P^{(j)} = -P^{(j)}P^{(i)}$ हो।
2. प्रमाणन (Certification): यह सत्यापित करना कि क्या सेट के सभी स्ट्रिंग्स युग्मवार कम्यूट करते हैं।
3. साक्षी खोजना (Witness Finding): यदि सभी स्ट्रिंग्स आपस में कम्यूट नहीं करते हैं, तो एक विशिष्ट एंटीकम्यूटिंग युग्म $(i, j)$ की पहचान करना।

मानक दृष्टिकोण पाउली स्ट्रिंग्स को बाइनरी सिम्प्लेक्टिक रूप (binary symplectic form) में प्रस्तुत करता है और प्रत्येक युग्म की जाँच करता है, जिसके परिणामस्वरूप $O(m^2)$ (या स्पार्स स्ट्रिंग्स के लिए $O(m^2 k)$) का समय जटिलता (time complexity) प्राप्त होती है। जबकि एक घने ग्राफ (dense graph) में सभी एंटीकम्यूटिंग किनारों को सूचीबद्ध करने के लिए स्वाभाविक रूप से $\Omega(m^2)$ समय की आवश्यकता होती है, लेखक नोट करते हैं कि सटीक गणना और प्रमाणन के लिए अक्सर केवल स्थिरांक या लघुगणकीय-आकार के आउटपुट की आवश्यकता होती है, जो उप-द्विघाती (sub-quadratic) सुधार की संभावना का सुझाव देते हैं।

कार्यप्रणाली: लोकैलिटी-ज़ेटा एल्गोरिदम (Methodology: The Locality-Zeta Algorithm)
लेखक एक ऐसा एल्गोरिदम प्रस्तावित करते हैं जो निश्चित $k$ के लिए $O(m)$ समय में कार्य करता है, जो युग्मवार तुलना के बजाय पैटर्न एकत्रीकरण (pattern aggregation) के प्रतिमान को बदल देता है। इस पद्धति का मुख्य आधार एक डेटा संरचना है जिसे लोकैलिटी-ज़ेटा डेटा स्ट्रक्चर (locality-zeta data structure) कहा जाता है, जो पहले से डाली गई स्ट्रिंग्स के लेबल किए गए उप-पैटर्न (subpatterns) की गणना बनाए रखता है।

1. पैटर्न परिभाषा (Pattern Definition): एक लेबल किया गया पाउली पैटर्न एक जोड़ा $(A, a)$ है, जहाँ $A$ क्वबिट स्थितियों का एक उपसमुच्चय (subset) है और $a$ प्रत्येक स्थिति में एक गैर-तत्काल पाउली अक्षर ($X, Y, Z$) असाइन करता है।
2. सम्मिलन (Insertion): जब एक नया पाउली स्ट्रिंग $Q$ डाला जाता है, तो एल्गोरिदम $\text{supp}(Q)$ के सभी उपसमुच्चयों $A \subseteq \text{supp}(Q)$ को सूचीबद्ध करता है और डिक्शनरी में पैटर्न $(A, Q|_A)$ के लिए गणना (count) को बढ़ाता है। $w$ भार वाली स्ट्रिंग के लिए, इसमें $2^w$ अपडेट शामिल होते हैं।
3. सबसेट ज़ेटा पहचान के माध्यम से क्वेरी (Query via Subset Zeta Identity): पहले से डाली गई स्ट्रिंग्स $G$ के विरुद्ध एक नई स्ट्रिंग $P$ को क्वेरी करने के लिए, एल्गोरिदम $P$ के $\text{supp}(P)$ के सभी उपसमुच्चयों $A$ पर एक भारित योग (weighted sum) की गणना करता है।
   • यह $F_G(P, A)$ की गणना करता है, जो $G$ में उन स्ट्रिंग्स की संख्या है जो $A$ के प्रत्येक निर्देशांक (coordinate) पर $P$ के साथ संघर्ष (conflict) करती हैं।
   • यह "ज़ेटा सम" $Z_G(P) = \sum_{A \subseteq \text{supp}(P)} (-2)^{|A|} F_G(P, A)$ की गणना करता है।
   • एंटीकम्यूटिंग स्ट्रिंग्स की संख्या $\text{anti}_G(P) = (|G| - Z_G(P)) / 2$ के रूप में प्राप्त की जाती है।

इसकी शुद्धता समावेशन-अपवर्जन सिद्धांत (inclusion-exclusion principle) (विशेष रूप से एक सबसेट ज़ेटा पहचान) पर आधारित है जो संघर्ष सेट के आकार की समता (parity) को अलग करने के लिए उपयोग की जाती है। यदि संघर्ष सेट का आकार $|\text{conf}(P, Q)|$ विषम है, तो योग के पद $-1$देने के लिए रद्द हो जाते; यदि सम है, तो वे$+1$ देने के लिए जुड़ जाते।

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

• रैखिक समय जटिलता (Linear Time Complexity): शोध पत्र एक एल्गोरिदम प्रस्तुत करता है जिसकी अपेक्षित समय जटिलता $O(\sum_{i=1}^m w_i 3^{w_i}$ है, जहाँ $w_i$ $i$-वीं स्ट्रिंग का भार है। सीमित लोकैलिटी वाले परिदृश्य में जहाँ $w_i \leq k$ सभी $i$ के लिए है, जटिलता $O(m k 3^k)$ हो जाती है। चूंकि $k$ को एक निश्चित स्थिरांक माना जाता है, इसलिए एल्गोरिदम स्ट्रिंग्स की संख्या $m$ के संबंध में रैखिक समय $O(m)$ में चलता है।
• स्थान जटिलता (Space Complexity): डिक्शनरी कुंजियों (keys) के लिए एल्गोरिदम को $O(\sum_{i=1}^m w_i 2^{w_i})$ स्थान की आवश्यकता होती है, जो सीमित लोकैलिटी के लिए $O(m k 2^k)$ में सरल हो जाता है।
• इष्टतमता (Optimality): लेखक दावा करते हैं कि स्पार्स-इनपुट मॉडल में निश्चित $k$ के लिए, यह एल्गोरिदम $k$ पर निर्भर एक स्थिरांक कारक तक इष्टतम है।
• साक्षी खोजना (Witness Finding): यदि कोई साक्षी मौजूद है, तो एल्गोरिदम एक विशिष्ट साक्षी युग्म $(i, j)$ को वापस करने के लिए विस्तारित किया जा सकता है। जबकि गणना और प्रमाणन चरण रैखिक हैं, विशिष्ट साक्षी खोजने में पिछले स्ट्रिंग्स का स्कैन शामिल है, जिससे $O(mk)$की लागत जुड़ जाती है, जो$O(m^2)$ बेसलाइन की तुलना में कुशल बनी रहती है।

महत्व और दावे (Significance and Claims)
यह शोध पत्र स्वयं को "बैचिंग समस्या" (batching problem) के समाधान के रूप में प्रस्तुत करता है, जहाँ कई पाउली स्ट्रिंग्स के युग्मों को स्क्रीन या संभावित कम्यूटिंग सेट को सत्यापित करने की आवश्यकता होती है। लेखक तर्क देते हैं कि हालांकि घने आउटपुट (सभी किनारों को सूचीबद्ध करना) स्वाभाविक रूप से द्विघाती होता है, कई क्वांटम एल्गोरिदम के सत्यापन चरण—जैसे कि वेरिएशनल क्वांटम आइजनवैल्यू सॉल्वर (VQE) मेजरमेंट रिडक्शन, पाउली-आधारित गणना, और लोकल हैमिल्टोनियन वर्कफ़लो—केवल गणना या प्रमाणन की आवश्यकता रखते हैं।

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