⚛️ quantum physics

A QUBO Formulation for the Generalized LinkedIn Queens and Takuzu/Tango Game

यह शोध पत्र लिंक्डइन क्वीन्स, ताकुज़ु और टैंगो जैसे लॉजिक पज़ल्स के सामान्य संस्करणों को हल करने के लिए एक बहुमुखी QUBO सूत्रीकरण प्रस्तुत करता है, साथ ही नए शतरंज-आधारित समस्याओं को भी पेश करता है और क्वांटम अनिलिंग या QAOA के माध्यम से क्वांटम हार्डवेयर पर निष्पादन के लिए मॉडल को अनुकूलित करता है।

मूल लेखक: Alejandro Mata Ali, Edgar Mencia

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

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

CC BY 4.0

मूल लेखक: Alejandro Mata Ali, Edgar Mencia

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

कल्पना कीजिए कि आप एक मास्टर पज़ल डिज़ाइनर हैं जो एक बहुत ही विशिष्ट, सुपर-फास्ट रोबोट को लॉजिक गेम्स हल करना सिखाने की कोशिश कर रहे हैं। यह पेपर वास्तव में एक "निर्देश पुस्तिका" (instruction manual) है जिसे QUBO (Quadratic Unconstrained Binary Optimization) नामक एक विशेष कोड में लिखा गया है। सोचिए कि QUBO एक सार्वभौमिक भाषा है जिसे क्वांटम कंप्यूटर समझते हैं, जहाँ खेल के हर नियम को एक गणितीय "ऊर्जा लागत" (energy cost) में बदल दिया जाता है। रोबोट का लक्ष्य टुकड़ों का वह विन्यास (arrangement) खोजना है जिसके परिणामस्वरूप सबसे कम ऊर्जा (शून्य लागत) प्राप्त हो, जो कि एक आदर्श समाधान (perfect solution) को दर्शाता है।

यहाँ रोजमर्रा की उपमाओं (analogies) का उपयोग करके पेपर के मुख्य विचारों का विवरण दिया गया है:

1. मूल अवधारणा: "ऊर्जा" का खेल (The Core Concept: The "Energy" Game)

लेखक लोकप्रिय लॉजिक पहेलियों को फिर से लिख रहे हैं ताकि एक क्वांटम कंप्यूटर उन्हें हल कर सके।

रूपक (Metaphor): एक पहाड़ी परिदृश्य की कल्पना करें जहाँ पहेली का हर संभावित विन्यास मानचित्र पर एक बिंदु है। एक "खराब" विन्यास (जहाँ नियम टूट जाते हैं) एक ऊँची पर्वत चोटी है। एक "आदर्श" विन्यास एक गहरी घाटी है। QUBO फॉर्मूला एक मानचित्र है जो क्वांटम कंप्यूटर को ठीक-ठीक बताता है कि पहाड़ियाँ कितनी ढालू हैं। कंप्यूटर "नीचे की ओर लुढ़कता" (rolls downhill) है जब तक कि वह सबसे गहरी घाटी न खोज ले, जो कि समाधान है।

2. क्वीन्स गेम्स (LinkedIn और N-Queens)

क्लासिक N-Queens समस्या आपसे शतरंज के बोर्ड पर $N$ रानियों (queens) को इस तरह रखने के लिए कहती है कि वे एक-दूसरे पर हमला न कर सकें।

पुराना नियम: रानियाँ एक ही पंक्ति (row), कॉलम या किसी भी विकर्ण रेखा (diagonal line) को साझा नहीं कर सकतीं।
LinkedIn ट्विस्ट: पेपर एक नए संस्करण (LinkedIn Queens) को देखता है जहाँ विकर्ण वाला नियम "नरम" (softer) है। रानियाँ तब एक-दूसरे पर हमला नहीं कर सकतीं जब वे विकर्ण रूप से एक-दूसरे के बिल्कुल बगल में हों, लेकिन वे दूर स्थित रानियों को अनदेखा कर सकती हैं। साथ ही, बोर्ड को रंगीन क्षेत्रों में विभाजित किया गया है, और आपको प्रत्येक क्षेत्र में ठीक एक रानी रखनी होगी।
पेपर का योगदान: लेखकों ने एक लचीला "नुस्खा" (QUBO formulation) बनाया है जो इसे संभाल सकता है:
- मानक N-Queens।
- LinkedIn के नरम नियम।
- अनियमित बोर्ड आकार (जैसे कि कोनों से गायब कोनों वाला बोर्ड)।
- डोनट की तरह लिपटे हुए बोर्ड (Toroidal), जहाँ एक टुकड़ा दाईं ओर से बाहर निकलने पर बाईं ओर से पुनः प्रकट होता है।
- "टेंट्स एंड ट्रीज़" (Tents & Trees) गेम: उन्होंने अपने नुस्खे को एक ऐसे खेल के लिए अनुकूलित किया जहाँ आपको पेड़ों के बगल में टेंट लगाने होते हैं बिना किसी टेंट को एक-दूसरे को (विकर्ण रूप से भी) छुए।

3. "चेस पीस" का विस्तार (The "Chess Piece" Expansion)

लेखकों ने महसूस किया कि उनका नुस्खा केवल रानियों (Queens) के लिए नहीं था। उन्होंने इसे किसी भी शतरंज के मोहरे के लिए सामान्यीकृत किया।

कलर्ड चेस पीस प्रॉब्लम (The Coloured Chess Piece Problem): एक ऐसे बोर्ड की कल्पना करें जहाँ अलग-अलग रंग के क्षेत्रों में ठीक एक मोहरा होना चाहिए। मोहरे हाथी (Rooks), ऊँट (Bors) या घोड़े (Knights) हो सकते हैं, और उनके चलने के तरीके अलग-अलग होते हैं। लक्ष्य उन्हें एक-दूसरे को खतरे में डाले बिना अधिक से अधिक रखना है।
मैक्स चेस पीसेस प्रॉब्लम (The Max Chess Pieces Problem): यहाँ, लक्ष्य बस बोर्ड को अधिक से अधिक मोहरों से भरना है बिना उन्हें एक-दूसरे पर हमला करने दिए। लेखकों ने अपने गणितीय फॉर्मूले में एक "पुरस्कार" (reward) जोड़ा है: हर बार जब आप सफलतापूर्वक एक मोहरा रखते हैं, तो ऊर्जा थोड़ी कम हो जाती है, जो कंप्यूटर को बोर्ड भरने के लिए प्रोत्साहित करती है।

4. ताकुज़ु और टैंगो गेम्स (The Takuzu and Tango Games)

ये ग्रिड भरने वाले खेल हैं (जैसे सुडोकू की तरह लेकिन 0s और 1s, या सूरज और चंद्रमा के साथ)।

नियम:
1. प्रत्येक पंक्ति और कॉलम में 0s और 1s की संख्या समान होनी चाहिए।
2. आप एक पंक्ति में तीन एक जैसे प्रतीक नहीं रख सकते (कोई "000" या "111" नहीं)।
3. Tango (LinkedIn का संस्करण): कोशिकाओं (cells) के बीच विशेष प्रतीक जोड़ता है। एक "=" का अर्थ है कि दोनों कोशिकाएं समान होनी चाहिए; एक "x" का अर्थ है कि वे भिन्न होनी चाहिए।
4. क्लासिक Takuzu: इसमें एक कठिन नियम जोड़ता है कि कोई भी दो पंक्तियाँ एक जैसी नहीं हो सकतीं, और कोई भी दो कॉलम एक जैसे नहीं हो सकते।
पेपर की सफलता (Breakthrough):
- उन्होंने Tango के लिए एक सटीक QUBO नुस्खा और Takuzu के स्थानीय नियमों के लिए बनाया।
- कठिन हिस्सा: क्लासिक Takuzu में "कोई समान पंक्ति नहीं" वाला नियम क्वांटम कंप्यूटरों के लिए कठिन है। लेखकों ने "विटनेस वेरिएबल्स" (Witness Variables) पेश करके इसे हल किया।
- उपमा (Analogy): कल्पना करें कि आपके पास लोगों की दो पंक्तियाँ हैं और आपको यह साबित करने की आवश्यकता है कि वे अलग हैं। आप प्रत्येक जोड़ी के लिए एक "गवाह" (witness) नियुक्त करते हैं। गवाह का काम एक ऐसा कॉलम ढूंढना है जहाँ दोनों पंक्तियाँ भिन्न हों। यदि गवाह अंतर नहीं ढूंढ पाता है, तो दंड (ऊर्जा) बढ़ जाता है। यह क्वांटम कंप्यूटर को अतिरिक्त "स्लैक" वेरिएबल्स (जो संसाधनों को बर्बाद करते हैं) की आवश्यकता के बिना क्लासिक Takuzu के "कोई समान पंक्ति नहीं" नियम को पूरी तरह से लागू करने की अनुमति देता है।

5. यह क्यों महत्वपूर्ण है (पेपर के अनुसार)

यह पेपर यह दावा नहीं करता है कि ये पहेलियाँ बीमारियों का इलाज करेंगी या शेयर बाजार की भविष्यवाणी करेंगी। इसके बजाय, यह दावा करता है कि यह एक सार्वभौमिक टूलकिट प्रदान करता है जो इन विशिष्ट लॉजिक पहेलियों को उस प्रारूप में बदलने के लिए है जिसे क्वांटम हार्डवेयर (जैसे D-Wave मशीनें) या क्वांटम एल्गोरिदम (जैसे QAOA) वास्तव में चला सकते हैं।

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

सारांश में:
लेखकों ने कई लोकप्रिय लॉजिक गेम्स (Queens, Tents, Takuzu, Tango) को लिया और एक एकल, अनुकूलन योग्य "अनुवाद मार्गदर्शिका" लिखी है जो उनके नियमों को उस भाषा में बदल देती है जिसे क्वांटम कंप्यूटर समझ सकते हैं। उन्होंने Takuzu पहेली के सबसे कठिन हिस्से को हल करने के लिए "विटनेस" का उपयोग करके एक चतुर ट्रिक का भी आविष्कार किया, जिससे यह सुनिश्चित हुआ कि उनका समाधान गणितीय रूप से पूर्ण है।

यहाँ एलेजांद्रो माता अलि और एडगर मेंसिया के शोध पत्र "A QUBO Formulation for the Generalized LinkedIn Queens and Takuzu/Tango Game" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या की परिभाषा

यह शोध पत्र क्वांटम एनीलिंग (Quantum Annealing) और क्वांटम एप्रोक्सिमेट ऑप्टिमाइज़ेशन एल्गोरिदम (QAOA) का उपयोग करके विभिन्न कॉम्बिनेटोरियल लॉजिक पहेलियों को हल करने की चुनौती को संबोधित करता है। इन एल्गोरिदम के लिए समस्याओं को क्वाड्रेटिक अनकन्स्ट्रेंड बाइनरी ऑप्टिमाइज़ेशन (QUBO) समस्याओं के रूप में तैयार करने की आवश्यकता होती है। लेखक कई विशिष्ट खेलों के लिए QUBO फॉर्मूलेशन को सामान्य बनाने और उन्हें एकीकृत करने पर ध्यान केंद्रित करते हैं:

N-Queens और LinkedIn Queens (LQueens): क्लासिक N-Queens समस्या (एक $N \times N$ बोर्ड पर $N$ रानियों को बिना एक-दूसरे पर हमला किए रखना) और इसका LinkedIn संस्करण, जो विकर्ण बाधाओं (diagonal constraints) को केवल "सन्निकट" (adjacent) विकर्णों तक सीमित करता है और रंगीन क्षेत्रों पर आधारित बाधाएं जोड़ता है (प्रत्येक रंगीन क्षेत्र में एक रानी)।
Takuzu (Binairo) और Tango: लॉजिक पहेलियाँ जिनमें ग्रिड को 0s और 1s (या सूर्य और चंद्रमा) से भरना शामिल है, जो कुछ बाधाओं के अधीन हैं: प्रत्येक पंक्ति/स्तंभ में 0s और 1s की समान संख्या, दो समान मानों का लगातार न होना, और (Takuzu के लिए) अद्वितीय पंक्तियाँ/स्तंभ। Tango, कोशिकाओं के बीच विशिष्ट समानता ("=") और असमानता ("x") बाधाओं को जोड़ता है।
विस्तार (Extensions): यह शोध पत्र Tents & Trees, Coloured Chess Piece Problems, और Max Chess Pieces Problem के लिए भी फॉर्मूलेशन पेश करता है।

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

मुख्य कार्यप्रणाली इन खेलों के तार्किक बाधाओं (logical constraints) को द्विघात दंड फलनों (quadratic penalty functions) में अनुवादित करने की है। लेखक यह सुनिश्चित करने के लिए कि सभी पद द्विघात (quadratic) बने रहें, मानक बाइनरी वेरिएबल पहचान ( $x^2 = x$ ) का उपयोग करते हैं।

मुख्य तकनीकी घटक:

बाधा दंड (Constraint Penalties): लेखक निम्नलिखित के लिए मानक दंड पदों को परिभाषित करते हैं:
- सटीक गणना (Exact Counts): सक्रिय चरों की ठीक $k$ संख्या सुनिश्चित करने के लिए $(s - k)^2$ ।
- अधिकतम एक (At-most-one): एक साथ सक्रिय होने से रोकने के लिए $\sum x_i x_j$ ।
- निरंतर मान (Consecutive Values): 000 या 111 जैसे पैटर्न के लिए दंड $(s-1)(s-2)$ का उपयोग करके।
- समानता/असमानता (Equality/Inequality): $(x-y)^2$ और $(x+y-1)^2$ ।
संघर्ष ग्राफ (Conflict Graphs): विकर्ण बाधाओं को जटिल क्षेत्रों के रूप में मानने के बजाय, लेखक उन्हें संघर्ष ग्राफ (conflict graphs) के रूप में मॉडल करते हैं जहाँ किनारे (edges) वर्जित समवर्ती सक्रियणों का प्रतिनिधित्व करते हैं। यह दृष्टिकोण दिखाया गया है कि N-Queens विविधताओं के लिए अधिक कठोर और कुशल है।
प्रीप्रोसेसिंग और वेरिएबल रिडक्शन:
- निश्चित चर (Fixed Variables): पहले से रखी गई गोटियाँ (clues) 0 या 1 के लिए फिक्स कर दी जाती हैं, और उनके संघर्ष करने वाले पड़ोसियों को 0 के लिए फिक्स किया जाता है, जिससे अनुकूलन चरों की संख्या कम हो जाती है।
- पैरिटी रिडक्शन (Takuzu/Tango): "=" और "x" बाधाओं के लिए, लेखक पैरिटी के साथ एक Union-Find संरचना का प्रस्ताव करते हैं। यह आश्रित कोशिकाओं को $x_v = y_C \oplus \pi_v$ के रूप में व्यक्त करके स्वतंत्र चरों की संख्या को कम करता है, जहाँ $y_C$ एक कनेक्टेड कंपोनेंट का प्रतिनिधि चर है।
वैश्विक विशिष्टता को संभालना (Global Uniqueness - Takuzu): शास्त्रीय Takuzu में कोई भी दो पंक्तियाँ या स्तंभ समान नहीं होने चाहिए। मानक स्थानीय दंड इसे लागू नहीं कर सकते। लेखक यह प्रमाणित करने के लिए कि प्रत्येक जोड़ी $r, s$ के लिए, कम से कम एक कॉलम $j$ मौजूद है जहाँ वे भिन्न होते हैं, विटनेस वेरिएबल्स (Witness Variables) ( $u_{rsj}$ ) का उपयोग करते हैं। यह स्लैक वेरिएबल्स के बिना एक सटीक QUBO फॉर्मूलेशन बनाता है, हालांकि इससे वेरिएबल की संख्या $O(N^3)$ तक बढ़ जाती है।

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

A. सामान्यीकृत N-Queens फ्रेमवर्क

लेखक N-Queens के लिए एक एकीकृत QUBO फॉर्मूलेशन प्रस्तावित करते हैं जो समर्थन करता है:

प्रति पंक्ति/स्तंभ रानियों की परिवर्तनशील संख्या।
"सॉफ्ट" क्षेत्र (0 या 1 रानी की अनुमति देने वाले) और ओवरलैपिंग क्षेत्र।
टोरोइडल बोर्ड (जहाँ किनारे चारों ओर घूमते हैं/wrap around)।
महत्वपूर्ण अंतर्दृष्टि: वे प्रदर्शित करते हैं कि विकर्ण बाधाओं को क्षेत्र-आधारित "अधिकतम एक" बाधाओं के बजाय युग्मवार संघर्ष ग्राफ (pairwise conflict graphs) के रूप में मॉडल करना सबसे अच्छा है, जो समाधान स्थान की सटीकता को बनाए रखता है।

B. सटीक Takuzu/Tango फॉर्मूलेशन

स्थानीय बनाम वैश्विक (Local vs. Global): वे "स्थानीय" TTP (Takuzu/Tango Problem), जो पंक्ति संतुलन और पुनरावृत्ति बाधाओं को संभालता है, और "वैश्विक" विशिष्टता बाधा के बीच अंतर करते हैं।
विटनेस वेरिएबल निर्माण: वे Takuzu में पंक्ति/स्तंभ की विशिष्टता को लागू करने के लिए सहायक विटनेस वेरिएबल्स का उपयोग करके एक नवीन विधि प्रस्तुत करते हैं। यह शास्त्रीय Takuzu के लिए एक सटीक QUBO फॉर्मूलेशन की अनुमति देता है, जिसे पहले बिना रिलैक्सेशन या स्लैक वेरिएबल्स के प्राप्त करना कठिन था।
सामान्यीकरण: वे Takuzu को असंतुलित नियमितता (0s/1s की अलग गणना), विकर्ण पुनरावृत्ति बाधाओं और लंबी दूरी की समानता/असमानता प्रतीकों को शामिल करने के लिए विस्तारित करते हैं।

C. नई समस्या परिभाषाएँ

कलर्ड चेस पीस प्रॉब्लम (Coloured Chess Piece Problem): एक सामान्यीकरण जहाँ विभिन्न प्रकार की गोटियों (अलग-अलग चाल सेट के साथ) को इस तरह रखा जाना चाहिए कि कोई भी गोटी दूसरे को खतरा न पहुँचाए, जिसमें एक रंगीन क्षेत्र में एक गोटी हो।
मैक्स चेस पीसेस प्रॉब्लम (Max Chess Pieces Problem): एक अनुकूलन समस्या जिसमें बोर्ड पर अधिकतम गैर-संघर्षित गोटियों को रखने के लिए एक रिवॉर्ड टर्म ( $-\sum w_{ij}x_{ij}$ ) और एक संघर्ष दंड (conflict penalty) का उपयोग किया जाता है।
सटीक Tents & Trees: वे असाइनमेंट वेरिएबल्स ( $y_{t,c}$ ) का उपयोग करके पेड़ों को टेंट से जोड़ने के लिए एक सटीक QUBO प्रदान करते हैं, जो सरलीकृत रिलैक्सेशन विधियों की अशुद्धियों से बचता है।

4. परिणाम और सैद्धांतिक विश्लेषण

सटीकता (Exactness): शोध पत्र सिद्ध करता है कि प्रस्तावित फॉर्मूलेशन सटीक (exact) हैं।
- LinkedIn Queens के लिए, प्रीप्रोसेसिंग यह सुनिश्चित करती है कि कम किया गया QUBO मूल समस्या के समाधान स्थान से मेल खाता है।
- Takuzu के लिए, विटनेस वेरिएबल विधि गारंटी देती है कि कोई भी शून्य-ऊर्जा अवस्था अद्वितीय पंक्तियों और स्तंभों के साथ एक वैध समाधान के अनुरूप है।
- Max Chess Pieces के लिए, लेखक सिद्ध करते हैं कि यदि संघर्षों के लिए दंड गुणांक $\lambda$ अधिकतम रिवॉर्ड वेट से अधिक है, तो कोई भी ग्लोबल मिनिमाइज़र संघर्षित गोटियों को नहीं रखेगा।
जटिलता (Complexity):
- मानक स्थानीय Takuzu फॉर्मूलेशन बोर्ड के आकार ( $O(N^2)$ वेरिएबल्स) के साथ स्केल करता है।
- विटनेस वेरिएबल्स के साथ सटीक Takuzu फॉर्मूलेशन $O(N^3)$ के रूप में स्केल करता है, क्योंकि विशिष्टता लागू करने के लिए $2N^2(N-1)$ सहायक वेरिएबल्स की आवश्यकता होती है।
अनुकूलन (Optimization): "फ्रैक्शनल" दंड पदों (जैसे, $(s - (q+0.5))^2$ ) का उपयोग एक तकनीक के रूप में हाइलाइट किया गया है जो स्लैक वेरिएबल्स से बचने (वेरिएबल की संख्या कम करने) के साथ-साथ एक स्थिर ऊर्जा ऑफसेट पेश करता है जो मिनिमाइज़र्स को प्रभावित नहीं करता है।

5. महत्व

क्वांटम हार्डवेयर तत्परता (Quantum Hardware Readiness): सटीक QUBO फॉर्मूलेशन प्रदान करके, यह शोध पत्र अमूर्त लॉजिक पहेलियों और क्वांटम एनीलर्स (जैसे D-Wave) और गेट-आधारित क्वांटम कंप्यूटरों (QAOA के माध्यम से) पर व्यावहारिक कार्यान्वयन के बीच के अंतर को पाटता है।
एकीकृत ढांचा (Unified Framework): यह कार्य प्रदर्शित करता है कि विविध प्रकार की पहेलियों (Queens, Takuzu, Tents) को संघर्ष ग्राफ और क्षेत्र बाधाओं का उपयोग करके एक ही गणितीय ढांचे के तहत मॉडल किया जा सकता है, जो कॉम्बिनेटोरियल समस्याओं के लिए सामान्य-उद्देश्य वाले क्वांटम सॉल्वर के विकास की सुविधा प्रदान करता है।
बेंचमार्किंग: ये फॉर्मूलेशन क्वांटम एल्गोरिदम के परीक्षण के लिए मजबूत बेंचमार्क के रूप में कार्य करते हैं, विशेष रूप से बाधाओं, वेरिएबल रिडक्शन को संभालने और समाधान की शुद्धता बनाम क्यूबिट ओवरहेड (जैसे, विटनेस वेरिएबल्स की लागत) के बीच ट्रेड-ऑफ के लिए।
भविष्य की दिशाएँ: शोध पत्र भविष्य के अनुसंधान के लिए मार्ग बताता है, जिसमें वैश्विक बाधाओं के लिए सहायक वेरिएबल ओवरहेड को कम करना, वास्तविक क्वांटम हार्डवेयर पर इन फॉर्मूलेशन को लागू करना और उच्च-क्रम के फॉर्मूलेशन (HOBO/QUDO) का पता लगाना शामिल है।

संक्षेप में, यह शोध पत्र जटिल, बाधा-प्रधान लॉजिक गेम्स को QUBO प्रारूप में अनुवादित करने के लिए एक व्यापक टूलकिट प्रदान करता है, जिसमें संघर्ष ग्राफ और विटनेस वेरिएबल्स जैसी उन्नत तकनीकों के माध्यम से सटीकता (exactness) प्राप्त करने पर विशेष जोर दिया गया है, जिससे ये समस्याएं निकट-अवधि क्वांटम कंप्यूटिंग अनुप्रयोगों के लिए व्यवहार्य उम्मीदवार बन जाती हैं।