⚛️ quantum physics

Unfair Sampling of Quantum Annealing in Weighted Graph Bipartitioning Problems

यह अध्ययन प्रदर्शित करता है कि भारित ग्राफ द्विपक्षीयकरण (weighted graph bipartitioning) समस्याओं में दंड गुणांक (penalty coefficient) को बढ़ाने से व्यावहारिक परिस्थितियों में कम ग्राउंड-स्टेट संभावना के समझौते के बावजूद, अधिकांश उदाहरणों में क्वांटम एनीलिंग की सैंपलिंग निष्पक्षता (sampling fairness) में सामान्य रूप से सुधार होता है।

मूल लेखक: Shunta Ide, Shu Tanaka

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

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

CC BY 4.0

मूल लेखक: Shunta Ide, Shu Tanaka

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

मुख्य चित्र: एक समूह को विभाजित करने का सबसे अच्छा तरीका खोजना

कल्पना कीजिए कि आप एक पार्टी प्लानर हैं जो 12 दोस्तों के एक समूह को खेल के लिए दो समान टीमों में विभाजित करने की कोशिश कर रहे हैं। आप चाहते हैं कि टीमें पूरी तरह से संतुलित (50/50) हों, लेकिन आप उन लोगों के बीच झगड़ों की संख्या को भी कम करना चाहते हैं जो एक-दूसरे को नापसंद करते हैं।

यह एक कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन समस्या (combinatorial optimization problem) है। वास्तविक दुनिया में, समूह को विभाजित करने के कई अलग-अलग तरीके हो सकते हैं जिसके परिणामस्वरूप बिल्कुल एक ही "परफेक्ट" स्कोर प्राप्त होता है। इन्हें डिजेनरेट ग्राउंड स्टेट्स (degenerate ground states) कहा जाता है।

समस्या:
आपके पास एक सुपर-स्मार्ट कंप्यूटर (क्वांटम एनेलर - Quantum Annealer) है जिसे इन परफेक्ट विभाजनों को खोजने के लिए बनाया गया है। आदर्श रूप से, यदि समूह को विभाजित करने के चार परफेक्ट तरीके हैं, तो कंप्यूटर को प्रत्येक तरीके को ठीक 25% बार खोजना चाहिए। इसे फेयर सैंपलिंग (fair sampling) कहा जाता है।

हालाँकि, शोधकर्ताओं ने पाया कि कंप्यूटर पक्षपाती है। यह दो परफेक्ट विभाजनों को 40% बार, और अन्य दो को केवल 10% बार चुनने की प्रवृत्ति रखता है। यह एक ऐसे रेफरी की तरह है जो गुप्त रूप से एक टीम को दूसरी टीम से बेहतर मानता है, भले ही दोनों टीमें समान रूप से अच्छी हों। यह अनफेयर सैंपलिंग (unfair sampling) है।

समाधान: "पेनल्टी" नॉब (The "Penalty" Knob)

कंप्यूटर को "समान टीम आकार" के नियम का पालन करने के लिए मजबूर करने हेतु, वैज्ञानिक पेनल्टी मेथड (Penalty Method) नामक एक ट्रिक का उपयोग करते हैं।

कंप्यूटर के लक्ष्य को एक हाइकर (पर्वतारोही) के रूप में सोचें जो घाटी के सबसे निचले बिंदु (सबसे अच्छा समाधान) को खोजने की कोशिश कर रहा है।

उद्देश्य (The Objective): हाइकर सबसे गहरी घाटी खोजना चाहता है (झगड़ों को कम करना)।
प्रतिबंध (The Constraint): हाइकर को एक विशिष्ट पथ पर रहना चाहिए (टीमों को समान आकार में रखना)।

यदि हाइकर पथ से भटक जाता है (असमान टीमें), तो उसे एक "पेनल्टी" मिलती है। कंप्यूटर के कोड में, यह एक पेनल्टी कोएफिशिएंट (Penalty Coefficient) है (जिसे हम पेनल्टी नॉब कह सकते हैं)।

लो नॉब (Low Knob): पथ से भटकने पर दंड एक हल्की सी थपकी की तरह है।
हाई नॉब (High Knob): दंड आपके पैर पर एक विशाल पत्थर गिरने जैसा है।

शोधकर्ताओं ने क्या खोजा

टीम (शुनता इडे और शु तनाका) ने एक सरल प्रश्न पूछा: यदि हम पेनल्टी नॉब को घुमाकर बढ़ा दें, तो कंप्यूटर के विकल्पों की "निष्पक्षता" (fairness) में क्या बदलाव आता है?

उन्होंने एक सिमुलेशन और डी-वेव (D-Wave) द्वारा बनाए गए एक वास्तविक क्वांटम कंप्यूटर का उपयोग करके इसका परीक्षण किया। यहाँ उन्हें क्या पता चला:

1. ट्रेड-ऑफ (The "Speed vs. Accuracy" Dilemma - गति बनाम सटीकता का द्वंद्व)

जब उन्होंने पेनल्टी नॉब को ऊँचा (high) किया:

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

उपमा (Analogy): कल्पना कीजिए कि आप एक अंधेरे कमरे में एक विशिष्ट चाबी खोजने की कोशिश कर रहे हैं।

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

2. वास्तविक दुनिया का परीक्षण

उन्होंने वास्तविक डी-वेव मशीन (एक वास्तविक क्वांटम कंप्यूटर) पर इसका परीक्षण किया। भले ही वास्तविक कंप्यूटर शोर वाले और अपूर्ण होते हैं, वही पैटर्न बना रहा: पेनल्टी बढ़ाने से सैंपलिंग निष्पक्ष हुई, लेकिन परिणाम प्राप्त करना थोड़ा कठिन हो गया।

3. "ज्यादातर सच" का नियम (The "Mostly True" Rule)

उन्होंने अलग-अलग समूह के आकार (4 दोस्तों से लेकर 12 दोस्तों तक) के साथ हजारों परीक्षण किए।

परिणाम: लगभग 70% से 75% मामलों में, पेनल्टी नॉब बढ़ाने से सैंपलिंग अधिक निष्पक्ष हो गई।
कैच (The Catch): यह हर एक मामले में काम नहीं करता था। कभी-कभी, पेनल्टी को बहुत अधिक करने से चीजें और खराब हो गईं या कुछ भी नहीं बदला। लेकिन अधिकांश मामलों के लिए, "हाई पेनल्टी = फेयरर रिजल्ट्स" का नियम कायम रहा।

यह क्यों मायने रखता है?

आमतौर पर, वैज्ञानिक पेनल्टी नॉब को केवल यह सुनिश्चित करने के लिए ट्यून करते हैं कि कंप्यूटर नियमों का पालन करे (जैसे, "मुझे 3 लोगों और 9 लोगों की टीम न दें")। वे इसे नियमों के लिए एक साधारण ऑन/ऑफ स्विच की तरह मानते हैं।

यह शोध दिखाता है कि पेनल्टी नॉब वास्तव में निष्पक्षता के लिए एक डायल (dial for fairness) है।

यदि आपको केवल एक उत्तर चाहिए, तो आप परिणाम तेजी से पाने के लिए नॉब को कम रख सकते हैं।
यदि आपको सभी संभावित समाधानों की विविधता को समझने की आवश्यकता है (जैसे ड्रग डिस्कवरी या वित्तीय मॉडलिंग में जहाँ आपको सभी विकल्पों को देखने की आवश्यकता होती है), तो आपको यह सुनिश्चित करने के लिए नॉब को ऊपर करना चाहिए कि आप कंप्यूटर के पक्षपाती होने के कारण छिपे हुए समाधानों को मिस न कर दें।

निचोड़ (The Bottom Line)

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

यह एक पक्षपाती जज को यह कहने जैसा है, "यदि आप योग्य उम्मीदवारों की पूरी सूची में से नहीं चुनते हैं, तो आप बड़ी मुसीबत में पड़ जाएंगे।" जज निर्णय लेने में अधिक समय ले सकता है, लेकिन जब वह निर्णय लेगा, तो वह पूरी सूची से निष्पक्ष रूप से चयन करेगा।

भविwi कार्य (Future Work): शोधकर्ता स्वीकार करते हैं कि वे अभी तक पूरी तरह से नहीं समझते हैं कि यह क्यों होता है। वे भौतिकी (physics) में और गहराई से जाने की योजना बना रहे हैं ताकि वे इन क्वांटम कंप्यूटरों को और भी बेहतर तरीके से निष्पक्ष बनाने के तरीके खोज सकें, शायद केवल दंड जोड़ने के बजाय "खेल के नियमों" को पूरी तरह से बदलकर।

यहाँ शुनता इडे और शु तनाका के शोध पत्र "Unfair Sampling of Quantum Annealing in Weighted Graph Bipartitioning Problems" का विस्तृत तकनीकी सारांश दिया गया है।

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

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

यह समस्या प्रतिबंधित कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन समस्याओं (constrained combinatorial optimization problems) में विशेष रूप से गंभीर है, जहाँ बाधाओं को आमतौर पर पेनल्टी मेथड (penalty method) के माध्यम से लागू किया जाता है। इस पद्धति में, एक गुणांक $\mu$ के साथ ऑब्जेक्टिव हैमिल्टोनियन ( $H_{obj}$ ) में एक पेनल्टी टर्म ( $H_{const}$ ) जोड़ा जाता है। जबकि पेनल्टी गुणांक पारंपरिक रूप से व्यवहार्यता (feasibility) सुनिश्चित करने के लिए (अर्थात, एक वैध समाधान खोजने के लिए) ट्यून किया जाता है, डैजेनरेट ग्राउंड स्टेट्स के बीच सैंपलिंग फेयरनेस (sampling fairness) पर इसके विशिष्ट प्रभाव को अभी तक पूरी तरह से समझा नहीं गया है।

लेखक इस अंतराल की जांच करने के लिए वेटेड ग्राफ बाइपार्टीशनिंग प्रॉब्लम (GBP) को एक टेस्टबेड के रूप में उपयोग करते हैं। GBP एक ग्राफ के वर्टिसेस को दो समान आकार के उपसमूहों में विभाजित करने से संबंधित है ताकि कट वेट (cut weight) को कम किया जा सके, जो कि एक कठिन समानता बाधा (equality constraint) वाला प्रश्न है।

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

यह अध्ययन सैद्धांतिक सिमुलेशन और प्रयोगात्मक सत्यापन को संयोजित करने वाले एक बहुआयामी दृष्टिकोण का उपयोग करता है:

हैमिल्टोनियन फॉर्मूलेशन (Hamiltonian Formulation):
समस्या को एक आइसिंग हैमिल्टोनियन (Ising Hamiltonian) में मैप किया गया है। कुल समस्या हैमिल्टोनियन को इस प्रकार परिभाषित किया गया है:
$H_p = H_{obj} + \mu H_{const}$
जहाँ $H_{obj}$ कट वेट का प्रतिनिधित्व करता है, और $H_{const} = (\sum \sigma_i^z)^2$ समान-विभाजन बाधा को लागू करता है। पेनल्टी गुणांक को $\mu = \mu_{opt} + \mu_+$ के रूप में विघटित किया गया है, जहाँ $\mu_{opt}$ व्यवहार्यता के लिए आवश्यक न्यूनतम मान है, और $\mu_+$ अतिरिक्त पेनल्टी है।
संख्यात्मक सिमुलेशन (Numerical Simulations):
- QA डायनेमिक्स को सिम्युलेट करने के लिए QuTiP का उपयोग करके समय-निर्भर श्रोडिंगर समीकरण (time-dependent Schrödinger equation) को हल किया गया।
- सिंगल इंस्टेंस विश्लेषण (Single Instance Analysis): एनीलिंग समय ( $T$ ), पेनल्टी गुणांक ( $\mu_+$ ), और सैंपलिंग वितरण के बीच संबंध को लक्षणित करने के लिए एक विशिष्ट 6-स्पिन GBP इंस्टेंस का विश्लेषण किया गया।
- स्केलिंग विश्लेषण (Scaling Analysis): सिस्टम साइज $N \in \{4, 6, 8, 10, 12\}$ के लिए 100 रैंडमली जनरेटेड इंस्टेंस बनाए गए। अध्ययन ने $\mu$ की पूरी रेंज को कवर करने के लिए एक नॉर्मलाइज्ड पेनल्टी पैरामीटर $\lambda \in [0, 1]$ का उपयोग किया।
- मेट्रिक (Metric): ग्राउंड-स्टेट प्रोबेबिलिटी डिस्ट्रीब्यूशन के शैनन एंट्रॉपी ( $S$ ) का उपयोग करके सैंपलिंग फेयरनेस को मापा गया। $S = \log_2 D$ (जहाँ $D$ डैजेनेरेसी है) पूर्ण निष्पक्षता (perfect fairness) को दर्शाता है; कम मान पूर्वाग्रह (bias) को दर्शाते हैं।
प्रयोगात्मक सत्यापन (Experimental Validation):
- प्रयोग D-Wave Advantage2 System 1.13 पर किए गए।
- हार्डवेयर शोर और व्यवस्थित त्रुटियों को कम करने के लिए तकनीकों में पैरेलल एनीलिंग (Parallel Annealing) (400 विशिष्ट एम्बेडिंग्स का उपयोग करके) और स्पिन रिवर्सल ट्रांसफॉर्मेशन (SRT) (10 गेज ट्रांसफॉर्मेशन) शामिल थे।
- एनीलिंग समय को एडियाबेटिक रिजीम के करीब पहुँचने के लिए 200 $\mu$ s (डिफ़ॉल्ट से 10 गुना अधिक) पर सेट किया गया था।

3. मुख्य योगदान (Key Contributions)

पेनल्टी गुणांकों की व्यवस्थित जांच: यह शोध पत्र पहला है जो व्यवस्थित रूप से विश्लेषण करता है कि प्रतिबंधित QA में पेनल्टी गुणांक सैंपलिंग फेयरनेस को कैसे प्रभावित करता है, जो केवल व्यवहार्यता सुनिश्चित करने की इसकी पारंपरिक भूमिका से आगे बढ़ता है।
ट्रेड-ऑफ बनाम रिजीम डिपेंडेंस की पहचान: अध्ययन से पता चलता है कि पेनल्टी गुणांक का फेयरनेस पर प्रभाव एनीलिंग रिजीम पर निर्भर करता है:
- कम एनीलिंग समय (Short Annealing Times): पेनल्टी बढ़ाने से फेयरनेस में सुधार होता है लेकिन कुल ग्राउंड-स्टेट प्रोबेबिलिटी कम हो जाती है (एक ट्रेड-ऑफ)।
- एडियाबेटिक के करीब रिजीम (Near-Adiabatic Regimes): पेनल्टी बढ़ाने से ग्राउंड-स्टेट प्रोबेबिलिटी का त्याग किए बिना फेयरनेस में सुधार होता है।
हार्डवेयर सत्यापन: लेखकों ने पुष्टि की कि अनफेयर सैंपलिंग वास्तविक D-Wave हार्डवेयर पर भी बनी रहती है और उच्च पेनल्टी के साथ बढ़ती फेयरनेस का गुणात्मक रुझान (qualitative trend), थर्मल नॉइज़ के बावजूद, सही है।
स्केलिंग विश्लेषण: 12 स्पिन्स तक व्यापक स्केलिंग अध्ययन यह दर्शाता है कि हालांकि यह रुझान सार्वभौमिक (universal) नहीं है, फिर भी यह अधिकांश इंस्टेंस के लिए सत्य है।

4. मुख्य परिणाम (Key Results)

सिंगल इंस्टेंस व्यवहार (Single Instance Behavior):
- 4 डैजेनरेट ग्राउंड स्टेट्स वाले 6-स्पिन इंस्टेंस के लिए, $\mu_+$ बढ़ाने से सैंपलिंग बायस (sampling bias) कम हुआ।
- कम एनीलिंग समय ( $T \lesssim 10^3$ ) पर, उच्च $\mu_+$ ने एंट्रॉपी (फेयरनेस) को बढ़ाया लेकिन किसी भी ग्राउंड स्टेट को खोजने की कुल प्रोबेबिलिटी ( $P_{GS}$ ) को कम कर दिया।
- लंबे एनीलिंग समय ( $T \approx 10^4$ ) पर, $P_{GS}$ सभी $\mu_+$ के लिए इकाई (unity) के करीब रहा, और $\mu_+$ बढ़ाने से एंट्रॉपी निरंतर बढ़ी, जिससे ट्रेड-ऑफ प्रभावी रूप से समाप्त हो गया।
D-Wave हार्डवेयर परिणाम (D-Wave Hardware Results):
- D-Wave सिस्टम पर अनफेयर सैंपलिंग देखी गई, हालांकि सिमुलेशन की तुलना में इसका परिमाण कम था (संभवतः थर्मल रिलैक्सेशन और नॉइज़ के कारण)।
- एंट्रॉपी शुरू में $\mu_+$ के साथ थोड़ी बढ़ी, $\mu_+ \approx 0.4$ पर गिरी, और फिर से बढ़ी। महत्वपूर्ण रूप से, सिमुलेशन में जो स्टेट्स बायस्ड (biased) थे, वे हार्डवेयर पर भी बायस्ड रहे, जो बायस की संरचनात्मक प्रकृति की पुष्टि करता है।
- जैसे-जैसे $\mu_+$ बढ़ा, सैंपलिंग डिस्ट्रीब्यूशन अधिक यूनिफॉर्म (uniform) होता गया, भले ही $P_{GS}$ कम हो गया।
स्केलिंग विश्लेषण (N = 4 से 12):
- $N=4$ के लिए, सभी इंस्टेंस ने $\lambda$ के बावजूद फेयर सैंपलिंग दिखाई।
- बड़े $N$ के लिए, व्यवहार जटिल हो गया, जिसमें कुछ इंस्टेंस में नॉन-मोनोटोनिक एंट्रॉपी परिवर्तन देखे गए।
- मोनोटोनिक इंक्रीज रेट (Monotonic Increase Rate): टेबल I दिखाता है कि उन इंस्टेंस का अंश जहाँ एंट्रॉपी पेनल्टी गुणांक के साथ निरंतर बढ़ी:
  - $N=4$ : 100%
  - $N=6$ : 91%
  - $N=8$ : 74%
  - $N=10$ : 72%
  - $N=12$ : 74%
- बड़े सिस्टम के लिए यह दर लगभग 70–75% पर स्थिर हो जाती है, जो यह संकेत देती है कि पेनल्टी गुणांक बढ़ाने से अधिकांश मामलों में फेयरनेस में सुधार होता है, भले ही यह सार्वभौमिक न हो।

5. महत्व और भविष्य की दिशाएं (Significance and Future Directions)

पेनल्टी डिज़ाइन पर नया दृष्टिकोण: निष्कर्ष बताते हैं कि पेनल्टी गुणांक को केवल व्यवहार्यता के लिए ही नहीं, बल्कि सैंपलिंग डाइवर्सिटी के लिए एक कंट्रोल पैरामीटर के रूप में भी ट्यून किया जाना चाहिए।
सैद्धांतिक निहितार्थ: परिणाम सैद्धांतिक समझ में एक अंतर को उजागर करते हैं, विशेष रूप से प्रतिबंधित सेटिंग्स में डैजेनरेट पर्टरबेशन थ्योरी (degenerate perturbation theory) के संबंध में। बायस को चलाने वाला तंत्र अभी भी एक खुला प्रश्न है।
भविष्य का कार्य: लेखक शोर/थर्मल रिलैक्सेशन की मात्रात्मक जांच करने, बड़ी डैजेनेरेसी को एक्सप्लोर करने, अन्य प्रतिबंधित समस्याओं तक विश्लेषण का विस्तार करने, और ऐसे स्ट्रक्चर-अवेयर ड्राइवर्स (जैसे XY-मिक्सर या QAOA) का उपयोग करने का प्रस्ताव करते हैं जो स्वाभाविक रूप से बाधाओं को बनाए रखते हैं ताकि अनफेयर सैंपलिंग को समाप्त किया जा सके।

निष्कर्षतः, यह कार्य इस बात का अनुभवजन्य प्रमाण प्रदान करता है कि पेनल्टी गुणांक को बढ़ाना प्रतिबंधित क्वांटम एनीलिंग में अनफेयर सैंपलिंग को कम करने के लिए एक व्यवहार्य रणनीति है, जो समाधान विविधता में सुधार के लिए एक व्यावहारिक लीवर प्रदान करता है।