Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems

तकनीकी सारांश: समीप-सममित अनुकूलन समस्याओं पर उथले QAOA की फॉल्ट-टोलरेंट लागत

समस्या विवरण
मोंटानारो और झोउ [1] ने प्रदर्शित किया है कि डेप्थ-वन क्वांटम एप्रोक्सिमेट ऑप्टिमाइज़ेशन एल्गोरिदम (QAOA) सर्किट कुछ समीप-सममित (near-symmetric) कंस्ट्रेंट सैटिस्फिएबिलिटी प्रॉब्लम्स (CSPs) के प्लांटेड सॉल्यूशन को $\Omega(1)$ की स्थिर संभावना के साथ पा सकते हैं। इसके विपरीत, इन समस्याओं के स्पष्ट यथार्थीकरण (explicit realizations) मजबूत क्लासिकल सॉल्वर के लिए स्पष्ट घातीय रनटाइम स्केलिंग प्रदर्शित करते हैं। हालांकि यह एक अनुभवजन्य घातीय गति (empirical exponential speedup) का सुझाव देता है, प्रारंभिक फॉल्ट-टोलरेंट क्वांटम कंप्यूटरों पर इन सर्किट्स को लागू करने के लिए संसाधन आवश्यकताओं का विवरण स्पष्ट नहीं है। इन समस्याओं के कॉस्ट हैमिल्टोनियन में $\Theta(n^\ell)$ क्लॉज़ होते हैं (जहाँ $\ell \ge 5$), जिसका अर्थ है कि मानक क्लिफोर्ड+$T$ सिंथेसिस का उपयोग करके कंपाइल किए जाने पर नॉन-क्लिफोर्ड गेट काउंट $\tilde{O}(n^\ell)$ स्केल करता है। यह स्केलिंग संबंधित समस्या आकारों को निकट-अवधि (near-term) फॉल्ट-टोलरेंट हार्डवेयर की पहुंच से बाहर कर देती है।

कार्यप्रणाली
लेखक इन समीप-सममित इंस्टेंस पर लागू डेप्थ-वन QAOA सर्किट्स के फॉल्ट-टोलरेंट संसाधन लागत का विश्लेषण करते हैं, विशेष रूप से फेज-सेपरेटर लेयर के सिंथेसिस पर ध्यान केंद्रित करते हैं। विश्लेषण तीन मुख्य चरणों में आगे बढ़ता है:

1. फेज-मैचिंग और एंगल स्केलिंग: लेखक निरंतर सफलता की संभावना के लिए आवश्यक फेज-मैचिंग स्थिति का पुनरावलोकन करते हैं। उन कॉस्ट फंक्शन्स के लिए जो एक प्लांटेड सॉल्यूशन के सापेक्ष वेरिएबल परम्यूटेशन के तहत सममित हैं, प्रमुख हैमिंग शेल्स (Hamming shells) के रचनात्मक हस्तक्षेप (constructive interference) को सुनिश्चित करने के लिए फेज-सेपरेटर एंगल $\gamma$ को $\gamma = \Theta(n^{1-\ell})$ के रूप में स्केल होना चाहिए।
2. स्मॉल-एंगल सिंथेसिस: इस तथ्य का लाभ उठाते हुए कि सिस्टम साइज के साथ $\gamma$ घटता है, लेखक स्मॉल-एंगल क्लिफोर्ड+$T$ रोटेशन सिंथेसिस तकनीकों (विशेष रूप से बोथे एट अल. [9] द्वारा) को लागू करते हैं। वे क्वाज़ी-प्रोबेबिलिटी और प्रोबेबिलिटी मिक्सचर फॉर्मुलेशन का उपयोग करते हैं जहाँ छोटे कोण वाले रोटेशन को उच्च संभावना के साथ आइडेंटिटी द्वारा अनुमानित किया जाता है, और केवल रोटेशन का एक छोटा हिस्सा ही नॉन-क्लिफोर्ड सिंथेसिस की आवश्यकता रखता है।
3. स्पष्ट क्लॉज कंपाइलेशन और लीकेज विश्लेषण: लेखक वैल्यू-ओरेकल मॉडल (जहाँ केवल कॉस्ट मान $C(x)$ को क्वेरी किया जाता है) से स्पष्ट क्लॉज-लिस्ट मॉडल की ओर बढ़ते हैं जो सर्किट कंपाइलेशन के लिए आवश्यक है। वे कॉस्ट फंक्शन से प्राप्त स्पष्ट क्लॉज लिस्ट के फूरियर गुणांकों का विश्लेषण करते हैं ताकि यह निर्धारित किया जा सके कि क्या कंपाइलेशन प्रक्रिया अनजाने में समाधान को प्रकट कर देती है।
4. डिसैप्टिव (Deceptive) इंस्टेंस निर्माण: स्पष्ट संरचना का लाभ उठाने वाले क्लासिकल हमलों के विरुद्ध स्पीडअप की मजबूती का परीक्षण करने के लिए, लेखक "अनप्लांटेड" समीप-सममित इंस्टेंस का निर्माण करते हैं। इन इंस्टेंस में एक घातीय रूप से बड़ा ऑप्टिमल हैमिंग शेल होता है जिसमें NP-हार्ड सब-प्रॉब्लम होती है, और एक ऐसा कॉस्ट लैंडस्केप होता है जो लोकल सर्च एल्गोरिदम को फंसाने के लिए डिज़ाइन किया गया है।

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

• क्वाड्रेटिक नॉन-क्लिफोर्ड स्केलिंग: प्राथमिक परिणाम यह है कि इन इंस्टेंस पर डेप्थ-वन QAOA के लिए नॉन-क्लिफोर्ड कॉस्ट घटकर $\tilde{O}(n^2)$ हो जाता है, जो क्लॉज लोकैलिटी $\ell$ और स्पारसिफिकेशन रेट से स्वतंत्र है। यह कमी इसलिए होती है क्योंकि कुल फेज मास ($m\gamma$, जहाँ $m$ क्लॉज़ की संख्या है) $n$ के साथ रैखिक रूप से स्केल करता है, और स्मॉल-एंगल सिंथेसिस लागत इस फेज मास के वर्ग पर निर्भर करती है। फलस्वरूप, वे समस्या आकार जिन्हें पहले $\tilde{O}(n^\ell)$ स्केलिंग के कारण अव्यवहार्य माना गया था, प्रारंभिक फॉल्ट-टोलरेंट डिवाइसेस के लिए व्यवहार्य हो जाते हैं (देखें चित्र 2)।
• प्लांटेड फैमिलीज में क्लासिकल लीकेज: संदर्भ [1] में अध्ययन किए गए प्लांटेड फैमिलीज के लिए, लेखक दिखाते हैं कि कंपाइलेशन के लिए आवश्यक स्पष्ट क्लॉज लिस्ट प्लांटेड सॉल्यूशन को उजागर करती है। फेज-मैचिंग कंडीशन ($F'(1/2) \neq 0$) कॉस्ट फंक्शन के डिग्री-वन फूरियर गुणांकों (लोकल फील्ड्स) के चिन्हों को फिक्स करती है। ये चिन्ह क्लॉज लिस्ट के सरल लीनियर-टाइम क्लासिकल स्कैन के माध्यम से सीधे प्लांटेड सॉल्यूशन $s$ को प्रकट करते हैं। इस प्रकार, जबकि QAOA स्थिर संभावना के साथ सफल होता है, स्पष्ट कार्यान्वयन समस्या को क्लासिकली ट्रिवियल बना देता है।
• कठिन अनप्लांटेड इंस्टेंस का अस्तित्व: लेखक प्रदर्शित करते हैं कि स्मॉल-एंगल रिजीम और $\tilde{O}(n^2)$ कॉस्ट स्केलिंग, प्लांटेड सॉल्यूशन के अस्तित्व पर निर्भर नहीं हैं। वे बिना प्लांटेड सॉल्यूशन वाले समीप-सममित इंस्टेंस का निर्माण करते हैं जहाँ:
  • ग्लोबल ऑप्टिमम एक घातीय रूप से बड़े हैमिंग शेल के भीतर स्थित है।
  • उस शेल के भीतर सटीक ऑप्टिमम को पाना NP-हार्ड है।
  • कॉस्ट लैंडस्केप "डिसैप्टिव" है, जो हाई एनर्जी बैरियर्स द्वारा अलग किए गए सब-ऑप्टिमल सेक्टर्स में लोकल सर्च और जनरल-परपस MaxSAT सॉल्वर को फंसाता है।
  • डेप्थ-वन QAOA स्मॉल एंगल पर आउटपुट को ऑप्टिमल शेल पर उसी $\tilde{O}(n^2)$ नॉन-क्लिफोर्ड कॉस्ट के साथ केंद्रित करता है।
  • इन अनप्लांटेड मामलों में, डिग्री-वन गुणांक यूनिफॉर्म होते हैं और सॉल्यूशन को प्रकट नहीं करते हैं, जिससे विशिष्ट सिमेट्री स्ट्रक्चर का लाभ न उठाने वाले क्लासिकल एल्गोरिदम के लिए हार्डनेस बनी रहती है।

महत्व
यह शोध पत्र स्थापित करता है कि समीप-सममित समस्याओं पर लो-डेप्थ QAOA के अनुभवजन्य स्पीडअप को पहले की तुलना में काफी कम फॉल्ट-टोलरेंट संसाधनों, विशेष रूप से $\tilde{O}(n^\ell)$ के बजाय $\tilde{O}(n^2)$ नॉन-क्लिफोर्ड गेट्स के साथ प्राप्त किया जा सकता है। यह इन छोटे-कोण वाले सर्किट्स को प्रारंभिक फॉल्ट-टोलरेंट हार्डवेयर के लिए एक यथार्थवादी लक्ष्य बनाता है।

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