⚛️ quantum physics

Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

यह शोध पत्र सेमिडेफिनेट प्रोग्रामिंग के लिए एक क्वांटम अल्टरनेटिंग डायरेक्शन मेथड ऑफ मल्टीप्लायर्स (QADMM) प्रस्तुत करता है जो शास्त्रीय और अन्य क्वांटम दृष्टिकोणों की तुलना में $\epsilon$ -इष्टतम समाधान तक बेहतर स्केलिंग और अभिसरण प्राप्त करने के लिए क्वांटम सिंगुलर वैल्यू ट्रांसफॉर्मेशन और एक अनिश्चित (inexact) ढांचे का लाभ उठाता है।

मूल लेखक: Hantao Nie, Dong An, Zaiwen Wen

प्रकाशित 2026-06-30

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

CC BY 4.0

मूल लेखक: Hantao Nie, Dong An, Zaiwen Wen

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

कल्पना कीजिए कि आप एक विशाल, जटिल पहेली को हल करने की कोशिश कर रहे हैं जिसे सेमीडेफिनेट प्रोग्रामिंग (SDP) कहा जाता है। यह केवल एक साधारण जिग्सॉ पहेली नहीं है; यह एक गणितीय समस्या है जिसका उपयोग रोबोट को नियंत्रित करने से लेकर वित्तीय पोर्टफोलियो प्रबंधित करने तक, हर चीज़ को अनुकूलित (optimize) करने के लिए किया जाता है। पेच यह है कि पहेली के टुकड़े विशाल मैट्रिसेस (संख्याओं के ग्रिड) हैं, और सही फिट ढूँढने के लिए आमतौर पर एक सुपरकंप्यूटर को अविश्वसनीय रूप से महंगी गणनाएँ करने की आवश्यकता होती है, विशेष रूप से "आइगेनवैल्यू डिकंपोजिशन" (ग्रिड के भीतर की संख्याओं को छाँटने और विश्लेषण करने का एक शानदार तरीका)।

यह शोध पत्र इस पहेली को हल करने का एक नया तरीका पेश करता है जो क्वांटम कंप्यूटरों का उपयोग करता है। लेखकों ने एक विधि बनाई है जिसे वे QADMM (क्वांटम अल्टरनेटिंग डायरेक्शन मेथड ऑफ मल्टीप्लायर्स) कहते हैं।

यह यहाँ कैसे काम करता है, इसे सरल अवधारणाओं में विभाजित किया गया है:

1. समस्या: "भारी काम" की बाधा (The Heavy Lifting Bottleneck)

एक SDP को हल करना एक विशाल पुस्तकालय को व्यवस्थित करने की तरह समझने की कोशिश करें।

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

2. समाधान: एक हाइब्रिड टीम (The "Inexact" Framework)

लेखकों ने पूरी समस्या को केवल क्वांटम कंप्यूटर के सामने नहीं फेंका। इसके बजाय, उन्होंने एक हाइब्रिड टीम बनाई है जहाँ क्लासिकल और क्वांटम कंप्यूटर मिलकर काम करते हैं, लेकिन वे बीच में कुछ "लापरवाही" (गलतियों) की अनुमति देते हैं।

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

3. जादुई ट्रिक: पॉलिनोमियल प्रॉक्सी (Polynomial Proxies)

पहेली का सबसे कठिन हिस्सा यह सुनिश्चित करना है कि समाधान "पॉजिटिव" रहे (एक गणितीय नियम जिसे सेमीडेफिनेट बाधा कहा जाता है)।

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

4. परिणाम: गति और दक्षता

यह शोध पत्र सिद्ध करता है कि यह नया तरीका काम करता है और महत्वपूर्ण लाभ प्रदान करता है:

कन्वर्जेंस (अभिसरण): भले ही क्वांटम स्टेप्स "ढीले" हों, यह विधि गणितीय रूप से गारंटी देती है कि वह अंततः सर्वोत्तम समाधान ( $\epsilon$ -optimal solution) खोज लेगी।
स्केलिंग: जब समस्या बहुत बड़ी हो जाती है (बड़ा $n$ $n$ ), तो क्वांटम विधि क्लासिकल तरीकों की तुलना में बहुत बेहतर तरीके से स्केल करती है।
- क्लासिकल ADMM: जैसे-जैसे पुस्तकालय बड़ा होता है, छाँटने का समय बहुत तेज़ी से बढ़ता है (जैसे $n^6$ )।
- QADMM: समय बहुत धीमी गति से बढ़ता है (लगभग $n^2$ ), जिससे यह विशाल समस्याओं के लिए बहुत अधिक उपयुक्त हो जाता है।
तुलना: यह कुछ प्रकार की बड़े पैमाने की समस्याओं के लिए मौजूदा क्वांटम तरीकों (जैसे क्वांटम इंटीरियर पॉइंट मेथड्स) की तुलना में तेज़ है, विशेष रूप से उन मामलों में जहाँ समाधान का कुल वजन (फ्रोबेनिअस नॉर्म) बहुत अधिक नहीं होता है।

5. पेच (सीमाएँ)

यह शोध पत्र अपनी सीमाओं के बारे में ईमानदार है। यह विधि वर्तमान में QRAM (क्वांटम रैंडम एक्सेस मेमोरी) नामक एक विशिष्ट प्रकार की क्वांटम मेमोरी पर निर्भर करती है।

उपमा: QRAM को एक जादुई, त्वरित-पहुँच वाली लाइब्रेरी कार्ड प्रणाली के रूप में सोचें। एल्गोरिदम मानता है कि यह प्रणाली मौजूद है और पूरी तरह से काम करती है। वास्तव में, ऐसा सिस्टम बनाना वर्तमान में बहुत कठिन और महंगा है। लेखकों ने उल्लेख किया है कि इस धारणा को कम करना भविष्य के काम का लक्ष्य है।

सारांश

यह शोध पत्र एक नया एल्गोरिदम, QADMM प्रस्तुत करता है, जो जटिल अनुकूलन समस्याओं को हल करने की गति बढ़ाने के लिए क्वांटम कंप्यूटरों का उपयोग करता है। यह इसे निम्नलिखित तरीकों से करता है:

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

लेखकों ने एक छोटे, सिम्युलेटेड उदाहरण (8 वर्टिसिस वाले ग्राफ पर एक Max-Cut समस्या) पर इसका परीक्षण किया और दिखाया कि उनका "धुंधला" (fuzzy) क्वांटम तरीका पूर्ण, धीमे क्लासिकल तरीके के प्रदर्शन का बारीकी से अनुसरण करता है।

यहाँ "Quantum Alternating Direction Method of Multipliers for Semidefinite Programming" शोध पत्र का विस्तृत तकनीकी सारांश दिया गया है।

समस्या विवरण (Problem Statement)

सेमीडेफिनेट प्रोग्रामिंग (SDP) एक मौलिक उत्तोलक (convex) अनुकूलन समस्या है जिसके अनुप्रयोग नियंत्रण सिद्धांत (control theory), सांख्यिकी, मशीन लर्निंग, वित्त और क्वांटम सूचना में हैं। हालाँकि, बड़े पैमाने पर SDP उदाहरणों को हल करना शास्त्रीय एल्गोरिदम के लिए चुनौतीपूर्ण बना हुआ है। मुख्य बाधाएँ प्रत्येक पुनरावृत्ति (iteration) में रैखिक प्रणालियों (linear systems) को हल करने और आइगेनवैल्यू अपघटन (eigenvalue decompositions) (विशेष रूप से, पॉजिटिव सेमीडेफिनेट कॉन पर प्रोजेक्शन) करने की उच्च लागत हैं। जबकि क्वांटम एल्गोरिदम जैसे कि क्वांटम मैट्रिक्स मल्टीप्लिकेटिव वेट्स अपडेट्स (QMWU) और क्वांटम इंटीरियर पॉइंट मेथड्स (QIPM) इन समस्याओं को संबोधित करने के लिए प्रस्तावित किए गए हैं, वे अक्सर आयाम निर्भरता (dimension dependence), स्पर्सिटी पैरामीटर या सटीकता आवश्यकताओं के मामले में समझौतों (trade-offs) का सामना करते हैं।

कार्यप्रणाली (Methodology)

लेखक क्वांटम अल्टरनेटिंग डायरेक्शन मेथड ऑफ मल्टीप्लायर्स (QADMM) का प्रस्ताव करते हैं, जो एक हाइब्रिड क्वांटम-शास्त्रीय एल्गोरिदम है। इसे SDP को हल करने के लिए डिज़ाइन किया गया है ताकि सबसे महंगी उप-प्रक्रियाओं (subroutines) के लिए क्वांटम स्पीड-अप का लाभ उठाया जा सके और शास्त्रीय प्रथम-क्रम विधियों की मजबूती को बनाए रखा जा सके।

1. इनएक्सैक्ट (Inexact) ADMM ढांचा:
इस दृष्टिकोण का मूल एक इनएक्सैक्ट ADMM ढांचा है जो विशेष रूप से SDP के लिए तैयार किया गया है। मानक ADMM के विपरीत, यह ढांचा क्वांटम उप-प्रक्रियाओं द्वारा पेश की गई त्रुटियों को स्पष्ट रूप से सहन करता है।

डुअल वेरिएबल अपडेट: डुअल वेरिएबल $y$ के लिए अपडेट में एक रैखिक प्रणाली $(AA^*)y = \dots$ को हल करना शामिल है। क्वांटम सेटिंग में, इसे क्वांटम लीनियर सॉल्वर (QLS) का उपयोग करके हल किया जाता है।
प्राइमल वेरिएबल अपडेट: प्राइमल वेरिएबल्स $S$ और $X$ के लिए अपडेट में पॉजिटिव सेमीडेफिनेट (PSD) कॉन पर प्रोजेक्शन शामिल है। शास्त्रीय रूप से, इसके लिए आइगेनवैल्यू अपघटन की आवश्यकता होती है। QADMM इस प्रक्रिया को एक पॉलीनोमियल प्रॉक्सिमल ऑपरेटर से बदल देता है।
त्रुटि सहनशीलता (Error Tolerance): यह ढांचा ब्लॉक-एनकोडिंग सन्निकटन (approximations), क्वांटम सिंगुलर वैल्यू ट्रांसफॉर्मेशन (QSVT), और क्वांटम स्टेट टोमोग्राफी से होने वाली अशुद्धियों को ध्यान में रखने के लिए त्रुटि पदों ( $\Delta \tilde{y}, \Delta \tilde{S}, \Delta \tilde{X}$ , आदि) को पेश करता है। लेखक सिद्ध करते हैं कि इस इनएक्सैक्ट योजना के औसत इटरिट्स (averaged iterates) अभी भी एक $\epsilon$ -इष्टतम समाधान की ओर अभिसरित (converge) होते हैं।

2. पॉलीनोमियल प्रॉक्सिमल ऑपरेटर और QSVT:
प्रोजेक्शन चरण में आइगेनवैल्यू अपघटन की भारी लागत से बचने के लिए, लेखक एक पॉलीनोमियल फलन $g(x)$ डिज़ाइन करते हैं जो प्रोजेक्शन ऑपरेटर $\text{Proj}_{S_+}(x) = \max(0, x)$ का सन्निकटन (approximate) करता है।

सन्निकटन सिद्धांत (approximation theory) का उपयोग करते हुए, वे एक मॉनोटोन बढ़ते हुए पॉलीनोमियल $g$ का निर्माण करते हैं जिसका डिग्री $d = O(1/\epsilon)$ है, जो त्रुटि $\epsilon$ के भीतर ReLU फंक्शन का सन्निकटन करता है।
इस पॉलीनोमियल को ब्लॉक-एनकोडिंग मॉडल के तहत क्वांटम सिंगुलर वैल्यू ट्रांसफॉर्मेशन (QSVT) का उपयोग करके क्वांटम कंप्यूटर पर लागू किया जाता है।
एक "आभासी" (virtual) बैरियर फंक्शन $h(S)$ का निर्माण किया जाता है ताकि इसका प्रॉक्सिमल ऑपरेटर इस पॉलीनोमियल ट्रांसफॉर्मेशन के अनुरूप हो, जिससे अभिसरण विश्लेषण (convergence analysis) के लिए आवश्यक वेरिएशनल संरचना सुनिश्चित होती है।

3. एल्गोरिदम प्रवाह (Algorithmic Flow):
एल्गोरिदम पुनरावृत्ति (iteratively) में आगे बढ़ता है:

$y$ -अपडेट: लीनियर मैप को क्लासिकली कंप्यूट करें, एक क्वांटम अवस्था तैयार करें, और QLS का उपयोग करके लीनियर सिस्टम को हल करें।
$V$ -अपडेट: मध्यवर्ती वेरिएबल $V = C - A^*(y) - \gamma X$ को कंप्यूट करने के लिए लीनियर कॉम्बिनेशन ऑफ यूनिटरीज (LCU) का उपयोग करें।
$S$ -अपडेट: $V$ पर पॉलीनोमियल स्पेक्ट्रल ट्रांसफॉर्मेशन (जो PSD प्रोजेक्शन का सन्निकटन करता है) को QSVT का उपयोग करके लागू करें, और फिर मैट्रिक्स को पुनर्गठित करने के लिए टोमोग्राफी का उपयोग करें।
$X$ -अपडेट: $S$ -अपडेट के समान, डुअल वेरिएबल $X$ को अपडेट करने के लिए पॉलीनोमियल ट्रांसफॉर्मेशन लागू करें।
क्लासिकल पोस्ट-प्रोसेसिंग: व्यवहार्यता (feasibility) सुनिश्चित करने के लिए पुनर्गठित मैट्रिसेस को बाउंडेड सेट्स (फ्रोबेनियस नॉर्म बाधाएं) पर प्रोजेक्ट किया जाता है।

मुख्य योगदान (Key Contributions)

मजबूत इनएक्सैक्ट ADMM ढांचा: यह शोध पत्र शास्त्रीय ADMM अभिसरण सिद्धांत और व्यावहारिक क्वांटम गणना के बीच एक सैद्धांतिक सेतु स्थापित करता है। यह सिद्ध करता है कि औसत इटरिट $\epsilon$ -इष्टतम समाधान की ओर $O(1/\epsilon)$ की दर से अभिसरित होता है, भले ही सबप्रॉब्लम सॉल्व और डुअल अपडेट में क्वांटम शोर और सन्निकटन सीमाओं द्वारा सीमित त्रुटियां हों।
SDP के लिए पॉलीनोमियल प्रॉक्सिमल मैपिंग: लेखक ADMM में आइगेनवैल्यू अपघटन को पॉलीनोमियल आइगेनवैल्यू ट्रांसफॉर्मेशन के साथ बदलने के लिए एक नया तरीका पेश करते हैं। यह PSD कॉन बाधाओं को कुशलतापूर्वक संभालने के लिए QSVT का उपयोग करने की अनुमति देता है, जिससे $O(n^3)$ या $O(n^4)$ की लागत से बचा जा सकता है।
जटिलता विश्लेषण और तुलना: शोध पत्र एक कठोर जटिलता विश्लेषण प्रदान करता है जो दिखाता है कि QADMM, शास्त्रीय ADMM और मौजूदा क्वांटम सॉल्वर (QMWU और QIPM) की तुलना में आयाम $n$ के संबंध में अनुकूल स्केलिंग प्राप्त करता है।

परिणाम और जटिलता (Results and Complexity)

लेखक ऑब्जेक्टिव वैल्यू और व्यवहार्यता अवशेष (feasibility residual) में एक पूर्ण सटीकता $\epsilon_{abs}$ प्राप्त करने के लिए आवश्यक कुल कम्प्यूटेशनल जटिलता का व्युत्पन्न (derive) करते हैं।

पुनरावृत्ति जटिलता (Iteration Complexity): एल्गोरिदम को $K = O\left(\frac{R_X^2 + R_S^2}{\epsilon_{abs}}\right)$ पुनरावृत्तियों की आवश्यकता होती है, जहाँ $R_X$ और $R_S$ इष्टतम प्राइमल और डुअल समाधानों के फ्रोबेनियस नॉर्म के ऊपरी बाउंड हैं।
कुल जटिलता (Total Complexity):
- शास्त्रीय संचालन (Classical Operations): $O\left((s_A + n^2)\frac{R_X^2 + R_S^2}{\epsilon_{abs}}\right)$ , जहाँ $s_A$ बाधा मैट्रिसेस में गैर-शून्य प्रविष्टियों की संख्या है।
- क्वांटम गेट जटिलता (Quantum Gate Complexity): $\tilde{O}\left( \left[ m\kappa_A^2(1+R_y)^2 + n^2(\kappa_A^2(1+R_y) + R_X) \right] \frac{(R_X + R_S)^3}{\epsilon_{abs}^3} \right)$ ।
- यहाँ, $\kappa_A$ का $AA^*$ का कंडीशन नंबर है, और $R_y$ डुअल वेरिएबल नॉर्म का बाउंड है।

तुलना:

शास्त्रीय ADMM के विरुद्ध: QADMM आयाम $n$ के संबंध में बेहतर निर्भरता प्रदान करता है (प्रत्येक पुनरावृत्ति में शास्त्रीय आइगेनवैल्यू अपघटन और मैट्रिक्स गुणन से जुड़े $O(n^6)$ या $O(n^4)$ कारकों से बचता है)।
QIPM के विरुद्ध: QADMM न्यूटन सिस्टम ( $\kappa_{newt}$ ) पर उच्च कंडीशन नंबर निर्भरता से बचता है और सटीकता निर्भरता में एक अलग ट्रेड-ऑफ प्रदान करता है।
QMWU के विरुद्ध: जबकि QADMM का आयाम निर्भरता QMWU के समान है, यह $\epsilon_{abs}$ पैरामीटर पर निम्न-क्रम (lower-order) की निर्भरता प्राप्त करता है (कुछ व्यवस्थाओं में क्यूबिक बनाम उच्च घात) और यह विशेष रूप से फायदेमंद है जब समाधान का फ्रोबेनियस नॉर्म $\|X^*\|_F$ उसके ट्रेस $\text{Tr}(X^*)$ की तुलना में बहुत छोटा होता है (जैसे, डायगोनल SDP एम्बेडिंग में)।

महत्व और दावे (Significance and Claims)

शोध पत्र का दावा है कि QADMM बड़े पैमाने के SDP को हल करने के लिए आयाम के संबंध में अनुकूल स्केलिंग प्रदान करता है, जो इसे उन समस्याओं के लिए एक आशाजनक उम्मीदवार बनाता है जहाँ शास्त्रीय सॉल्वर आइगेनवैल्यू अपघटन की लागत के कारण संघर्ष करते हैं।

लेखक इस बात पर जोर देते हैं कि उनका दृष्टिकोण:

क्वांटम स्पीड-अप को एकीकृत करता है: यह ADM एल्गोरिदम के सबसे गणना-गहन भागों को तेज करने के लिए सफलतापूर्वक QSVT और QLS का लाभ उठाता है।
अभिसरण गारंटी बनाए रखता है: एक इनएक्सैक्ट ढांचे को विकसित करके, वे सुनिश्चित करते हैं कि क्वांटम त्रुटियां इष्टतम समाधान की ओर अभिसरण को नहीं रोकती हैं।
विशिष्ट धारणाओं पर निर्भर है: एल्गोरिदम डेटा एक्सेस के लिए पॉलीनोमियल-साइज QRAM की उपलब्धता और इनपुट मैट्रिसेस के ब्लॉक-एनकोडिंग की धारणा पर आधारित है। लेखक इसे एक मजबूत धारणा के रूप में स्वीकार करते हैं और नोट करते हैं कि भविष्य का कार्य इस आवश्यकता को कम करने पर केंद्रित होगा।

शोध पत्र निष्कर्ष निकालता है कि हालांकि एल्गोरिदम QRAM धारणा द्वारा सीमित है, यह बड़े पैमाने के उत्तोलक (convex optimization) को लागू करने में एक महत्वपूर्ण कदम है, जो विशेष रूप से आयाम और सटीकता की विशिष्ट व्यवस्थाओं में शास्त्रीय प्रथम-क्रम विधियों और अन्य क्वांटम SDP सॉल्वर दोनों के लिए एक व्यवहार्य विकल्प प्रदान करता है।