🔬 physics

Local-Minima-Preserving Continuous Relaxation of Ising Problems

यह शोध पत्र सामान्यीकृत आइसिंग समस्या (generalized Ising problem) के लिए एक बहुपद विश्राम (polynomial relaxation) प्रस्तुत करता है जो इसके स्थानीय निम्नीकृतों (local minima) और मूल असतत समस्या के वन-फ्लिप स्थानीय निम्नीकृतों के बीच एक एक-से-एक पत्राचार को संरक्षित करता है, जिससे MAX-CUT और नंबर पार्टीशनिंग जैसे चुनौतीपूर्ण संयोजन संबंधी बेंचमार्क को हल करने के लिए ADAM जैसे स्केलेबल ग्रेडिएंट-आधारित ऑप्टिमाइज़र का उपयोग करना सक्षम होता है।

मूल लेखक: Debraj Banerjee, Santanu Mahapatra, Kunal N. Chaudhury

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

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

CC BY 4.0

मूल लेखक: Debraj Banerjee, Santanu Mahapatra, Kunal N. Chaudhury

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

कल्पना कीजिए कि आप एक विशाल, जटिल पहेली को हल करने की कोशिश कर रहे हैं जहाँ हर टुकड़ा केवल दो अवस्थाओं में से एक में ही हो सकता है: ऊपर (Up) या नीचे (Down)। यह "आइसिंग समस्या" (Ising Problem) है, जो कंप्यूटर विज्ञान की कुछ सबसे कठिन पहेलियों को हल करने के लिए उपयोग किया जाने वाला एक गणितीय मॉडल है, जैसे कि लोगों के एक समूह को दो टीमों में इस तरह विभाजित करना कि उनके बीच बहस सबसे कम हो, या संख्याओं के एक ढेर को दो समान ढेरों में विभाजित करना।

समस्या यह है कि इन टुकड़ों को पलटने के इतने सारे तरीके हैं कि हर एक संभावना की जांच करना असंभव है, यहाँ तक कि सबसे तेज़ सुपरकंप्यूटर के लिए भी।

पुराना तरीका: अनुमान लगाना और जांचना

परंपरागत रूप से, कंप्यूटर इस पहेली को हल करने के लिए "चलने" (walking) का प्रयास करते हैं। वे एक बार में एक टुकड़ा पलटते हैं ताकि देख सकें कि क्या स्कोर बेहतर होता है।

जाल (The Trap): कल्पना कीजिए कि आप एक धुंधले पहाड़ी क्षेत्र में हाइकिंग कर रहे हैं। आप नीचे की ओर चलते रहते हैं जब तक कि आप एक छोटी घाटी में नहीं पहुँच जाते। आप सोचते हैं, "मैं तल पर हूँ!" लेकिन हो सकता है कि आप एक छोटी घाटी (एक लोकल मिनिमम) में फंसे हों, जबकि अगली पहाड़ी के ठीक पार एक बहुत गहरी, बेहतर घाटी (ग्लोबल मिनिमम) मौजूद हो।
सीमा (The Limitation): क्योंकि पहेली "ऊपर/नीचे" के डिस्क्रीट (discrete) स्विचों से बनी है, इसलिए मानक सुचारू उपकरण (जैसे कि AI को प्रशिक्षित करने के लिए उपयोग किए जाने वाले उपकरण) आसानी से इस ऊबड़-खाबड़ इलाके में नेविगेट नहीं कर सकते। वे फंस जाते हैं या बेकार में इधर-उधर उछलते रहते हैं।

नया समाधान: MiP-CRIM

इस शोध पत्र के लेखकों ने, देबराज बनर्जी और सहयोगियों ने, एक नई विधि विकसित की है जिसे MiP-CRIM कहा जाता है। इसे एक चतुर ट्रिक की तरह समझें जो एक ऊबड़-खाबड़, ऊबड़-खाबड़ पहाड़ी क्षेत्र को एक चिकने, बहते हुए परिदृश्य में बदल देती है, बिना सबसे अच्छी घाटियों के स्थान को खोए।

उन्होंने इसे सरल उपमाओं का उपयोग करके यहाँ समझाया है:

1. "स्मूदी" ट्रिक (कंटीन्यूअस रिलैक्सेशन)

पहेली के टुकड़ों को सख्ती से "ऊपर" या "नीचे" होने के बजाय, उन्होंने उन्हें बीच में कहीं भी रहने की अनुमति दी।

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

2. "चुंबकीय जाल" (द अट्रैक्टर)

एक बड़ा डर था: यदि हम टुकड़ों को कहीं भी तैरने देते हैं, तो वे स्लाइड के बीच में (एक नकली घाटी) फंस सकते हैं जो वास्तविक "ऊपर" या "नीचे" के समाधान के अनुरूप नहीं है।

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

3. "एक-से-एक" गारंटी (The One-to-One Guarantee)

उनके शोध पत्र का सबसे महत्वपूर्ण हिस्सा एक गणितीय प्रमाण (लैंडस्केप इक्विवेलेंस थ्योरम) है।

उन्होंने सिद्ध किया कि मूल कठिन पहेली में प्रत्येक अच्छे "ऊपर/नीचे" समाधान का उनकी चिकनी, चुंबकीय स्लाइड में एक मिलान वाला स्थान होता है।
इसके विपरीत, प्रत्येक स्थान जहाँ गेंद उनकी चिकनी स्लाइड पर रुकती है, वह एक वैध "ऊपर/नीचे" समाधान के अनुरूप होता है।
यह क्यों मायने रखता है: आपको यह अनुमान लगाने की आवश्यकता नहीं है कि आपका चिकना समाधान वास्तविक है या नहीं। यदि गेंद रुकती है, तो आप जानते हैं कि आपने मूल पहेली का एक वैध स्थानीय सर्वश्रेष्ठ समाधान पा लिया है।

व्यवहार में यह कैसे काम करता है

लेखकों ने एक कंप्यूटर प्रोग्राम बनाया है जो इस चिकनी, चुंबकीय स्लाइड का उपयोग करता है।

गति (Speed): क्योंकि परिदृश्य चिकना है, वे शक्तिशाली, तेज़ उपकरणों (जैसे कि ADAM, जो AI में उपयोग किया जाने वाला एक मानक ऑप्टिमाइज़र है) का उपयोग करके घाटियों के निचले हिस्से को अविश्वसनीय रूप से तेज़ी से खोज सकते हैं।
स्केलेबिलिटी (Scalability): जबकि पुराने तरीके (जैसे सटीक सॉल्वर) बहुत बड़े होने पर (500 टुकड़ों से अधिक) फंस जाते हैं, MiP-CRIM आसानी से स्केल होता है। इसने 1,000 से 5,000 टुकड़ों वाली पहेलियों को सेकंडों में हल किया, जहाँ अन्य तरीकों को घंटों लग गए या वे पूरी तरह विफल हो गए।
सटीकता (Accuracy): उन्होंने तीन प्रसिद्ध कठिन समस्याओं पर इसका परीक्षण किया:
1. स्पिन-ग्लास मॉडल (Spin-Glass Models): चुंबकों का एक भौतिक मॉडल।
2. MAX-CUT: समूहों के बीच कनेक्शन को अधिकतम करने के लिए एक नेटवर्क को विभाजित करना।
3. नंबर पार्टीशनिंग (Number Partitioning): संख्याओं को दो समान योगों में विभाजित करना।
  इन सभी मामलों में, उनकी विधि ने उन समाधानों को पाया जो वर्तमान में उपलब्ध सर्वोत्तम विशिष्ट उपकरणों के बराबर या उनसे बेहतर थे, और उन्होंने यह काम बहुत तेज़ी से किया।

निष्कर्ष (The Bottom Line)

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

तकनीकी सारांश: MiP-CRIM

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

यह शोध पत्र सामान्यीकृत आइसिंग समस्या (Generalized Ising Problem) को संबोधित करता है, जो एक व्यापक स्पेक्ट्रम वाली NP-hard कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन समस्याओं को समाहित करती है, जिसमें मैक्स-कट (MAX-CUT), नंबर पार्टीशनिंग (NPP), और मैक्सिमम इंडिपेंडेंट सेट शामिल हैं। मुख्य चुनौती एक स्पिन वेक्टर $s \in \{-1, 1\}^n$ खोजने की है जो आइसिंग ऊर्जा $E(s) = -\frac{1}{2}s^\top Js - h^\top s$ को न्यूनतम करता हो।

मौजूदा दृष्टिकोण एक ट्रेड-ऑफ का सामना करते हैं:

सटीक सॉल्वर (Exact solvers): (जैसे ब्रांच-एंड-बाउंड) इनका पैमाना (scaling) खराब है और ये बड़े उदाहरणों के लिए अव्यवहारिक हो जाते हैं।
क्लासिकल ह्यूरिस्टिक्स (Classical heuristics): (जैसे सिम्युलेटेड एनीलिंग) ये डिस्क्रीट स्पेस में स्टोकेस्टिक रूप से नेविगेट करते हैं लेकिन अक्सर धीमी अभिसरण (convergence) या खराब स्थानीय इष्टतम (local optima) से जूझते हैं।
सतत विश्राम (Continuous relaxations): (जैसे SDP) ये कुशलतापूर्वक स्केल करते हैं लेकिन अक्सर "स्पूरियस" (spurious) स्थानीय मिनिमा पेश करते हैं जो वैध डिस्क्रीट समाधानों के अनुरूप नहीं होते, और इनके राउंडेड समाधान की गुणवत्ता पर कोई कठोर गारंटी नहीं होती।
फिजिक्स-प्रेरित और न्यूरल सॉल्वर: (जैसे कोहेरेंट आइसिंग मशीन, GNNs) ये आशाजनक दिखते हैं लेकिन अक्सर जटिल डायनेमिकल सिस्टम, ट्यून किए गए एनीलिंग शेड्यूल्स, या डेटा-संचालित प्रायर्स (priors) पर निर्भर करते हैं जो सामान्यीकरण (generalize) करने में सक्षम नहीं हो सकते या जिनमें कठोर इष्टिमलिटी गारंटी का अभाव होता है।

कार्यप्रणाली: MiP-CRIM

लेखक MiP-CRIM (Minima-Preserving Continuous Relaxation of Ising Model) प्रस्तावित करते हैं, जो एक ढांचा है जो डिस्क्रीट आइसिंग समस्या को एक सुचारू, बाधित निरंतर अनुकूलन (constrained continuous optimization) समस्या में बदल देता है, जबकि स्थानीय मिनिमा के परिदृश्य (landscape) को कठोरता से संरक्षित करता है।

1. निरंतर पुनर्गठन (Continuous Reformulation)

डिस्क्रीट खोज स्थान $H_n = \{-1, 1\}^n$ को एक स्केल्ड हाइपरक्यूब $\lambda Q_n = [-\lambda, \lambda]^n$ में शिथिल (relax) किया जाता है। लेखक मूल ऊर्जा फलन $E(x)$ में एक पॉलिनोमियल रेगुलराइज़र (अट्रैक्टर) $A(x)$ पेश करते हैं। नया ऑब्जेक्टिव, या हैमिल्टनियन, है:
$H(x) = E(x) + A(x)$
लक्ष्य $x \in \lambda Q_n$ पर $H(x)$ को न्यूनतम करना है।

2. अट्रैक्टर फंक्शन्स (Attractor Functions)

यह सुनिश्चित करने के लिए कि निरंतर मिनिमा डिस्क्रीट कोनों के साथ संरेखित हों, लेखक सक्षम अट्रैक्टर्स (admissible attractors) $f_\theta$ की एक श्रेणी को परिभाषित करते हैं। इन फलनों को विशिष्ट शर्तों को पूरा करना चाहिए:

समरूपता (Symmetry): $f_\theta(x) = f_\theta(-x)$ ।
कन्केविटी (Concavity): $|x| < \lambda$ के लिए $f''_\theta(x) < 0$ ।
बाउंड्री अट्रैक्शन (Boundary Attraction): $f'_\theta(\lambda) < 0$ ।
मजबूती (Robustness): $f'_\theta(\lambda) + \lambda\gamma > 0$ , जहाँ $\gamma$ डिस्क्रीट स्टेशनैरिटी के मार्जिन से संबंधित है।

शोध पत्र तीन भौतिकी-प्रेरित विकल्पों का मूल्यांकन करता है:

$f_{\theta_1}$ : क्वाड्रेटिक (सेल्फ-कपलिंग)।
$f_{\theta_2}$ : क्वार्टिक पॉलिनोम (नॉनलीन पैरामेट्रिक ऑसिलेटर्स से संबंधित)।
$f_{\theta_3}$ : $\tanh^{-1}$ का इंटीग्रल (मीन-फील्ड एप्रोक्सिमेशन से संबंधित)।

अनुभवजन्य परिणाम संकेत देते हैं कि क्वार्टिक अट्रैक्टर ( $f_{\theta_2}$ ) का प्रदर्शन सबसे अच्छा है, जो एक "डबल-वेल" संरचना बनाता है जो स्वाभाविक रूप से स्थानीय मिनिमा को हाइपरक्यूब कोनों $\{-\lambda, \lambda\}^n$ की ओर झुकाता है।

3. लैंडस्केप इक्विवेलेंस थ्योरम (Landscape Equivalence Theorem)

इस कार्य का सैद्धांतिक केंद्र लैंडस्केप इक्वैलेंस थ्योरम (थ्योरम 3.13) है। यह सिद्ध करता है कि यदि अट्रैक्टर सक्षम है, तो निम्नलिखित के बीच एक-से-एक पत्राचार (one-to-one correspondence) मौजूद है:

मूल डिस्क्रीट आइसिंग समस्या के वन-फ्लिप स्थानीय मिनिमा (जहाँ किसी भी एकल स्पिन को पलटने से ऊर्जा बढ़ जाती है)।
हाइपरक्यूब पर मूल हैमिल्टनियन $H(x)$ के स्थानीय मिनिमा के सेट के बीच।

यह प्रमेय गारंटी देता है कि स्मूथ फलन $H(x)$ के स्थानीय न्यूनतम को खोजना, मूल कॉम्बिनेटोरियल समस्या के वन-फ्लिप स्थानीय न्यूनतम को खोजने के बराबर है।

4. अनुकूलन एल्गोरिदम (Optimization Algorithm)

लेखक एक मानक फर्स्ट-ऑर्डर ऑप्टिमाइज़र, विशेष रूप से ADAM का उपयोग करके एक स्केलेबल सॉल्वर लागू करते हैं। एल्गोरिदम सैडल पॉइंट्स (saddle points) से बचने के लिए गॉसियन पर्सर्बेशन के साथ "बेसिन-हॉपिंग" रणनीति का उपयोग करता है (जो अट्रैक्टर की कन्केविटी के कारण हाइपरक्यूब के इंटीरियर में अस्थिर सिद्ध होते हैं)। प्रक्रिया में शामिल है:

$x$ को रैंडमली इनिशियलाइज़ करना।
बॉक्स कंस्ट्रेंट्स पर प्रोजेक्शन के साथ $H(x)$ पर ग्रेडिएंट डिसेंट का उपयोग करके $x$ को पुनरावृत्ति से अपडेट करना।
अंतिम निरंतर वेक्टर को $s = \text{sign}(x)$ के माध्यम से डिस्क्रीट स्पिन वेक्टर में मैप करना।
वन-फ्लिप लोकल ऑप्टिमलिटी स्थिति का सत्यापन करना।

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

अट्रैक्टर-आधारित रिलैक्सेशन: डिस्क्रीट हाइपरक्यूब कोनों के लिए अट्रैक्टर के रूप में कार्य करने वाले पॉलिनोमियल रेगुलराइज़र के एक परिवार का परिचय, जो एक बाधित निरंतर फॉर्मूलेशन को सक्षम बनाता है।
कठोर लैंडस्केप इक्वैलेंस: एक प्रमाण जो स्थापित करता है कि निरंतर रिलैक्सेशन के स्थानीय मिनिमा ठीक वही हैं जो डिस्क्रीट आइसिंग समस्या के वन-फ्लिप स्थानीय मिनिमा हैं, जिससे अन्य रिलैक्सेशन में पाए जाने वाले स्पूरियस मिनिमा की समस्या समाप्त हो जाती है।
स्केलेबल सॉल्वर: GPU-एक्सेलेरेटेड ग्रेडिएंट-आधारित ऑप्टिमाइज़ेशन (ADAM) का उपयोग करके बड़े पैमाने के उदाहरणों को कुशलतापूर्वक हल करने के लिए एक व्यावहारिक एल्गोरिदम (MiP-CRIM) का विकास।

प्रयोगात्मक परिणाम (Experimental Results)

लेखकों ने तीन बेंचमार्क क्लास पर MiP-CRIM का मूल्यांकन किया:

स्पिन-ग्लास मॉडल्स (Sherrington-Kirkpatrick): 1000-स्पिन उदाहरणों पर, MiP-CRIM ने फ्री एनर्जी मशीन के बाद दूसरा सबसे अच्छा ऊर्जा स्तर और एक परफेक्ट सिंक्रोनाइज़ेशन स्कोर (1.0) प्राप्त किया, जो क्लासिकल एनीलिंग और GW-SDP से काफी बेहतर प्रदर्शन करता है। इसने लगातार वैध वन-फ्लिप स्थानीय मिनिमा खोजे।
MAX-CUT: डेंस और स्पार्स एर्दोस-रेनी ग्राफ और मानक G-सेट बेंचमार्क (5000 नोड्स तक) पर, MiP-CRIM ने सर्वोत्तम ज्ञात परिणामों के 1% के भीतर समाधान खोजे। इसने कई उदाहरणों (जैसे G14, G50, G55) पर D-Wave और विशिष्ट ह्यूरिस्टिक्स को पछाड़ दिया और K2000 ग्राफ पर सर्वश्रेष्ठ कट वैल्यू प्राप्त की।
नंबर पार्टीशनिंग प्रॉब्लम (NPP): 1000-नंबर उदाहरणों पर, MiP-CRIM ने सभी परीक्षण किए गए ह्यूरिस्टिक्स के बीच सबसे कम डिस्क्रीमिनेट प्राप्त किया, जो NPP की उच्च-परिशुद्धता संवेदनशीलता के विरुद्ध मजबूती प्रदर्शित करता है।

स्केलेबिलिटी: सटीक सॉल्वर्स (Gurobi, CP-SAT) के विपरीत जो $n=500$ के बाद विफल हो जाते हैं, MiP-CRIM लगभग स्थिर रनटाइम स्केलिंग प्रदर्शित करता है, जो GW-SDP और D-Wave की तुलना में कई गुना तेजी से बड़े उदाहरणों को हल करता है।

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

लेखक दावा करते हैं कि MiP-CRIM ग्रेडिएंट-आधारित अनुकूलन की स्केलेबिलिटी के साथ समाधान की गुणवत्ता पर कठोर सैद्धांतिक गारंटी को जोड़कर विविध NP-hard समस्याओं को हल करने के लिए एक एकीकृत और व्यावहारिक दृष्टिकोण प्रदान करता है।

सैद्धांतिक गारंटी: कई निरंतर रिलैक्सेशन के विपरीत जिन्हें पोस्ट-हॉक राउंडिंग की आवश्यकता होती है जिसमें कोई इष्टिमलिटी गारंटी नहीं होती, MiP-CRIM यह सुनिश्चित करता है कि निरंतर डोमेन में पाया गया कोई भी स्थानीय न्यूनतम डिस्क्रीट डोमेन में एक वैध वन-फ्लिप स्थानीय न्यूनतम के अनुरूप होता है।
व्यावहारिक दक्षता: यह विधि आधुनिक GPU हार्डवेयर और मानक ऑप्टिमाइज़र (ADAM) का लाभ उठाती है, जिससे यह विशेष हार्डवेयर (क्वांटम एनेलर) या जटिल डायनेमिकल सिस्टम की तुलना में अत्यधिक स्केलेबल और ऊर्जा-कुशल बन जाती है।
मजबूती (Robustness): यह दृष्टिकोण दिखाया गया है कि प्रति समस्या क्लास न्यूनतम पैरामीटर ट्यूनिंग के साथ विभिन्न समस्या वर्गों (स्पार्स ग्राफ से लेकर संख्यात्मक रूप से कठिन पार्टीशनिंग समस्याओं तक) में मजबूत है।

लेखक MiP-CRIM को लॉजिस्टिक्स, सर्किट डिजाइन और ऑपरेशंस रिसर्च जैसे डोमेन में बड़े पैमाने पर समस्या समाधान को तेज करने की दिशा में एक महत्वपूर्ण कदम के रूप में प्रस्तुत करते हैं, जो विशेष हार्डवेयर प्लेटफॉर्मों के लिए एक ऊर्जा-कुशल विकल्प प्रदान करता है।