Quantum Search without Global Diffusion

यहाँ जॉन बर्क और कियारन मैक गोल्डरिक के शोध पत्र "Quantum Search without Global Diffusion" का विस्तृत तकनीकी सारांश दिया गया है।

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

क्वांटम एम्प्लीट्यूड एम्प्लीफिकेशन (Quantum amplitude amplification), जो ग्रोवर के सर्च एल्गोरिदम के पीछे का मुख्य तंत्र है, पारंपरिक रूप से दो वैश्विक ऑपरेटरों (global operators) पर निर्भर करता है:

1. ओरेकल ($S_x$): जो लक्षित अवस्था (target state) को चिह्नित करता है।
2. डिफ्यूजन ऑपरेटर ($S_\psi$): जो प्रारंभिक समान सुपरपोजिशन (uniform superposition) के चारों ओर अवस्था को परावर्तित (reflect) करता है।

जबकि ओरेकल अक्सर समस्या-विशिष्ट होता है और संभावित रूप से गहरा (deep) हो सकता है, डिफ्यूजन ऑपरेटर एक वैश्विक परावर्तन है जो सभी $n$ क्विबिट्स पर कार्य करता है। एक वैश्विक डिफ्यूजन ऑपरेटर को लागू करने के लिए जटिल मल्टी-क्विबिट कंट्रोल्ड गेट्स (जैसे $n$-क्विबिट कंट्रोल्ड-Z) की आवश्यकता होती है, जो सर्किट डेप्थ के मामले में महंगे होते हैं और शोर (noise) के प्रति संवेदनशील होते हैं, विशेष रूप से सीमित कनेक्टिविटी वाले हार्डवेयर पर। "आंशिक" (partial) डिफ्यूजन ऑपरेटरों (जो क्विबिट्स के उपसमुच्चयों पर कार्य करते हैं) का उपयोग करने के पिछले प्रयास या तो वैश्विक डिफ्यूजन ऑपरेटर को पूरी तरह से हटाने में विफल रहे या उन्होंने महत्वपूर्ण विश्लेषणात्मक जटिलता पेश की, जिससे मानक एम्प्लीट्यूड एम्प्लीफिकेशन की सरल 2D रोटेशनल ज्योमेट्री टूट गई।

मुख्य प्रश्न: क्या क्वांटम सर्च की द्विघातीय गति (quadratic speedup) को तब संरक्षित किया जा सकता है यदि डिफ्यूजन ऑपरेटर को खोज रजिस्टर के गैर-अतिव्यापी विभाजनों (non-overlapping partitions) पर कार्य करने वाले स्थानीय ऑपरेशन्स द्वारा पूरी तरह से बदल दिया जाए, जिससे केवल ओरेकल ही एकमात्र वैश्विक ऑपरेटर रह जाए?

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

लेखक एक पुनरावर्ती निर्माण (recursive construction) प्रस्तावित करते हैं जो वैश्विक डिफ्यूजन ऑपरेटर को विभाजनों के अनुक्रम में कार्य करने वाले आंशिक डिफ्यूजन ऑपरेटरों से बदल देता है।

मुख्य धारणाएँ (Key Assumptions)

यह विधि तब लागू होती है जब:

• स्टेट प्रिपरेशन यूनिटरी $A$, टेंसर उत्पाद के रूप में विघटित होती है: $A = \bigotimes_{i=1}^m A_i$।
• लक्षित अवस्था $|x\rangle$, टेंसर उत्पाद के रूप में विघटित होती है: $|x\rangle = \bigotimes_{i=1}^m |x_i\rangle$।
• खोज स्थान (search space) को $m$ रजिस्टरों में विभाजित किया गया है जिनके आकार $n_1, \dots, n_m$ हैं।

पुनरावर्ती एल्गोरिदम (The Recursive Algorithm)

एल्गोरिदम चरणों के माध्यम से आगे बढ़ता है, जो रजिस्टरों को $1$से$m$ तक प्रोसेस करता है:

1. पुनरावर्ती परिभाषा (Recursive Definition): ऑपरेटरों के एक अनुक्रम $W_i$ को पुनरावर्ती रूप से परिभाषित करें।
   • $W_0 = S_x$ (वैश्विक ओरेकल)।
   • $W_i = (S_{\psi_i} W_{i-1})^{t_i} S_{\psi_i} (W_{i-1} S_{\psi_i})^{t_i}$, जहाँ $S_{\psi_i}$ केवल रजिस्टर $i$ पर कार्य करने वाला आंशिक डिफ्यूजन ऑपरेटर है।
2. पुनरावर्ती प्रवर्धन (Iterative Amplification):
   • अंतिम रजिस्टर $m$ में लक्षित घटक के आयाम (amplitude) को बढ़ाने के लिए इटरेशन $(S_{\psi_m} W_{m-1})$ को $t_m$ बार लागू करें।
   • शेष रजिस्टरों ($1$से$m-1$) को मापें (measure)। यह एंटैंगलमेंट को कोलैप्स कर देता है, जिससे रजिस्टर $m$ एक विशिष्ट अवस्था में प्रोजेक्ट हो जाता है।
   • मापे गए रजिस्टरों को उनकी प्रारंभिक अवस्थाओं में पुनः आरंभ (re-initialize) करें।
   • अगले रजिस्टर ($m-1$) के लिए प्रक्रिया को दोहराएं, जो पहले से परिभाषित $W_{m-1}$ का उपयोग करता है, जब तक कि सभी रजिस्टर प्रोसेस न हो जाएं।

सैद्धांतिक सफलता: प्रिंसिपल एंगल डिजेनेरेसी (Principal Angle Degeneracy)

केंद्रीय गणितीय अंतर्दृष्टि यह है कि इसके बावजूद कि ऑपरेटर $W_i$ एक ऐसे सबस्पेस पर कार्य करता है जिसका आयाम $2^{i-1}$ है (जो तेजी से बढ़ता है), क्रमिक परावर्तनों (successive reflections) के आइजनस्पेस के बीच के प्रिंसिपल एंगल्स केवल दो विशिष्ट मानों ($\gamma_i$ और $\pi/2 - \gamma_i$) में सिमट जाते हैं।

• यह डिजेनेरेसी जटिल उच्च-आयामी गतिकी (high-dimensional dynamics) को एक स्केलर 2x2 समस्या में बदल देती है।
• कोण $\gamma_i$ एक एकल पुनरावर्ती संबंध द्वारा नियंत्रित होता है: $\sin(2\gamma_i) = \sin(2\theta_i) \sin(2t_{i-1}\gamma_{i-1})$, जहाँ $\theta_i$ रजिस्टर $i$ में स्थानीय ओवरलैप कोण है।
• यह एल्गोरिदम की गतिकी और सफलता की संभावना के लिए एक सटीक क्लोज्ड-फॉर्म समाधान की अनुमति देता है, जिसे पहले आंशिक खोज विधियों के लिए असंभव माना जाता था।

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

1. वैश्विक डिफ्यूजन का उन्मूलन: सिद्ध किया कि द्विघातीय गति के लिए वैश्विक डिफ्यूजन ऑपरेटर आवश्यक नहीं है। ओरेकल ही एकमात्र वैश्विक ऑपरेटर रह सकता है।
2. सटीक विश्लेषणात्मक समाधान: सफलता की संभावना और इष्टतम इटरेशन काउंट के लिए क्लोज्ड-फॉर्म अभिव्यक्तियाँ प्राप्त कीं, जिससे पिछले आंशिक खोज तरीकों की विश्लेषणात्मक जटिलता दूर हुई।
3. जटिलता सीमाएँ (Complexity Bounds): ओरेकल ओवरहेड को $O(1/\prod \cos(\theta_i))$ के रूप में स्थापित किया। अनस्ट्रक्चर्ड सर्च के लिए, यदि प्रत्येक विभाजन में कम से कम $\log_2(\log_2 N)$ क्विबिट्स हैं, तो एल्गोरिदम $O(\sqrt{N})$ क्वेरी कॉम्प्लेक्सिटी बनाए रखता है।
4. सर्किट डेप्थ में कमी: वैश्विक परावर्तनों को स्थानीय परावर्तनों से बदलने से सर्किट डेप्थ में उल्लेखनीय कमी आई, विशेष रूप से डिफ्यूजन स्टेप्स के लिए।

4. परिणाम (Results)

लेखकों ने एक 18-क्विबिट अनस्ट्रक्चर्ड सर्च समस्या पर दृष्टिकोण का मूल्यांकन किया और विश्लेषण को 50 क्विबिट्स तक बढ़ाया।

• सफलता की संभावना (Success Probability):
  • 18-क्विबिट सर्च के लिए, 2-स्टेज पार्टीशन ने 99.5% सफलता दर प्राप्त की (सैद्धांतिक सीमा 99.8%), जबकि 3-स्टेज पार्टीशन ने 96.5% प्राप्त की।
  • सफलता की संभावना स्टेज की संख्या बढ़ने के साथ थोड़ी कम हो जाती है, लेकिन इसे पेनल्टीमेट स्टेज के इटरेशन काउंट को समायोजित करके बढ़ाया जा सकता है।
• सर्किट डेप्थ में कमी:
  • 18-क्विबिट मामला: 2-स्टेज पार्टीशन ने अनस्ट्रक्चर्ड सर्च (ग्रोवर) की तुलना में नॉन-ओरेकल सर्किट डेप्थ को 51%–96% तक कम कर दिया (एन्सेला उपलब्धता और डिकंपोजिशन रणनीति के आधार पर)।
  • 3-स्टेज मामला: डेप्थ में कमी 63%–97% तक पहुँच गई।
  • ओरेकल ओवरहेड: इन कटौतियों की कीमत 9% (2-स्टेज) से 30% (3-स्टेज) अतिरिक्त ओरेकल कॉल्स के रूप में चुकानी पड़ी।
• स्केलेबिलिटी (n = 20 से 50):
  • जैसे-जैसे $N$ बढ़ता है, ओरेकल ओवरहेड और विफलता दर तेजी से गिरती है।
  • भले ही ओरेकल सर्किट, डिफ्यूजन ऑपरेटर से 10 गुना गहरा हो, फिर भी पुनरावर्ती योजना शुद्ध सर्किट डेप्थ में कमी (लगभग 5% $N=50$ पर) प्रदान करती है।
  • वह "ब्रेक-इवन" बिंदु जहाँ पुनरावर्ती योजना ग्रोवर से उथली (shallower) हो जाती है, समस्या के आकार के साथ बढ़ता है, जिससे यह योजना गहरे ओरेकल कार्यान्वयन को सहन करने में सक्षम होती है।

5. महत्व और निहितार्थ (Significance and Implications)

• हार्डवेयर दक्षता: यह दृष्टिकोण निकट-अवधि मध्यवर्ती पैमाने के क्वांटम (NISQ) उपकरणों के लिए अत्यधिक फायदेमंद है। डिफ्यूजन ऑपरेटर को स्थानीयकृत करके, एल्गोरिदम गहरे, त्रुटि-प्रवण मल्टी-क्विबिट गेट्स से बचता है, जिससे गेट एरर संचय और निष्पादन समय कम हो जाता है।
• डिस्ट्रीब्यूटेड कंप्यूटिंग: यह विधि वितरित क्वांटम आर्किटेक्चर के लिए स्वाभाविक रूप से उपयुक्त है। नॉन-ओरेकल ऑपरेशन्स को व्यक्तिगत प्रोसेसिंग नोड्स तक सीमित किया जा सकता है, जिसमें केवल ओरेकल के लिए इंटर-नोड संचार की आवश्यकता होती है। यह लंबी दूरी के एंटैंगलमेंट उत्पन्न करने से जुड़े शोर को कम करता है।
• वैचारिक अंतर्दृष्टि: परिणाम क्वांटम स्पीडअप के लिए वैश्विक एंटैंगलमेंट की आवश्यकता को चुनौती देते हैं। पेपर सुझाव देता है कि टेंसर-डिकम्पोजेबल समस्याओं के लिए, स्पीडअप के लिए आवश्यक गैर-स्थानीय सहसंबंध (non-local correlations) पूरी तरह से ओरेकल के भीतर होते हैं, जबकि प्रवर्धन तंत्र (amplification mechanism) पूरी तरह से स्थानीय हो सकता है।
• एल्गोरिदम डिजाइन: "प्रिंसिपल एंगल डिजेनेरेसी" की खोज एक नया विश्लेषणात्मक उपकरण प्रदान करती है, जो सरल सर्च से परे क्वांटम वॉक और फेज एस्टीमेशन में भी लागू हो सकती है।

संक्षेप में, यह कार्य प्रदर्शित करता है कि क्वांटम सर्च की मूलभूत द्विघातीय गति (quadratic speedup) को वैश्विक डिफ्यूजन ऑपरेटर के बिना प्राप्त किया जा सकता है, जो वर्तमान और भविष्य के हार्डवेयर पर अधिक कुशल और शोर-प्रतिरोधी क्वांटम एल्गोरिदम के लिए एक व्यावहारिक मार्ग प्रदान करता है।