Quantum algorithms through graph composition

तकनीकी सारांश: ग्राफ संरचना के माध्यम से क्वांटम एल्गोरिदम

लेखक: अरजन कॉर्नलिसेन (Arjan Cornelissen)
दिनांक: 10 फरवरी, 2026
विषय: क्वांटम क्वेरी जटिलता और एल्गोरिद्मिक ढांचे

1. समस्या विवरण

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

इन ढांचों में स्पैन प्रोग्राम्स (span programs), लर्निंग ग्राफ्स (learning graphs), वेटेड डिसीजन ट्री (weighted decision trees), st-कनेक्टिविटी (st-connectivity), और क्वांटम डिवाइड-एंड-कॉन्कर (quantum divide-and-conquer) शामिल हैं। जबकि प्रत्येक शक्तिशाली है, उन्हें अक्सर अलग-थलग मॉडलों के रूप में माना जाता है। इस कार्य में संबोधित केंद्रीय समस्या यह है कि क्या इन विविध ढांचों को एक एकल, सुसंगत गणितीय संरचना में एकीकृत किया जा सकता है और क्या उन्हें समय जटिलता (time complexity) के संदर्भ में कुशलतापूर्वक लागू किया जा सकता है।

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

यह शोध पत्र इन ढांचों को एकीकृत करने के लिए एक बहु-आयामी गणितीय दृष्टिकोण अपनाता है:

• ग्राफ थ्योरी और इलेक्ट्रिकल नेटवर्क: लेखक क्वांटम एल्गोरिदम को मॉडल करने के लिए इलेक्ट्रिकल नेटवर्क के भौतिकी (किरचॉफ के नियम, प्रभावी प्रतिरोध/effective resistance, और सर्कुलेशन स्पेस) का उपयोग करता है।
• स्पैन प्रोग्राम्स: लेखक स्पैन प्रोग्राम्स को मौलिक निर्माण खंड (building block) के रूप में उपयोग करता है, जो एक हिल्बर्ट स्पेस में सबस्पेस के माध्यम से प्रतिबिंब (reflections) के रूप में क्वांटम एल्गोरिदम का प्रतिनिधित्व करते हैं।
• ग्राफ संरचना (Graph Composition): एक नया ढांचा पेश किया गया है जहाँ स्पैन प्रोग्राम्स को एक अनडिरेक्टेड ग्राफ के किनारों (edges) के साथ जोड़ा जाता है। ग्राफ की कनेक्टिविटी (विशेष रूप से एक स्रोत $s$ और सिंक $t$ के बीच प्रभावी प्रतिरोध) एल्गोरिदम की जटिलता निर्धारित करती है।
• ट्री-पैरेलल डिकंपोजिशन (Tree-Parallel Decomposition): समय जटिलता को संबोधित करने के लिए, लेखक ग्राफ को पेड़ों या समानांतर संरचनाओं में विघटित करने के लिए एक नवीन पुनरावर्ती (recursive) विधि विकसित करता है, जिससे ग्राफ के "सर्कुलेशन स्पेस" के माध्यम से प्रतिबिंबों का कुशल कार्यान्वयन संभव होता है।

3. मुख्य योगदान

A. ढांचों का एकीकरण (The "Hierarchy")
यह शोध पत्र मौजूदा क्वांटम एल्गोरिद्मिक मॉडलों के बीच एक औपचारिक पदानुक्रम स्थापित करता है।

• st-कनेक्टिविटी की केंद्रीयता: लेखक सिद्ध करता है कि st-कनेक्टिविटी ढांचा एक एकीकृत मध्य मार्ग है। यह लर्निंग ग्राफ और वेटेड डिसीजन ट्री दोनों ढांचों को अपने भीतर समाहित करता है।
• मध्यवर्ती मॉडल: एक आश्चर्यजनक परिणाम दिखाता है कि किसी भी क्लासिकल रैंडमाइज्ड एल्गोरिदम को st-कनेक्टिविटी समस्या में परिवर्तित किया जा सकता है। यह st-कनेक्टिविटी को एक मध्यवर्ती कम्प्यूटेशनल मॉडल के रूप में स्थापित करता है—जो क्लासिकल रैंडमाइज्ड एल्गोरिदम से स्पष्ट रूप से अधिक शक्तिशाली है लेकिन पूर्ण क्वांटम एल्गोरिदम से स्पष्ट रूप से कम शक्तिशाली है।
• ग्राफ संरचना ढांचा: लेखक इसे st-कनेक्टivity के सामान्यीकरण के रूप में पेश करता है, जहाँ किनारे केवल बिट्स नहीं बल्कि संपूर्ण स्पैन प्रोग्राम हैं। यह ढांचा क्वांटम डिवाइड-एंड-कॉन्कर को समाहित करता है और स्वयं मल्टीडायमेंशनल क्वांटम वॉक्स द्वारा समाहित किया जाता है।

B. जटिलता माप विश्लेषण (Complexity Measure Analysis)
यह शोध पत्र उनके जटिलता मापों (जैसे, $WDT(f)$, $st(f)$, $R(f)$) को जोड़कर इन ढांचों की "शक्ति" का कठोर तुलनात्मक विश्लेषण प्रदान करता है।

• यह सिद्ध करता है कि वेटेड डिसीजन ट्री ढांचा अधिकतम एक क्वाड्रेटिक स्पीड-अप (quadratic speed-up) तक ही सीमित है।
• यह कुल (total) और आंशिक (partial) बूलियन फलनों के लिए सभी प्रमुख जटिलता मापों के बीच संबंधों को दर्शाने वाला एक हासे आरेख (Hasse diagram - चित्र 1.2) प्रदान करता है।

C. समय-कुशल कार्यान्वयन (Time-Efficient Implementations)
लेखक क्वेरी जटिलता से आगे बढ़कर समय जटिलता को संबोधित करता है। मामलों को टू-सबस्पेस फेज एस्टिमेशन (two-subspace phase estimation) ढांचे में बदलकर और उन्हें ट्रांसड्यूसर (transducers) के रूप में लागू करके, लेखक "इफेक्टिव स्पेक्ट्रल गैप लेम्मा" की आवश्यकता को समाप्त कर देता है, जिससे विश्लेषण सरल हो जाता है और तेज़ निष्पादन संभव होता है।

4. मुख्य परिणाम

• जटिलता संबंध:
  • $st(f) \in O(R(f))$ (st-कनेक्टिविटी रैंडमाइज्ड जटिलता द्वारा सीमित है)।
  • $D(f) \in O(WDT(f)^2)$ (डिटरमिनिस्टिक जटिलता वेटेड डिसीजन ट्री के साथ बहुपद रूप से संबंधित है)।
• बेहतर स्ट्रिंग सर्च एल्गोरिदम: लेखक कई क्लासिकल समस्याओं पर ग्राफ संरचना ढांचे को लागू करता है, जिससे निम्नलिखित के लिए बेहतर या सटीक क्वेरी/समय जटिलता प्राप्त होती है:
  • एपीरियोडिक पैटर्न मैचिंग (Aperiodic Pattern Matching): $O(\sqrt{n \log m})$ क्वेरी।
  • OR $\circ$ pSEARCH: $O(\sqrt{T \log T})$ क्वेरी।
  • $\Sigma^* 2 0^* 2 \Sigma^*$ (Dynamic AND-OR): $O(\sqrt{n \log n})$ क्वेरी।
  • Dyck Language (Depth 3): $O(\sqrt{n \log n})$ क्वेरी।
  • 3-Increasing Subsequence: $O(\sqrt{n \log n})$ क्वेरी।
• सैविच के एल्गोरिदम (Savitch’s Algorithm) में सुधार: लेखक एक निर्देशित st-कनेक्टिविटी एल्गोरिदम का समय-कुशल कार्यान्वयन प्रदान करता है जिसकी जटिलता $eO(\sqrt{2^n} \log n)$ है।

5. महत्व

यह कार्य महत्वपूर्ण है क्योंकि यह क्वांटम क्वेरी एल्गोरिदम के लिए एक "ग्रैंड यूनिफाइड थ्योरी" (Grand Unified Theory) प्रदान करता है। यह दिखाकर कि ये भिन्न-भिन्न ढांचे वास्तव में एक ही अंतर्निहित ग्राफ-आधारित संरचनाओं के विभिन्न दृश्य हैं, लेखक शोधकर्ताओं को एल्गोरिदम डिजाइन करने के लिए एक अधिक शक्तिशाली टूलकिट प्रदान करता है।

इसके अलावा, ट्री-पैरेलल डिकंपोजिशन के माध्यम से क्वेरी जटिलता से समय जटिलता की ओर संक्रमण, सैद्धांतिक क्वेरी बाउंड और व्यावहारिक क्वांटम सर्किट कार्यान्वयन के बीच के अंतर को पाटता है। यह खोज कि st-कनेक्टिविटी, क्लासिकल और क्वांटम मॉडलों के बीच स्थित है, क्वांटम स्पीड-अप की सीमाओं को देखने के लिए एक नया दृष्टिकोण प्रदान करती है।