⚛️ quantum physics

Planted-solution SAT and Ising benchmarks from integer factorization

यह शोध पत्र SAT सॉल्वर और इसिंग ऑप्टिमाइज़ेशन (Ising optimization) के लिए प्लांटेड-सॉल्यूशन बेंचमार्क के एक स्केलेबल और सत्यापन योग्य परिवार को प्रस्तुत करता है, जो पूर्णांक गुणनखंडन बाधाओं (integer factorization constraints) से व्युत्पन्न है, और जो कारकों के बिट-लेंथ के सापेक्ष घातीय रनटाइम वृद्धि प्रदर्शित करता है।

मूल लेखक: Itay Hen

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

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

CC BY 4.0

मूल लेखक: Itay Hen

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

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

यह शोध पत्र एक नई, सुपर-संगठित पहेली पेश करता है जो एक ऐसी चीज़ पर आधारित है जिसे हम सभी जानते हैं: गुणा (Multiplication)।

यहाँ बताया गया है कि लेखकों ने क्या किया, सरल उपमाओं का उपयोग करते हुए:

1. मूल विचार: "रिवर्स मल्टीप्लिकेशन" पहेली

गुणा को एक फैक्ट्री असेंबली लाइन की तरह समझें। आप दो संख्याओं (मान लीजिए प्राइम A और प्राइम B) को लेते हैं, उन्हें एक मशीन से गुजारते हैं, और बाहर एक बड़ी संख्या (प्रोडक्ट N) आती है।

सामान्य तरीका: आप A और B जानते हैं, आप "Go" दबाते हैं, और मशीन N निकाल देती है। आसान है।
पहेली (फैक्टरइज़ेशन): आपको केवल N दिया गया है। आपको यह पता लगाना है कि A और B क्या थे। यह वह "कठिन" समस्या है जो इंटरनेट पर आपके क्रेडिट कार्ड नंबरों की सुरक्षा करती है।

लेखकों ने एक ऐसी पहेली बनाई है जहाँ कंप्यूटर को एक जासूस की तरह काम करना होगा। उसे उन दो गुप्त संख्याओं (A और B) को खोजना है जिन्हें गुणा करने पर N बनता है। लेकिन यहाँ एक चाल है: लेखकों को उत्तर पता है। उन्होंने समाधान (A और B) को पहेली के अंदर ही बो दिया है। इसका मतलब है कि वे तुरंत जांच सकते हैं कि कंप्यूटर सही है या गलत।

2. उन्होंने पहेली कैसे बनाई: "कैरी-ओवर" चेन रिएक्शन

गुणा को कंप्यूटर द्वारा हल की जाने वाली पहेली में बदलने के लिए, उन्होंने इसे छोटे तार्किक चरणों (जैसे "क्या यह बिट 0 है या 1?") में तोड़ दिया।

कल्पना कीजिए कि आप कागज पर हाथ से लंबी गुणा (long multiplication) कर रहे हैं। जब आप दो कॉलम को गुणा करते हैं, तो कभी-कभी परिणाम उस कॉलम के लिए बहुत बड़ा होता है, इसलिए आपको अगले कॉलम में एक संख्या "कैरी ओवर" (हासिल) करनी पड़ती है।

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

3. यह एक बेहतरीन टेस्ट क्यों है (द "स्ट्रेस टेस्ट")

लेखक यह देखना चाहते थे कि आधुनिक कंप्यूटर (जिन्हें SAT सॉल्वर कहा जाता है) इन पहेलियों को कितनी तेज़ी से हल कर सकते हैं।

विकास (Growth): उन्होंने पाया कि जैसे-जैसे वे संख्याओं को थोड़ा बड़ा बनाते हैं (सिर्फ एक या दो अंक जोड़कर), पहेली केवल थोड़ी कठिन नहीं होती; यह घातीय (exponentially) रूप से कठिन होती जाती है।
उपमा: एक सीढ़ी चढ़ने की कल्पना करें। एक सामान्य पहेली में, हर पायदान की ऊँचाई समान होती है। इस पहेली में, हर बार जब आप एक पायदान जोड़ते हैं, तो सीढ़ी की ऊँचाई दोगुनी हो जाती है।
परिणाम: जब उन्होंने इसका परीक्षण किया, तो कंप्यूटर ने हर एक अतिरिक्त अंक जोड़ने के लिए लगभग दोगुना समय लिया। यह ठीक उसी तरह की कठिनाई है जिसकी शोधकर्ताओं को यह परीक्षण करने के लिए आवश्यकता होती है कि क्या नए क्वांटम कंप्यूटर या अत्यधिक उन्नत AI वास्तव में एन्क्रिप्शन को तोड़ सकते हैं।

4. पहेली को देखने के दो तरीके

यह शोध पत्र विशेष है क्योंकि यह एक ही पहेली को दो अलग-अलग भाषाओं में अनुवादित करता है:

SAT (तर्क भाषा): एक विशाल "सही/गलत" चेकलिस्ट की तरह।
Ising (भौतिकी भाषा): छोटे चुंबकों (स्पिन्स) को संरेखित करने वाले एक चुंबकीय पहेली की तरह जहाँ आपको सबसे कम ऊर्जा अवस्था ढूंढनी होती है।

यह एक मैकेनिक को कार के इंजन की समस्या समझाने जैसा है, जहाँ आप एक बार अंग्रेजी में और एक बार स्पेनिश में वर्णन करते हैं। यह शोधकर्ताओं को यह परीक्षण करने की अनुमति देता है कि कौन सा प्रकार का कंप्यूटर (तर्क-आधारित बनाम भौतिकी-आधारित) बेहतर है।

5. "ब्लूप्रिंट"

लेखकों ने केवल एक पहेली नहीं सुलझाई; उन्होंने अनंत पहेलियाँ बनाने वाली एक मशीन बनाई है।

आप मशीन को बताते हैं: "मुझे 20-अंकों वाली संख्याओं की पहेली चाहिए।"
यह तुरंत एक अद्वितीय, सत्यापन योग्य पहेली बनाता है जिसका उत्तर ज्ञात है।
यह स्केलेबल (scalable) है: आप बस एक डायल घुमाकर इसे आसान (छोटी संख्याएँ) या असंभव (विशाल संख्याएँ) बना सकते हैं।

सारांश

इस शोध पत्र को कंप्यूटर के लिए एक परफेक्टली कैलिब्रेटेड स्ट्रेस टेस्ट के आविष्कार के रूप में समझें।

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

यह वैज्ञानिकों को वर्तमान तकनीक की सीमाओं को समझने में मदद करता है और हमें भविष्य के लिए तैयार करता है, जहाँ हमें यह जानने की आवश्यकता हो सकती है कि क्या हमारे डिजिटल लॉक वास्तव में सुपर-शक्तिशाली नए कंप्यूटरों के सामने सुरक्षित हैं।

यहाँ इते (Itay) हेन के शोध पत्र "Planted-solution SAT and Ising benchmarks from integer factorization" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र सैटेसिबिलिटी (SAT) सॉल्वर और इसिंग (Ising) ऑप्टिमाइज़ेशन मशीनों के बेंचमार्किंग में एक महत्वपूर्ण अंतराल को संबोधित करता है। मौजूदा बेंचमार्क आम तौर पर दो श्रेणियों में आते हैं:

रैंडम एन्सेम्बल्स (जैसे, रैंडम k-SAT): ये व्यवस्थित स्केलेबिलिटी और थ्रेशोल्ड के पास कठिनाई तो प्रदान करते हैं, लेकिन इनमें ज्ञात "ग्राउंड ट्रुथ" समाधान का अभाव होता है, जिससे यह सत्यापित करना असंभव हो जाता है कि सॉल्वर ने सही उत्तर पाया है या नहीं।
क्राफ्टेड इंस्टेंस (Crafted Instances): इनके ज्ञात समाधान होते हैं, लेकिन इनमें अक्सर नियंत्रित, एकल-पैरामीटर स्केलिंग या यथार्थवादी संरचनात्मक जटिलता का अभाव होता है।

लेखक पूर्णांक गुणनखंडन (integer factorization) से व्युत्पन्न प्लांटेड-सॉल्यूशन बेंचमार्क्स की एक नई श्रेणी का प्रस्ताव करते हैं। इसका लक्ष्य ऐसे इंस्टेंस बनाना है जहाँ समाधान (अभाज्य गुणनखंड $p$ और $q$ ) डिज़ाइन द्वारा ज्ञात हो, कठिनाई एक एकल पैरामीटर (बिट-लेंथ $d$ ) के साथ व्यवस्थित रूप से स्केल हो, और इसकी संरचना वास्तविक दुनिया की अंकगणितीय समस्याओं में पाए जाने वाले नियत (deterministic), दीर्घ-रेंज सहसंबंधों (long-range correlations) को दर्शाती हो, न कि यादृच्छिक विकार (random disorder) को।

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

निर्माण प्रक्रिया दो $d$ -बिट अभाज्य संख्याओं के गुणन ( $N = p \times q$ ) के अंकगणितीय प्रतिबंधों को एक कंस्ट्रेंट सैटिस्फैक्शन प्रॉब्लम (CSP) में एनकोड करती है। यह पाइपलाइन तीन चरणों से मिलकर बनी है:

A. बाइनरी मल्टीप्लिकेशन से क्लॉज जनरेशन (Clause Generation from Binary Multiplication)

लेखक मानक शिफ्ट-एंड-ऐड (shift-and-add) बाइनरी मल्टीप्लिकेशन एल्गोरिदम को मॉडल करते हैं।

पार्शियल प्रोडक्ट्स (Partial Products): प्रत्येक बिट युग्म $(p_i, q_j)$ के लिए, एक AND ऑपरेशन एक पार्शियल प्रोडक्ट उत्पन्न करता है जिसे कॉलम $k = i+j$ में रखा जाता है।
कॉलम कॉन्ट्रैक्शन (Column Contraction): कई प्रविष्टियों वाले कॉलम को हाफ-एडर (half-adder) लॉजिक का उपयोग करके कम किया जाता है। एक कॉलम में दो प्रविष्टियाँ $x, y$ को एक सम ( $x \oplus y$ , जो कॉलम में रहता है) और एक कैरी ( $x \land y$ , जो अगले कॉलम में प्रमोट होता है) में संकुचित किया जाता है।
पिनिंग (Pinning): उत्पाद $N$ के अंतिम बिट्स ज्ञात स्थिरांक (constants) हैं। प्रत्येक कॉलम में बचा हुआ एकल वेरिएबल $N$ के संगत बिट से मेल खाने के लिए "पिन" किया जाता है।
परिणाम: यह AND क्लॉज़ (कैरी), XOR क्लॉज़ (सम), और पिनिंग प्रतिबंधों की एक प्रणाली उत्पन्न करता है।

B. बूलियन प्रीप्रोसेसिंग (Boolean Preprocessing)

मानक CNF में बदलने से पहले, सिस्टम को पुनरावृत्तिपूर्ण तार्किक सरलीकरण से गुजारा जाता है:

प्रोपैगेशन (Propagation): फिक्स्ड वेरिएबल्स (पिनिंग से) को पूरे सिस्टम में प्रतिस्थापित किया जाता है।
सरलीकरण (Simplification): वेरिएबल्स और क्लॉज़ को हटाने के लिए तार्किक नियमों (जैसे, $0 \land x = 0$ , $x \oplus x = 0$ ) को लागू किया जाता है।
इक्विवेलेंस मर्जिंग (Equivalence Merging): जो वेरिएबल्स समान या पूरक निर्धारित होते हैं, उन्हें यूनियन-फाइंड डेटा स्ट्रक्चर का उपयोग करके मर्ज किया जाता है।
परिणाम: यह छोटे $d$ के लिए इंस्टेंस के आकार को काफी कम कर देता है, हालांकि $d$ बढ़ने के साथ रिडक्शन रेश्यो कम होता जाता है, जिससे अवशेष प्रतिबंधों (residual constraints) का एक "हार्ड कोर" बच जाता है।

C. DIMACS CNF और इसिंग फॉर्म में रूपांतरण (Conversion to DIMACS CNF and Ising Form)

CNF: अवशेष AND और XOR क्लॉज़ को मानक एनकोडिंग (AND के लिए 3 क्लॉज़, XOR के लिए 4) का उपयोग करके कंजंक्टिव नॉर्मल फॉर्म (CNF) में परिवर्तित किया जाता है।
इसिंग कंपाइलेशन (Ising Compilation): सिस्टम को एक द्विघातीय (quadratic) इसिंग हैमिल्टोनियन $H(s)$ $H (s)$ में मैप किया जाता है।
- बूलियन वेरिएबल्स स्पिन $s_i \in \{-1, +1\}$ में मैप होते हैं।
- गैजेट्स (Gadgets): AND प्रतिबंधों को 3-स्पिन द्विघातीय गैजेट्स में मैप किया जाता है। XOR प्रतिबंधों (जो स्पिन में क्यूबिक होते हैं) को द्विघातीय क्रम में कम करने के लिए एक सहायक स्पिन की आवश्यकता होती है।
- परिणामी हैमिल्टोनियन का ग्राउंड स्टेट ठीक से प्लांटेड गुणनखंडन (factorization) के अनुरूप होता है।

3. मुख्य योगदान और सैद्धांतिक विश्लेषण (Key Contributions and Theoretical Analysis)

A. क्वार्टिक स्केलिंग ( $d^4$ )

लेखक इंस्टेंस के आकार के लिए सटीक क्लोज्ड-फॉर्म एक्सप्रेशन प्राप्त करते हैं।

तंत्र (Mechanism): जटिलता का मुख्य चालक कैरी कैस्केडिंग (carry cascading) है। कॉलम $k$ में एक संकुचन (contraction) $k+1$ के लिए एक कैरी उत्पन्न करता है, जो अगले कॉलम में प्रविष्टियों की संख्या को बढ़ाता है, जिससे अधिक संकुचन की आवश्यकता होती है, और इसी तरह।
कॉलम जनसंख्या (Column Population): कॉलम $k$ में प्रविष्टियों की संख्या ( $m_k$ ) द्विघातीय रूप से बढ़ती है, जो मल्टीप्लिकेशन टेबल के मध्य के पास $O(d^2)$ तक चरम पर पहुँचती है।
कुल आकार: $O(d^2)$ सक्रिय कॉलमों पर संकुचन को जोड़ने पर, कुल बाधाओं और वेरिएबल्स का आकार $\Theta(d^4)$ के रूप में स्केल होता है।
महत्व: यह अंकगणितीय संरचना का सीधा परिणाम है, जो इसे रैंडम SAT एन्सेम्बल्स से अलग करता है जहाँ आकार वेरिएबल्स की संख्या के साथ रैखिक या द्विघातीय रूप से स्केल होता है।

B. दीर्घ-रेंज सहसंबंध (Long-Range Correlations)

रैंडम SAT या फ्रस्ट्रेशन-आधारित प्लांटेड इंस्टेंस के विपरीत, इन बेंचमार्क्स में नियत, दीर्घ-रेंज सहसंबंध होते हैं। एक लो-ऑर्डर बिट में बदलाव कैरी को सीधे सबसे महत्वपूर्ण बिट (दूरी $\sim d^2$ ) तक पहुँचा सकता है, जिससे एक जटिल इंटरेक्शन ग्राफ बनता है जिसमें शामिल हैं:

विषम डिग्री वितरण (उच्च-डिग्री स्पिन मध्य कॉलम के पास)।
दूर के कॉलमों को जोड़ने वाले लॉन्ग-रेंज किनारे (edges)।
कॉलम संकुचन पर आधारित पदानुभित सामुदायिक संरचना (hierarchical community structure)।

C. दोहरा प्रतिनिधित्व (Dual Representation)

निर्माण प्रक्रिया एक एकीकृत बेंचमार्क प्रदान करती है जो CNF (SAT सॉल्वर के लिए) और Ising (क्लासिकल/क्वांटम ऑप्टिमाइज़र के लिए) दोनों में उपलब्ध है, जिससे समान ग्राउंड ट्रुथ का उपयोग करके प्रत्यक्ष क्रॉस-प्लेटफ़ॉर्म तुलना संभव होती है।

4. परिणाम (Results)

अनुभवजन्य बेंचमार्किंग (Empirical Benchmarking)

लेखकों ने $d = 8$ से $27$ बिट-लेंथ के लिए अत्याधुनिक कॉन्फ्लिक्ट-ड्रिवन क्लॉज लर्निंग (CDCL) SAT सॉल्वर (Kissat 3.0 और CaDiCaL 1.5) पर इन इंस्टेंस का परीक्षण किया।

रनटाइम स्केलिंग: मीडियन रनटाइम $T$ $T$ , बिट-लेंथ $d$ $d$ के साथ एक्सपोनेंशियल (exponentially) रूप से बढ़ता है।
- फिटेड स्केलिंग: $T \sim 2^{\beta d}$ जहाँ $\beta \approx 1$ ।
- व्याख्या: प्रत्येक अतिरिक्त बिट मीडियन रनटाइम को लगभग दोगुना कर देता है।
सॉल्वर निरंतरता (Solver Consistency): दोनों सॉलवर्स ने लगभग समान विकास दर प्रदर्शित की, जो यह सुझाव देता है कि कठिनाई समस्या की संरचना (कैरी कोरिलेशन) में निहित है, न कि सॉल्वर-विशिष्ट ह्यूरिस्टिक्स में।
कठिनाई: $d=27$ ( $N \approx 10^{16}$ ) पर, रनटाइम $\sim 10^4$ सेकंड तक पहुँच गया, जो दर्शाता है कि $d \ge 35$ वाले इंस्टेंस आधुनिक सॉलवर्स के लिए कठोर स्ट्रेस टेस्ट के रूप में काम करेंगे।

इसिंग मॉडल गुण (Ising Model Properties)

कंपाइल किए गए इसिंग मॉडल्स का एक ज्ञात ग्राउंड-स्टेट एनर्जी $E_0$ है।
स्पेक्ट्रल गैप (एक प्रतिबंध का उल्लंघन करने के लिए न्यूनतम ऊर्जा दंड) 2 से नीचे सीमित है, जो एक संरचित "सीढ़ीदार" (staircase) पेनल्टी लैंडस्केप प्रदान करता है।

5. महत्व और प्रभाव (Significance and Impact)

नया बेंचमार्क रिजीम: यह कार्य एक ऐसा बेंचमार्क परिवार पेश करता है जो स्केलेबल, सत्यापन योग्य (verifiable) और संरचनात्मक रूप से समृद्ध है। यह रैंडम एन्सेम्बल्स (कठिन लेकिन अपुष्ट) और सरल क्राफ्टेड इंस्टेंस (सत्यापित लेकिन संरचनात्मक रूप से सरल) के बीच के शून्य को भरता है।
सॉल्वर स्ट्रेस टेस्टिंग: $d^4$ स्केलिंग और एक्सपोनेंशियल रनटाइम ग्रोथ इन इंस्टेंस को CDCL ह्यूरिस्टिक्स और क्वांटम एनीलिंग/ऑप्टिमाइज़ेशन हार्डवेयर की सीमाओं को परखने के लिए आदर्श बनाती है।
अंकगणितीय संरचना: बाइनरी मल्टीप्लिकेशन के कैरी-प्रोपैगेशन से कठिनाई प्राप्त करके, यह शोध पत्र सॉलवर्स द्वारा दीर्घ-रेंज डिपेंडेंसी को संभालने के तरीके को समझने के लिए एक टेस्टबेड प्रदान करता है, जो कि एक ऐसी विशेषता है जो वास्तविक दुनिया की समस्याओं में सामान्य है लेकिन रैंडम बेंचमार्क्स में अक्सर अनुपस्थित होती है।
ओपन सोर्स: लेखक इन इंस्टेंस को उत्पन्न करने के लिए ओपन-सोर्स सॉफ्टवेयर प्रदान करते हैं, जिससे पुनरुत्पादकता (reproducibility) और आगे के अनुसंधान को सक्षम बनाया जा सके।

संक्षेप में, यह शोध पत्र सफलतापूर्वक पूर्णांक गुणनखंडन की अंकगणितीय समस्या को SAT और इसिंग सॉलवर्स के लिए एक कठोर, स्केलेबल और सत्यापन योग्य बेंचमार्क सूट में बदल देता है, यह प्रदर्शित करते हुए कि बाइनरी मल्टीप्लिकेशन के स्वाभाविक कैरी-प्रोपैगेशन स्ट्रक्चर से एक अनूठा चुनौतीपूर्ण अनुकूलन (optimization) वर्ग निर्मित होता है।