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

Simulating Gaussian boson sampling on graphs in polynomial time

यह शोध पत्र यह प्रदर्शित करता है कि गॉसियन बोसन सैंपलिंग और ग्राफ पर बोसन सैंपलिंग से संबंधित विशिष्ट वितरण, जिनका व्यावहारिक अनुप्रयोगों में व्यापक रूप से उपयोग किया जाता है, उन्हें शास्त्रीय रूप से बहुपद समय (polynomial time) में कुशलतापूर्वक नमूनाबद्ध (sample) किया जा सकता है, जिससे इन परिदृश्यों के लिए घातांकीय क्वांटम गति (exponential quantum speedup) की संभावना समाप्त हो जाती है।

मूल लेखक: Konrad Anand, Zongchen Chen, Mary Cryan, Graham Freifeld, Leslie Ann Goldberg, Heng Guo, Xinyuan Zhang

प्रकाशित 2026-11-09

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

CC BY 4.0

मूल लेखक: Konrad Anand, Zongchen Chen, Mary Cryan, Graham Freifeld, Leslie Ann Goldberg, Heng Guo, Xinyuan Zhang

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

क्वांटम भौतिकी की विचित्र दुनिया में, बोसोन नामक कण होते हैं जो उन तरीकों से व्यवहार करते हैं जैसा कोई भी रोजमर्रा की वस्तु कभी नहीं कर सकती। जब वैज्ञानिक इन कणों को दर्पणों और बीम स्प्लिटर के एक जटिल नेटवर्क के माध्यम से भेजते हैं, तो वे परिणामों का एक ऐसा पैटर्न बनाते हैं जिसकी भविष्यवाणी करना अविश्वसनीय रूप से कठिन होता है। बोसान सैंपलिंगिंग (boson sampling) के रूप में ज्ञात यह सेटअप, लंबे समय से यह सिद्ध करने का एक आशाजनक तरीका माना जाता रहा है कि क्वांटम कंप्यूटर वे चीजें कर सकते हैं जो साधारण कंप्यूटर सरल ही नहीं कर सकते। उम्मीद यह रही है कि जहां एक क्वांटम मशीन इन पैटर्न को पलक झपकते ही उत्पन्न कर सकती है, वहीं एक क्लासिकल कंप्यूटर को इन्हें समझने में ब्रह्मांड की आयु से अधिक समय बिताने की आवश्यकता होगी। इन दोनों प्रकार की मशीनों के बीच का यह संभावित अंतर जिसे शोधकर्ता "क्वांटम एडवांटेज" (quantum advantage) कहते हैं, एक ऐसी उपलब्धि है जो कंप्यूटिंग शक्ति के एक नए युग का संकेत देगी।

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

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

टीम ने दिखाया कि यह क्लासिकल विधि किसी भी ग्राफ के लिए काम करती है, चाहे वह कितना भी सघन या जटिल क्यों न हो, और वह भी एक ऐसे समय में जो इनपुट के आकार के साथ 'पॉलीनोमियल' (polynomial) दर से बढ़ता है। व्यावहारिक शब्दों में, इसका अर्थ यह है कि जैसे-जैसे समस्या बड़ी होती जाती है, उसे हल करने में लगने वाला समय एक प्रबंधनीय दर से बढ़ता है, न कि एक असंभव कार्य में बदल जाता है। यह खोज सीधे उस प्रश्न को संबोधित करती है कि क्या ये क्वांटम मशीनें उन ग्राफ समस्याओं के लिए घातांकीय गति (exponential speedup) प्रदान करती हैं जिन्हें हल करने के लिए उन्हें डिज़ाइन किया गया है। लेखक निष्कर्ष निकालते हैं कि इन विशिष्ट अनुप्रयोगों के लिए, क्वांटम मशीन वह विशाल लाभ प्रदान नहीं करती है जिसकी उम्मीद की गई थी, क्योंकि एक क्लासिकल कंप्यूटर भी उसी गति से वही काम कर सकता है।

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

इस खोज के निहितार्थ क्वांटम कंप्यूटिंग के क्षेत्र के लिए महत्वपूर्ण हैं। यह सुझाव देता है कि एक स्पष्ट क्वांटम एडवांटेज प्रदर्शित करने का मार्ग पहले की तुलना में अधिक संकीर्ण हो सकता है, कम से कम उन अनुप्रयोगों के लिए जिनका वर्तमान में अनुसरण किया जा रहा है। शोधकर्ताओं ने यह दावा नहीं किया कि क्वांटम कंप्यूटर बेकार हैं; बल्कि, उन्होंने दिखाया कि इन ग्राफ वितरणों से नमूना लेने के विशिष्ट कार्य के लिए, क्वांटम बढ़त मौजूद नहीं है। उनका प्रमाण कठोर है और सभी संभावित ग्राफों को कवर करता है, जिससे इस विचार की कोई गुंजाइश नहीं बचती कि बाद में उनके तरीके को बदलने के लिए एक तेज़ क्लासिकल एल्गोरिदम मिल सकता है। इसके बजाय, उन्होंने दिखाया है कि वह क्लासिकल तरीका पहले से ही मौजूद है और कुशल है।

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

तकनीकी सारांश: ग्राफ पर गॉसियन बोसॉन सैंपलिंग का बहुपद समय में अनुकरण (Simulating)

समस्या विवरण
यह शोध पत्र बोसॉन सैंपलिंग (BS) और गॉसियन बोसॉन सैंपलिंग (GBS) से संबंधित वितरणों (distributions) की कम्प्यूटेशनल जटिलता को संबोधित करता है। जबकि आरोंसन और अर्किपोव [1] ने एक मॉडल के रूप में BS का प्रस्ताव दिया था, जिसमें यह माना गया है कि स्थायी (permanent) एंटी-कन्सन्ट्रेशन और स्थायी के अनुमानों के आधार पर, सटीक आउटपुट वितरण से शास्त्रीय सैंपलिंग (classical sampling) कठिन मानी जाती है (जो पॉलीनोमियल हाइरार्की को ध्वस्त कर सकती है)। इसी तरह, GBS, जो विशिष्ट फोटॉन स्रोत लागतों से बचने के लिए स्क्वीज़्ड स्टेट्स (squeezed states) का उपयोग करता है, कठिन ग्राफ समस्याओं जैसे कि परफेक्ट मैचिंग्स की गिनती, डेंसएस्ट सबग्राफ खोजना और ग्राफ आइसोमॉर्फिज्म को हल करने के लिए प्रस्तावित किया गया है।

मुख्य खुला प्रश्न जिसका समाधान किया गया है, वह यह है कि क्या ग्राफ पर GBS वितरण, विशेष रूप से $\mu_{GBS,G}$ से संबंधित वितरण, से सैंपलिंग करने के लिए कुशल शास्त्रीय एल्गोरिदम मौजूद हैं, जहाँ $\mu_{GBS,G}$ का मान $c^{2|S|} \text{PM}(S)^2$ के समानुपाती है (जहाँ $\text{PM}(S)$ प्रेरित उपग्राफ $G[S]$ में परफेक्ट मैचिंग्स की संख्या है)। पिछले कार्य [12] ने केवल बहुत घने (dense) ग्राफों के लिए एक तेज़ एल्गोरिदम प्रदान किया था, और ओह एट अल. [13] ने एक थोड़े अलग वितरण (जो $\text{PM}(S)$ के बजाय $\text{PM}(S)^2$ के समानुपाती है) के लिए एक शास्त्रीय एल्गोरिदम प्रस्तावित किया था, जिससे गैर-ऋणात्मक (non-negative) GBS का मामला खुला रह गया था।

कार्यप्रणाली (Methodology)
लेखक एक रिडक्शन रणनीति (reduction strategy) का उपयोग करते हैं जो लक्षित सैंपलिंग वितरणों को ग्राफ में भारित परफेक्ट मैचिंग्स (weighted perfect matchings) की समस्या में मैप करती है। वे जेरम और सिनक्लेयर [14] तथा जेरम, सिनक्लेयर और विगोडा [17] द्वारा विकसित मार्कोव चेन मोंटे कार्लो (MCMC) एल्गोरिदम का लाभ उठाते हैं, जो विशिष्ट स्थितियों के तहत परफेक्ट मैचिंग्स के कुशल अनुमानित सैंपलिंग की अनुमति देते हैं।

गैर-ऋणात्मक बोसॉन सैंपलिंग के लिए (Theorem 1.3):
लेखक एक दिए गए गैर-ऋणात्मक वास्तविक आव्यूह (matrix) $A$ से एक द्विपक्षीय ग्राफ (bipartite graph) $G$ का निर्माण करते हैं। इस निर्माण में वर्टेक्स सेट्स $L_1, L_2$ और $R_1, R_2$ बनाना शामिल है, जिसमें किनारों (edges) को $A$ के प्रविष्टियों (entries) द्वारा भारित किया जाता है। विशिष्ट किनारे भारों के साथ इस निर्मित ग्राफ से एक परफेक्ट मैचिंग को सैंपल करके, $R_1$ में मैच किए गए वर्टेक्स का मार्जिनल वितरण बोसॉन सैंपलिंग वितरण $\mu_{BS}$ का सन्निकटन (approximate) करता है। अनुमान त्रुटि (approximation error) को एक पैरामीटर $k$ (वर्टेक्स की कॉपियों की संख्या) द्वारा नियंत्रित किया जाता है, जिसे पर्याप्त रूप से बड़ा ( $O(n^2/\varepsilon)$ ) चुना जाता है।
ग्राफ पर गॉसियन बोसॉन सैंपलिंग के लिए (Theorem 1.1):
लेखक GBS वितरण $\mu_{GBS,G}(S) \propto c^{2|S|} \text{PM}(S)^2$ को परिभाषित करते हैं। इसे सैंपल करने के लिए, वे इनपुट ग्राफ $G$ और एक किनारे का कार्टेशियन उत्पाद (Cartesian product) निर्मित करते हैं, जिसे $G \square K_2$ कहा जाता है।

निर्माण: $G \square K_2$ में $G$ की दो कॉपियाँ ( $G$ और $G'$ ) और उनके संगत वर्टेक्स को जोड़ने वाले किनारे शामिल हैं।
भारण (Weighting): $G$ और $G'$ की कॉपियों के भीतर के किनारों (सेट्स $E$ और $E'$ ) को $c^2$ भार दिया जाता है, जबकि कॉपियों को जोड़ने वाले किनारों (सेट $E_0$ ) को भार $1$ दिया जाता है।
रिडक्शन: $G \square K_2$ में एक परफेक्ट मैचिंग एक उपसमुच्चय $S \subseteq V$ को प्रेरित करती है (वे वर्टेक्स जो अपने ही कॉपी के भीतर मैच किए गए हैं)। प्रेरित होने वाले विशिष्ट सेट $S$ की प्रायिकता यह दिखाने के लिए है कि वह $c^{2|S|} \text{Haf}(A_S)^2$ के समानुपाती है, जो प्रेरित उपग्राफ के लिए $c^{2|S|} \text{PM}(S)^2$ के बराबर है।
दक्षता शर्त (Efficiency Condition): जेरम-सिनक्लेयर एल्गोरिदम के लिए यह आवश्यक है कि निकट-पूर्ण मैचिंग्स (near-perfect matchings) और पूर्ण मैचिंग्स का अनुपात एक बहुपद (polynomial) द्वारा सीमित हो। इसे सुनिश्चित करने के लिए, लेखक एक नया भार फलन $\lambda'$ (जिसे $4n^2$ द्वारा स्केल किया गया है) परिभाषित करते हैं और सिद्ध करते हैं कि इस नए भारण के तहत निकट-पूर्ण मैचिंग्स के कुल भार का अनुपात ( $Z'_{n-1}$ ) पूर्ण मैचिंग्स के कुल भार ( $Z'_n$ ) से बंधा हुआ है। यह सुनिश्चित करने के लिए कि मार्कोव चेन बहुपद समय में मिक्स (mix) हो जाए, यह सिद्ध किया गया है कि $Z'_{n-1} \le Z'_n/2$ है। यह लेम्मा 4.2 से प्राप्त किया गया है, जो स्थापित करता है कि मूल भारों के तहत $Z_{n-1} < 2n^2 Z_n$ है, जो मैचिंग बहुपद की लॉग-कॉन्केविटी (log-concavity) और AM-GM असमानता का उपयोग करता है।

मुख्य योगदान और परिणाम
लेखक दो मुख्य प्रमेय प्रस्तुत करते हैं जो बहुपद-समय शास्त्रीय एल्गोरिदम स्थापित करते हैं:

प्रमेय 1.1 (ग्राफ पर GBS): एक एल्गोरिदम मौजूद है जो, एक ग्राफ $G$ और एक वास्तविक पैरामीटर $c > 0$ दिया जाने पर, कुल भिन्नता दूरी (total variation distance) में $\mu_{GBS,G}$ के $\varepsilon$ -निकट वितरण से सैंपल करता है। इसका रनिंग टाइम $O(\bar{c}mn^4 \log^2(nc/\varepsilon))$ है, जहाँ $m=|E|$ , $n=|V|$ , और $\bar{c} = \max\{1, c\}$ । यह परिणाम सभी ग्राफों के लिए मान्य है, न कि केवल घने ग्राफों के लिए, और किसी भी धनात्मक वास्तविक $c$ के लिए।
प्रमेय 1.3 (गैर-ऋणात्मक बोसॉन सैंपलिंग): एक एल्गोरिदम मौजूद है जो, एक दिए गए गैर-ऋणात्मक वास्तविक आव्यूह $A$ (जहाँ $A$ अनिवार्य रूप से एक ट्रंकेटेड यूनिटरी मैट्रिक्स नहीं है) के लिए, बोसॉन सैंपलिंग वितरण $\mu_{BS}$ से $\varepsilon$ -निकट वितरण से सैंपल करने के लिए $O(m^7 n^{14} \varepsilon^{-7} \log^4(mn/\varepsilon))$ समय में कार्य करता है।

महत्व और दावे
लेखक दावा करते हैं कि उनके परिणाम यह प्रदर्शित करते हैं कि क्वांटम एल्गोरिदम $\mu_{GBS,G}$ वितरण से सैंपलिंग करने पर आधारित अनुप्रयोगों के लिए घातांकीय गति (exponential speedup) प्रदान नहीं करते हैं। चूंकि कई प्रस्तावित GBS अनुप्रयोग (जैसे, ग्राफ आइसोमॉर्फिज्म, परफेक्ट मैचिंग्स की गिनती) इस विशिष्ट वितरण से सैंपलिंग करने पर निर्भर करते हैं, इसलिए एक बहुपद-समय शास्त्रीय सैंपलर का अस्तित्व यह दर्शाता है कि ये विशिष्ट कार्य मानक GBS मॉडल के तहत क्वांटम लाभ (quantum advantage) प्रदर्शित नहीं करते हैं।

लेखक उल्लेख करते हैं कि हालांकि जेरम-सिनक्लेयर-विगोडा एल्गोरिदम सामान्य बोसॉन सैंपलिंग (जहाँ इनपुट मैट्रिक्स जटिल प्रविष्टियों वाला एक ट्रंकेटेड यूनिटरी मैट्रिक्स है) के लिए सीधे तौर पर लागू नहीं है, उनका निर्माण सैंपलिंग समस्या को जटिल भारित मैट्रिसेस के स्थायी (permanent) के सन्निकटन में बदल देता है। चूंकि स्थायी का सन्निकटन आम तौर पर NP-hard है, इसलिए सामान्य बोसण सैंपलिंग का शास्त्रीय अनुकरण कठिन बना हुआ है। हालांकि, गैर-ऋणात्मक मैट्रिसेस और ग्राफ-आधारित GBS वितरण के विशिष्ट मामले के लिए, लेखकों ने दिखाया है कि कुशल शास्त्रीय अनुकरण संभव है।

यह कार्य स्वयं को पिछले दृष्टिकोणों (जैसे, झांग एट अल. [12]) से अलग करता है क्योंकि यह केवल घने ग्राफों के लिए ही नहीं, बल्कि सभी ग्राफों के लिए लागू है, और कार्टेशियन उत्पाद निर्माण का उपयोग करके एक सरल, तेज़ एल्गोरिदम का उपयोग करता है।

तकनीकी सारांश: ग्राफ पर गॉसियन बोसॉन सैंपलिंग का बहुपद समय में अनुकरण (Simulating)

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