⚛️ क्वांटम भौतिकी

Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs

यह शोध पत्र प्रदर्शित करता है कि एक शास्त्रीय स्थानीय एल्गोरिदम, वेरिएशनल इटरेटिव रोटेशन एल्गोरिदम (VIRAL), बड़े-गर्थ (large-girth) वाले 3-रेगुलर ग्राफ पर मैक्स-कट अंश के लिए नए निचले स्तर (lower bounds) स्थापित करने में क्वांटम एप्रोक्सिमेट ऑप्टिमाइज़ेशन एल्गोरिदम (QAOA) से बेहतर प्रदर्शन करता है, जिससे यह बड़े-गर्थ 3-रेगुलर ग्राफ पर निचले स्तर को 0.912 से बढ़ाकर 0.9127 कर देता है और इस विशिष्ट क्षेत्र में क्वांटम लाभ की संभावनाओं को चुनौती देता है।

मूल लेखक: Flaviano Morone, Shivang Rawat, Dries Sels

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

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

CC BY 4.0

मूल लेखक: Flaviano Morone, Shivang Rawat, Dries Sels

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

कंप्यूटर विज्ञान के विशाल परिदृश्य में, समस्याओं का एक ऐसा वर्ग मौजूद है जो इतना जटिल है कि एक बड़े सिस्टम के लिए पूर्ण समाधान खोजना प्रभावी रूप से असंभव है, यहाँ तक कि सबसे शक्तिशाली सुपरकंप्यूटरों के साथ भी। ऐसी ही एक चुनौती "मैक्सिमम कट" (maximum cut) समस्या है। कल्पना कीजिए कि बिंदुओं का एक नेटवर्क है जो रेखाओं से जुड़ा हुआ है, जहाँ प्रत्येक बिंदु ठीक तीन अन्य बिंदुओं से जुड़ा है। लक्ष्य इन बिंदुओं को दो समूहों में इस प्रकार विभाजित करना है कि समूहों के बीच से गुजरने वाली रेखाओं की संख्या यथासं 가능 अधिक से अधिक हो। हालाँकि सबसे अच्छा विभाजन खोजना एक गणितीय दुःस्वप्न जैसा है, शोधकर्ता विशेष रूप से इस बात में रुचि रखते हैं कि विभिन्न विधियाँ इन नेटवर्कों पर कैसा प्रदर्शन करती हैं, खासकर जब नेटवर्क को छोटे लूप्स (loops) से बचने के लिए डिज़ाइन किया गया हो। 'लार्ज-गर्थ ग्राफ' (large-girth graph) के रूप में ज्ञात यह विशिष्ट प्रकार का नेटवर्क, गणना की सीमाओं के परीक्षण स्थल के रूप में कार्य करता है। दशकों से, यह प्रश्न बना हुआ है कि क्या क्वांटम कंप्यूटर, जो सूचना को संसाधित करने के लिए भौतिकी के विचित्र नियमों का उपयोग करते हैं, इन नेटवर्कों के लिए शास्त्रीय (classical) कंप्यूटरों की तुलना में काफी बेहतर समाधान खोज सकते हैं, जो मानक तर्क और बाइनरी स्विच पर निर्भर करते हैं।

शोधकर्ताओं की एक टीम ने अब उस प्रचलित आशा को चुनौती दी है कि क्वांटम कंप्यूटर इस विशिष्ट क्षेत्र में निर्णायक बढ़त रखते हैं। सरल, स्थानीय नियमों का उपयोग करके निर्णय लेने वाली एक शास्त्रीय विधि को परिष्कृत करके, उन्होंने प्रदर्शित किया है कि एक पारंपरिक एल्गोरिदम इन लूप-मुक्त नेटवर्कों पर विशिष्ट गहराई पर अग्रणी क्वांटम दृष्टिकोण से बेहतर प्रदर्शन कर सकता है। यह अध्ययन एक विशिष्ट एल्गोरिदम पर केंद्रित है जिसे 'वेरिएशनल इटरेटिव रोटेशन एल्गोरिदम' (Variational Iterative Rotation Algorithm) या VIRAL कहा जाता है। जबकि क्वांटम विधियाँ जटिल संभाव्यता तरंगों (probability waves) के माध्यम से कई संभावनाओं को एक साथ खोजने का प्रयास करती हैं, VIRAL नेटवर्क के प्रत्येक बिंदु को एक दिशा निर्दिष्ट करता है और फिर उनके निकटतम पड़ोसियों के प्रभाव के आधार पर इन दिशाओं को घुमाता है। यह प्रक्रिया परतों में होती है, जहाँ प्रत्येक परत बिंदुओं को अपने पड़ोसियों की नई स्थिति के अनुसार प्रतिक्रिया करने की अनुमति देती है। शोधकर्ताओं ने इस पद्धति का परीक्षण एक सैद्धांतिक नेटवर्क मॉडल पर किया है जिसमें कोई छोटे लूप नहीं हैं, जो एक ऐसी स्थिति है जो एल्गोरिदम को दूर के कनेक्शनों से भ्रमित हुए बिना पूरी तरह से स्थानीय जानकारी पर निर्भर रहने के लिए मजबूर करती है।

इस जांच के परिणाम सटीक और आश्चर्यजनक हैं। शोधकर्ताओं ने इन लूप-मुक्त नेटवर्कों में किसी भी बिंदु के स्थानीय दृश्य का प्रतिनिधित्व करने वाले एक सैद्धांतिक ट्री स्ट्रक्चर (tree structure) पर अपना शास्त्रीय एल्गोरिदम चलाया। उन्होंने एल्गोरिदम को तैंतीसवीं परत (p=32) की गहराई तक धकेला, जो पिछले परीक्षणों की तुलना में एक महत्वपूर्ण वृद्धि है। p=4 से p=32 तक के प्रत्येक परीक्षण किए गए सम गहराई (even depth) पर, शास्त्रीय विधि ने क्वांटम एप्रोक्सिमेट ऑप्टिमाइज़ेशन एल्गोरिदम (QAOA) से बेहतर परिणाम दिया, जो इन ग्राफों पर क्वांटम प्रदर्शन के लिए मानक रहा है। विशेष रूप से, शास्त्रीय एल्गोरिदम ने गारंटी दी कि वह क्वांटम पद्धति की तुलना में जोड़ने वाली रेखाओं के एक बड़े अंश को काट सकता है, और जैसे-जैसे परतों की जटिलता बढ़ती है, यह अंतर भी बढ़ता जाता है। परीक्षण की गई सबसे गहरी स्तर पर, शास्त्रीय विधि ने लगभग 91.27 प्रतिशत की सफलता दर प्राप्त की, जो इन प्रकार के नेटवर्कों के लिए पिछले सर्वश्रेष्ठ गारंटी से अधिक है। यह निष्कर्ष बताता है कि इस प्रकार की समस्याओं के लिए, क्वांटम लाभ—यह विचार कि क्वांटम कंप्यूटर वे चीजें कर सकते हैं जो शास्त्रीय कंप्यूटर नहीं कर सकते—इन विशिष्ट गहराइयों पर मौजूद नहीं है, कम से कम उस तरह से नहीं जैसा पहले सोचा गया था।

इस कार्य का महत्व इसमें निहित है कि यह क्या खारिज करता है जितना कि यह क्या सिद्ध करता है। कुछ समय से, यह माना जाता था कि एक निश्चित सीमा तक पहुँचने पर ये विशिष्ट नेटवर्क के लिए क्वांटम एल्गोरिदम का शास्त्रीय एल्गोरिदम पर स्पष्ट लाभ होता है। नया अध्ययन तीन-कनेक्टेड (three-connected) नेटवर्कों के मामले में, p=32 तक की सम गहराइयों के लिए इस विश्वास को स्पष्ट रूप से उलट देता है। शोधकर्ताओं ने केवल यह सुझाव नहीं दिया कि शास्त्रीय विधि प्रतिस्पर्धी थी; उन्होंने कठोर गणितीय सीमाएँ प्रदान कीं जो दर्शाती हैं कि शास्त्रीय विधि p=4 से आगे के प्रत्येक परीक्षण किए गए सम गहराई पर स्पष्ट रूप से श्रेष्ठ है। उन्होंने गणना की कि उनके परिणाम के सांख्यिकीय रूप से त्रुटिपूर्ण होने की संभावना दस मिलियन में एक से भी कम है। इसके अलावा, उन्होंने दिखाया कि यह शास्त्रीय दृष्टिकोण न केवल एक सैद्धांतिक जिज्ञासा है बल्कि एक रचनात्मक (constructive) भी है, जिसका अर्थ है कि यह एक स्पष्ट, चरण-दर-चरण रेसिपी प्रदान करता है जिसे एक मानक कंप्यूटर नेटवर्क के आकार के साथ रैखिक (linear) समय में प्राप्त करने के लिए पालन कर सकता है।

यह खोज इस समझ को नया आकार देती है कि क्वांटम कंप्यूटर कहाँ लाभ दे सकते हैं। अध्ययन इंगित करता है कि जटिल क्वांटम उतार-चढ़ाव, जो क्वांटम कंप्यूटरों को शक्ति देते हैं, हमेशा एक आवश्यक संसाधन नहीं होते हैं। इस विशिष्ट परिदृश्य में, सरल, शास्त्रीय बीजों (seeds)—अनिवार्य रूप से एल्गोरिदम के लिए यादृच्छिक शुरुआती बिंदु—द्वारा प्रदान की गई यादृच्छिकता, क्वांटम पद्धति से बेहतर समाधान तक पहुँचने के लिए पर्याप्त थी। शोधकर्ताओं ने पाया कि जैसे-जैसे उन्होंने अधिक परतें जोड़ीं, शास्त्रीय एल्गोरिदम का प्रदर्शन बेहतर होता गया, जिससे इन नेटवर्कों के लिए सैद्धांतिक अधिकतम संभव मान की ओर का अंतर कम होता गया। जबकि एक स्थानीय एल्गोरिदम जो प्राप्त कर सकता है उसकी सटीक सीमा अज्ञात है, नया डेटा शास्त्रीय कंप्यूटिंग के साथ संभव मानी जाने वाली निचली सीमा को पहले से कहीं अधिक ऊँचा उठा देता है। यह कार्य एक अनुस्मारक के रूप में कार्य करता है कि कम्प्यूटेशनल सर्वोच्चता की दौड़ में, सबसे परिष्कृत उपकरण हमेशा सबसे प्रभावी नहीं होते हैं, और कभी-कभी, एक अच्छी तरह से ट्यून की गई शास्त्रीय रणनीति सबसे उन्नत क्वांटम मशीनरी को भी मात दे सकती है।

तकनीकी सारांश: क्वांटम लाभ कहाँ है? बड़े-गर्थ वाले 3-रेगुलर ग्राफ्स पर Max-Cut के लिए नए क्लासिकल लोअर बाउंड्स

समस्या की परिभाषा
यह शोध पत्र किसी भी 3-रेगुलर ग्राफ में काटे जा सकने वाले किनारों (edges) के अधिकतम अंश, जिसे $M_g$ द्वारा दर्शाया गया है, को निर्धारित करने की समस्या का समाधान करता है। यहाँ $g$ गर्थ (सबसे छोटे चक्र की लंबाई) है। मात्रा $M_g$ को कम से कम $g$ गर्थ वाले सभी 3-रेगुलर ग्राफ्स पर अधिकतम कट अंश के इन्फिमम (infimum) के रूप में परिभाषित किया गया है। जबकि एसिम्प्टोटिक लिमिट $\lim_{g\to\infty} M_g$ ज्ञात रूप से एक संकीर्ण विंडो ( $0.912 \le \lim M_g \le 0.92386$ ) में स्थित है, सटीक लोअर बाउंड अभी भी अज्ञात है।

इस कार्य का मुख्य केंद्र स्थानीय क्लासिकल एल्गोरिदम और क्वांटम एप्रोक्सिमेट ऑप्टिमाइज़ेशन एल्गोरिदम (QAOA) के बीच तुलना है। पिछले शोध ने स्थापित किया था कि $g \ge 16$ गर्थ वाले 3-रेगुलर ग्राफ्स के लिए, डेप्थ- $p$ वाला QAOA, प्रमाणित गारंटी के साथ सर्वोत्तम ज्ञात क्लासिकल लोकल एल्गोरिदम से बेहतर प्रदर्शन करता है। इसने मध्यम गर्थ पर स्थानीय एल्गोरिदम के लिए एक संभावित "क्वांटम एडवांटेज" (क्वांटम लाभ) का सुझाव दिया था। लेखक यह जांचते हैं कि क्या यह लाभ तब भी बना रहता है जब उसी सैद्धांतिक सेटिंग पर एक अधिक शक्तिशाली क्लासिकल लोकल एल्गोरिदम लागू किया जाता है।

कार्यप्रणाली (Methodology)
लेखक विशिष्ट ज्यामितीय संरचना पर वेरिएशनल इटरेटिव रोटेशन एल्गोरिदम (VIRAL) का मूल्यांकन करते हैं, जो एक क्लासिकल लोकल एल्गोरिदम है।

एल्गोरिद्मिक फ्रेमवर्क: VIRAL प्रत्येक वर्टेक्स (vertex) को एक क्लासिकल यूनिट वेक्टर (स्पिन) असाइन करता है। $p$ लेयर्स के दौरान, ये स्पिन अपने पड़ोसियों के $z$ -घटकों से प्राप्त स्थानीय क्षेत्रों (local fields) द्वारा निर्धारित रोटेशन का उपयोग करके सिंक्रोनस रूप से अपडेट किए जाते हैं। अपडेट नियम है:
$s_i(n+1) = R_x(\beta_n) R_z(\gamma_n h_i(n)) s_i(n)$
जहाँ $h_i(n) = \sum_{j \in \partial i} s^z_j(n)$ है। समरूपता (symmetry) को तोड़ने के लिए प्रक्रिया को रैंडम "सीड्स" $\epsilon_i \in \{-1, +1\}$ के साथ इनिशियलाइज़ किया जाता है, जो रेगुलर ग्राफ्स पर एक गैर-तुच्छ (non-trivial) कट उत्पन्न करने के लिए महत्वपूर्ण है। $p$ लेयर्स के बाद, कट पार्टीशन निर्धारित करने के लिए स्पिन को थ्रेशोल्ड किया जाता है।
लोकल नेबरहुड विश्लेषण: लेखक इस गुण का लाभ उठाते हैं कि $g \ge 2p+2$ गर्थ वाले ग्राफ पर, किसी किनारे का रेडियस- $p$ नेबरहुड एक परिमित ट्री (finite tree) होता है (विशेष रूप से, एक किनारा जिससे जुड़े दो वर्टेक्स, जो गहराई $p$ के पूर्ण बाइनरी ट्री से जुड़े होते हैं)। चूंकि एल्गोरिदम लोकल है, इसलिए एक किनारे के कट होने की प्रायिकता केवल इस ट्री के भीतर मौजूद रैंडम सीड्स पर निर्भर करती है।
बाउंड्स का निर्धारण: परिमित रैंडम ग्राफ्स पर VIRAL चलाने के बजाय (जिनमें छोटे चक्र हो सकते हैं जो $M_g$ के सख्त लोअर बाउंड्स को अमान्य कर देते हैं), लेखक इस डेप्थ- $p$ ट्री पर अपेक्षित कट अंश, $c_{\text{VIRAL}}(p)$ , की सीधे गणना करते हैं। $M_g$ की परिभाषा के अनुसार, यदि कोई लोकल एल्गोरिदम ट्री पर एक कट अंश $c$ प्राप्त करता है, तो वह $g \ge 2p+2$ गर्थ वाले किसी भी 3-रेगुलर ग्राफ के लिए कम से कम $c$ का कट अंश सुनिश्चित करता है। अतः, $M_g \ge c_{\text{VIRAL}}(p)$ ।
गणना और सांख्यिकी: VIRAL के मापदंडों को रैंडम 3-रेगुलर ग्राफ्स पर प्री-ट्रेन किया गया था (जैसा कि संदर्भ [15] में वर्णित है) और उन्हें स्थिर रखा गया। लेखकों ने $p=32$ तक प्रत्येक सम गहराई (even depth) $p$ के लिए $10^7$ स्वतंत्र सीड कॉन्फ़िगरेशन के नमूने लेकर $c_{\text{VIRAL}}(p)$ का अनुमान लगाया। $p=2$ के लिए, मान को सभी $2^{14}$ कॉन्फ़िगरेशन की गणना करके निकाला गया। सांख्यिकीय लोअर बाउंड्स ( $L$ ) को 99.99999% कॉन्फिडेंस लेवल पर कैलकुलेट किया गया।

मुख्य परिणाम
यह अध्ययन $M_g$ के लिए ऐसे कठोर लोअर बाउंड्स प्रस्तुत करता है जो पिछले रिकॉर्ड्स को पीछे छोड़ देते हैं:

QAOA से श्रेष्ठता: प्रत्येक सम गहराई $p \ge 4$ के लिए, VIRAL ट्री वैल्यू $c_{\text{VIRAL}}(p)$ , संदर्भ [4] में रिपोर्ट किए गए संगत QAOA बाउंड्स से अधिक है। सुधार की सीमा 0.005 से 0.011 के बीच है।
क्लासिकल वेक्टर एल्गोरिदम से श्रेष्ठता: VIRAL सभी डेप्थ $p \ge 4$ पर थॉम्पसन, पारेख और मारवाह (TPM) [8] के स्पष्ट वेक्टर एल्गोरिदम से भी बेहतर प्रदर्शन करता है।
गर्थ रेंज का विस्तार: परिणाम गर्थ की उस रेंज को बढ़ाते हैं जहाँ सुधरे हुए लोअर बाउंड्स ज्ञात हैं, जो $g=36$ (पिछले QAOA परिणामों की सीमा) से बढ़कर $g=66$ तक पहुँच जाते हैं।
नया एसिम्प्टोटिक लोअर बाउंड: $g=66$ (जो $p=32$ के अनुरूप है) पर, लेखक 99.99999% कॉन्फिडेंस लेवल पर $M_{66} \ge 0.91271$ का एक कठोर लोअर बाउंड प्राप्त करते हैं। यह $\lim_{g\to\infty} M_g$ के लिए ज्ञात एसिम्प्टोटिक लोअर बाउंड को 0.912 से बढ़ाकर 0.9127 कर देता है।
अभिसरण व्यवहार (Convergence Behavior): प्रदर्शन में वृद्धि ( $c_{\text{VIRAL}}(p) - c_{\text{VIRAL}}(p-2)$ ) $p=32$ पर भी घट रही है, जो इंगित करता है कि $p \to \infty$ की सीमा अभी तक प्राप्त नहीं हुई है, लेकिन एल्गोरिदम सैद्धांतिक ऊपरी सीमा 0.92386 की ओर अभिसरित (converging) हो रहा है।

महत्व और दावे
यह शोध दावा करता है कि मध्यम गर्थ वाले 3-रेगुलर ग्राफ्स पर Max-Cut के लिए QAOA का जो स्पष्ट "क्वांटम एडवांटेज" दिखता है, वह वास्तव में तुलना के लिए उपयोग किए गए विशिष्ट क्लासिकल एल्गोरिदम का एक आर्टिफैक्ट (artifact) है। रैंडम सीड्स का उपयोग करके एक क्लासिकल एल्गोरिदम, VIRAL को नियोजित करके—जो सेमी-क्लासिकल डायनेमिक्स के शोर (noise) की नकल करने के लिए रैंडम सीड्स का उपयोग करता है—लेखक यह प्रदर्शित करते हैं कि क्लासिकल मेथड्स संबंधित ट्री स्ट्रक्चर पर हर डेप्थ $p \ge 4$ पर QAOA से बेहतर प्रदर्शन कर सकते हैं।

लेखक निष्कर्ष निकालते हैं कि 3-रेगुलर ग्राफ्स पर Max-Cut के विशिष्ट मामले के लिए, क्वांटम फ्लक्चुएशन (जैसा कि QAOA में उपयोग किया जाता है) रैंडम सीड्स द्वारा संचालित क्लासिकल डायनेमिक्स की तुलना में कोई संसाधन लाभ (resource advantage) प्रदान नहीं करते हैं। पिछले अध्ययनों में देखा गया "क्वांटम एडवांटेज" तब गायब हो जाता है जब क्लासिकल बेसलाइन को अनुकूलित (optimize) किया जाता है। यह कार्य स्थापित करता है कि इस विशिष्ट रिजीम (regime) में वह लाभ मौजूद नहीं है, हालांकि लेखक यह भी नोट करते हैं कि क्या यह उच्च डिग्री या $k \ge 3$ (Max- $k$ -Cut) के लिए भी सत्य है, यह एक खुला प्रश्न है। ये परिणाम रचनात्मक (constructive) हैं, जो इन बाउंड्स को प्राप्त करने के लिए किनारों की संख्या के सापेक्ष लीनियर टाइम में चलने वाला एक एल्गोरिदम प्रदान करते हैं।

इसी तरह के और पेपर