Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability

तकनीकी सारांश: न्यूक्लियर टेंसर नॉर्म्स और मल्टीपार्टाइट सेपेरेबिलिटी के लिए बहुपद-समय एल्गोरिदम (Polynomial-Time Algorithms)

समस्या विवरण
यह शोध पत्र उच्च-आयामी अनुकूलन (high-dimensional optimization) और क्वांटम सूचना सिद्धांत के दो मौलिक कम्प्यूटेशनल समस्याओं को संबोधित करता है:

1. न्यूक्लियर नॉर्म वीक मेंबरशिप (Nuclear Norm Weak Membership): दिए गए टेंसर $M \in (\mathbb{R}^d)^{\otimes k}$ के लिए, यह निर्णय लेना कि क्या इसका न्यूक्लियर नॉर्म 1 से अधिक है, या यदि इसकी यूनिट न्यूक्लियर-नॉर्म बॉल से दूरी $\epsilon$ है। न्यूक्लियर नॉर्म को रैंक-वन अपघटन (rank-one decomposition) में निरपेक्ष गुणांकों (absolute coefficients) के योग के इन्फिममियम (infimum) के रूप में परिभाषित किया गया है।
2. मल्टीपार्टाइट क्वांटम सेपेरेबिलिटी (Multipartite Quantum Separability): दिए गए $k$-पार्टी क्वांटम स्टेट $\rho$ (या तो एक स्पष्ट शास्त्रीय विवरण के माध्यम से या अज्ञात स्टेट की प्रतियों के माध्यम से) के लिए, यह निर्णय लेना कि क्या $\rho$ सेपरेबल है (अर्थात उत्पाद अवस्थाओं का एक कॉनवेक्स कॉम्बिनेशन है) या फ्रोबेनियस नॉर्म में सेपरेबल स्टेट्स के सेट $\text{Sep}(d,k)$ से इसकी दूरी $\epsilon$ है।

ये दोनों समस्याएँ NP-hard ज्ञात हैं जब सटीकता $\epsilon$ आयाम $d$ पर निर्भर करती है या जब इनपुट के भाग के रूप में $k$ की संख्या शामिल होती है। जबकि पिछले कार्यों ने फिक्स्ड $k$ या बाइपार्टाइट मामलों ($k=2$) के लिए पॉलीनोमियल-टाइम समाधान या क्वासी-पॉलीनोमियल एल्गोरिदम प्रदान किए थे, $k$ और $d$ के लिए सामान्य पॉलीनोमियल-टाइम एल्गोरिदम (स्थिर एडिटिव एक्यूरेसी के साथ) एक खुला प्रश्न बना हुआ था।

कार्यप्रणाली (Methodology)
लेखक दो अलग-अलग एल्गोरिथमिक फ्रेमवर्क विकसित करते हैं: स्पष्ट रूप से दिए गए टेंसरों के लिए एक शास्त्रीय नियतात्मक (classical deterministic) दृष्टिकोण और प्रतियों के रूप में दिए गए स्टेट्स के लिए एक क्वांटम दृष्टिकोण।

1. शास्त्रीय एल्गोरिदम (नियतात्मक)
स्पष्ट रूप से दिए गए टेंसरों के लिए शास्त्रीय दृष्टिकोण का मूल एक रिकर्सिव स्पेक्ट्रल कम्प्रेशन (spectral compression) तकनीक है, जो मल्टीलीनियर ऑप्टिमाइज़ेशन समस्या को एक सहकारी मल्टीप्रोवर गेम (cooperative multiprover game) के रूप में देखता है।

• स्पेक्ट्रल कम्प्रेशन: प्रत्येक $k$ पार्टियों के स्ट्रैटेजी स्पेस को स्वतंत्र रूप से विविक्त (discretize) करने के बजाय (जिससे एक्सपोनेंशियल ब्लोअप होता है), लेखक पहली $j$ पार्टियों और शेष $k-j$ पार्टियों के बीच की अंतःक्रिया को एक एकल निम्न-आयामी "मैसेज" स्पेस $V_j$ में संकुचित करते हैं।
• रिकर्सिव प्रीफिक्स कम्प्रेशन: $V_{j-1} \otimes H_j$ और शेष सिस्टम्स के बीच के कट्स पर स्पेक्ट्रल ट्रंकेशन (केवल $\eta$ से ऊपर के सिंगुलर वैल्यूज को रखना) लागू करके, वे एक संदेश $p_j$ बनाए रखते हैं जिसका आयाम $O(\eta^{-2})$ होता है।
• एनर्जी आर्गुमेंट (Energy Argument): एक महत्वपूर्ण तकनीकी नवाचार एक "एनर्जी आर्गुमेंट" है जो संचयी त्रुटि (cumulative error) को सीमित करता है। यह दिखाकर कि हटाए गए घटकों के स्क्वेर्ड नॉर्म्स एक बाउंडेड मात्रा (प्रारंभिक नॉर्म) तक टेलिस्कोप करते हैं, कुल त्रुटि को $O(\eta k)$ के बजाय $O(\eta\sqrt{k})$ द्वारा सीमित किया जाता है। यह $\eta$ को $\Theta(\epsilon/\sqrt{k})$ के रूप में सेट करने की अनुमति देता है, जिससे मैसेज स्पेस का आयाम $k$ में पॉलीनोमियल रहता है।
• मेटा-एल्गोरिदम: एल्गोरिदम पुनरावृत्ति से सुलभ (reachable) संदेशों के $\delta$-कवर का निर्माण करता है। छोटे $k$ ($k \le d^2$) के लिए, यह स्थानीय सेटों पर कॉनवेक्स ऑप्टिमाइज़ेशन का उपयोग करता है। बड़े $k$ ($k > d^2$) के लिए, यह साइटों को ब्लॉक्स में समूहित करता है और ब्लॉक्स के भीतर गहन खोज (exhaustive search) करता है, यह लाभ उठाते हुए कि स्थानीय आयाम $k$ के सापेक्ष छोटे हैं।
• वीक मेंबरशिप में रिडक्शन: फ्रैंक-वोल्के (Frank-Wolfe) एल्गोरिदम का उपयोग करके, ड्यूल ऑप्टिमाइज़ेशन समस्या (अधिकतम $\langle M, \rho_1 \otimes \dots \otimes \rho_k \rangle$) के समाधान को न्यूक्लियर नॉर्म और सेपेरेबिलिटी के लिए एक वीक मेंबरशिप टेस्ट में परिवर्तित किया जाता है।

2. क्वांटम एल्गोरिदम (प्रॉपर्टी टेस्टिंग)
उस सेटिंग के लिए जहाँ इनपुट अज्ञात स्टेट $\rho$ है जो प्रतियों के रूप में दिया गया है, लेखक एक डाइमेंशनलिटी रिडक्शन प्रोटोकॉल प्रस्तावित करते हैं जो स्टेट के स्पष्ट आधार (basis) को सीखने से बचता है।

• साइंड प्रोडक्ट-स्टेट ऑप्टिमाइज़ेशन: एल्गोरिदम बाक्शी एट अल. के प्रोडक्ट-स्टेट लर्नर को क्वडिट्स (qudits) और साइंड ऑब्जेक्टिव्स (जैसे $\text{Tr}((\rho - \sigma)\pi)$ को अधिकतम करना) के लिए विस्तारित करता है। यह एक छोटा "ओवरलैप प्रोडक्ट कवर" बनाता है जो सबस्पेस टोमोग्राफी और पॉलीनोमियल ऑप्टिमाइज़ेशन का उपयोग करके लक्ष्य के साथ उच्च ओवरलैप वाली उत्पाद अवस्थाओं की पहचान करने वाली लोकल सर्च प्रक्रिया का उपयोग करता है।
• फिल्टरिंग के माध्यम से डाइमेंशनलिटी रिडक्शन: एल्गोरिदम स्थानीय "फ्रोबेनियस मास" ऑपरेटर्स $A_j = \text{Tr}_{-j}(\rho^2)$ को परिभाषित करता है। यह एक क्वांटम चैनल लागू करता है जो $A_j$ के उन आइगेनवैल्यूज़ को फ़िल्टर करता है जो एक थ्रेशोल्ड से नीचे हैं, प्रभावी रूप से स्टेट को $q = O(k^2/\epsilon^4)$ आयाम वाले निम्न-आयामी सबस्पेस पर प्रोजेक्ट करता है।
• शूर-वेइल ड्यूअलिटी (Schur-Weyl Duality): बिना उच्च-आयामी सबस्पेस के स्पष्ट शास्त्रीय विवरण को सीखे इस प्रोजेक्शन को लागू करने के लिए, लेखक शूर-वेइल ड्यूअलिटी का उपयोग करते हैं। स्टेट की $N$ प्रतियों पर शूर ट्रांसफॉर्म लागू करके, वे परम्यूटेशन रजिस्टर को यूनिटरी रिप्रेजेंटेशन रजिस्टर से अलग करते हैं। वे यूनिटरी रजिस्टर (जिसमें अज्ञात आधार की जानकारी होती है) को हटा देते हैं और उसे एक मानक निम्न-आयामी स्थान से बदल देते हैं, जो प्रभावी रूप से स्थानीय यूनिटरीज पर एक 'हार-एवरेज' (Haar-average) करता है। यह सेपरेबल स्टेट्स से दूरी को बनाए रखते हुए स्थानीय आयाम को $q$ तक कम कर देता है।
• परिणाम: इस रिड्यूस्ड स्टेट को फिर लो-डायमेंशनल टेस्टर में फीड किया जाता है, जिससे $k$ और $\log d$ में पॉलीनोमियल रनटाइम और सैंपल कॉम्प्लेक्सिटी प्राप्त होती है, जो $d$ पर स्वतंत्र है।

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

• थ्योरम 1.1 (न्यूक्लियर नॉर्म): यह पेपर उच्च-क्रम के टेंसरों के न्यूक्लियर-नॉर्म यूनिट बॉल में वीक मेंबरशिप के लिए पहला नियतात्मक पॉलीनोमियल-टाइम एल्गोरिदम प्रस्तुत करता है। इसका रनटाइम $d^{O_\epsilon(k)}$ है।
• थ्योरम 1.2 (क्वांटम सेपेरेबिलिटी): लेखक सामान्य $k$ और $d$ के लिए फ्रोबेनियस नॉर्म में मल्टीपार्टाइट वीक मेंबरशिप समस्या के लिए पहला नियतात्मक पॉलीनोमियल-टाइम एल्गोरिदम प्रदान करते हैं, जो हाल के बाइपार्टाइट-ओनली परिणामों में सुधार करता है। इसका रनटाइम $d^{O_\epsilon(k)}$ है।
• थ्योरम 1.3 (प्रतियों से सेपेरेबिलिटी): एक क्वांटम एल्गोरिदम प्रदान किया गया है जो सेपरेबल स्टेट्स को उन स्टेट्स से अलग करता है जो फ्रोबेनियस नॉर्म में $\epsilon$-दूर हैं, जिसमें $k^{O_\epsilon(1)}$ प्रतियाँ और समय $k^{O_\epsilon(1)} \cdot \text{polylog}(d)$ लगता है। यह सेपरेबल स्टेट्स के सेट में वीक मेंबरशिप के लिए पहला डाइमेंशन-फ्री टेस्ट है।
• तकनीकी नवीनता: कार्य एक रिकर्सिव स्पेक्ट्रल कम्प्रेशन तंत्र पेश करता है जो $O(\eta\sqrt{k})$ एरर बाउंड प्राप्त करता है, जो पिछले $O(\eta k)$ बाउंड्स के विपरीत है जिन्होंने एल्गोरिदम को क्वासी-पॉलीनोमियल टाइम तक सीमित कर दिया था। यह भी प्रदर्शित करता है कि कैसे रिप्रेजेंटेशन थ्योरी (शूर-वेइल ड्यूअलिटी) का उपयोग उच्च-आयामी सबस्पेस के स्पष्ट शास्त्रीय विवरणों की आवश्यकता को बायपास करने के लिए किया जा सकता है।

महत्व
यह शोध पत्र निरंतर सटीकता (constant accuracy) शासन में मल्टीपार्टाइट सेपेरेबिलिटी और न्यूक्लियर नॉर्म मूल्यांकन के लिए पॉलीनोमियल-टाइम एल्गोरिदम खोजने के खुले प्रश्न को हल करने का दावा करता है। कोऑपरेटिव गेम थ्योरी परिप्रेक्ष्य को स्पेक्ट्रल कम्प्रेशन के साथ जोड़कर, लेखक इन समस्याओं के लिए क्वासी-पॉलीनोमियल और पॉलीनोमियल टाइम के बीच के अंतर को पाटते हैं। क्वांटम सेटिंग में, प्रतियों की संख्या और समय को स्थानीय आयाम $d$ (केवल एक पॉलीलॉगैरिद्मिक फैक्टर को छोड़कर) से स्वतंत्र रखकर सेपेरेबिलिटी को टेस्ट करने की क्षमता, पिछले लोअर बाउंड्स और डाइमेंशन-डिपेंडेंट एल्गोरिदम पर एक महत्वपूर्ण प्रगति का प्रतिनिधित्व करती है। यह कार्य रेखांकित करता है कि ट्रेस-नॉर्म सेपेरेबिलिटी के ज्ञात लोअर बाउंड्स को बायपास करने के लिए प्रतियों के बीच कोहेरेंट मेजरमेंट्स आवश्यक हैं, जो कुशल क्वांटम प्रॉपर्टी टेस्टिंग के लिए एक नया मार्ग प्रदान करता है।