⚛️ quantum physics

Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem

यह शोध पत्र न्यूनतम वर्टेक्स कवर (Minimum Vertex Cover) समस्या के लिए एक स्केलेबल, निरंतर-समय क्वांटम वॉक-आधारित ह्यूरिस्टिक प्रस्तुत करता है जो विविध ग्राफ टोपोलॉजी में सटीक और शास्त्रीय ह्यूरिस्टिक विधियों दोनों की तुलना में बेहतर सन्निकटन अनुपात (approximation ratios) और मजबूती प्राप्त करने के लिए एक डायनेमिक डिकपलिंग तंत्र और कॉम्पैक्ट बाइनरी एनकोडिंग का उपयोग करता है।

मूल लेखक: F. S. Luiz, A. K. F. Iwakami, D. H. Moraes, M. C. de Oliveira

प्रकाशित 2026-05-26

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

CC BY 4.0

मूल लेखक: F. S. Luiz, A. K. F. Iwakami, D. H. Moraes, M. C. de Oliveira

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

मुख्य चित्र: "गार्ड पोस्ट" की खोज

कल्पना कीजिए कि आपके पास एक शहर है जिसमें विभिन्न चौराहों (vertices) को जोड़ने वाली कई सड़कें (edges) हैं। आपका लक्ष्य न्यूनतम संभव चौराहों पर सुरक्षा गार्ड तैनात करना है ताकि हर एक सड़क पर कम से कम एक गार्ड की नज़र रहे। गणित में, इसे मिनिमम वर्टेक्स कवर (Minimum Vertex Cover) समस्या कहा जाता है।

यह एक अत्यंत कठिन पहेली है। यदि आप केवल सबसे व्यस्त चौराहों (जिनमें सबसे अधिक सड़कें निकलती हैं) को चुनने की कोशिश करते हैं, तो अक्सर आप एक बेहतर और अधिक कुशल व्यवस्था को चूक जाते हैं। यह शोध पत्र इस पहेली को हल करने का एक नया तरीका पेश करता है जो क्वांटम भौतिकी (quantum physics) के अजीब और जादुई नियमों का उपयोग करता है, लेकिन इसमें एक आश्चर्यजनक मोड़ है: क्वांटम हिस्सा हमें एक सामान्य कंप्यूटर का उपयोग करके इसे हल करने का एक बेहतर तरीका खोजने में मदद करता है।

क्वांटम जादू: "क्वांटम वॉक" (The Quantum Walk)

लेखकों ने एक अवधारणा का उपयोग किया जिसे कंटीन्यूअस-टाइम क्वांटम वॉक (CTQW) कहा जाता है।

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

हार्डवेयर परीक्षण: वास्तविक क्वांटम कंप्यूटरों पर चलाना

टीम ने इसे वास्तविक हार्डवेयर (IBM का ibm_marrakesh और एक न्यूट्रल-एटम प्लेटफॉर्म जिसे Bloqade कहा जाता है) पर चलाने का प्रयास किया।

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

असली सफलता: "क्वांटम-प्रेरित" शॉर्टकट (The Quantum-Inspired Shortcut)

इस शोध पत्र का सबसे महत्वपूर्ण हिस्सा यहाँ है: उन्हें बड़े समस्याओं को हल करने के लिए क्वांटम कंप्यूटर की आवश्यकता नहीं थी।

क्वांटम वॉक के गणित का विश्लेषण करके, उन्होंने पाया कि जटिल क्वांटम व्यवहार एक सरल, क्लासिकल फॉर्मूले में बदल जाता है।

पुराना तरीका (Degree-Greedy): "उस चौराहे को चुनें जिसमें सबसे अधिक सड़कें हैं।"
नया क्वांटम-प्रेरित तरीका: "उस चौराहे को चुनें जो ऐसे पड़ोसियों से जुड़ा है जिनमें स्वयं कम सड़कें हैं।"

रूपक:
कल्पना कीजिए कि आप किसी अफवाह को फैलने से रोकने की कोशिश कर रहे हैं।

पुराना तरीका कहता है: "उस व्यक्ति को रोकें जो सबसे अधिक लोगों से बात करता है।"
नया तरीका कहता है: "उस व्यक्ति को रोकें जो शांत लोगों से बात करता है।" क्यों? क्योंकि यदि आप उस व्यक्ति को रोकते हैं जो शांत लोगों से जुड़ा है, तो आप अफवाह के मार्ग को उन "शांत" कोनों तक पहुँचने से काट देते हैं जिन्हें शोर मचाने वाले व्यस्त केंद्र शायद छोड़ दें।

इस नए नियम को स्पेक्ट्रल ग्रीडी ह्यूरिस्टिक (Spectral Greedy Heuristic) कहा जाता है। इसे एक सामान्य कंप्यूटर पर गणना करना अविश्वसनीय रूप से तेज़ है और इसके लिए क्वांटम मशीन की आवश्यकता नहीं है।

परिणाम: यह कितना प्रभावी रहा?

लेखकों ने इस नई पद्धति का परीक्षण हजारों अलग-अलग प्रकार के मानचित्रों (रैंडम शहर, सामाजिक नेटवर्क और पूरी तरह से संरचित ग्रिड) पर किया और इसकी तुलना सर्वोत्तम मौजूदा तरीकों से की।

लगभग पूर्ण सटीकता: 98.3% परीक्षण मामलों में, नई "क्वांटम-प्रेरित" पद्धति ने जटिल क्वांटम सिमुलेशन के समान ही समाधान खोजा।
प्रतिस्पर्धा को पछाड़ना: इसने लगातार मानक "सबसे व्यस्त चौराहे को चुनने" वाले तरीके की तुलना में बेहतर (छोटे) गार्ड सेट खोजे।
- औसतन, उनका समाधान पूर्ण उत्तर से केवल 1.5% बड़ा था।
- मानक तरीका पूर्ण उत्तर से लगभग 2.3% बड़ा था।
- हालांकि 1% छोटा लगता है, लेकिन विशाल नेटवर्क (जैसे इंटरनेट या पावर ग्रिड) में, यह अंतर हजारों संसाधनों की बचत करता है।
स्केलिंग अप: उन्होंने 1,00,000 चौराहों तक के विशाल मानचित्रों पर इसका परीक्षण किया। इस नई पद्धति ने इन बड़े परीक्षणों में 100% में सबसे अच्छा समाधान खोजा, जबकि मानक तरीका पीछे रह गया।

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

यह शोध पत्र एक अद्वितीय कार्यप्रवाह (workflow) प्रदर्शित करता है:

पैटर्न खोजने और समस्या का पता लगाने के लिए क्वांटम वॉक का उपयोग करें।
महसूस करें कि वह पैटर्न एक क्लासिकल फॉर्मूला में सरल हो जाता है।
उस क्लासिकल फॉर्मूला का उपयोग करके सामान्य कंप्यूटरों पर बड़े पैमाने की समस्याओं को कुशलतापूर्वक हल करें।

क्वांटम कंप्यूटर एक "खोज उपकरण" (discovery tool) के रूप में कार्य करता है ताकि एक सामान्य कंप्यूटर के लिए एक बेहतर नियम खोजा जा सके। परिणाम एक तेज़, स्मार्ट तरीका है जिससे कंप्यूटर विज्ञान की सबसे कठिन पहेलियों में से एक को हल किया जा सकता है, बिना क्वांटम मशीन द्वारा भारी काम करने की आवश्यकता के।

तकनीकी सारांश: न्यूनतम वर्टेक्स कवर समस्या के लिए स्केलेबल क्वांटम वॉक-आधारित ह्यूरिस्टिक्स

समस्या विवरण
न्यूनतम वर्टेक्स कवर (Minimum Vertex Cover - MVC) समस्या कॉम्बिनेटरियल ऑप्टिमाइज़ेशन में एक मौलिक NP-कम्प्लीट चुनौती है, जिसमें एक ग्राफ $G=(V, E)$ में सबसे छोटा वर्टेक्सों का उपसमुच्चय $C \subseteq V$ खोजने की आवश्यकता होती है ताकि प्रत्येक किनारा (edge) कम से कम एक वर्टेक्स $C$ से जुड़ा हो। जबकि सटीक एल्गोरिदम मौजूद हैं, वे कवर आकार के साथ तेजी से (exponentially) बढ़ते हैं। क्लासिकल एप्रोक्सीमेशन रणनीतियाँ, जैसे कि मैक्सिमल मैचिंग, $\le 2$ का अनुपात प्रदान करती हैं, लेकिन डिनर और सफ्रा ने स्थापित किया है कि कोई भी पॉलिनॉमियल-टाइम एल्गोरिदम बड़े-डिग्री वाले ग्राफों के लिए $\approx 1.3606$ से नीचे का अनुपात प्राप्त नहीं कर सकता। लेखक यह अन्वेषण करने का लक्ष्य रखते हैं कि क्या निरंतर-समय क्वांटम वॉक (Continuous-Time Quantum Walks - CTQWs) एक सिद्धांतिक, उच्च-गुणवत्ता वाला चयन मानदंड प्रदान कर सकते हैं जो क्लासिकल ह्यूरिस्टिक्स से बेहतर प्रदर्शन करे और स्केलेबल भी रहे।

कार्यप्रणाली (Methodology)
यह शोध पत्र एक CTQW-आधारित ह्यूरिस्टिक का प्रस्ताव करता है जो एक वर्टेक्स कवर बनाने के लिए पुनरावृत्ति (iteratively) में कार्य करता है। मुख्य कार्यप्रणाली में तीन मुख्य घटक शामिल हैं:

क्वांटम फॉर्मूलेशन:
- हैमिल्टनियन (Hamiltonian): ग्राफ को नॉर्मलाइज्ड सिमेट्रिक लैपलेसियन $H = I - D^{-1/2}AD^{-1/2}$ पर आधारित एक हैमिल्टनियन में एनकोड किया गया है, जहाँ $A$ एडजेसेंसी मैट्रिक्स है और $D$ डिग्री मैट्रिक्स है। यह नॉर्मलाइजेशन यूनिफॉर्म प्रोपेगेशन डायनेमिक्स सुनिश्चित करता है, जिससे उच्च-डिग्री वाले वर्टेक्सों की ओर झुकाव (bias) कम हो जाता है।
- इवोल्यूशन (Evolution): सिस्टम एक इष्टतम समय $t_{opt}$ के लिए $U(t) = e^{-iHt}$ के तहत विकसित होता है। लेखक एक बाइनरी एनकोडिंग स्कीम का उपयोग करते हैं, जो $V$ वर्टेक्सों को $n = \lceil \log_2 V \rceil$ क्यूबिट्स के साथ प्रदर्शित करता है, जो वन-हॉट एनकोडिंग की तुलना में क्यूबिट आवश्यकताओं को काफी कम कर देता है।
- चयन मानदंड (Selection Criterion): प्रत्येक पुनरावृत्ति में, वह वर्टेक्स $m$ जिसके लिए उच्चतम ट्रांजिशन प्रोबेबिलिटी $P(m \to \text{out}) = 1 - |[e^{i\Gamma t}]_{mm}|^2$ है, उसे चुना जाता है और कवर में जोड़ा जाता है। यहाँ, $\Gamma$ नॉर्मलाइज्ड एडजेसेंसी मैट्रिक्स है।
- फ्रीजिंग मैकेनिज्म (Freezing Mechanism): पुन: चयन को रोकने और चुने गए वर्टेक्स को अलग करने के लिए, चुने गए वर्टेक्स के सबस्पेस पर एक एनर्जी-पेनल्टी टर्म लागू किया जाता है। यह "स्पेक्ट्रल आइसोलेशन" (या फ्रीजिंग) चुने गए स्टेट को ऑफ-रेजोनेंस में शिफ्ट कर देता है, जो हैमिल्टनियन मैट्रिक्स से किनारों को भौतिक रूप से हटाए बिना, उसे आगामी पुनरावृत्तियों के लिए सक्रिय डायनेमिक्स से प्रभावी रूप से बाहर कर देता है।
क्लासिकल डेरिवेशन (क्वांटम-प्रेरित ह्यूरिस्टिक):
- मैट्रिक्स एक्सपोनेंशियल $e^{i\Gamma t}$ के शॉर्ट-टाइम एक्सपेंशन के माध्यम से, लेखक विश्लेषणात्मक रूप से यह सिद्ध करते हैं कि क्वांटम चयन मानदंड एक क्लासिकल स्पेक्ट्रल मात्रा में बदल जाता है जिसे $O(|E|)$ समय में गणना योग्य बनाया जा सकता है:
  $s(m) = [\Gamma^2]_{mm} = \frac{1}{d_m} \sum_{j \in N(m)} \frac{1}{d_j}$
- यह मात्रा एक वर्टेक्स के पड़ोसियों के औसत इन्वर्स डिग्री (inverse degree) को दर्शाती है, जिसे उस वर्टेक्स की अपनी डिग्री द्वारा स्केल किया गया है। यह दो-हॉप (two-hop) स्ट्रक्चरल जानकारी कैप्चर करती है, जो इसे साधारण डिग्री-आधारित ग्रीडी दृष्टिकोणों से अलग बनाती है।
कार्यान्वयन (Implementation):
- क्वांटम हार्डवेयर: एल्गोरिदम को IBM के ibm_marrakesh (गेट-बेस्ड) और Bloqade (न्यूट्रल-एटम) प्लेटफॉर्म पर लागू किया गया। गेट-बेस्ड कार्यान्वयन सर्किट डेप्थ ( $O(V^2)$ टू-क्यूबिट गेट्स) के कारण छोटे ग्राफ ( $V \lesssim 16$ ) तक सीमित है, जबकि न्यूट्रल-एटम दृष्टिकोण में एक वर्टेक्स के लिए एक परमाणु का उपयोग किया जाता है।
- क्लासिकल सिमुलेशन: व्युत्पन्न स्पेक्ट्रल ग्रीडी एल्गोरिदम (एल्गोरिदम 2) का सटीक मिक्सड-इंटीजर लीनियर प्रोग्रामिंग (MILP) समाधानों और क्लासिकल ह्यूरिस्टिक्स (डिग्री-ग्रीडी, फास्टVC, 2-एप्रोक्सीमेशन, सिम्युलेटेड एनीलिंग) के विरुद्ध 14,680 इंस्टेंस पर बेंचमार्किंग किया गया।

मुख्य योगदान

भौतिक संबंध: यह कार्य क्वांटम ट्रांसपोर्ट डायनेमिक्स और MVC समस्या के बीच एक सीधा भौतिक लिंक स्थापित करता है, यह प्रदर्शित करते हुए कि उच्च ट्रांजिशन प्रोबेबिलिटी वाले वर्टेक्स स्वाभाविक रूप से संरचनात्मक रूप से प्रासंगिक कवर एलिमेंट्स के अनुरूप होते हैं।
संसाधन दक्षता: बाइनरी एनकोडिंग का उपयोग करके, क्वांटम एल्गोरिदम को केवल $\lceil \log_2 V \rceil$ क्यूबिट्स की आवश्यकता होती है, जो मानक QAOA फॉर्मुलेशन द्वारा आवश्यक $V$ क्यूबिट्स की तुलना में एक महत्वपूर्ण कमी है।
क्वांटम-प्रेरित क्लासिकल एल्गोरिदम: प्राथमिक योगदान एक क्लासिकल ह्यूरिस्टिक (एल्गोरिदम 2) का निष्कर्षण है जो क्वांटम एल्गोरिदम के प्रदर्शन को $O(|E|)$ जटिलता के साथ पुनरुत्पादित करता है, जिससे यह $V \sim 10^5$ वर्टेक्स वाले ग्राफों के लिए भी स्केलेबल हो जाता है।
व्यापक बेंचमार्किंग: अर्डोस-रेनी (Erdős–Rényi), बाराबासी-अलबर्ट (Barabási–Albert), और रेगुलर ग्राफ एन्सेम्बल्स के साथ-साथ SNAP रिपॉजिटरी से वास्तविक दुनिया के नेटवर्क पर विस्तृत सत्यापन प्रदान किया गया है।

परिणाम

क्लासिकल ह्यूरिस्टिक्स के विरुद्ध प्रदर्शन: 14,680 बेंचमार्क इंस्टेंस ( $N \in [4, 150]$ ) में, CTQW-आधारित दृष्टिकोण (और इसके क्लासिकल स्पेक्ट्रल समकक्ष) ने 1.015 का औसत एप्रोक्सीमेशन रेश्यो प्राप्त किया, जो डिग्री-ग्रीडी (1.023) और सिम्युलेटेड एनीलिंग (1.027) से काफी बेहतर है। यह लाभ रेगुलर ग्राफों पर सबसे अधिक स्पष्ट था, जहाँ स्पेक्ट्रल मानदंड ने उन टाइज़ (ties) को सफलतापूर्वक हल किया जहाँ डिग्री-आधारित विधियाँ विफल रहीं।
कठिन इंस्टेंस: संरचनात्मक रूप से कठिन परिवारों (क्राउन ग्राफ, पीटरसन ग्राफ, रैंडम 3-रेगुलर ग्राफ) पर, वर्स्ट-केस रेश्यो 1.143 था, जो $\approx 1.3606$ के सैद्धांतिक इनएप्रोक्सिमेबिलिटी थ्रेशोल्ड से काफी नीचे है।
स्केलेबिलिटी: बड़े पैमाने पर ( $V \in [10^3, 10^5]$ ), स्पेक्ट्रल ग्रीडी एल्गोरिदम ने 210 मामलों में से 100% इंस्टेंस में सर्वश्रेष्ठ कवर साइज (वर्चुअल बेस्ट सॉल्वर के सापेक्ष 1.000 का अनुपात) प्राप्त किया। इसने डिग्री-ग्रीडी (औसत रेश्यो 1.047) और सिम्युलेटेड एनीलिंग (औसत रेश्यो 1.072) को पछाड़ दिया।
हार्डवेयर सत्यापन: IBM हार्डवेयर पर, एल्गोरिदम ने $V=4$ के लिए सटीक समाधान दिए लेकिन $V=32$ पर डीप सर्किट्स के कारण गेट एरर्स का सामना किया। हालांकि, परिणामों ने पुष्टि की कि बाइनरी एनकोडिंग छोटे $V$ के लिए व्यवहार्य है और क्वांटम वॉक विश्लेषण क्लासिकल मानदंड के लिए एक खोज तंत्र (discovery mechanism) के रूप में कार्य करता है।
वास्तविक दुनिया के नेटवर्क: आठ वास्तविक दुनिया के नेटवर्क (जिसमें रोड और कोलैबोरेशन ग्राफ शामिल हैं) पर, स्पेक्ट्रल ग्रीडी विधि ने सभी मामलों में वर्चुअल बेस्ट सॉल्वर के बराबर प्रदर्शन किया, और पेंसिल्वेनिया रोड नेटवर्क पर डिग्री-ग्रीडी की तुलना में 5.3% सुधार किया।

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

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