⚛️ quantum physics

Adaptive Qubit Freezing Enables Robust Graph Partitioning for Divide-and-Conquer QAOA

यह शोध पत्र FrozenLGP को प्रस्तुत करता है, जो एक अनुकूलन योग्य ढांचा (adaptive framework) है जो बाधा डालने वाले शीर्षों (obstructing vertices) को शास्त्रीय रूप से फ्रीज करने और उनके ऊर्जा योगदान को संरक्षित करने के माध्यम से डिवाइड-एंड-कॉन्कर QAOA के लिए सुदृढ़ ग्राफ विभाजन सक्षम बनाता है, जिससे उन सघन ग्राफों पर 100% अपघटन कवरेज प्राप्त होता है जहाँ पारंपरिक विधियाँ विफल हो जाती हैं, जबकि साथ ही सन्निकटन गुणवत्ता (approximation quality) को बनाए रखता है और शोर रोधकता (noise robustness) में सुधार करता है।

मूल लेखक: Sokea Sang, Leanghok Hour, Dongmin Kim, Youngsun Han

प्रकाशित 2026-07-10

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

CC BY 4.0

मूल लेखक: Sokea Sang, Leanghok Hour, Dongmin Kim, Youngsun Han

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

कल्पना कीजिए कि आपके पास एक विशाल, बिखरा हुआ पहेली (puzzle) है जो आपकी छोटी मेज पर फिट होने के लिए बहुत बड़ा है। आप इसे हल करना चाहते हैं, लेकिन आप एक बार में केवल कुछ ही टुकड़ों पर काम कर सकते हैं। यह आज के क्वांटम कंप्यूटरों का दैनिक संघर्ष है। वे शक्तिशाली हैं, लेकिन वे "शोरभरी" (noisy) भी हैं और उनके पास "क्यूबिट्स" (पहेली के टुकड़ों) की संख्या सीमित है। बड़ी समस्याओं को हल करने के लिए, वैज्ञानिक एक तकनीक का उपयोग करते हैं जिसे "विभाजित करो और जीतो" (Divide-and-Conquer) कहा जाता है: वे उस विशाल पहेली को छोटे हिस्सों में काटते हैं, प्रत्येक हिस्से को हल करते हैं, और फिर उत्तरों को वापस जोड़ देते हैं।

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

यहाँ FrozenLGP आता है, जो एक नई विधि है जो एक चतुर, अनुकूलन योग्य पहेली मास्टर की तरह कार्य करती है। हार मानने के बजाय, FrozenLGP "क्यूबिट फ्रीजिंग" (Qubit Freezing) नामक एक तकनीक का उपयोग करता है।

जादू का तरीका: समस्याग्रस्त टुकड़ों को फ्रीज़ करना

कल्पना कीजिए कि आप एक भीड़ भरे कमरे को दो समूहों में विभाजित करने की कोशिश कर रहे हैं। आमतौर पर, आप कुछ लोगों को दरवाजे पर खड़े होने के लिए कहेंगे ताकि वे एक दीवार का काम कर सकें। लेकिन एक बहुत ही घनी भीड़ में, लोग हर जगह एक-दूसरे का हाथ पकड़े हुए हैं, इसलिए दरवाजा काम नहीं करता; कमरा एक बड़े गोले जैसा बना रहता है।

FrozenLGP का समाधान क्या है? यह सबसे अधिक परेशानी करने वाले लोगों (वे जो हर किसी के साथ हाथ पकड़े हुए हैं) को चुनता है और कहता है, "ठीक है, तुम दोनों, अभी इसी वक्त तय करो: तुम 'लेफ्ट टीम' (Left Team) में हो।" एक बार जब वे "फ्रीज़" होकर एक निश्चित स्थिति में आ जाते हैं, तो उनके द्वारा पकड़े गए संबंध उनके बगल वाले लोगों के लिए सरल निर्देशों में बदल जाते हैं। हाथ पकड़ने का वह उलझा हुआ जाल सुलझ जाता है क्योंकि वे विशिष्ट लोग अब हिल-डुल नहीं रहे हैं।

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

यह विधि क्या करती है (और क्या नहीं करती)

यह पेपर बहुत स्पष्ट है कि FrozenLGP क्या हासिल करता है। यह यह दावा नहीं करता कि यह एक जादुई छड़ी है जो हर समस्या को तुरंत या शास्त्रीय (classical) कंप्यूटरों से बेहतर हल कर देती है। वास्तव में, छोटी पहेलियों (20 टुकड़ों से कम) के लिए, शास्त्रीय कंप्यूटर अभी भी चैंपियन हैं, और लेखक स्वीकार करते हैं कि उनकी विधि वहां प्रतिस्पर्धी नहीं है।

इसके बजाय, FrozenLGP विशेष रूप से "नॉइजी इंटरमीडिएट-स्केल क्वांटम" (NISQ) युग के लिए डिज़ाइन किया गया एक मजबूत फ्रंट-एंड है। इसका मुख्य कार्य यह सुनिश्चित करना है कि "विभाजित करो और जीतो" की पाइपलाइन कभी क्रैश न हो।

गारंटी: मानक ग्राफों पर, यह पुराने तरीके की तरह ही काम करता है। सघन, उलझे हुए ग्राफों पर, जहाँ पुराना तरीका पूरी तरह विफल हो जाता (शून्य परिणाम देता), वहाँ FrozenLGP हस्तक्षेप करता है, कुछ नोड्स को फ्रीज़ करता है, और सफलतापूर्वक विभाजन करता है।
परिणाम: अपने परीक्षणों में, जबकि मानक विधि कठिन, उच्च-कनेक्टिविटी वाले ग्राफ उदाहरणों में से केवल 4.6% को ही हल कर पाई थी, FrozenLGP ने 100% डिकंपोजिशन कवरेज प्राप्त किया। इसने केवल कुछ अधिक ही हल नहीं किए; इसने सभी को सफलतापूर्वक हल किया।

हम कितने आश्वस्त हैं?

लेखक अपने आंकड़ों को लेकर आश्वस्त हैं, लेकिन वे इस बात के बीच अंतर करने में सावधानी बरतते हैं कि उन्होंने क्या सिमुलेट (simulate) किया है और उन्होंने क्या सिद्ध (prove) किया है।

सिमुलेशन: "शोर प्रतिरोधकता" (noise robustness - यह विधि त्रुटियों को कितनी अच्छी तरह संभालती है) और विशिष्ट "अनुमान अनुपात" (approximation ratios - समाधान पूर्णता के कितने करीब है) के संबंध में परिणाम शास्त्रीय कंप्यूटरों पर सिमुलेशन से आए हैं जो क्वांटम उपकरणों की नकल करते हैं। वे दिखाते हैं कि नोड्स को फ्रीज़ करके, यह विधि त्रुटि-प्रवण "एंटैंगलिंग गेट्स" (entangling gates) की आवश्यकता को कम करता है, जिससे प्रक्रिया अधिक स्थिर हो जाती है।
प्रमाण: यह गणितीय गारंटी कि यह विधि फ्रीज़ करने के लिए न्यूनतम नोड्स को खोज लेती है, "मैक्स-फ्लो" (max-flow) की अवधारणा का उपयोग करके सिद्ध की गई है (जो बाधाओं को खोजने के लिए एक मानक गणितीय उपकरण है)। उन्होंने सिद्ध किया कि यदि समाधान मौजूद है, तो उनका एल्गोरिदम उसे ढूंढ लेगा।
थ्रेशोल्ड (सीमा): उन्होंने एक तीखा "टिपिंग पॉइंट" खोजा। यदि ग्राफ एक निश्चित मात्रा (vertex connectivity $\kappa$ ) तक उलझा हुआ है, तो इसे काम करने के लिए आपको ठीक $\kappa - (k - 1)$ नोड्स को फ्रीज़ करने की आवश्यकता है, जहाँ $k$ क्वांटम कंप्यूटर की मेमोरी का आकार है। यह कोई अनुमान नहीं है; रैंडम रेगुलर ग्राफ्स पर उनके परीक्षणों में, यह नियम पूरी तरह से सही रहा, जो एक सटीक स्विच की तरह काम करता है जो समाधान को 0% से 100% सफलता में बदल देता है।

ट्रेड-ऑफ (समझौता)

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

निष्कर्ष

FrozenLGP यह दावा नहीं करता कि यह क्वांटम कंप्यूटिंग का अंतिम उत्तर है। यह शोर की समस्या को पूरी तरह से हल नहीं करता है, न ही यह छोटे कार्यों पर शास्त्रीय कंप्यूटरों को हराता है। लेकिन यह एक विशिष्ट, महत्वपूर्ण बाधा को हल करता है: यह "विभाजित करो और जीतो" की रणनीति को घने, बिखरे हुए ग्राफों पर विफल होने से रोकता है।

"फ्रीजिंग" के माध्यम से एक असंभव संरचनात्मक समस्या को एक समाधान योग्य समस्या में बदलकर, यह सुनिश्चित करता है कि क्वांटम कंप्यूटर बिना किसी रुकावट के वास्तविक दुनिया की बहुत सारी विविध समस्याओं का सामना कर सकें। यह एक ऐसे मानचित्र के बीच का अंतर है जो कहता है "रास्ता बंद है" और एक ऐसे मानचित्र के बीच जो कहता है "डायवर्जन: इस रास्ते से जाएं, और आप वहां पहुंच जाएंगे।"

तकनीकी सारांश: एडेप्टिव क्वबिट फ्रीजिंग (Adaptive Qubit Freezing) डिवाइड-एंड-कॉन्कर (Divide-and-Conquer) QAOA के लिए सुदृढ़ ग्राफ पार्टीशनिंग को सक्षम बनाता है

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

क्वांटम एप्रोक्सिमेट ऑप्टिमाइज़ेशन एल्गोरिदम (QAOA), मैक्सकट (MaxCut) जैसे कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन समस्याओं के लिए एक अग्रणी हाइब्रिड क्वांटम-क्लासिकल दृष्टिकोण है। हालाँकि, नोइज़ी इंटरमीडिएट-स्केल क्वांटम (NISQ) उपकरणों पर इसका अनुप्रयोग सीमित क्वबिट रजिस्टरों और शोर संचय (noise accumulation) द्वारा बाधित है। डिवाइड-एंड-कॉन्कर QAOA (DC-QAOA) बड़े समस्या ग्राफों को छोटे सबग्राफ में विघटित करके इस समस्या का समाधान करता है जो हार्डवेयर बजट के भीतर फिट होते हैं, उन्हें व्यक्तिगत रूप से हल करता है, और फिर एक वैश्विक समाधान का पुनर्निर्माण करता है।

मौजूदा DC-QAOA फ्रेमवर्क में महत्वपूर्ण बाधा विघटन चरण (decomposition stage) है। मानक दृष्टिकोण, जैसे कि लार्ज ग्राफ पार्टीशनिंग (LGP), एक छोटे वर्टेक्स सेपरेटर (vertex separator) की पहचान करने पर निर्भर करते हैं जो ग्राफ को दो स्वतंत्र उप-घटकों में विभाजित करने के लिए उसे हटा देता है। यह धारणा घने या अत्यधिक जुड़े हुए ग्राफों (जैसे कि घने Erdős–Rényi, उच्च अटैचमेंट वाले Barabási–Albert, या पूर्ण ग्राफ/complete graphs) पर पूरी तरह विफल हो जाती है, जहाँ नोड्स के एक छोटे सेट को हटाने से नेटवर्क विच्छेदित नहीं होता है। ऐसे मामलों में, मानक DC-QAOA पाइपलाइन पूरी तरह से विफल हो जाती है, और उप-इष्टतम (suboptimal) समाधानों के लिए भी कोई समाधान वापस नहीं करती है। मौजूदा फुल-कवरेज विकल्प या तो पुनर्निर्माण की सटीकता (reconstruction fidelity) से समझौता करते हैं या अत्यधिक क्लासिकल ओवरहेड उत्पन्न करते हैं।

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

लेखक Frozen Large Graph Partitioning (FrozenLGP) का प्रस्ताव करते हैं, जो एक एडेप्टिव डिकंपोज़िशन फ्रेमवर्क है जो पार्टीशनयोग्यता (partitionability) को एक संरचनात्मक धारणा के बजाय एक प्रवर्तनीय गुण (enforceable property) में बदल देता है। यह विधि तीन चरणों वाली पाइपलाइन के माध्यम से कार्य करती है:

चरण 1: मानक LGP

एल्गोरिदम पहले मानक वर्टेक्स-सेपरेटर पार्टीशनिंग का प्रयास करता है। यदि एक वैध सेपरेटर मौजूद है जो क्रॉसिंग एड्ज (crossing edges) के बिना ग्राफ को दो घटकों में विभाजित करता है, तो पाइपलाइन बिना किसी अतिरिक्त ओवरहेड के ठीक मानक DC-QAOA की तरह आगे बढ़ती है।

चरण 2: एडेप्टिव क्वबिट फ्रीजिंग (Adaptive Qubit Freezing)

जब मानक पार्टीशनिंग विफल हो जाती है (अर्थात, आकार $\le k-1$ का कोई सेपरेटर मौजूद नहीं है), तब FrozenLGP एक एडेप्टिव फ्रीजिंग तंत्र को सक्रिय करता है:

मिनिमम वर्टेक्स कट (MVC) गणना: एक उम्मीदवार सेपरेटर $S$ के लिए, एल्गोरिदम एक नोड-स्प्लिट ऑक्सिलरी नेटवर्क पर मैक्स-फ्लो फॉर्मूलेशन का उपयोग करके अवशेष ग्राफ $G \setminus S$ का मिनिमम वर्टेक्स कट $F$ की गणना करता है। यह उन "बाधक" वर्टिसेस के न्यूनतम सेट की पहचान करता है जो द्विपार्श्व विभाजन (bipartition) को रोक रहे हैं।
क्लासिकल फ्रीजिंग: वर्टिसेस $F$ की अवस्थाओं को नियतात्मक स्पिन ( $+1$ या $-1$) के रूप में क्लासिकली फिक्स कर दिया जाता है।
बायस फोल्डिंग (Bias Folding): फ्रीज़ किए गए नोड्स से जुड़े किनारों (edges) के ऊर्जा योगदान को हटाया नहीं जाता है। इसके बजाय, उन्हें आइसोइंग हैमिल्टोनियन (Ising Hamiltonian) में सक्रिय क्वबिट्स पर लागू होने वाले लीनियर बायस टर्म्स ( $h_i$ ) में गणितीय रूप से फोल्ड किया जाता है। यह फ्रीज़ किए गए नोड्स से जुड़े एंटैंगलिंग गेट्स की आवश्यकता को हटाते हुए कॉस्ट फंक्शन की कठोर परिभाषा को सुरक्षित रखता है।
सब-सर्किट निष्पादन: अब द्विपार्श्व विभाजन योग्य अवशेष सक्रिय ग्राफ को संशोधित हैमिल्टोनियन के साथ संवर्धित (augmented) QAOA सर्किट्स का उपयोग करके हल किया जाता है।

चरण 3: कनेक्टिविटी-प्रिजर्विंग पार्टीशनिंग (CPP)

यदि मिनिमम कट को फ्रीज़ करना (बजट $B_f$ के भीतर) अभी भी एक वैध पार्टीशन बनाने में विफल रहता है (जैसे, पूर्ण ग्राफ $K_n$ में), तो एक नियतात्मक फॉलबैक (fallback) आह्वान किया जाता है। CPP सॉर्ट किए गए वर्टेक्स लिस्ट को मिडपॉइंट पर विभाजित करता है, जिससे दो सबग्राफ बनते हैं जो एक एकल बाउंड्री नोड साझा करते हैं। क्रॉस-पार्टीशन एड्ज को क्वांटम सर्किट्स से हटा दिया जाता है लेकिन क्लासिकली ट्रैक किया जाता है। अंतिम समाधान का पुनर्निर्माण हटाए गए एड्ज के क्लासिकल योगदान के आधार पर क्वांटम आउटपुट डिस्ट्रीबशन को री-स्कोर करके किया जाता है, जिससे 100% कवरेज सुनिश्चित होता है।

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

सटीक, बजट-जागरूक विघटन: FrozenLGP बाधक वर्टिसेस की प्रमाणित न्यूनतम संख्या को फ्रीज़ करता है (MVC के माध्यम से) ताकि पार्टीशनिंग संभव हो सके। यह न्यूनता (minimality) सब-सर्किट हैमिल्टोनियन में होने वाले विरूपण (distortion) को सीमित करती है और एक स्पष्ट, टोपोलॉजी-अनुमानित रिकवरी थ्रेशोल्ड ( $B_f = \kappa - (k-1)$ , जहाँ $\kappa$ वर्टेक्स कनेक्टिविटी है) स्थापित करती है।
अनकंडीशनल कवरेज फ्लोर: CPP फॉलबैक को एकीकृत करके, यह फ्रेमवर्क सभी ग्राफ टोपोलॉजी पर 100% डिकंपोज़िशन कवरेज की गारंटी देता है, जिसमें वे भी शामिल हैं जहाँ वर्टेक्स-रिमूवल रणनीतियाँ मौलिक रूप से विफल हो जाती हैं (जैसे, पूर्ण ग्राफ)।
NISQ मजबूती: उच्च-डिग्री वाले "हॉटस्पॉट" नोड्स को फ्रीज़ करके, यह विधि आवश्यक टू-क्विबिट एंटैंगलिंग गेट्स (CNOTs) और सर्किट डेप्थ की संख्या को कम करती है। यह गेट एरर्स और डिकोहेरेंस के संपर्क को कम करता है, जिससे शोर वाले वातावरण में बेहतर मजबूती मिलती है।

4. प्रयोगात्मक परिणाम

लेखकों ने $n=10,000$ तक के ग्राफ आकारों और विभिन्न टोपोलॉजी (Barabási–Albert, Erdős–Rényi, रैंडम d-रेगुलर) के लिए FrozenLGP का मूल्यांकन किया।

डिकंपोज़िशन कवरेज: उच्च-कनेक्टिविटी वाले उदाहरणों पर जहाँ मानक DC-QAOA बेसलाइन ने केवल 4.6% कवरेज प्राप्त किया, FrozenLGP ने 100% कवरेज प्राप्त किया।
बजट थ्रेशोल्ड्स: प्रयोगों ने एक शार्प ट्रांजिशन (sharp transition) की पुष्टि की। रैंडम d-रेगुलर ग्राफों के लिए, पूर्ण रिकवरी ठीक तभी प्राप्त हुई जब फ्रीज बजट ने $B_f \ge d - (k-1)$ को संतुष्ट किया।
समाधान की गुणवत्ता:
- संरक्षण (Preservation): उन उदाहरणों पर जो मानक DC-QAOA द्वारा हल किए जा सकते हैं, FrozenLGP (जिसमें $B_f=3$ है) ने बेसलाइन की तुलना में सांख्यिकीय रूप से अविभेद्य (indistinguishable) एप्रोक्सिमेशन रेश्यो (AR) उत्पन्न किए (जैसे, सामान्य सेट्स पर AR 0.988 बनाम 0.983), जो शून्य गिरावट की पुष्टि करता है।
- विस्तार (Extension): पहले से असमर्थ घने ग्राफों पर, FrozenLGP ने उच्च एप्रोक्सिमेशन रेश्यो (AR $\approx 0.98$ ) बनाए रखा, जो अन्य फुल-कवरेज रणनीतियों जैसे QAOA-इन-QAOA (QAOA2) के मुकाबले काफी बेहतर प्रदर्शन करता है, जो संचित कट-एज लॉस (cut-edge losses) के कारण कम AR ( $\approx 0.76$ at $n=100$ ) से ग्रस्त था।
दक्षता: प्रीप्रोसेसिंग समय नगण्य (सेकंडों में) था, और जहाँ मानक पार्टीशनिंग सफल रही वहाँ इस पद्धति ने कोई फ्रीजिंग ओवरहेड नहीं लिया।

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

यह पेपर दावा करता है कि FrozenLGP निकट-अवधि हार्डवेयर (near-term hardware) के लिए वितरित QAOA के लिए एक टोपोलॉजी-रोबस्ट फ्रंट एंड स्थापित करता है। इसका प्राथमिक महत्व डिवाइड-एंड-कॉन्कर दृष्टिकोणों के "स्ट्रक्चरल फेलियर मोड" को हटाना है। पार्टीशनयोग्यता को एक अनिवार्य पूर्व शर्त के बजाय एक प्रवर्तनीय गुण के रूप में मानकर, यह विधि QAOA की प्रयोज्यता को घने, अत्यधिक जुड़े हुए ग्राफों तक विस्तारित करती है जो पहले विघटन-आधारित रणनीतियों के लिए अप्राप्य थे।

लेखक जोर देते हैं कि यह दृष्टिकोण केवल कवरेज का विस्तार नहीं करता है, बल्कि सेपरेटर स्ट्रक्चर को सुरक्षित रखकर और कट-एज एरर के संचय से बचकर घने ग्राफों पर समाधान की गुणवत्ता में सुधार करता है। इसके अलावा, क्वबिट फ्रीजिंग के कारण एंटैंगलिंग गेट्स में कमी, NISQ उपकरणों पर शोर को कम करने के लिए एक व्यावहारिक मार्ग प्रदान करती है। निष्कर्षतः, FrozenLGP एक स्केलेबल, स्ट्रक्चर-रोबस्ट समाधान प्रदान करता है जो सैद्धांतिक QAOA क्षमताओं और वर्तमान क्वांटम हार्डवेयर की सीमाओं के बीच के अंतर को पाटता है।