⚛️ quantum physics

An improved Quantum Max Cut approximation via matching

यह शोध पत्र क्वांटम मैक्स कट समस्या के लिए एक शास्त्रीय सन्निकटन एल्गोरिदम (approximation algorithm) प्रस्तुत करता है जो अधिकतम भारित मिलान (maximum weighted matching) का उपयोग करके अधिकतम दो क्वबिट्स की सरल उत्पाद अवस्थाओं (product states) को उत्पन्न करके 0.595 का सन्निकटन अनुपात प्राप्त करता है, जिससे पिछले सर्वोत्तम परिणामों से बेहतर प्रदर्शन होता है।

मूल लेखक: Eunou Lee, Ojas Parekh

प्रकाशित 2026-02-17

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

CC BY 4.0

मूल लेखक: Eunou Lee, Ojas Parekh

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

कल्पना कीजिए कि आप एक विशाल, अराजक पार्टी आयोजित करने की कोशिश कर रहे हैं जहाँ मेहमान छोटे, अदृश्य कण हैं जिन्हें क्विबिट्स (qubits) कहा जाता है। इस पार्टी का लक्ष्य सभी को इस तरह से "नाचने" के लिए प्रेरित करना है जिससे अधिकतम ऊर्जा उत्पन्न हो सके। क्वांटम भौतिकी की दुनिया में, इसे एक सिस्टम की अधिकतम ऊर्जा अवस्था (maximum energy state) खोजना कहा जाता है।

यह विशिष्ट क्वांटम पार्टी गेम क्वांटम मैक्स कट (Quantum Max Cut) है। यह कंप्यूटर साइंस के क्लासिक "मैक्स कट" गेम जैसा ही है, लेकिन इसमें केवल स्विचों को ऑन या ऑफ करने के बजाय, आपके मेहमान सुपरपोजिशन की अवस्थाओं में हो सकते हैं और यहाँ तक कि वे "एंटैंगल्ड" (एक स्पूकी कनेक्शन जहाँ दो कण एक इकाई की तरह व्यवहार करते हैं) भी हो सकते हैं।

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

यहाँ इस नए शोध पत्र का विवरण दिया गया है, जिसे सरल उपमाओं का उपयोग करके समझाया गया है:

1. पुराना तरीका: "परफेक्ट डांस" की समस्या

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

चुनौती: एक बहुत अच्छा स्कोर प्राप्त करने के लिए, इन एल्गोरिदम को एंटैंगल्ड स्टेट्स (entangled states) बनाने की आवश्यकता होती थी। कल्पना कीजिए कि आप एक ऐसा डांस कोरियोग्राफ करने की कोशिश कर रहे हैं जहाँ अतिथि A, अतिथि B का हाथ थामे हुए है, जो अतिथि C का हाथ थामे हुए है, पूरे कमरे में इस तरह से। यह सुंदर है, लेकिन इसे कैलकुलेट और निष्पादित करना अविश्वसनीय रूप से कठिन है।
स्कोर: पिछला सबसे अच्छा तरीका लगभग 56.2% पूर्ण ऊर्जा का गारंटीड स्कोर दे सकता था।

2. नया विचार: "जोड़ी बनाओ और बाकी को छोड़ दो"

लेखकों, यूनौ ली और ओजस पारेख ने एक बहुत अधिक सरल रणनीति आज़माने का निर्णय लिया। पूरे कमरे को कोरियोग्राफ करने के बजाय, उन्होंने पूछा: "क्या होगा यदि हम केवल उन मेहमानों की जोड़ी बना दें जो एक-दूसरे के साथ सबसे अच्छा तालमेल रखते हैं, और बाकी को आराम करने दें?"

उन्होंने कंप्यूटर साइंस की एक क्लासिक ट्रिक का उपयोग किया जिसे मैक्सिमम वेट मैचिंग (Maximum Weight Matching) कहा जाता है।

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

3. सफलता का रहस्य: यह बेहतर क्यों काम करता है?

आप सोच सकते हैं, "लेकिन बिना जोड़ी वाले मेहमानों को अनदेखा करना एक बुरा विचार लगता है!" और आमतौर पर, यह बुरा होता है। हालाँकि, लेखकों ने कुछ बहुत चतुर महसूस किया:

"मोनोगैमी" का नियम: क्वांटम भौतिकी में, एक नियम है जिसे "एंटैंगमेंट की मोनोगैमी" (Monogamy of Entanglement) कहा जाता है। यह मूल रूप से कहता है: यदि कण A, कण B के साथ बहुत गहरा एंटैंगल्ड है, तो वह कण C के साथ बहुत अधिक एंटैंगल्ड नहीं हो सकता।
अंतर्दृष्टि: लेखकों ने महसूस किया कि "परफेक्ट पेयरिंग" रणनीति (मैक्सिमम मैचिंग) स्वाभाविक रूप से इस नियम का सम्मान करती है। यदि आप सबसे मजबूत कनेक्शनों की जोड़ी बनाते हैं, तो आप भौतिकी के नियमों का उल्लंघन नहीं कर रहे हैं।
हाइब्रिड दृष्टिकोण: वे केवल जोड़ी बनाने पर निर्भर नहीं रहे। उन्होंने दो सिमुलेशन चलाए:
1. "प्रोडक्ट स्टेट" विधि: एक मानक विधि जहाँ सभी स्वतंत्र रूप से नाचते हैं (कोई हाथ नहीं थामते)।
2. "मैचिंग" विधि: नई विधि जहाँ हम सबसे अच्छे दोस्तों की जोड़ी बनाते हैं।
- विजेता: वे बस उन दो परिणामों में से चुनते हैं जो उच्च ऊर्जा स्कोर देते हैं।

4. परिणाम: एक नया रिकॉर्ड

इन दो सरल विचारों को मिलाकर, उन्होंने एक नया रिकॉर्ड तोड़ देने वाला स्कोर हासिल किया:

पुराना सर्वश्रेष्ठ: ~56.2% (सामान्य ग्राफ के लिए)।
नया सर्वश्रेष्ठ: 59.5%।

यह एक बड़ी बात है क्योंकि:

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

बड़ी तस्वीर

इसे एक टूटी हुई मशीन को ठीक करने की कोशिश के रूप में देखें।

पुराना दृष्टिकोण: आप हर गियर, स्प्रिंग और तार को एक साथ समझने की कोशिश करते हैं ताकि एक सटीक प्रतिलिपि बनाई जा सके। यह कठिन है, और आप केवल 56% मशीन को काम करते हुए पाते हैं।
नया दृष्टिकोण: आप मशीन को देखते हैं, सबसे महत्वपूर्ण दो गियरों को ढूंढते हैं और उन्हें पूरी तरह से एक साथ ठीक करते हैं। आप अन्य गियर्स को ढीला छोड़ देते हैं। फिर, आप उस दूसरे सरल फिक्स के साथ तुलना करते हैं। आप सबसे अच्छे को चुनते हैं।
आश्चर्य: यह "आलसी" दृष्टिकोण वास्तव में जटिल दृष्टिकोण से बेहतर काम करता है, और 59.5% दक्षता प्राप्त करता है।

यह क्यों मायने रखता है?
यह साबित करता है कि कभी-कभी, क्वांटम समस्याओं को हल करने के लिए आपको क्वांटम जादूगर होने की आवश्यकता नहीं होती है। सरल, चतुर क्लासिकल ट्रिक्स (जैसे कि सबसे अच्छी जोड़ियाँ खोजना) जटिल क्वांटम सिमुलेशन से बेहतर प्रदर्शन कर सकते हैं। यह हमें "क्वांटम एडवांटेज" को समझने की दिशा में एक कदम और करीब लाता है—क्लासिकल कंप्यूटरों की तुलना में समस्याओं को तेज़ी से या बेहतर तरीके से हल करना।

यहाँ एन्नौ ली (Eunou Lee) और ओजस पारेख (Ojas Parekh) के शोध पत्र "An improved Quantum Max Cut approximation via Maximum Matching" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या की परिभाषा: क्वांटम मैक्स कट (QMC)

यह शोध पत्र क्वांटम मैक्स कट (QMC) समस्या को संबोधित करता है, जो एक $n$ -qubit सिस्टम पर परिभाषित एक क्वांटम अनुकूलन बेंचमार्क है।

उद्देश्य: एक भारित ग्राफ $G=(V, E, w)$ दिया गया है, हमें एक क्वांटम अवस्था $|\psi\rangle$ ज्ञात करनी है जो एंटीफेरोमैग्नेटिक हाइजनबर्ग हैमिल्टोनियन (antiferromagnetic Heisenberg Hamiltonian) की ऊर्जा को अधिकतम करती है:
$H = \sum_{(i,j) \in E} w_{ij} \frac{I - X_iX_j - Y_iY_j - Z_iZ_j}{4}$
जहाँ $X_i, Y_i, Z_i$ क्रमशः क्वबिट $i$ पर कार्य करने वाले पाउली मैट्रिसेस (Pauli matrices) हैं।
जटिलता: सटीक अधिकतम ऊर्जा अवस्था खोजना QMA-hard है। इसलिए, लक्ष्य ऐसे शास्त्रीय सन्निकटन एल्गोरिदम (classical approximation algorithms) डिजाइन करना है जो एक ऐसी क्वांटम अवस्था का विवरण आउटपुट करें जिसकी ऊर्जा गारंटीकृत रूप से इष्टतम ऊर्जा ( $\lambda_{\max}(H)$ ) के एक निश्चित अंश ( $\alpha$ ) के बराबर हो।
संदर्भ: पिछले एल्गोरिदम आमतौर पर गोएलमैन-विलियमसन फ्रेमवर्क (Goemans-Williamson framework) पर निर्भर करते हैं: समस्या को सेमीडेफिनेट प्रोग्राम (SDP) में ढीला (relax) करना, उसे हल करना, और फिर समाधान को एक व्यवहार्य क्वांटम अवस्था में "राउंड" (round) करना।

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

लेखक एक नया शास्त्रीय सन्निकटन एल्गोरिदम प्रस्तावित करते हैं जो SDP-राउंडिंग दृष्टिकोणों से अलग है। यह SDP वेक्टर्स से सीधे प्राप्त जटिल एंटैंगलमेंट संरचनाओं पर निर्भर रहने के बजाय, एंटैंगल्ड अवस्थाएँ उत्पन्न करने के लिए मैक्सिमम वेट मैचिंग (Maximum Weight Matching - MWM) का उपयोग करता है।

एल्गोरिदम (Algorithm 1)

एल्गोरिदम दो संभावित अवस्थाओं की गणना करता है और उच्च ऊर्जा वाली अवस्था को आउटपुट के रूप में देता है:

प्रोडक्ट स्टेट ( $\rho_1$ ):
- लेवल-2 क्वांटम लासेरे (Lasserre) SDP को हल करता है।
- सिंगल-क्वबिट पाउलीज़ ( $v(X_i), v(Y_i), v(Z_i)$ ) के अनुरूप वेक्टर्स निकालता है।
- एक प्रोडक्ट स्टेट (1-qubit अवस्थाओं का टेंसर उत्पाद) उत्पन्न करने के लिए घरीबियन-पारेख राउंडिंग (Gharibian-Parekh rounding) तकनीक (रैंडमाइज्ड राउंडिंग) लागू करता है।
मैचिंग स्टेट ( $\rho_2$ ):
- अवस्था निर्माण के लिए SDP समाधान को अनदेखा करता है।
- इनपुट ग्राफ $G$ पर मैक्सिमम वेट मैचिंग (MWM) समस्या को हल करता है (जैसे, एडमंड्स एल्गोरिदम का उपयोग करके)।
- एक ऐसी अवस्था का निर्माण करता है जहाँ:
  - मैचिंग $M$ में प्रत्येक एज $(i,j)$ के लिए, क्वबिट्स को सिंगलेट अवस्था (singlet state) (अधिकतम एंटैंगल्ड 2-qubit अवस्था): $\frac{|01\rangle - |10\rangle}{\sqrt{2}}$ सौंपा जाता है।
  - बिना मैच हुए क्वबिट्स के लिए, अवस्था मैक्सिमली मिक्स्ड 1-qubit अवस्था ( $I/2$ ) होती है।
- कुल अवस्था इन स्थानीय अवस्थाओं का टेंसर उत्पाद है।

सैद्धांतिक आधार

मुख्य नवाचार मैक्सिमम वेट मैचिंग के मान को लेवल-2 SDP समाधान से जोड़ने में निहित है, जिसमें बिना सीधे SDP वेक्टर से एंटैंगल्ड अवस्था बनाने की आवश्यकता नहीं होती।

एंटैंगलमेंट की मोनोगामी (Monogamy of Entanglement): लेखक SDP वेरिएबल्स (विशेष रूप से $h_{ij}^+$ , जो SDP समाधान से प्राप्त होता है) पर नियंत्रणों का लाभ उठाते हैं, जो एक एज पर एंटैंगलमेंट की "क्षमता" (potential) को दर्शाते हैं।
कन्वेक्सगामी (Convexgamy): वे एक नया सिद्धांत पेश करते हैं जिसे "एंटैंगलमेंट कन्वेक्सगामी" (entanglement convexgamy) कहा जाता है (लेम्मा 3), जो स्टार ग्राफ और ट्राइएंगल (त्रिकोण) पर एंटैंगलमेंट मानों के व्यवहार योग्य क्षेत्र पर पहले के रैखिक "मोनोगमी" (monogamy) बाउंड्स की तुलना में अधिक सटीक, गैर-रैखिक सीमाएँ प्रदान करता है।
LP रिलैक्सेशन: वे सिद्ध करते हैं कि SDP से प्राप्त मान $h_{ij}^+$ मैक्सिमम वेट मैचिंग के लीनियर प्रोग्रामिंग (LP) रिलैक्सेशन के बाधाओं (constraints) को $4/5$ के स्केलिंग फैक्टर तक संतुष्ट करते हैं। यह उन्हें मैक्सिमम वेट मैचिंग के भार को SDP ऑब्जेक्टिव के विरुद्ध बांधने की अनुमति देता है।

3. मुख्य योगदान

नया सन्निकटन अनुपात (Approximation Ratio): एल्गोरिदम 0.595 का सन्निकटन अनुपात प्राप्त करता है।
- यह सामान्य ग्राफों के लिए पिछले सर्वश्रेष्ठ (ली [10], अनुपात 0.562) से बेहतर है।
- यह ट्राइएंगल-फ्री ग्राफों के लिए पिछले सर्वश्रेष्ठ (किंग [8], अनुपात 0.582) से भी बेहतर है।
एंटैंगल्ड स्टेट जनरेशन का सरलीकरण:
- एंटैंगल्ड अवस्थाएँ आउटपुट करने वाले पिछले सर्वोत्तम QMC एल्गोरिदमों को पूर्ण लेवल-2 SDP समाधान पर आधारित जटिल राउंडिंग प्रक्रियाओं की आवश्यकता थी।
- यह एल्गोरिदम एंटैंगल्ड घटक ( $\rho_2$ ) को शुद्ध रूप से मैक्सिमम वेट मैचिंग के माध्यम से उत्पन्न करता है, जो एक शास्त्रीय कॉम्बिनेटोरियल समस्या है जिसे SDP समाधान से स्वतंत्र होकर बहुपद समय (polynomial time) में हल किया जा सकता है।
- SDP का उपयोग केवल प्रोडक्ट स्टेट ( $\rho_1$ ) के प्रदर्शन को बांधने और मैचिंग स्टेट के लिए सैद्धांतिक गारंटी सिद्ध करने के लिए किया जाता है।
सैद्धांतिक अंतर्दृष्टि (Convexgamy): यह शोध पत्र छोटे सबग्राफ (त्रिकोण और 2-एज स्टार) पर एंटैंगलमेंट के व्यवहार्य स्थान (feasible space) का वर्णन करने वाले कड़े गैर-रैखिक असमानताओं (लेम्मा 2 और लेम्मा 3) को व्युत्पन्न करता है, जिसे "एंटैंगलमेंट कन्वेक्सगामी" कहा जाता है। यह पिछले रैखिक मोनोगामी बाधाओं की तुलना में SDP व्यवहार्य क्षेत्र का अधिक सटीक चित्रण प्रदान करता है।

4. परिणाम और विश्लेषण

प्रदर्शन गारंटी: लेखक सिद्ध करते हैं कि किसी भी इनपुट ग्राफ के लिए, आउटपुट अवस्था $\sigma$ की ऊर्जा इस प्रकार होती है:
$\text{Energy}(\sigma) \geq 0.595 \times \lambda_{\max}(H)$
सुधार का तंत्र: सुधार इस तथ्य से आता है कि मैक्सिमम वेट मैचिंग एक "सुरक्षा जाल" (safety net) के रूप में कार्य करता है। यदि प्रोडक्ट स्टेट राउंडिंग ( $\rho_1$ ) खराब प्रदर्शन करता है (जो तब होता है जब SDP उच्च एंटैंगलमेंट का सुझाव देता है), तो मैचिंग स्टेट ( $\rho_2$ ) यह गारंटी देता है कि वह ऊर्जा के एक महत्वपूर्ण हिस्से को कैप्चर करेगा क्योंकि SDP वेरिएबल्स $h_{ij}^+$ एक फ्रैक्शनल मैचिंग बनाते हैं जो एक इंटीग्रल मैचिंग के करीब होती है।
दृष्टिकोण की इष्टतमता: लेखक नोट करते हैं कि यदि कोई LP को पूरी तरह से हल कर सके (स्केलिंग फैक्टर $\alpha=1$ ), तो इस विशिष्ट दृष्टिकोण की सैद्धांतिक सीमा 0.606 होगी। अतः, उनके परिणाम (0.595) और इस पद्धति की सैद्धांतिक सीमा के बीच का अंतर बहुत कम है।

5. महत्व

व्यावहारिकता: एल्गोरिदम गणनात्मक रूप से कुशल है। हालांकि यह एक SDP को हल करता है, लेकिन एंटैंगल्ड अवस्था का निर्माण करने के लिए SDP वेक्टर्स से जटिल क्वांटम स्टेट सिंथेसिस की आवश्यकता नहीं होती; यह मानक ग्राफ मैचिंग एल्गोरिदम पर निर्भर करता है।
वैचारिक परिवर्तन: यह इस धारणा को चुनौती देता है कि QMC के लिए उच्च-गुणवत्ता वाले सन्निकटन के लिए अनिवार्य रूप से SDP राउंडिंग से सीधे प्राप्त जटिल, वैश्विक रूप से एंटैंगल्ड एंसेट्ज़ (ansatzes) की आवश्यकता होती है। यह प्रदर्शित करता है कि सरल, संरचित अवस्थाएँ (सिंलेट्स और मिक्स्ड स्टेट्स के उत्पाद) अधिक जटिल एंटैंगल्ड अवस्थाओं से बेहतर प्रदर्शन कर सकती हैं यदि ग्राफ संरचना (मैचिंग) का सही ढंग से लाभ उठाया जाए।
भविष्य की दिशाएँ: यह शोध पत्र नए अनुसंधान के मार्ग खोलता है, जिसमें शामिल हैं:
- कठोर क्वांटम एल्गोरिदम (जैसे, VQE) खोजना जो शास्त्रीय सीमाओं से आगे निकल सकें।
- यह जांचना कि क्या लासेरे पदानुक्रम (Lasserre hierarchy) के उच्च स्तर बेहतर "कन्वेक्सगामी" संबंध प्रदान कर सकते हैं ताकि सन्निकटन अनुपात को सैद्धांतिक सीमा के करीब पहुँचाया जा सके।
- यह परिभाषित करना कि क्या किसी क्वांटम अनुकूलन समस्या को हल करने वाले "शास्त्रीय" एल्गोरिदम के स्पष्ट मानदंड हैं (शोध पत्र में परिभाषा 2)।

संक्षेप में, ली और पारेख मैक्सिमम वेट मैचिंग रणनीति के साथ SDP-आधारित प्रोडक्ट स्टेट राउंडिंग को जोड़कर क्वांटम मैक्स कट के लिए एक सुव्यवस्थित, उच्च-प्रदर्शन वाला एल्गोरिदम प्रस्तुत करते हैं, जो 0.595 का एक नया अत्याधुनिक (state-of-the-art) सन्निकटन अनुपात प्राप्त करता है और एंटैंगल्ड आउटपुट अवस्थाओं के निर्माण को काफी सरल बनाता है।