⚛️ quantum physics

A scalable quantum-enhanced greedy algorithm for maximum independent set problems

यह शोध पत्र एक स्केलेबल हाइब्रिड क्वांटम-क्लासिकल एल्गोरिदम प्रस्तुत करता है जो बड़े ग्राफों पर मैक्सिमम इंडिपेंडेंट सेट समस्याओं को कुशलतापूर्वक हल करने के लिए पूर्व-निर्धारित QAOA मापदंडों को एक ग्रीडी रणनीति के साथ जोड़ता है, जो वर्तमान 20-क्यूबिट हार्डवेयर और टेंसर नेटवर्क सिमुलेशन दोनों पर क्लासिकल बेसलाइन्स की तुलना में बेहतर प्रदर्शन प्रदर्शित करता है।

मूल लेखक: Elisabeth Wybo, Jami Rönkkö, Olli Hirviniemi, Jernej Rudi Finžgar, Martin Leib

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

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

CC BY 4.0

मूल लेखक: Elisabeth Wybo, Jami Rönkkö, Olli Hirviniemi, Jernej Rudi Finžgar, Martin Leib

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

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

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

नया विचार: एक क्वांटम "क्रिस्टल बॉल"

शोधकर्ताओं ने एक हाइब्रिड टीम बनाई है: एक क्लासिकल कंप्यूटर (ग्रीडी प्लानर) और एक क्वांटम कंप्यूटर (क्रिस्टल बॉल)।

यह "क्वांटम-एन्हांस्ड ग्रीडी एल्गोरिदम" कैसे काम करता है, इसे एक सरल उपमा से समझते हैं:

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

यह विशेष क्यों है?

आमतौर पर, क्वांटम कंप्यूटर नाजुक कांच के वाद्य यंत्रों की तरह होते हैं; उन्हें काम करने के लिए एकदम सटीक होने और गहरे, जटिल गणनाओं को चलाने की आवश्यकता होती है। लेकिन यह तरीका अलग है:

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

उन्होंने क्या पाया?

टीम ने एक वास्तविक क्वांटम कंप्यूटर पर परीक्षण किया जिसे IQM द्वारा बनाया गया है (एक 20-क्यूबिट डिवाइस) और सुपरकंप्यूटरों पर इसका सिमुलेशन किया।

बुनियादी चीजों को मात देना: एक बहुत ही सरल क्वांटम सेटअप (डेप्थ $p=4$ , जो कि केवल 4 त्वरित नज़र लेने जैसा है) के साथ भी, उनके हाइब्रिड तरीके ने सबसे अच्छे शुद्ध क्लासिकल "ग्रीडी" तरीकों की तुलना में बेहतर समूह खोजे।
विशेषज्ञों को मात देना: उन्होंने 5,000 नोड्स तक के ग्राफों पर एक बहुत ही परिष्कृत, अत्याधुनिक क्लासिकल एल्गोरिदम (जिसे "लीनियर-टाइम प्रायोरिटाइज्ड सर्च" कहा जाता है) को भी पीछे छोड़ दिया।
सही संतुलन (The Sweet Spot): क्वांटम कंप्यूटर एक स्मार्ट गाइड की तरह काम करता है। यह पूरी समस्या को हल करने का भारी काम नहीं करता है; यह बस हर कदम पर क्लासिकल प्लानर को सही दिशा में एक हल्का सा धक्का देता है।

निचोड़ (The Bottom Line)

यह पेपर दिखाता है कि आपको लाभ प्राप्त करने के लिए एक पूर्ण, विशाल क्वांटम कंप्यूटर की आवश्यकता नहीं है। एक तेज़, क्लासिकल "वर्कर" को निर्देशित करने के लिए एक छोटे, सरल क्वांटम "सलाहकार" का उपयोग करके, आप अकेले किसी भी एक का उपयोग करने की तुलना में कठिन अनुकूलन समस्याओं (optimization problems) को बेहतर ढंग से हल कर सकते हैं। यह हमारे शोर-शराबे वाले, शुरुआती दौर के क्वांटम हार्डवेयर के बावजूद, अभी भी "क्वांटम उपयोगिता" प्राप्त करने का एक व्यावहारिक, स्केलेबल तरीका है।

तकनीकी सारांश: मैक्सिमम इंडिपेंडेंट सेट समस्याओं के लिए एक स्केलेबल क्वांटम-एन्हांस्ड ग्रीडी एल्गोरिदम

समस्या विवरण

यह शोध पत्र मैक्सिमम इंडिपेंडेंट सेट (MIS) समस्या को संबोधित करता है, जो ग्राफ थ्योरी में एक मौलिक NP-hard कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन कार्य है। दिए गए ग्राफ $G=(V, E)$ के लिए, लक्ष्य शीर्षों (vertices) का सबसे बड़ा उपसमुच्चय $I \subseteq V$ खोजना है ताकि $I$ के दो शीर्ष आपस में जुड़े हुए न हों। जबकि क्लासिकल ग्रीडी एल्गोरिदम रैखिक-समय (linear-time) स्केलेबिलिटी प्रदान करते हैं, वे अक्सर जटिल वैश्विक संरचनाओं को पकड़ने में विफल रहते हैं, जिससे उप-इष्टतम (suboptimal) समाधान प्राप्त होते हैं। इसके विपरीत, स्टैंडअलोन क्वांटम एल्गोरिदम जैसे कि क्वांटम एप्रोक्सीमेट ऑप्टिमाइज़ेशन एल्गोरिदम (QAOA), नोइजी इंटरमीडिएट-स्केल क्वांटम (NISQ) युग में महत्वपूर्ण चुनौतियों का सामना करते हैं: उन्हें इष्टतमता प्राप्त करने के लिए गहरे सर्किटों की आवश्यकता होती है (जो वर्तमान हार्डवेयर शोर के कारण समर्थित नहीं कर सकते) और वे वेरिएशनल पैरामीटर ऑप्टिमाइज़ेशन के दौरान "बैरन प्लेटो" (barren plateau) की समस्या से ग्रस्त होते हैं। इसके अलावा, सैद्धांतिक परिणाम बताते हैं कि कांस्टेंट-डेप्थ QAOA, लोकैलिटी बाधाओं के कारण, MIS को निकट-इष्टतमता (near-optimality) तक हल नहीं कर सकता है।

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

लेखक एक हाइब्रिड क्वांटम-क्लासिकल एल्गोरिदम का प्रस्ताव करते हैं जो एक क्लासिकल ग्रीडी फ्रेमवर्क के भीतर सब-रूटीन के रूप में QAOA को एकीकृत करता है। मुख्य कार्यप्रणाली में निम्नलिखित घटक शामिल हैं:

फिक्स्ड-एंगल QAOA: इंस्टेंस-विशिष्ट वेरिएशनल पैरामीटर ऑप्टिमाइज़ेशन करने के बजाय (जो गणनात्मक रूप से महंगा और बैरन प्लेटो के प्रति संवेदनशील है), यह एल्गोरिदम पूर्व-निर्धारित QAOA कोणों (angles) का उपयोग करता है। ये कोण रेगुलर ट्रीज़ (बेथ लैटिस) पर डेप्थ- $p$ QAOA सर्किटों से प्राप्त किए जाते हैं, जो बड़े $d$ -रेगुलर ग्राफ के स्थानीय पड़ोस के सटीक अनुमान के रूप में कार्य करते हैं।
क्वांटम-एन्हांस्ड ग्रीडी चयन:
- एल्गोरिदम पुनरावृत्ति (iteratively) के माध्यम से एक इंडिपेंडेंट सेट बनाता है।
- प्रत्येक चरण में, केवल डिग्री के आधार पर नोड चुनने के बजाय (जैसा कि क्लासिकल मिनिमल-डिग्री ग्रीडी में होता है), एल्गोरिदम उस नोड $i$ का चयन करता है जो QAOA स्टेट $|\gamma^*, \beta^*\rangle$ से प्राप्त स्थानीय एक्सपेक्टेशन वैल्यू $\langle Z_i \rangle_p$ को अधिकतम करता है।
- इस एक्सपेक्टेशन वैल्यू का अनुमान उम्मीदवार नोड के लाइट-कोन सबग्राफ (त्रिज्या $p$ का पड़ोस) पर प्रतिबंधित एक शैलो (shallow) QAOA सर्किट को निष्पादित करके लगाया जाता है।
- चयनित नोड को इंडिपेंडेंट सेट में जोड़ा जाता है, और उस नोड के साथ उसके पड़ोसियों को ग्राफ से हटा दिया जाता है।
दक्षता तंत्र (Efficiency Mechanisms):
- लोकल रीकंप्यूटेशन: QAOA की लोकैलिटी के कारण, एक नोड को हटाने से केवल $p+1$ दूरी के भीतर के नोड्स के एक्सपेक्टेशन वैल्यू प्रभावित होते हैं। एल्गोरिदम केवल इन प्रभावित मूल्यों को पुनर्गणना करता है।
- कैशिंग: आइसोमॉर्फिक लाइट-कोन सबग्राफ के लिए एक्सपेक्टेशन वैल्यू को कैश किया जाता है ताकि गणना को दोहराने से बचा जा सके।
- जटिलता: फिक्स्ड डेप्थ $p$ के लिए, स्थानीय एक्सपेक्टेशन वैल्यू की गणना करने की लागत ग्राफ के आकार $N$ के संबंध में स्थिर रहती है। फलस्वरूप, कुल रनटाइम रैखिक रूप से, $O(N)$ , स्केल करता है, जो मूल क्लासिकल ग्रीडी एल्गोरिदम की जटिलता से मेल खाता है।

मुख्य योगदान

वेरिएशनल ऑप्टिमाइज़ेशन का उन्मूलन: यह कार्य एक "प्लग-एंड-प्ले" दृष्टिकोण प्रदर्शित करता है जहाँ QAOA पैरामीटर ट्री मॉडल्स पर आधारित होते हैं, जो महंगे क्लासिकल ऑप्टिमाइज़ेशन लूप की आवश्यकता को समाप्त करते हैं और इसे स्केलेबल बनाते हैं।
स्केलेबल हाइब्रिड आर्किटेक्चर: लेखक एक ऐसी विधि प्रस्तुत करते हैं जो शैलो क्वांटम सर्किटों (जो NISQ उपकरणों के अनुकूल हैं) का उपयोग करते हुए भी क्वांटम सहसंबंधों (correlations) का लाभ उठाती है, जिससे रैखिक-समय जटिलता प्राप्त होती है।
प्रायोगिक सत्यापन: एल्गोरिदम को एक 20-क्यूबिट IQM सुपरकंडक्टिंग क्वांटम प्रोसेसर (Garnet) पर लागू किया गया। अध्ययन ने हजारों नोड्स वाले ग्राफों में सफलतापूर्वक इंडिपेंडेंट सेट खोजे, जिससे वास्तविक हार्डवेयर पर इस दृष्टिकोण की वैधता सिद्ध हुई।
टेंसर नेटवर्क बेंचमार्किंग: वर्तमान हार्डवेयर सीमाओं से परे प्रदर्शन का मूल्यांकन करने के लिए, लेखकों ने $p=4$ तक की डेप्थ और $N=5000$ तक के ग्राफ साइज के लिए सटीक एक्सपेक्टेशन वैल्यू की गणना करने के लिए टेंसर नेटवर्क सिमुलेशन (QUIMB पैकेज का उपयोग करके) का उपयोग किया।

परिणाम

क्लासिकल बेसलाइन बनाम प्रदर्शन:
- रैंडम 3-रेगुलर ग्राफ्स पर, क्वांटम-एन्हांस्ड ग्रीडी एल्गोरिदम स्टैंडर्ड मिनिमल-डिग्री ग्रीडी बेसलाइन की तुलना में काफी बेहतर प्रदर्शन करता है।
- डेप्थ $p=4$ पर, हाइब्रिड विधि $N \approx 5000$ तक के ग्राफ साइज के लिए स्टेट-ऑफ-द-आर्ट (SOTA) लीनियर-टाइम प्रायोरिटाइज्ड सर्च एल्गोरिदम (मारिनो एट अल.) की तुलना में सांख्यिकीय रूप से महत्वपूर्ण सुधार प्राप्त करती है।
- कम डेप्थ ( $p=2, 3$ ) पर भी, क्वांटम-एन्हांस्ड विधि शुद्ध क्लासिकल दृष्टिकोणों की तुलना में बेहतर इंडिपेंडेंस रेशियो प्रदान करती है।
हार्डवेयर कार्यान्वयन:
- $p=2$ और $p=3$ पर IQM Garnet डिवाइस पर प्रयोगों ने पुष्टि की कि नॉइजी हार्डवेयर से निकाले गए एक्सपेक्टेशन वैल्यू प्रभावी रूप से ग्रीडी चयन को निर्देशित कर सकते हैं।
- एल्गोरिदम ने शोर (noise) के प्रति मजबूती प्रदर्शित की; हालाँकि शोर क्वांटम प्रोसेसर द्वारा प्रदान की गई "सलाह" की सटीकता को कम करता है, लेकिन यह एल्गोरिदम को अमान्य इंडिपेंडेंट सेट बनाने के लिए मजबूर नहीं करता है।
स्केलिंग और सीमाएं:
- टेंसर नेटवर्क सिमुलेशन ने खुलासा किया कि एक्सपेक्टेशन वैल्यू की गणना करने की क्लासिकल लागत डेप्थ $p$ के साथ तेजी से (विशेष रूप से ट्री-लाइक स्ट्रक्चर के लिए $O(\exp(O(p)))$ ) बढ़ती है, जबकि क्वांटम हार्डवेयर की लागत $p$ के साथ पॉलिनोमियल रूप से (ऑल-टू-ऑल कनेक्टिविटी मानते हुए) या प्लेनर हार्डवेयर पर $O(\exp(p)^{1/2})$ के रूप में स्केल होती है। यह उस शासन (regime) का सुझाव देता जहाँ इन स्थानीय मात्राओं को कुशलतापूर्वक मूल्यांकन करने के लिए क्वांटम प्रोसेसर आवश्यक हो जाते हैं।

महत्व और दावे

यह शोध पत्र इस बात पर जोर देता है कि यह कार्य NISQ-युग की क्वांटम उपयोगिता (utility) के लिए एक व्यावहारिक मार्ग को दर्शाता है। QAOA को एक स्टैंडअलोन सॉल्वर के बजाय एक सब-रूटीन के रूप में पुनर्गठित करके, जो क्लासिकल ह्यूरिस्टिक्स को बढ़ाता है, लेखक शैलो सर्किट की सीमाओं और पैरामीटर ऑप्टिमाइज़ेशन की कठिनाई को दूर करते हैं।

महत्व के संबंध में मुख्य दावे इस प्रकार हैं:

मामूली क्वांटम संसाधन, महत्वपूर्ण लाभ: क्लासिकल रणनीतियों में मामूली क्वांटम संसाधनों (शैलो सर्किट, फिक्स्ड एंगल्स) का एकीकरण ऐसे परिणाम दे सकता है जो अकेले किसी भी विधि से बेहतर हों।
स्केलेबिलिटी: रैखिक-समय स्केलिंग इस दृष्टिकोण को हजारों नोड्स जैसी बड़ी समस्याओं के लिए वर्तमान और निकट भविष्य के हार्डवेयर पर व्यवहार्य बनाती है।
मजबूती (Robustness): हाइब्रिड प्रकृति अंतर्निहित मजबूती प्रदान करती है; शोर समाधान की वैधता (इंडिपेंडेंट सेट बाधा) को बनाए रखते हुए केवल ह्यूरिस्टिक मार्गदर्शन की गुणवत्ता को प्रभावित करता है।
सामान्यीकरण (Generalizability): लेखक सुझाव देते हैं कि यह नॉन-वेरिएशनल, क्वांटम-एन्हांस्ड प्रतिमान स्वाभाविक रूप से अन्य स्पार्स-ग्राफ कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन समस्याओं (जैसे MaxCut, Minimum Vertex Cover) के लिए विस्तार योग्य है जहाँ स्थानीय संरचना प्रमुख होती है।

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