⚛️ quantum physics

Evaluating QAOA expectation values can be as hard as counting optimal solutions

यह शोध पत्र यह स्थापित करता है कि गहराई $p \geq 2$ पर MaxCut समस्या के लिए सटीक या घातांकीय रूप से सटीक (exponentially precise) QAOA प्रत्याशा मानों (expectation values) का मूल्यांकन करना #P-कठिन (hard) है, जो यह दर्शाता है कि गणनात्मक कठिनाई केवल अनुकूलन (optimization) से हटकर इष्टतम समाधानों की गणना करने की ओर स्थानांतरित हो जाती है।

मूल लेखक: Stuart Hadfield

प्रकाशित 2026-08-13

📖 9 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Stuart Hadfield

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

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

यह जानने के लिए कि खजाने की खोज अच्छी चल रही है या नहीं, वैज्ञानिकों को "एक्सपेक्टेशन वैल्यू" (अपेक्षा मान) की जांच करने की आवश्यकता होती है। सरल शब्दों में, यह क्वांटम कंप्यूटर के नृत्य को एक त्वरित नज़र डालने जैसा है ताकि यह देखा जा सके कि वह सोने को खोजने के कितने करीब है, बिना वास्तव में नृत्य को रोकने और हर एक सिक्के को गिनने के। लंबे समय तक, शोधकर्ताओं को पता था कि यदि नृत्य में केवल एक चरण (डेप्थ $p=1$ ) था, तो इस स्कोर की जांच करना आसान था, जैसे एक सरल रेसिपी को पढ़ना। लेकिन क्या होता है जब नृत्य अधिक जटिल हो जाता है, दो या अधिक चरणों के साथ? वांग और सहयोगियों द्वारा किए गए एक हालिया अध्ययन ने दिखाया कि इन गहरे नृत्यों के लिए स्कोर की जांच करना अविश्वसनीय रूप से कठिन है—इतना कठिन कि यह मूल खजाने की खोज को हल करने जितना ही कठिन है। लेकिन क्या यह केवल एक अच्छा पथ खोजने जितना ही कठिन है, या यह उससे भी अधिक कठिन है?

स्टुअर्ट हैडफील्ड द्वारा लिखित यह शोध पत्र उसी प्रश्न की गहराई में उतरता है। लेखक सिद्ध करते हैं कि दो या अधिक परतों वाले QAOA के लिए, स्कोर की जांच करना केवल एक एकल सर्वोत्तम समाधान खोजने जितना कठिन नहीं है; यह प्रत्येक मौजूदा सर्वोत्तम समाधानों को गिनने जितना कठिन है। कंप्यूटर विज्ञान की दुनिया में, एक समाधान खोजना एक कठिन चुनौती है, लेकिन उन सभी को गिनना एक अलग स्तर का दैत्य है, जिसे अक्सर शास्त्रीय (क्लासिकल) कंप्यूटरों के लिए और भी अधिक असंभव माना जाता है। हैडफील्ड दिखाते हैं कि यह "गिनने वाला दैत्य" (काउंटिंग मॉन्स्टर) एल्गोरिदम में दूसरी परत जोड़ने के साथ ही प्रकट हो जाता है। यह शोध पत्र केवल यह सुझाव नहीं देता है; यह एक कठोर गणितीय प्रमाण प्रदान करता है, जो एक विशिष्ट प्रकार के समस्या ग्राफ का निर्माण करता है जो किसी भी कंप्यूटर को, जो QAOA स्कोर की गणना करने की कोशिश कर रहा है, अनिवार्य रूप से उस असंभव गणना समस्या को हल करने के लिए मजबूर करता है। इसका अर्थ यह है कि इन गहरे क्वांटम एल्गोरिदम के लिए, यह कार्य कि वे कितनी अच्छी तरह प्रदर्शन कर रहे हैं, बदतर स्थिति में, एक ऐसा कार्य है जो शास्त्रीय कंप्यूटरों की पहुंच से मौलिक रूप से परे हो सकता है, भले ही हमारे पास नृत्य चलाने के लिए एक आदर्श क्वांटम मशीन क्यों न हो।

खजाने की खोज जटिल हो जाती है

आइए इस जादू के पीछे के तर्क को समझें। QAOA एल्गोरिदम "मैक्सकट" (MaxCut) समस्या को हल करने के लिए डिज़ाइन किया गया है। कल्पना कीजिए कि पार्टी में दोस्तों का एक समूह है, और आप उन्हें दो टीमों (टीम रेड और टीम ब्लू) में विभाजित करना चाहते हैं ताकि एक खेल खेला जा सके। लक्ष्य टीमों को इस तरह व्यवस्थित करना है कि दोनों पक्षों के बीच अधिकतम संख्या में मित्रताएँ टूटें। यह "मैक्सकट" है। कुछ व्यवस्थाएं दूसरों से बेहतर होती हैं, और पूर्णतः सर्वोत्तम व्यवस्था खोजना एक क्लासिक पहेली है जो दोस्तों की संख्या बढ़ने के साथ कठिन होती जाती है।

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

एक ट्विस्ट ( $p=1$ ) के लिए, इस स्कोर की गणना करना आसान है। आप इसे एक नैपकिन पर लिख सकते हैं। लेकिन जब आप दूसरा ट्विस्ट ( $p=2$ ) जोड़ते हैं, तो चीजें अजीब हो जाती हैं। पिछले शोध ने दिखाया था कि इस स्कोर की गणना करना "NP-hard" था, जिसका अर्थ था कि यह एक एकल सर्वोत्तम टीम व्यवस्था खोजने जितना कठिन था। लेकिन हैडफील्ड का पेपर कहता है, "रुको, यह वास्तव में उससे भी बदतर है।"

गिनने वाला दैत्य (The Counting Monster)

हैडफील्ड की मुख्य खोज हमारी समझ में एक तीव्र सुधार है। वह सिद्ध करते हैं कि $p \ge 2$ के लिए स्कोर की गणना करना केवल "NP-hard" (एक समाधान खोजना) नहीं है, बल्कि यह #P-hard है।

अंतर को समझने के लिए, कल्पना करें कि आप एक जासूस हैं।

NP-hard ऐसा है जैसे आपसे पूछा जाए: "क्या आप एक संदिग्ध को ढूंढ सकते हैं जिसने अपराध किया है?" यह कठिन है, लेकिन यदि आप भाग्यशाली हैं या पर्याप्त प्रयास करते हैं, तो आप एक को ढूंढ सकते हैं।
#P-hard ऐसा है जैसे आपसे पूछा जाए: "कुल कितने संदिग्धों ने अपराध किया है?" आपको उन सभी को खोजना होगा और उन्हें गिनना होगा।

कंप्यूटर विज्ञान की दुनिया में, गिनती करना आमतौर पर केवल एक को खोजने की तुलना में बहुत अधिक कठिन माना जाता है। हैडफील्ड दिखाते हैं कि दो या अधिक परतों वाले QAOA के लिए, स्कोर की गणना करने के लिए आवश्यक गणित आपको पूर्ण समाधानों की संख्या गिनने के लिए मजबूर करता है।

जादुई गैजेट (The Magic Gadget)

उन्होंने इसे कैसे सिद्ध किया? हैडफील्ड ने एक चतुर "गैजेट" बनाया, जो एक जाल की तरह है जिसे कंप्यूटर को पकड़ने के लिए डिज़ाइन किया गया है। उन्होंने एक मानक मैक्सकट समस्या ली और उसके चारों ओर एक विशाल, जटिल ग्राफ बनाया। इस ग्राफ में विशेष "एंकर" बिंदु और "वेरिएबल" ब्लॉक हैं।

ट्रिक इसके डिज़ाइन में है। जब क्वांटम कंप्यूटर इस विशिष्ट ग्राफ पर अपना नृत्य चलाता है, तो अंतिम स्कोर (एक्सपेक्टेशन वैल्यू) एक विशाल गणितीय अभिव्यक्ति में बदल जाता है जिसे "लॉरेंट पॉलीनोमियल" (Laurent polynomial) कहा जाता है। यह अभिव्यक्ति शब्दों की एक लंबी श्रृंखला की तरह है, प्रत्येक का एक अलग चर (variable) की घात (power) है (जैसे $z^1, z^2, z^3...$ )।

हैडफील्ड ने दिखाया कि इस श्रृंखला में उच्चतम घात (extreme coefficient) एक रहस्य रखती है। यदि आप स्कोर की पूरी तरह से गणना कर सकते हैं, तो आप इस उच्चतम घात को निकाल सकते हैं। और यहाँ मुख्य बात यह है: उस विशिष्ट संख्या का आकार मूल समस्या के कुल पूर्ण समाधानों के सीधे आनुपातिक है।

इसलिए, यदि आप इस ग्राफ के लिए QAOA स्कोर आसानी से निकाल सकते हैं, तो आप तुरंत "गिनने वाले दैत्य" वाली समस्या का उत्तर जान जाएंगे। चूंकि गिनती करना शास्त्रीय कंप्यूटरों के लिए कुशलतापूर्वक करना असंभव माना जाता है, इसलिए QAOA स्कोर की गणना करना भी उनके लिए असंभव होना चाहिए।

"एक किनारे" का आश्चर्य (The "One Edge" Surprise)

पेपर और भी आश्चर्यजनक हो जाता है। आप सोच सकते हैं, "ठीक है, कुल स्कोर की गणना करना कठिन है, लेकिन शायद केवल एक विशिष्ट मित्रता (एक सिंगल एज) के लिए स्कोर की गणना करना आसान है?"

हैडफील्ड कहते हैं, नहीं। वह सिद्ध करते हैं कि यदि आप केवल क्वांटम कंप्यूटर से दो विशिष्ट लोगों के बीच सहसंबंध (एक "टू-क्यूबिट कोरिलेटर" जैसे $\langle Z_r Z_s \rangle$ ) के बारे में पूछते हैं, तो भी समस्या #P-hard बनी रहती है। कठिनाई केवल बड़े चित्र में नहीं है; यह एल्गोरिदम के सबसे छोटे विवरणों में भी रची-बसी है।

भविष्य के लिए इसका क्या अर्थ है

यह शोध पत्र एक स्पष्ट रेखा खींचता है:

डेप्थ $p=1$ : आसान। हम स्कोर की गणना कुशलतापूर्वक कर सकते हैं।
डेप्थ $p \ge 2$ : कठिन। स्कोर की गणना करना सभी समाधानों को गिनने जितना कठिन है।

इसके बहुत बड़े निहितार्थ हैं। कई आधुनिक एल्गोरिदम मशीन को प्रशिक्षित करने के लिए QAOA का उपयोग करते हैं, जिससे "ट्विस्ट" (पैरामीटर्स) को बेहतर स्कोर प्राप्त करने के लिए समायोजित किया जाता है। यदि स्कोर की गणना करना इतना कठिन है, तो इन एल्गोरिदम को शास्त्रीय कंप्यूटर पर प्रशिक्षित करना (यह देखने के लिए कि क्वांटम मशीन कैसा प्रदर्शन कर रही है) गहरे सर्किटों के लिए असंभव हो सकता है।

लेखक यह भी नोट करते हैं कि इसका मतलब यह नहीं है कि क्वांटम कंप्यूटर बेकार हैं। वास्तव में, इसका मतलब यह हो सकता है कि वे अधिक उपयोगी हैं। यदि एक शास्त्रीय कंप्यूटर स्कोर की जांच भी नहीं कर सकता, तो शायद क्वांटम कंप्यूटर ही एकमात्र चीज़ है जो ऐसा कर सकता है। हालांकि, पेपर यह चेतावनी भी देता है कि यह "कठिनाई" एक 'वर्स्ट-केस' (सबसे खराब स्थिति) परिदृश्य है। इसका मतलब यह नहीं है कि हर ग्राफ को हल करना असंभव है; इसका मतलब केवल यह है कि कुछ विशिष्ट, जटिल ग्राफ मौजूद हैं जहाँ गणित विफल हो जाता है।

निष्कर्ष

स्टुअर्ट हैडफील्ड का पेपर क्वांटम समुदाय के लिए एक चेतावनी है। यह हमें बताता है कि जैसे-जैसे हम अधिक परतें जोड़कर QAOA को अधिक शक्तिशाली बनाते हैं, हम न केवल समस्या को हल करना कठिन नहीं बना रहे हैं, बल्कि हम अपने काम की जांच करना भी घातीय रूप से (exponentially) कठिन बना रहे हैं। हमने एक ऐसी दुनिया से निकलकर एक ऐसी दुनिया में प्रवेश कर लिया है जहाँ क्वांटम नृत्य को सत्यापित करना एक ऐसी गणनात्मक पहेली को हल करने के समान है जो कंप्यूटर विज्ञान की सबसे कठिन चीजों में से एक हो सकती है। यह हमें याद दिलाता है कि क्वांटम क्षेत्र में, आप जितनी गहराई में जाएंगे, गणित उतना ही रहस्यमय होता जाएगा।

तकनीकी सारांश: QAOA प्रत्याशा मानों (Expectation Values) का मूल्यांकन करना #P-Hard है

समस्या विवरण
यह शोध पत्र मैक्सकट (MaxCut) समस्या पर लागू क्वांटम एप्रोक्सिमेट ऑप्टिमाइज़ेशन एल्गोरिदम (QAOA) के लिए प्रत्याशा मानों (expectation values) के मूल्यांकन की कम्प्यूटेशनल जटिलता को संबोधित करता है। जबकि किसी भी ग्राफ के लिए गहराई $p=1$ पर लागत प्रत्याशा मान $F_p(G; \gamma, \beta) = \langle \psi_p | C_G | \psi_p \rangle$ का मूल्यांकन कुशलतापूर्वक गणना योग्य (efficiently computable) माना जाता है, हालिया कार्यों ने स्थापित किया है कि किसी भी निश्चित गहराई $p \ge 2$ के लिए सटीक मूल्यांकन NP-hard हो जाता है। यहाँ जांचा गया केंद्रीय प्रश्न यह है कि क्या $p \ge 2$ के लिए हार्डनेस केवल अनुकूलन (समाधान खोजना) तक सीमित है या यह गणना (समाधानों की संख्या निर्धारित करना) तक विस्तृत होती है। विशेष रूप से, लेखक पूछते हैं कि क्या इन प्रत्याशा मानों का मूल्यांकन करना #P-hard है, जो एक ऐसी जटिलता श्रेणी (complexity class) है जिसे सामान्यतः NP से अधिक कठिन माना जाता है, और जो एक बाधा संतुष्टि समस्या (constraint satisfaction problem) के समाधानों की संख्या गिनने की कठिनाई के अनुरूप है।

कार्यप्रणाली (Methodology)
लेखक द्वारा Wang et al. [5] द्वारा प्रस्तुत हार्डनेस प्रूफ तंत्र को परिष्कृत किया गया है, जिसने सबसे बड़े घातांक (exponent) से अधिकतम कट मान को पुनः प्राप्त करने के लिए लॉरेंट बहुपदों (Laurent polynomials) का उपयोग किया था। लेखक का दृष्टिकोण निम्नलिखित चरणों में शामिल है:

ग्राफ निर्माण (संतुलित गणना गैजेट - Balanced Counting Gadget): पूर्ववर्ती कार्य में प्रयुक्त असममित गैजेट्स के बजाय, लेखक एक इनपुट ग्राफ $H$ से एक विशिष्ट ग्राफ $G(H)$ का निर्माण करते हैं। यह निर्माण निम्नलिखित का उपयोग करता है:
- वैरिएबल गैजेट्स (Variable Gadgets): $H$ के प्रत्येक शीर्ष (vertex) के लिए, एक संतुलित पूर्ण द्विपक्षीय ग्राफ $K_{L,L}$ बनाया जाता है, जहाँ $L = O(n)$ है।
- तुल्यकालिक किनारे (Synchronous Edges): $H$ के आसन्न (adjacent) शीर्षों के $K_{L,L}$ गैजेट्स के बीच के संगत शीर्षों को जोड़ने वाले किनारे, ताकि मूल ग्राफ की संरचना सुरक्षित रहे।
- एंकर वर्टिस (Anchor Vertices): दो सार्वभौमिक शीर्ष (universal vertices), $r$ और $s$ , जो वैरिएबल गैजेट्स के प्रत्येक शीर्ष से और आपस में जुड़े हुए हैं।
  यह निर्माण सुनिश्चित करता है कि ग्राफ $G(H)$ का व्यास (diameter) 2 है और इसके अधिकतम कट (maximum cuts) कठोर रूप से बाधित हैं: $K_{L,L}$ गैजेट्स को पूरी तरह से काटा जाना चाहिए, और एंकर्स को विपरीत पक्षों पर होना चाहिए।
लॉरेंट बहुपद विश्लेषण (Laurent Polynomial Analysis): लागत प्रत्याशा मान (या एक विशिष्ट दो-क्विबिट कोरिलेटर $\langle Z_r Z_s \rangle$ ) को चरण चर (phase variable) $z = e^{i\phi}$ में एक लॉरेंट बहुपद के रूप में व्यक्त किया जाता है। लेखक इस बहुपद के गुणांकों का विश्लेषण करते हैं।
- वे एक "चरम गुणांक" (extreme coefficient) की पहचान करते हैं जो उच्चतम घात वाले घातांक $D^*$ के अनुरूप है।
- एक "रिड्यूस्ड पाथ सम" (reduced path sum) विश्लेषण के माध्यम से, वे सिद्ध करते हैं कि गुणांक $a_{D^*}$ गैर-शून्य है और मूल ग्राफ के अधिकतम कट्स की संख्या, जिसे $|\# \text{MC}(H)|$ द्वारा दर्शाया गया है, के सीधे आनुपातिक है।
- विशेष रूप से, $a_{D^*} = \kappa \cdot |\# \text{MC}(H)|$ , जहाँ $\kappa$ मिक्सर कोणों (mixer angles) और ग्राफ के आकार पर निर्भर एक ज्ञात गैर-शून्य बीजगणितीय कारक है।
इंटरपोलेशन के माध्यम से रिडक्शन (Reduction via Interpolation): लेखक यह प्रदर्शित करते हैं कि पॉलीनोमियल रूप से कई अलग-अलग चरण मानों (इकाई के मूल रूप - roots of unity) पर QAOA प्रत्याशा मान ऑरेकल (oracle) को क्वेरी करके, इन्वर्स डिस्क्रीट फूरियर ट्रांसफॉर्म का उपयोग करके लॉरेंट गुणांकों को सटीक रूप से पुनः प्राप्त किया जा सकता है। चूंकि चरम गुणांक अधिकतम कट्स की गिनती को समाहित करता है, इसलिए एक सटीक मूल्यांकन (या घातीय सटीकता वाला मूल्यांकन) करने वाला ऑरेकल इस गिनती को पुनः प्राप्त करने की अनुमति देता है, जिससे अधिकतम कट्स की गणना करने वाली #P-hard समस्या से QAOA प्रत्याशा मानों के मूल्यांकन की समस्या तक एक नियत (deterministic) बहुपद-समय ट्यूरिंग रिडक्शन स्थापित होता है।

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

जटिलता द्विशाख (Complexity Dichotomy): यह शोध पत्र अनवेटेड सरल ग्राफों पर QAOA प्रत्याशा मानों के लिए एक स्पष्ट जटिलता संक्रमण स्थापित करता है:
- $p=1$ : समस्या FP (बहुपद-समय गणना योग्य) में है।
- $p \ge 2$ : समस्या नियत बहुपद-समय ट्यूरिंग रिडक्शन के तहत #P-hard है।
गणना बनाम अनुकूलन (Counting vs. Optimization): पिछले NP-hardness परिणाम के विपरीत, जो अधिकतम कट के मान को पुनः प्राप्त करता था, यह कार्य दिखाता है कि प्रत्याशा मान का मूल्यांकन करने से अधिकतम कट्स की संख्या को पुनः प्राप्त किया जा सकता है। यह हार्डनेस को अनुकूलन (optimization) से बढ़ाकर गणना (counting) तक ले जाता है।
प्रतिबंधित हार्डनेस (Restricted Hardness): यह हार्डनेस महत्वपूर्ण प्रतिबंधों के तहत भी बनी रहती है:
- यह वैश्विक लागत फलन (global cost function) के बजाय एक निर्दिष्ट एकल दो-क्विबिट कोरिलेटर $\langle Z_r Z_s \rangle$ के मूल्यांकन पर लागू होता है।
- यह मिश्रण कोणों के एक अत्यधिक प्रतिबंधित सेट ( $\beta_1 = \arctan(1/2)$ , $\beta_2 = \pi/4$ , और समान लागत कोण $\gamma_1 = \gamma_2 = \phi$ ) के लिए मान्य है।
- यह व्यास 2 वाले ग्राफों पर लागू होता है (हालांकि इन ग्राफों में उच्च डिग्री होती है)।
डेरिवेटिव और हेसियन (Derivatives and Hessians): लेखक इन परिणामों को यह दिखाने के लिए विस्तारित करते हैं कि मापदंडों के सापेक्ष QAOA लागत फलन के सटीक ग्रेडिएंट (gradients) और हेसियन (Hessians) की गणना करना भी #P-hard है।
घातीय सटीकता (Exponential Precision): हार्डनेस घातीय रूप से छोटी योगात्मक त्रुटि ( $2^{-\alpha N}$ ) के साथ प्रत्याशा मान को अनुमानित करने की समस्या तक विस्तृत है, क्योंकि यह सटीकता चरम गुणांक को अलग करने और राउंडिंग के माध्यम से पूर्णांक गणना को पुनः प्राप्त करने के लिए पर्याप्त है।

महत्व और दावे
यह शोध पत्र दावा करता है कि यह QAOA प्रत्याशा मानों के लिए एक "स्वच्छ सटीक-जटिलता वर्गीकरण" (clean exact-complexity classification) प्रदान करता है। प्राथमिक महत्व यह प्रदर्शित करने में है कि $p=1$ से $p=2$ में संक्रमण केवल ट्रैक्टेबिलिटी (tractability) से अनुकूलन हार्डनेस (NP-hard) में बदलाव नहीं है, बल्कि यह गणना हार्डनेस (#P-hard) में बदलाव है।

लेखक इस बात पर जोर देते हैं कि उनके परिणाम उच्च-डिग्री वाले विशिष्ट ग्राफ परिवारों के संबंध में 'वर्स्ट-केस' (worst-case) कथन हैं और वे सभी ग्राफों या सामान्य उदाहरणों के लिए QAOTA का मूल्यांकन करना कठिन होने का संकेत नहीं देते हैं। वे नोट करते हैं कि हार्डनेस सटीक या घातीय सटीकता वाले मूल्यांकन पर निर्भर करती है; वे निरंतर (constant) या बहुपद-स्तर की योगात्मक त्रुटि वाले शासन (regimes) के लिए हार्डनेस का दावा नहीं करते हैं, जो वर्तमान शोरयुक्त इंटरमीडिएट-स्केल क्वांटम (NISQ) उपकरणों के लिए अधिक प्रासंगिक हैं।

इसके अतिरिक्त, यह शोध पत्र सैंपलिंग से संबंधित क्वांटम सुप्रीमेसी (quantum supremacy) परिणामों से अपने निष्कर्षों को अलग करता है। जबकि $p=1$ पर QAOA आउटपुट से सैंपलिंग करना कुछ शर्तों के तहत पहले से ही क्लासिकली कठिन है, यह कार्य दिखाता है कि $p=2$ पर प्रत्याशा मान का मूल्यांकन करना #P-hard गणना समस्याओं को हल करने के लिए पर्याप्त है। लेखक निष्कर्ष निकालते हैं कि उनके परिणाम यह संकेत देते हैं कि यदि कोई $2^{-\alpha N}$ की घातीय सटीकता के साथ QAOA प्रत्याशा मानों को कुशलतापूर्वक मूल्यांकन कर सकता है, तो पॉलीनोमियल हाइरार्की (polynomial hierarchy) अपने निम्नतम स्तर ($P=PH$) तक ढह जाएगी। इसके हाइब्रिड एल्गोरिदम के लिए निहितार्थ हैं जो क्वांटम प्रत्याशा मानों के क्लासिकल प्रोसेसिंग पर निर्भर करते हैं, जो यह सुझाव देते हैं कि यदि उच्च सटीकता की आवश्यकता हो, तो ऐसे दृष्टिकोणों को वर्स्ट-केस में मौलिक कम्प्यूटेशनल बाधाओं का सामना करना पड़ सकता है।