The power of constant-depth quantum circuits of unbounded size

तकनीकी सारांश: असीमित आकार के निरंतर-गहराई वाले क्वांटम सर्किट की शक्ति

समस्या विवरण
यह शोध पत्र इस बात की जांच करता है कि जब सर्किट के आकार और सहायक स्थान (ancillary space) पर प्रतिबंध हटा दिए जाते हैं, तो क्वांटम सर्किट की गणनात्मक शक्ति क्या होती है। क्लासिकल कॉम्प्लेक्सिटी में, $AC^0$ क्लास (अनबाउंडेड फैन-इन AND/OR गेट्स के साथ निरंतर-गहराई वाले सर्किट) पेरिटी (parity) की गणना नहीं कर सकता है। हालांकि, यदि बहुपद आकार (polynomial size) का प्रतिबंध हटा दिया जाए, तो डिसजंक्टिव नॉर्मल फॉर्म (DNF) निर्माणों के माध्यम से प्रत्येक बूलियन फंक्शन की गणना निरंतर गहराई में की जा सकती है। लेखक यह पूछते हैं कि क्या यह घटना क्वांटम सर्किट के लिए भी लागू होती है जो मनमाने सिंगल-क्विबिट गेट्स और जनरलाइज्ड टोफ़ोली (Toffoli) गेट्स से बने होते हैं (असीमित आकार $QAC^0$)। विशेष रूप से, क्या प्रत्येक यूनिटरी ऑपरेशन को निरंतर गहराई में सटीक रूप से लागू किया जा सकता है यदि सर्किट का आकार और सहायक क्विबिट्स की संख्या असीमित हो?

लेखक इस जांच को चार बढ़ते हुए सामान्य कार्यों के माध्यम से प्रस्तुत करते हैं:

1. किसी भी सेट $L \subseteq \{0, 1\}^n$ की सदस्यता (membership) की गणना करना।
2. कम्प्यूटेशनल बेसिस स्टेट्स के किसी भी क्रमपरिवर्तन (permutation) को लागू करना।
3. किसी भी शुद्ध क्वांटम अवस्था (pure quantum state) को तैयार करना।
4. प्रत्येक इनपुट स्टेट पर किसी भी मनमाने यूनिटरी को लागू करना।

कार्यप्रणाली
लेखक रिवर्सिबल क्लासिकल सर्किट निर्माण, क्वांटम डोमेन के लिए अनुकूलित संभाव्य शास्त्रीय तकनीकों (probabilistic classical techniques) और क्वांटम टेलीपोर्टेशन प्रोटोकॉल के संयोजन का उपयोग करते हैं।

• रिवर्सिबल क्लासिकल निर्माण: लेखक पहले यह स्थापित करते हैं कि टोफ़ोली और फैनआउट गेट्स का उपयोग करके बिटस्ट्रिंग्स के मनमाने क्रमपरिवर्तनों को निरंतर गहराई में लागू किया जा सकता है। यह एक "इंडिकेटर एनकोडिंग" योजना के माध्यम से प्राप्त किया जाता है: इनपुट को $2^n$-आयामी इंडिकेटर वेक्टर (जहाँ ठीक एक प्रविष्टि 1 है) में मैप किया जाता है, हेरफेर किया जाता है, और फिर मूल स्ट्रिंग में वापस डिकोड किया जाता है। यह सभी संभावित इनपुट स्ट्रिंग्स के समानांतर मूल्यांकन की अनुमति देता है।
• संभाव्य से क्वांटम अनुकूलन: मनमाने संभाव्यता वितरणों और शुद्ध क्वांटम अवस्थाओं को तैयार करने के लिए, लेखक एक क्लासिकल संभाव्य निर्माण को अनुकूलित करते हैं। इसमें वितरण को एनकोड करने के लिए स्वतंत्र रूप से बिट्स का नमूना लेना शामिल है जो पहले '1' की स्थिति पर आधारित होता है। क्वांटम सेटिंग में, इसे सुसंगत (coherent) बनाने के लिए पहले '1' के बाद आने वाले क्विबिट्स पर इनवर्स रोटेशन लागू किया जाता है ताकि सुपरपोजिशन को नष्ट किए बिना उन्हें $|0\rangle$ पर वापस लाया जा सके।
• गेट सेट विस्तार: जबकि प्राथमिक गेट सेट में सिंगल-क्विबिट गेट्स और जनरलाइज्ड टोफ़ोली गेट्स शामिल हैं, लेखक एक वैचारिक उपकरण के रूप में फैनआउट गेट्स का उपयोग करते हैं। वे Grier, Morris, और Wu [GMW26] तथा Rosenthal [Ros20] के परिणामों का हवाला देते हुए यह दिखाते हैं कि फैनआउट को केवल प्राथमिक गेट सेट का उपयोग करके निरंतर गहराई में सटीक रूप से लागू किया जा सकता है, हालांकि इसके लिए सर्किट के आकार में दोगुना घातीय (doubly exponential) वृद्धि हो सकती है।
• यूनिटरीज के लिए रिडक्शन: मनमाने यूनिटरीज के कार्यान्वयन के लिए, लेखक कोई सीधा निर्माण प्रदान नहीं करते हैं। इसके बजाय, वे कई समकक्ष स्वरूपों और रिडक्शन पेश करते हैं। इनमें शामिल हैं:
  • एक निर्दिष्ट ऑर्थोनॉर्मल बेसिस के वेक्टर्स को क्लोन करना।
  • बेसिस वेक्टर्स की सूचियों को क्रमपरिवर्तित करना।
  • बेसिस लेबल्स को डिकोड करना।
  • इकाई पंक्ति और स्तंभ योग (unit row and column sums) वाली यूनिटरीज को लागू करना (Idel-Wolf normal form के माध्यम से)।
  • ट्रेसलेस यूनिटरी इनवोल्यूशन को लागू करना (एक अतिरिक्त क्लीन क्विबिट का उपयोग करके)।
• पोर्ट-बेस्ड टेलीपोर्टेशन (PBT): विशिष्ट गेट पर निर्भर यूनिटरी सुधारों के बिना मनमाने यूनिटरीज के कार्यान्वयन के करीब पहुँचने के लिए, लेखक पोर्ट-बेस्ड टेलीपोर्टेशन का उपयोग करते हैं। वे मैक्सिमली एंटेंगल्ड स्टेट्स (या लक्षित यूनिटरी के Choi स्टेट्स) और एक जॉइंट मेजरमेंट के साथ PBT करने वाला एक यूनिटरी सर्किट निर्मित करते हैं, जिसके बाद पोर्ट चयन किया जाता है।

प्रमुख योगदान और परिणाम

1. विशिष्ट कार्यों के लिए सटीक निरंतर-गहराई वाले निर्माण:

   • क्रमपरिवर्तन (Permutations): कम्प्यूटेशनल बेसिस स्टेट्स के मनमाने क्रमपरिवर्तनों को $O(n2^n)$ गेट्स और सहायक क्विबिट्स का उपयोग करके निरंतर गहराई (गहराई $\le 20$) में लागू किया जा सकता है।
   • डायगोनल यूनिटरीज: मनमाने डायगोनल यूनिटरीज को इंडिकेटर्स की गणना करके, समानांतर में फेजेस (phases) लागू करके और अनकंप्यूट करके निरंतर गहराई (गहराई 7) में लागू किया जा सकता है।
   • स्टेट प्रिपरेशन: मनमाने शुद्ध क्वांटम स्टेट्स को $O(4^n)$ क्विबिट्स और $O(n2^n)$ गेट्स का उपयोग करके निरंतर गहराई (गहराई $\le 37$) में तैयार किया जा सकता है। सभी सहायक क्विबिट्स को शून्य पर वापस लाया जाता है।
   • फैनआउट कार्यान्वयन: फैनआउट को केवल सिंगल-क्विबिट और जनरलाइज्ड टोफ़ोली गेट्स का उपयोग करके सटीक रूप से निरंतर गहराई में लागू किया जा सकता है, हालांकि इसके लिए दोगुना घातीय आकार की आवश्यकता हो सकती है।

2. मनमाने यूनिटरीज के लिए रिडक्शन:
   लेखक यह प्रदर्शित करते हैं कि निरंतर गहराई में मनमाने यूनिटरीज को लागू करना कई विशिष्ट ऑपरेशन्स (जैसे बेसिस वेक्टर्स को क्लोन करना, लेबल डिकोड करना, या ट्रेसलेस इनवोल्यूशन को लागू करना) को लागू करने के समान है। यह मनमाने यूनिटरी कार्यान्वयन के खुले प्रश्न को समकक्ष संरचनात्मक चुनौतियों के एक सेट में बदल देता है।

3. अनुकूली माप (Adaptive Measurements) और गेट टेलीपोर्टेशन:
   लेखक दिखाते हैं कि यदि अनुकूली मध्यवर्ती मापों (adaptive intermediate measurements) की अनुमति दी जाती है, तो क्लिफोर्ड पदानुक्रम (Clifford hierarchy) के स्तर $\ell$ पर किसी भी गेट को गहराई $O(\ell)$ के साथ लागू किया जा सकता है। इसके अलावा, मनमाने यूनिटरी कार्यान्वयन को अनुकूली मॉडल में ट्रेसलेस यूनिटरी इनवोल्यूशन को लागू करने में बदला जा सकता है।

4. पोर्ट-बेस्ड टेलीपोर्टेशन सन्निकटन (Approximation):
   लेखक एक इनपुट डाइमेंशन $d$ और $M \ge d^2 - 1$ पोर्ट्स के लिए पोर्ट-बेस्ड टेलीपोर्टेशन (PBT) हेतु एक यूनिटरी सर्किट का निर्माण करते हैं।

   • गहराई: सर्किट की गहराई $O(\sqrt{d})$ है, जो पोर्ट्स की संख्या $M$ से स्वतंत्र है।
   • फिडेलिटी (Fidelity): एंटैंगलमेंट फिडेलिटी $F_e \ge (1 - \frac{d^2-1}{2M})^2$ द्वारा सीमित है।
   • सटीकता बनाम गहराई: किसी भी निश्चित इनपुट डाइमेंशन $d$ के लिए, सर्किट की गहराई बढ़ाए बिना पोर्ट्स की संख्या $M$ बढ़ाकर सन्निकटन को मनमाना सटीक बनाया जा सकता है। हालांकि, इनपुट डाइमेंशन $d$ पर निर्भरता बनी रहती है; क्या $d$ से स्वतंत्र गहराई सीमा प्राप्त की जा सकती है, यह एक खुला प्रश्न बना हुआ है।
   • कार्यान्वयन: सर्किट केवल सिंगल-क्विबिट और जनरलाइज्ड टोफ़ोली गेट्स का उपयोग करता है और इसमें किसी मध्यवर्ती माप की आवश्यकता नहीं होती है।

महत्व और दावे
यह शोध पत्र स्थापित करता है कि आकार और सहायक स्थान के प्रतिबंधों को हटाने से निरंतर-गहराई वाले क्वांटम सर्किट उन कार्यों को करने में सक्षम हो जाते हैं जो आमतौर पर बहुपद-आकार वाले निरंतर-गहराई मॉडलों में असंभव होते हैं, जैसे कि मनमाना स्टेट प्रिपरेशन और बेसिस स्टेट्स का क्रमपरिवर्तन। यह क्वांटम स्टेट प्रिपरेशन को रिवर्सिबल क्लासिकल कंप्यूटेशन और प्रोबेबिलिटी डिस्ट्रीब्यूशन प्रिपरेशन से सीधे जोड़ता है।

हालांकि, मनमाने यूनिटरीज के कार्यान्वयन के संबंध में यह शोध पत्र एक मध्यम रुख अपनाता है। जबकि यह क्रमपरिवर्तन, डायगोनल यूनिटरीज और स्टेट प्रिपरेशन के लिए सटीक निरंतर-गहराई वाले निर्माण प्रदान करता है, सामान्य यूनिटरीज का कार्यान्वयन एक खुला प्रश्न बना हुआ है। लेखक इसके समकक्ष लक्षण वर्णन प्रदान करते हैं लेकिन इसे हल नहीं करते हैं।

सामान्य यूनिटरीज के संबंध में प्राथमिक योगदान PBT निर्माण है। लेखक प्रदर्शित करते हैं कि किसी भी निश्चित इनपुट डाइमेंशन के लिए, पोर्ट्स की संख्या बढ़ाकर सर्किट की गहराई बढ़ाए बिना मनमाने यूनिटरीज को मनमाने सटीकता के साथ अनुमानित (approximate) किया जा सकता है। हालांकि, इस निर्माण की गहराई इनपुट डाइमेंशन $d$ के साथ $O(\sqrt{d})$ के रूप में स्केल करती है। लेखक स्पष्ट रूप से कहते हैं कि क्या $d$ पर इस निर्भरता को हटाया जा सकता है (अर्थात, $d$ से स्वतंत्र गहराई सीमा प्राप्त करना) एक खुला प्रश्न है। यह कार्य इस बात पर प्रकाश डालता है कि निरंतर-गर्थी यूनिटरी कार्यान्वयन में मौलिक कठिनाई एक निश्चित इनपुट से मनमाना आउटपुट उत्पन्न करने में नहीं है, बल्कि यूनिटैरिटी बनाए रखते हुए प्रत्येक इनपुट स्टेट पर एक साथ कार्य करने के लिए निर्धारित करने में है।