🔢 mathematics

Symmetry-based quantum algorithms for open-shop scheduling with hard constraints

यह शोध पत्र क्वांटम कंप्यूटिंग के लिए ओपन-शॉप शेड्यूलिंग समस्याओं में कठिन बाधाओं (hard constraints) को एनकोड करने के लिए एक समरूपता-आधारित (symmetry-based) दृष्टिकोण प्रस्तुत करता है, जो एक नवीन वेरिएशनल एल्गोरिदम का प्रस्ताव देता है जो अनुकूलतम समाधानों तक निश्चित रूप से पहुँचने की गारंटी देने के लिए व्यवहार्यता-संरक्षण क्रमचय समूहों (feasibility-preserving permutation groups) का लाभ उठाता है और केवल एक द्विघातीय (quadratic) संख्या में मापदंडों को अनुकूलित करता है।

मूल लेखक: Lennart Binkowski, Gereon Koßmann, Christian Tutschku, René Schwonnek

प्रकाशित 2026-05-18

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

CC BY 4.0

मूल लेखक: Lennart Binkowski, Gereon Koßmann, Christian Tutschku, René Schwonnek

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

मुख्य चित्र: क्वांटम पहेली बॉक्स (The Quantum Puzzle Box)

कल्पना कीजिए कि आप एक लॉजिस्टिक्स मैनेजर हैं जो डिलीवरी ट्रकों के बेड़े (fleet) का शेड्यूल बनाने की कोशिश कर रहे हैं। आपके पास कामों की एक सूची (डिलीवरी) है, मशीनों का एक सेट (ट्रक) है, और एक समय सीमा (टाइम स्लॉट) है। नियम सख्त हैं:

हर काम को ठीक एक बार किया जाना चाहिए।
कोई भी ट्रक एक ही समय में दो जगहों पर नहीं हो सकता।
किसी भी टाइम स्लॉट में दो काम नहीं हो सकते।

इसे ओपन-शॉप शेड्यूलिंग प्रॉब्लम (OSSP) कहा जाता है। यह एक क्लासिक "कठिन" पहेली है। यदि आप इसे एक सामान्य कंप्यूटर के साथ हल करने की कोशिश करते हैं, तो इसमें बहुत समय लग सकता है क्योंकि गलत संयोजनों (combinations) की संख्या बहुत अधिक होती है।

इस शोध पत्र के लेखकों ने पूछा: क्या हम इसे तेजी से हल करने के लिए क्वांटम कंप्यूटर का उपयोग कर सकते हैं?

समस्या यह है कि वर्तमान क्वांटम कंप्यूटर अनाड़ी बच्चों की तरह हैं; वे आसानी से गलतियाँ करते हैं। यदि आप उनसे बस "सबसे अच्छा शेड्यूल ढूंढने" के लिए कहते हैं, तो वे अक्सर "निषिद्ध क्षेत्रों" (ऐसे शेड्यूल जो नियमों को तोड़ते हैं, जैसे एक ही समय में एक ट्रक को दो काम सौंपना) में भटक जाते हैं।

टीम का समाधान एक क्वांटम रोबोट बनाना है जो केवल "सुरक्षित पथ" पर चलना जानता है। उन्होंने एक नया एल्गोरिदम डिज़ाइन किया जो कंप्यूटर को कभी भी एक अवैध शेड्यूल पर विचार करने से भौतिक रूप से रोकता है।

मूल विचार: "सिमेट्री" (Symmetry) की कुंजी

उनके नुस्खे को समझने के लिए, लोगों से भरे एक कमरे की कल्पना करें (संभावित शेड्यूल)।

बुरे शेड्यूल: गलत जगहों पर खड़े लोग (नियम तोड़ना)।
अच्छे शेड्यूल: सही जगहों पर खड़े लोग।

अधिकांश क्वांटम एल्गोरिदम "बुरे" लोगों को कमरे से बाहर धकेलने की कोशिश करते हैं (जैसे जुर्माना लगाकर)। लेकिन यह अव्यवस्थित है। बुरे लोग अभी भी वहीं रह सकते हैं, या जुर्माना पर्याप्त रूप से मजबूत नहीं हो सकता है।

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

लेखकों ने एक गणितीय "ग्रुप" (नियमों का एक सेट) की खोज की जो सटीक रूप से बताता है कि आप नियमों को तोड़े बिना इन कामों को कैसे इधर-उधर व्यवस्थित कर सकते हैं। वे इसे फिजिबिलिटी-प्रिजर्विंग ग्रुप (Feasibility-Preserving Group) कहते हैं।

उपमा (Analogy):
एक रुबिक्स क्यूब की कल्पना करें।

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

नया एल्गोरिदम: "शफल" (Shuffle) मशीन

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

सुरक्षित शुरुआत: आप कंप्यूटर को एक वैध शेड्यूल (एक "सीड" समाधान) के साथ शुरू करते हैं।
मिक्सर: रैंडम शोर (noise) के बजाय, कंप्यूटर एक विशेष "मिक्सर" गेट लागू करता है। यह गेट एक 'शफल बटन' की तरह है जो केवल कामों को उन तरीकों से बदलता है जो गणितीय रूप से गारंटी देते हैं कि शेड्यूल वैध रहेगा।
गारंटी: लेखकों ने एक बहुत ही मजबूत गणितीय तथ्य सिद्ध किया है: यदि आपके पास $J$ काम हैं, तो आपको किसी भी संभावित वैध शेड्यूल (बेहतरीन वाले सहित) तक पहुँचने के लिए केवल एक विशिष्ट, प्रबंधनीय संख्या में "नॉब्स" (पैरामीटर्स) को एडजस्ट करने की आवश्यकता है।

"नॉब" (Knob) की उपमा:
कल्पना कीजिए कि आपके पास एक विशाल तिजोरी है जिसमें कॉम्बिनेशन लॉक लगा है।

पुराने क्वांटम तरीके: आपको अरबों रैंडम नंबरों को आजमाकर कॉम्बिनेशन का अनुमान लगाना पड़ता है। आप भाग्यशाली हो सकते हैं, लेकिन आप किसी डेड एंड (बंद रास्ते) में भी फंस सकते हैं।
यह तरीका: लेखकों ने नक्शा खोज लिया है। उन्होंने सिद्ध किया कि हर दरवाजे तक पहुँचने के लिए आपको केवल $J^3$ (लगभग कामों की संख्या का घन) विशिष्ट नॉब्स को घुमाने की आवश्यकता है। यह एक मास्टर की (master key) होने जैसा है जो हर दरवाजा खोल सकती है यदि आप सही क्रम में सही डायल घुमाते हैं।

उन्होंने वास्तव में क्या किया (प्रमाण)

यह पेपर केवल सिद्धांत की बात नहीं करता; उन्होंने इसका परीक्षण भी किया।

सिमुलेशन: उन्होंने एक क्लासिकल कंप्यूटर पर समस्या के एक छोटे संस्करण (4 काम, 2 मशीन) का सिमुलेशन किया।
- परिणाम: पुराना तरीका (जो बुरे शेड्यूल के लिए "जुर्माना" का उपयोग करता है) अच्छे समाधान खोजने में विफल रहा। वह "निषिद्ध क्षेत्रों" में फंस गया।
- परिणाम: उनका नया तरीका, जो सख्ती से "सुरक्षित पथ" पर रहता है, जल्दी से परफेक्ट समाधान खोजने में सफल रहा।
वास्तविक हार्डवेयर टेस्ट: उन्होंने समस्या का एक बहुत छोटा संस्करण (3 काम, 1 मशीन—मूल रूप से ट्रैवलिंग सेल्सपर्सन समस्या) लिया और उसे एक वास्तविक क्वांटम कंप्यूटर (IBM Q System One) पर चलाया।
- परिणाम: भले ही वास्तविक कंप्यूटर शोर वाला (static वाले रेडियो की तरह) था, उनका एल्गोरिदम फिर भी रैंडम चांस की तुलना में बेहतर समाधान खोजने में सक्षम रहा। इसने दिखाया कि "सुरक्षित पथ" का तर्क आज के अपूर्ण हार्डवेयर पर भी काम करता है।

निचोड़ (The Bottom Line)

यह पेपर क्वांटम कंप्यूटरों के लिए "गार्डरेल्स" (सुरक्षा घेरा/बाउंड्री) बनाने के बारे में है।

इस उम्मीद में कि कंप्यूटर सड़क पर बना रहेगा, उन्होंने कार को ही फिर से डिज़ाइन किया ताकि वह सड़क छोड़ ही न सके। शेड्यूलिंग समस्या की गणितीय सिमेट्री का उपयोग करके, उन्होंने एक ऐसा एल्गोरिदम बनाया जो:

कभी भी असंभव शेड्यूल पर विचार नहीं करता है।
एक विशिष्ट, सीमित संख्या में नॉब्स को घुमाकर परफेक्ट समाधान तक पहुँच सकता है।
आज की शोर वाली, अपूर्ण क्वांटम मशीनों पर भी मौजूदा तरीकों से बेहतर काम करता है।

उन्होंने अभी तक दुनिया के हर उद्योग के लिए इस समस्या को हल नहीं किया है, लेकिन उन्होंने इस विशिष्ट प्रकार की शेड्यूलिंग पहेली को हल करने के लिए एक नया, अधिक विश्वसनीय इंजन बनाया है।

तकनीकी सारांश: कठिन बाधाओं वाले ओपन-शॉप शेड्यूलिंग के लिए सममिति-आधारित क्वांटम एल्गोरिदम

समस्या विवरण
यह शोध पत्र ओपन-शॉप शेड्यूलिंग समस्या (OSSP) को संबोधित करता है, जो एक कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन समस्या है जहाँ $J$ कार्यों (jobs) को $M$ मशीनों में वितरित किया जाना है, जिनमें से प्रत्येक में $T$ समय स्लॉट हैं। बाधाएं यह अनिवार्य करती हैं कि प्रत्येक कार्य ठीक एक बार किया जाए और किसी भी मशीन-समय स्लॉट को एक से अधिक कार्य आवंटित न किया जाए। यह समस्या ट्रैवलिंग सेल्सपर्सन प्रॉब्लम (TSP) का एक सामान्यीकरण है, जहाँ $TSP = OSSP(1, T, T)$ है।

मुख्य चुनौती इन "कठिन बाधाओं" (hard constraints) को वेरिएशनल क्वांटम एल्गोरिदम (VQAs) में एनकोड करने में निहित है। अनकन्स्ट्रेंड समस्याओं (जैसे MAX-CUT) या "सॉफ्ट-कोडेड" बाधाओं (जहाँ अव्यवहारिकता को ऑब्जेक्टिव फंक्शन में दंडित किया जाता है) के विपरीत, OSSP के लिए अनुकूलन को सख्ती से व्यवहार्य उप-स्थान (feasible subspace) के भीतर रहना चाहिए। सॉफ्ट-कोडिंग अक्सर उप-इष्टतम अनुकूलन परिदृश्य या व्यवहार्यता संबंधी समस्याओं का कारण बनती है। हालाँकि क्वांटम अल्टरनेटिंग ऑपरेटर एंसेबल (QAOA) व्यवहार्यता-संरक्षण मिक्सर्स (feasibility-preserving mixers) के माध्यम से कठिन बाधाओं के लिए एक ढांचा प्रदान करता है, लेकिन शेड्यूलिंग समस्याओं के लिए मौजूदा निर्माण अक्सर हेयुरिस्टिक रहे हैं, जो अंतर्निहित सममिति संरचनाओं का पूर्ण उपयोग करने में विफल रहे हैं।

कार्यप्रणाली
लेखक OSSP की व्यवहार्यता संरचना का विश्लेषण करने के लिए ग्राफ थ्योरी के साथ मिलकर एक कठोर समूह-सैद्धांतिक (group-theoretic) दृष्टिकोण अपनाते हैं:

बाधा ग्राफ मॉडल (Constraint Graph Model): समस्या को एक बाधा ग्राफ $G=(V, E)$ में मैप किया गया है जहाँ वर्टिस (vertices) संभावित जॉब असाइनमेंट (बिट्स) का प्रतिनिधित्व करते हैं और किनारे (edges) उन बाधाओं का प्रतिनिधित्व करते हैं जो एक साथ असाइनमेंट को प्रतिबंधित करती हैं। समाधान आकार $J$ के स्वतंत्र सेटों (independent sets/cocliques) के अनुरूप होते हैं।
व्यवहार्यता-संरक्षण समूह ( $F$ ): लेखक उस समूह $F$ $F$ की पहचान करते हैं जो बिट-वैल्यू परम्यूटेशन का समूह है जो व्यवहार्य समाधानों को अन्य व्यवहार्य समाधानों में मैप करता है। वे सिद्ध करते हैं कि OSSP के लिए, यह समूह बाधा ग्राफ के ऑटोमॉर्फिज्म समूह, $\text{Aut}(G)$ $Aut (G)$ , के आइसोमोर्फिक है।
- "बिजी" केस ($MT = J$) के लिए, यह समूह व्रेथ प्रोडक्ट (wreath product) का एक हिस्सा है जिसमें सिमेट्रिक ग्रुप शामिल हैं।
- महत्वपूर्ण रूप से, वे प्रदर्शित करते हैं कि $F$ सभी व्यवहार्य समाधानों पर ट्रांजिटिवली (transitively) कार्य करता है। इसका अर्थ है कि किसी भी व्यवहार्य समाधान को $F$ के परम्यूटेशन के एक अनुक्रम के माध्यम से किसी भी अन्य समाधान में बदला जा सकता है।
एल्गोरिदम डिज़ाइन:
- QAOA विस्तार: वे $F$ के जनरेटरों (generators) से सीधे मिक्सर का निर्माण करके QAOA ढांचे को परिष्कृत करते हैं। चूंकि $F$ ट्रांजिटिवली कार्य करता है, इसलिए $F$ के तत्वों से प्राप्त मिक्सर यह गारंटी देते हैं कि संपूर्ण व्यवहार्य उप-स्थान सुलभ है।
- नया VQA (क्वांटम ग्रुप ऑप्टिमाइज़ेशन): बिजी OSSP इंस्टेंस के लिए, लेखक एक नया एल्गोरिदम प्रस्तावित करते हैं जो मानक फेज सेपरेटर को बायपास करता है। सिमेट्रिक ग्रुप $S_J$ (जो बिजी OSSP के समाधान स्थान का प्रतिनिधित्व करता है) में परम्यूटेशन को ट्रांसपोज़िशन (transpositions) के उत्पादों में विघटित करके, वे SWAP गेट्स का उपयोग करते हुए एक पैरामीटराइज्ड सर्किट का निर्माण करते हैं।
- पैरामीट्रेशन (Parameterization): एल्गोरिदम $J(J-1)/2$ ट्रांसपोज़िशन के विशिष्ट अपघटन का उपयोग करता है। प्रत्येक ट्रांसपोज़िशन को जॉब ब्लॉक्स के बीच विलगित (disjoint) SWAP गेट्स के उत्पाद के रूप में लागू किया जाता है।

प्रमुख योगदान

सैद्धांतिक लक्षण वर्णन: शोध पत्र OSSP के लिए व्यवहार्यता-संरक्षण समूह का पूर्ण लक्षण वर्णन प्रदान करता है, यह सिद्ध करते हुए कि यह बाधा ग्राफ के ऑटोमॉर्फिज्म समूह के आइसोमोर्फिक है और समाधान सेट पर इसके ट्रांजिटिव एक्शन को स्थापित करता है।
गारंटीकृत पहुंच (Guaranteed Reachability): जेनेरिक QAOA के विपरीत, जहाँ इष्टतम की पहुंच केवल अनंत सर्किट गहराई ( $p \to \infty$ ) की सीमा में ही गारंटीकृत होती है, प्रस्तावित VQA एक सख्त ऊपरी सीमा प्रदान करता है। लेखक सिद्ध करते हैं कि $O(J^3)$ (विशेष रूप से $J(J-1)/2$ ) पैरामीटर किसी भी व्यवहार्य समाधान, जिसमें ग्लोबल ऑप्टिमम भी शामिल है, तक निश्चितता के साथ पहुँचने के लिए पर्याप्त हैं।
कठिन-बाधा कार्यान्वयन: यह कार्य यह प्रदर्शित करने के लिए एक व्यवस्थित विधि प्रदान करता है कि कैसे मिक्सर को सख्ती से व्यवहार्य उप-स्थान को संरक्षित करने के लिए बनाया जा सकता है, जिससे सॉफ्ट-कोडिंग बाधाओं की कमियों से बचा जा सके।
हार्डवेयर कार्यान्वयन: लेखक एक $OSSP(1, 3, 3)$ इंस्टेंस (जो 3-सिटी TSP के बराबर है) के लिए एक वास्तविक क्वांटम डिवाइस (IBM Q System One) पर एल्गोरिदम लागू करते हैं और $OSSP(2, 2, 4)$ के लिए नॉइलेस सिमुलेशन करते हैं।

परिणाम

नॉइलेस सिमुलेशन ($OSSP(2, 2, 4)$): प्रस्तावित VQA, जो कठिन बाधाओं को हार्डकोड करता है, छह पुनरावृत्तियों (12 पैरामीटर को ऑप्टिमाइज़ करते हुए) के भीतर वैश्विक न्यूनतम (100% एप्रोक्सिमेशन रेशियो) तक सफलतापूर्वक पहुँच गया। इसके विपरीत, सॉफ्ट-कोडेड बाधाओं वाला एक मानक QAOA, सभी 18 पैरामीटर्स तक पहुँच होने के बावजूद, 30% से अधिक का एप्रोक्सिमेशन रेशियो प्राप्त करने में विफल रहा, क्योंकि छोटे व्यवहार्य उप-स्थान में एम्प्लीट्यूड को केंद्रित करना कठिन था।
वास्तविक हार्डवेयर ($OSSP(1, 3, 3)$): IBM Q System One पर, एल्गोरिदम ने प्रारंभिक अवस्था से बाहर निकलने और स्थानीय इष्टतम (local optimum) के साथ ओवरलैप बढ़ाने की क्षमता प्रदर्शित की। हालाँकि, लेखक नोट करते हैं कि हार्डवेयर शोर (noise) ने ग्लोबल ऑप्टिमम तक अभिसरण (convergence) को काफी हद तक अस्पष्ट कर दिया, जहाँ शोर वाला बैकग्राउंड सिग्नल पर हावी रहा। क्लासिकल नॉइसी सिमुलेशन ने बेहतर अभिसरण दिखाया, जो यह सुझाव देता है कि वर्तमान हार्डवेयर सीमाएँ (कोहेरेंस टाइम, गेट फिडेलिटी) प्राथमिक बाधाएँ हैं, न कि एल्गोरिदम का डिज़ाइन।

महत्व और दावे
शोध पत्र का दावा है कि इसका प्राथमिक महत्व VQAs में कठिन बाधाओं को हार्डकोड करने के लिए एक व्यवस्थित, सममिति-आधारित ढांचा प्रदान करने में है, जो हेयुरिस्टिक मिक्सर डिज़ाइन से आगे बढ़ता है। समस्या की व्यवहार्यता संरचना को ग्राफ ऑटोमॉर्फिज्म से जोड़कर, लेखक एक ऐसा एल्गोरिदम प्राप्त करते हैं जिसके पास एक सैद्धांतिक गारंटी है कि $O(J^3)$ पैरामीटर्स की बहुपद संख्या (polynomial number) पूरे समाधान स्थान को खोजने के लिए पर्याप्त है।

लेखक व्यावहारिक स्केलेबिलिटी के संबंध में विनम्र हैं। वे स्वीकार करते हैं कि हालांकि सैद्धांतिक पैरामीटर बाउंड मजबूत है, लेकिन इन पैरामीटर्स का व्यावहारिक अनुकूलन उच्च-आयामी स्थानों में "बेरेन प्लेटो" (barren plateaus) और स्थानीय मिनिमा की घातीय संख्या द्वारा बाधित होता है। इसके अलावा, वे स्पष्ट रूप से कहते हैं कि उनका दृष्टिकोण समानता बाधाओं (equality constraints/symmetries) पर निर्भर करता है और असमानता बाधाओं (जैसे नैपसैक समस्या) पर सीधे लागू नहीं हो सकता है जहाँ ऐसी सममितियाँ अनुपस्थित होती हैं। यह कार्य एक 'प्रूफ ऑफ प्रिंसिपल' के रूप में कार्य करता है कि शेड्यूलिंग समस्याओं के लिए अधिक कुशल और सैद्धांतिक रूप से सुदृढ़ क्वांटम एल्गोरिदम डिजाइन करने के लिए व्यवहार्यता-संरक्षण समूह संरचनाओं का लाभ उठाया जा सकता है, बशर्ते भविष्य के हार्डवेयर सुधार शोर और कनेक्टिविटी संबंधी मुद्दों को हल करें।

मुख्य चित्र: क्वांटम पहेली बॉक्स (The Quantum Puzzle Box)

मूल विचार: "सिमेट्री" (Symmetry) की कुंजी

नया एल्गोरिदम: "शफल" (Shuffle) मशीन

उन्होंने वास्तव में क्या किया (प्रमाण)

निचोड़ (The Bottom Line)

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