Halving the cost of QROM

तकनीकी सारांश: QROM की लागत को आधा करना

समस्या विवरण

क्वांटम रीड-ओनली मेमोरी (QROM) फॉल्ट-टोलरेंट एल्गोरिदम में एक मौलिक सबरूटीन है, जो शास्त्रीय डेटा को सुपरपोजिशन में सुसंगत रूप से लोड करने में सक्षम बनाता है। यह हैमिल्टोनियन सिमुलेशन, स्टेट प्रिपरेशन, यूनिटरी सिंथेसिस, और डिफरेंशियल एवं लीनियर इक्वेशंस के क्वांटम सॉल्वर जैसे अनुप्रयोगों में एल्गोरिद्मिक ओवरहेड का एक प्राथमिक स्रोत है।

QROM का मुख्य कार्य इस रूपांतरण को लागू करना है:
$$\sum_{x=0}^{N-1} \psi_x |x\rangle|0\rangle \to \sum_{x=0}^{N-1} \psi_x |x\rangle|f(x)\rangle$$
जहाँ $N$ डेटा प्रविष्टियों (entries) की संख्या है, $b$ प्रत्येक प्रविष्टि की बिट-लंबाई है, और $f(x)$ एक पूर्व-निर्धारित शास्त्रीय फलन (function) है।

ऐतिहासिक रूप से, नॉन-क्लिफोर्ड लागत (विशेष रूप से टोफोली गेट काउंट) QROM के लिए एक बाधा रही है। जबकि यूनरी इटरेशन (unary iteration) का उपयोग करने वाले शुरुआती तरीकों ने लागत को $N$ तक कम कर दिया था, एंसिलरी क्वबिट्स (ancillary qubits) का उपयोग करने वाली "SelectSwap" तकनीकों के आगमन ने और अधिक अनुकूलन की अनुमति दी। इस कार्य से पहले का अत्याधुनिक (state-of-the-art) स्तर, बेरी एट अल. द्वारा स्थापित किया गया था, जिसने $b(\lambda-1)$ "डर्टी" (गैर-प्योर) एंसिला क्वबिट्स का उपयोग करके निम्नलिखित टोफोली लागत प्राप्त की थी:
$$2\frac{N}{\lambda} + 4b(\lambda-1)$$
जहाँ $\lambda$ एक पैरामीटर है जो एंसिला क्वबिट्स की संख्या और टोफोली गणना के बीच के ट्रेड-ऑफ को निर्धारित करता है। इस निर्माण में डर्टी एंसिला के उपयोग के कारण प्रमुख $N/\lambda$ पद पर 2 का मल्टीप्लिकेटिव फैक्टर लगा था, जो कि एक ऐसी सीमा थी जो सात वर्षों से अधिक समय तक बनी रही।

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

लेखक QROM के लिए एक नया निर्माण प्रस्तावित करते हैं जो व्यावहारिक परिदृश्यों में इसके कार्यान्वयन लागत को प्रभावी रूप से आधा कर देता है। कार्यप्रणाली दो चरणों में आगे बढ़ती है:

1. SelectSwap से SelectCopy तक

पहला अनुकूलन "SelectSwap" आर्किटेक्चर को "SelectCopy" आर्किटेक्चर से बदल देता है।

• पिछला दृष्टिकोण (SelectSwap): डर्टी एंसिला का उपयोग करके डेटा लोड करने के लिए, एल्गोरिदम एड्रेस स्टेट $|r\rangle$ के आधार पर $r$-वें डर्टी रजिस्टर को ज़ीरोथ (zeroth) रजिस्टर के साथ स्वैप करता है, ज़ीरोथ रजिस्टर को क्लीन रजिस्टर में कॉपी करता है, और वापस स्वैप करता है। इस अनुक्रम के लिए कई मल्टीप्लेक्सड स्वैप और CNOT की आवश्यकता होती है।
• नया दृष्टिकोण (SelectCopy): लेखक देखते हैं कि स्वैपिंग, कॉपी करने और वापस स्वैप करने का अनुक्रम $|r\rangle$ के आधार पर $r$-वें रजिस्टर को सीधे क्लीन रजिस्टर में मल्टीप्लेक्सड कॉपी करने के गणितीय रूप से समकक्ष है।
  • यह डायरेक्ट कॉपी ऑपरेशन स्वैप-आधारित दृष्टिकोण की तुलना में मल्टीप्लेक्सड ऑपरेशंस की टोफोली लागत को आधा कर देता है।
  • इसके अलावा, लोडिंग रणनीति को $f(q, 0)$ को सीधे क्लीन रजिस्टर में और $f(q, r) \oplus f(q, 0)$ को डर्टी रजिस्टरों में ( $r > 0$ के लिए) लोड करने के लिए संशोधित करके, लेखक डर्टी एंसिला की आवश्यकता को $b\lambda$ से घटाकर $b(\lambda-1)$ कर देते हैं और निरंतर पदों (constant terms) को और अधिक परिष्कृत करते हैं।
  • परिणामी लागत: $2\frac{N}{\lambda} + 2b(\lambda-1) + 2\lambda - 6$।

2. अनुक्रमिक बिट पैकेट्स (पैरामीट्रिक अनुकूलन)

दूसरा अनुकूलन उस क्वबिट-सीमित परिदृश्य को संबोधित करता है जहाँ $N/\lambda$ पद प्रभावी होता है। लेखक एक एकल $b$-बिट QROM को $\alpha$ अनुक्रमिक QROM के रूप में मानने की विधि पेश करते हैं, जिनमें से प्रत्येक $b/\alpha$ बिट्स लोड करता है।

• अनुक्रमिक अनलोडिंग (Sequential Unloading): $m$ QROM अनुप्रयोगों को श्रृंखलाबद्ध करके, $j$-वें अनुप्रयोग के अनलोडिंग चरण को $(j+1)$-वें अनुप्रयोग के लोडिंग चरण के साथ जोड़ा जा सकता है। यह पूर्ण लोड/अनलोड चक्रों की संख्या को कम करता है।
• लागत में कमी: $m$ अनुक्रमिक QROMs के लिए, $N/\lambda$ पद का प्रीफैक्टर $2m$ के बजाय $(m+1)$ हो जाता है।
• एकल QROM पर अनुप्रयोग: लेखक एक $b$-बिट QROM को $b/\alpha$ आकार के $\alpha$ अनुक्रमिक QROMs के रूप में मानते हैं। यह "SelectCopy" की गहराई को $\lambda$ से बढ़ाकर $\alpha\lambda$ करने की अनुमति देता है।
• पैरामीट्रिक फैमिली: यह एक लागत फलन (cost function) प्रदान करता है जो ट्यूनेबल पैरामीटर $\alpha$ पर निर्भर है:
  $$\left(1 + \frac{1}{\alpha}\right)\frac{N}{\lambda} + \left(b + \frac{b}{\alpha}\right)(\alpha\lambda - 1) + (\alpha + 1)(\alpha\lambda - 3)$$
  $\alpha$ को $1$से$b$तक बदलकर,$N/\lambda$के प्रमुख पद के प्रीफैक्टर को$2$से घटाकर$(1 + 1/b)$ तक इंटरपोलेट किया जा सकता है।

मुख्य परिणाम

• इष्टतम परिदृश्य (Optimal Regime): उस सीमा में जहाँ $N \gg b^2\lambda^2$ है और उपलब्ध डर्टी क्वबिट्स की संख्या सीमित है, $\alpha = b$ (एक बार में एक बिट को अनुक्रमिक रूप से लोड करना) सेट करना इष्टतम है।
• लागत में कमी: इन स्थितियों के तहत, कुल टोफोली लागत लगभग निम्न हो जाती है:
  $$\left(1 + \frac{1}{b}\right)\frac{N}{\lambda}$$
• प्रदर्शन लाभ: यह पिछले अत्याधुनिक स्तर ($2N/\lambda$) की तुलना में लागत में लगभग 50% की कमी का प्रतिनिधित्व करता है।
• क्लीन-क्वबिट समानता: इस डर्टी-क्वबिट निर्माण का प्रदर्शन क्लीन-क्वबिट QROM (जो आमतौर पर 1 का प्रीफैक्टर प्राप्त करता है) के प्रदर्शन के बराबर है।
• सामान्यीकरण (Generalization): पेपर विधियों का एक पैरामीट्रिक परिवार प्रदान करता है जो उपयोगकर्ताओं को विशिष्ट क्वबिट बजट बनाम गेट डेप्थ के आधार पर पैरामीटर $\alpha$ को ट्यून करके अनुकूलित करने की अनुमति देता है।

लेखक नोट करते हैं कि जबकि वर्तमान निर्माण मानता है कि पैरामीटर 2 की घात (powers of 2) हैं, भविष्य के कार्य पूर्णांक विभाजन (integer division) तकनीकों को शामिल कर सकते हैं ताकि उपलब्ध डर्टी क्वबिट बजट का पूरी तरह से उपयोग किया जा सके जब वे $2^k$ बाधा में फिट नहीं होते हैं, जिससे विशिष्ट परिदृश्यों में और भी कमी संभव हो सकती है। प्रस्तावित निर्माण को PennyLane लाइब्रेरी में लागू किया गया है।

महत्व और दावे

पेपर का दावा है कि यह आधे दशक से अधिक समय में QROM सबरूटीन में पहला बड़ा सुधार प्रदान करता है। इसका महत्व इस प्रकार है:

1. ओवरहेड में कमी: चूंकि QROM अधिकांश व्यावहारिक क्वांटम अनुप्रयोगों (जैसे केमिस्ट्री, लीनियर सिस्टम) में अधिकांश एल्गोरिद्मिक ओवरहेड का हिस्सा है, इसलिए इसकी लागत को आधा करने से सीधे तौर पर पूरे क्षेत्र में महत्वपूर्ण संसाधन बचत होती है।
2. व्यावहारिकता: सुधार "डर्टी" एंसिला क्वबिट्स का उपयोग करके प्राप्त किए जाते हैं, जो क्लीन क्वबिट्स से जुड़ी दक्षता के लाभों से समझौता किए बिना, क्लीन (प्योर) एंसिला की तुलना में फॉल्ट-टोलरेंट आर्किटेक्चर में लागू करने में आसान हैं।
3. लचीलापन: समाधान की पैरामीट्रिक प्रकृति डिजाइनरों को क्वबिट बजट बनाम गेट डेप्थ जैसे विशिष्ट हार्डवेयर बाधाओं के लिए पैरामीटर $\alpha$ को ट्यून करके अनुकूलित करने की अनुमति देती है।

लेखक उल्लेख करते हैं कि हालांकि वर्तमान निर्माण मानता है कि पैरामीटर 2 की घात हैं, भविष्य के कार्य पूर्णांक विभाजन तकनीकों को शामिल कर सकते हैं ताकि उपलब्ध डर्टी क्वबिट बजट का पूरी तरह से उपयोग किया जा सके जब वे $2^k$ बाधा में फिट नहीं होते हैं, जिससे विशिष्ट परिदृश्यों में और भी कमी संभव हो सकती है। प्रस्तावित निर्माण को PennyLane लाइब्रेरी में लागू किया गया है।