तकनीकी सारांश: नॉनलोकल गेम्स में परफेक्ट प्ले की सटीक जटिलता

1. समस्या विवरण

यह शोध पत्र इस निर्णय समस्या (decision problem) का समाधान करता है कि क्या दो अलग-अलग खिलाड़ी विभिन्न क्वांटम मैकेनिकल मॉडलों के तहत एक परिमित नॉनलोकल गेम को निश्चितता (प्रायिकता 1) के साथ जीत सकते हैं। जबकि किसी गेम की जीतने की प्रायिकता का अक्सर एक सुप्रीमम (supremum) के रूप में अध्ययन किया जाता है, यह कार्य परफेक्ट प्ले पर केंद्रित है: यानी एक ऐसी रणनीति का अस्तित्व जो ठीक एक की जीतने वाली प्रायिकता प्राप्त करती है।

केंद्रीय प्रश्न यह है: एक दिए गए परिमित तर्कसंगत (rational) बूलियन गेम के लिए एक परफेक्ट रणनीति के अस्तित्व को निर्धारित करने के लिए आवश्यक अरिथमेटिक पदानुक्रम (arithmetical hierarchy) का सटीक स्तर क्या है?

लेखक इसे कई मॉडलों में विश्लेषित करते हैं:

• परिमित-आयामी ($PERF_q$): परिमित-आयामी हिल्बर्ट स्पेस पर रणनीतियाँ।
• स्थानिक ($PERF_{qs}$): अनंत-आयामी टेंसर उत्पादों पर सामान्य रणनीतियाँ (spatial model)।
• कम्यूटिंग ($PERF_{co}$): एक एकल हिल्बर्ट स्पेस पर कम्यूटिंग ऑपरेटर बीजगणित द्वारा परिभाषित रणनीतियाँ।
• वॉन न्यूमैन प्रकार (Von Neumann Type): विशिष्ट वॉन न्यूमैन बीजगणित (Type I, II, III) द्वारा होस्ट की गई रणनीतियाँ।
• संसाधन बाधाएं (Resource Constraints): वे वेरिएंट जिनमें परिमित मार्जिनल एंट्रॉपी या रिड्यूस्ड डेंसिटी मैट्रिक्स के परिमित $\alpha$-मोमेंट्स की आवश्यकता होती है।

2. कार्यप्रणाली

यह शोध पत्र जटिलता सीमाओं को स्थापित करने के लिए ऑपरेटर थ्योरी, कंप्यूटेबिलिटी थ्योरी और एक नवीन "कंपाइलर" निर्माण के संयोजन का उपयोग करता है।

2.1 कंपाइलर निर्माण

एक मुख्य तकनीकी योगदान एक परिमित कंपाइलर है जो ऑपरेटर-थ्योरेटिक प्रस्तुतियों को परिमित नॉनलोकल गेम्स में अनुवादित करता है।

• इनपुट: एक स्वीकार्य प्रस्तुति जिसमें सेंट्रलइज़र लेबल (यूनिटरीज, प्रोजेक्शंस, कॉन्ट्रैक्शंस) और तर्कसंगत $*$-पॉलीनोमियल समीकरण शामिल हैं, जिसमें $h A_\alpha = \nu A_\alpha h$ (जहाँ $h$ एक डेंसिटी है और $\nu$ एक स्केलिंग फैक्टर है) जैसे मॉड्यूलर संबंध भी शामिल हैं।
• तंत्र: कंपाइलर डेंसिटी स्केलिंग को लागू करने के लिए फ्लैग्ड मैजिक-स्क्वायर (FMS) ब्रिज का उपयोग करता है। $n$ ब्रिजों की एक श्रृंखला स्रोत और लक्ष्य कोनों के बीच $2^n$ का डेंसिटी अनुपात मजबूर करती है। यह "मॉड्यूलर आइसोमेट्रिक्स" का निर्माण करने की अनुमति देता है जो डेंसिटी को स्केल करते हुए ऑपरेटरों को ट्रांसपोर्ट करते हैं।
• आउटपुट: एक परिमित तर्कसंगत बूलियन गेम जहाँ एक परफेक्ट नॉर्मल स्पेशियल रणनीति तभी मौजूद होती है जब इनपुट प्रस्तुति की एक नॉर्मल रियलाइजेशन (realization) हो।
• सत्यता और पूर्णता (Soundness and Completeness): कंपाइलर यह सुनिश्चित करता है कि गेम में कोई भी परफेक्ट रणनीति एक वैध ऑपरेटर रियलाइजेशन निकालती है, और किसी भी वैध रियलाइजेशन को एक परफेक्ट रणनीति (अक्सर परिमित एनसिलरी फैक्टर्स जोड़कर) में विस्तारित किया जा सकता है।

2.2 क्वांटिफायर के माध्यम से जटिलता विश्लेषण

लेखक अस्तित्व की शर्तों के तार्किक ढांचे का विश्लेषण करते हैं:

• $\Pi^0_1$ (को-रिकर्सिवली एन्यूमेरेबल): ऐसी स्थितियाँ जहाँ एक काउंटर-एग्जांपल को सीमित समय में खोजा जा सकता है (जैसे, एक अभिसारी पदानुक्रम की विफलता)।
• $\Sigma^0_2$ (हाल्टिंग प्रॉब्लम के सापेक्ष रिकर्सिवली एन्यूरेबल): $\exists \kappa \forall d \, R(G, \kappa, d)$ के रूप में स्थितियाँ, जहाँ $\kappa$ एक अस्तित्वगत पूर्णांक साक्षी (witness) है और $d$ परिमित परीक्षणों की श्रेणी में आता है।

2.3 हार्डनेस रिडक्शन

$\Sigma^0_2$-पूर्णता (completeness) सिद्ध करने के लिए, लेखक फॉक क्लॉक (Fock clock) और एक रूटेड ट्री (rooted tree) पर आधारित गेम्स का निर्माण करते हैं:

• ट्री (Tree): परिमित शब्दों का एक पेड़ जहाँ डेंसिटी वेट्स ज्यामितीय रूप से घटते हैं।
• क्लॉक (Clock): एक वेइल पेयर $(J_W, K_W)$ और एक फेज ऑपरेटर $Z_{clk}$ जो रूट स्पेस पर कार्य करता है। कम्यूटेशन संबंध $Z_{clk}$ के फेज को $d_{clk}$ के क्रम का एक रूट ऑफ यूनिटी होने के लिए मजबूर करते हैं।
• रिडक्शन (Reduction): गेम एक निर्णय योग्य प्रेडिकेट $R_{dec}(e, j, t)$ को एनकोड करता है। एक परफेक्ट रणनीति को एक क्लॉक ऑर्डर $d_{clk}$ (अस्तित्वगत साक्षी $\kappa$) "चुनना" होगा ताकि सभी समय चरणों $t$ के लिए, गणना रुक जाए या प्रेडिकेट को संतुष्ट करे। हार्डनेस इसलिए उत्पन्न होती है क्योंकि कोई भी कंप्यूट करने योग्य फलन सभी YES इंस्टेंस के लिए पर्याप्त क्लॉक ऑर्डर $d_{clk}$ को बाउंड नहीं कर सकता है।

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

3.1 जटिलता वर्गों पर मुख्य प्रमेय

यह शोध पत्र विभिन्न मॉडलों के लिए परफेक्ट प्ले की सटीक अरिथमेटिक जटिलता स्थापित करता है (पेपर की तालिका 1):

मॉडल / स्थिति	जटिलता वर्ग (Complexity Class)	मुख्य निष्कर्ष
परिमित-आयामी ($PERF_q$)	$\Sigma^0_1$-complete	हाल्टिंग प्रॉब्लम के लिए एक ऑरेकल के साथ निर्णायक (Dimension पर सर्च)।
कम्यूटिंग ($PERF_{co}$)	$\Pi^0_1$-complete	एक अभिसारी पदानुक्रम के साथ निर्णायक; विफलता को सीमित चरणों में पहचाना जा सकता है।
स्पेशियल ($PERF_{qs}$)	$\Sigma^0_2$-complete	दोनों (परिमित-आयामी और कम्यूटिंग) से अधिक कठिन। एक अस्तित्वगत पूर्णांक साक्षी (जैसे, सबसे बड़े श्मिट गुणांक के व्युत्क्रम पर बाउंड) की आवश्यकता होती है।
सेमीफाइनाइट होस्ट्स ($PERF_{sf}$)	$\Sigma^0_2$-complete	इसमें Type II$_1$, II$_\infty$, और सामान्य सेमीफाइनाइट बीजगणित शामिल हैं।
Type III फैक्टर्स ($PERF_{III_\lambda}$)	$\Pi^0_1$-complete	कम्यूटिंग मॉडल की जटिलता में सिमट जाता है।
फाइनाइट एंट्रॉपी ($PERF_{finS}$)	$\Sigma^0_2$-complete	परिमित मार्जिनल एंट्रॉपी के साथ परफेक्ट प्ले भी $\Sigma^0_2$-complete है।
फाइनाइट $\alpha$-मोमेंट्स ($P_\alpha$)	$\Sigma^0_2$-complete	किसी भी निश्चित कंप्यूट करने योग्य $0 < \alpha < 1$ के लिए, $\text{Tr}(h^\alpha) < \infty$ के साथ परफेक्ट प्ले $\Sigma^0_2$-complete है।

3.2 "ट्रेस कॉस्ट" (Trace Cost)

पेपर तर्क देता है कि एक ट्रेस (trace) ठीक एक अस्तित्वगत क्वांटिफायर (existential quantifier) की लागत लेता है।

• स्पेशियल मॉडल में, एक परफेक्ट रणनीति के अस्तित्व के लिए सबसे बड़े श्मिट गुणांक (या समकक्ष रूप से, सेमीफाइनाइट बीजगणित में एक परिमित कोने के साथ ओवरलैप) को बाउंड करना आवश्यक है। यह बाउंड अस्तित्वगत साक्षी $\kappa$ के रूप में कार्य करता है।
• Type III बीजगणितों में, कोई परिमित कोने (कोई ट्रेस नहीं) नहीं होते हैं, और भाषा $\Pi^0_1$ (कम्यूटिंग परफेक्शन) में सिमट जाती है।
• लेखक संसाधन स्थितियों की एक "स्ट्रिक्ट लैडर" (strict ladder) का निर्माण करते हैं: $P_0 \subsetneq P_\alpha \subsetneq P_1 \subsetneq P_{normal}$, जहाँ $P_0$ परिमित रैंक है, $P_\alpha$ परिमित $\alpha$-मोमेंट है, और $P_1$ परिमित एंट्रॉपी है। सभी मध्यवर्ती चरण $\Sigma^0_2$-complete रहते हैं।

3.3 ज़ीरो-एरर कम्युनिकेशन

परिणाम एक-शॉट ज़ीरो-एरर कम्युनिकेशन पर भी लागू होते हैं:

• नॉर्मल एंटैंगलमेंट के साथ ज़ीरो-एरर कोड के अस्तित्व को तय करना $\Sigma^0_2$-complete है।
• लेखक एक परिमित क्लासिकल चैनल का निर्माण करते हैं जहाँ नॉर्मल एंटैंगलमेंट के साथ एक ज़ीरो-एरर कोड मौजूद है, लेकिन प्रत्येक ऐसा कोड अनंत मार्जिनल एंट्रॉपी की आवश्यकता रखता है। यह एक कोड के अस्तित्व और उसके द्वारा उपयोग किए जाने वाले एंटैंगलमेंट संसाधनों के बीच अलगाव को प्रदर्शित करता है।

3.4 औपचारिक सत्यापन (Formal Verification)

लेखक Theorem A (Spatial Perfection) का Lean 4 में औपचारिक सत्यापन प्रदान करते हैं। प्रमाण में Lean के मानक तीन सिद्धांतों (propext, Classical.choice, Quot.sound) के अलावा किसी अन्य एक्सिओम का उपयोग नहीं किया गया है। सत्यापन कंपाइलर अनुबंध, ऊपरी सीमा (compactness arguments), और हार्डनेस रिडक्शन को कवर करता है।

4. महत्व और दावे

यह शोध पत्र दावा करता है कि यह नॉनलोकल गेम्स में परफेक्ट प्ले की सटीक कम्प्यूटेशनल जटिलता को हल करता है, जो एक गैर-मोनोटोनिक (non-monotonic) कठिनाई पदानुक्रम को प्रकट करता है:

1. गैर-मोनोटोनिसिटी (Non-Monotonicity): स्पेशियल मॉडल, जो सहसंबंध सेटों (correlation sets) के मामले में परिमित-आयामी और कम्यूटिंग मॉडलों के बीच स्थित है, परफेक्ट प्ले के लिए दोनों से काफी अधिक कठिन है।
   • परिमित-आयामी: $\Sigma^0_1$
   • कम्यूटिंग: $\Pi^0_1$
   • स्पेशियल: $\Sigma^0_2$
2. क्वांटिफायर की आवश्यकता: हार्डनेस प्रमाण दर्शाते हैं कि अस्तित्वगत क्वांटिफायर केवल प्रमाण तकनीक का एक अवशेष नहीं है बल्कि आवश्यक है। कोई भी कंप्यूट करने योग्य फलन परफेक्ट रणनीति के लिए आवश्यक "क्लॉक पीरियड" या "श्मिट स्ट्रेटा" (Schmidt stratum) को बाउंड नहीं कर सकता है।
3. संसाधन पृथक्करण: कार्य परफेक्ट रणनीति के अस्तित्व और उसके द्वारा उपभोग किए जाने वाले संसाधनों के बीच अंतर करता है। यह दिखाता है कि परफेक्ट स्पेशियल प्ले तब भी मौजूद हो सकता है जब परिमित-आयामी रणनीतियाँ विफल हो जाती हैं, और यहाँ तक कि जब परिमित-एंट्रॉपी रणनीतियाँ मौजूद नहीं होती हैं।
4. ऑपरेशनल स्प्लिट: पेपर सेमीफाइनाइट बीजगणित (जहाँ एक ट्रेस मौजूद है और जटिलता $\Sigma^0_2$ है) और Type III फैक्टर्स (जहाँ कोई ट्रेस नहीं है और जटिलता $\Pi^0_1$ हो जाती है) के बीच एक स्पष्ट ऑपरेशनल विभाजन की पहचान करता है।

लेखक इस बात पर जोर देते हैं कि ये परिणाम प्राप्ति (प्रोबेबिलिटी 1 के साथ जीतना) के बारे में हैं, न कि केवल जीतने की प्रायिकताओं के सुप्रीमम के बारे में। वे स्पष्ट करते हैं कि जबकि सुप्रीमम 1 हो सकता है, स्पेशियल मॉडल में उसे प्राप्त करने वाली रणनीति मौजूद नहीं हो सकती है, और स्पेशियल मॉडल में इसके अस्तित्व का निर्णय लेना हाल्टिंग प्रॉब्लम के ऑरेकल के साथ भी अनिर्णायक (undecidable) है।

5. सीमाएँ और खुले प्रश्न

पेपर कुछ खुले प्रश्नों को स्वीकार करता है:

• एसिम्टोटिक कैपेसिटी (Asymptotic Capacity): परिणाम एक-शॉट ज़ीरो-एरर कम्युनिकेशन पर लागू होते हैं; एसिम्टोटिक एंटैंगलमेंट-असिस्टेड ज़ीरो-एरर कैपेसिटी की कंप्यूटेबिलिटी अभी भी खुली है।
• निर्धारित टेबल्स (Prescribed Tables): विशिष्ट निर्धारित सहसंबंध तालिकाओं (केवल किसी परफेक्ट रणनीति के अस्तित्व के बजाय) के लिए सदस्यता को तय करने की जटिलता, विशेष रूप से परिदृश्यों पर एकरूपता के संबंध में, सभी मामलों के लिए पूरी तरह से हल नहीं की गई है।
• इष्टतम सीमाएँ (Optimal Bounds): पेपर रिडक्शन गेम्स के आकार या आवश्यक श्मिट स्ट्रेटा के लिए इष्टतम प्रभावी सीमाएँ प्रदान नहीं करता है, केवल उनके अस्तित्व को बताता है।

संक्षेप में, यह शोध पत्र परफेक्ट क्वांटम रणनीतियों से जुड़ी निर्णय समस्याओं का एक कठोर वर्गीकरण प्रदान करता है, यह स्थापित करते हुए कि ट्रेस की उपस्थिति (या सबसे बड़े श्मिट गुणांक को बाउंड करने की क्षमता) जटिलता को $\Pi^0_1$ या $\Sigma^0_1$ से बढ़ाकर $\Sigma^0_2$ कर देती है, जिससे परफेक्ट स्पेशियल प्ले मौलिक रूप से हाल्टिंग प्रॉब्लम ऑरेकल वाले किसी भी एल्गोरिदम द्वारा अनिर्णायक हो जाता है।