⚛️ quantum physics

CNOT-Distance is NP-complete under all-to-all connectivity

यह शोध पत्र सिद्ध करता है कि सभी-से-सभी (all-to-all) कनेक्टिविटी के तहत एक दी गई व्युत्क्रमणीय बाइनरी मैट्रिक्स (invertible binary matrix) को लागू करने के लिए आवश्यक CNOT गेट्स की न्यूनतम संख्या निर्धारित करना NP-complete है, जो मिनिमम वर्टेक्स कवर (Minimum Vertex Cover) समस्या से रिडक्शन के माध्यम से सटीक और अनुमानित दोनों प्रकार की जटिलता (hardness) स्थापित करता है।

मूल लेखक: Antonio Acuaviva, Arturo Acuaviva, Pablo Acuaviva

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

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

CC BY 4.0

मूल लेखक: Antonio Acuaviva, Arturo Acuaviva, Pablo Acuaviva

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

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

वैज्ञानिक लंबे समय से जानते हैं कि वे इन मशीनों को डेटा के किसी भी संभावित पुनर्व्यवस्था को करने के लिए कैसे बना सकते हैं। वे यह भी जानते हैं कि वे उन्हें कुशलतापूर्वक कैसे बना सकते हैं, सबसे खराब स्थिति में भी, गेटों की एक ऐसी संख्या का उपयोग करके जो समस्या के आकार के साथ अनुमानित रूप से बढ़ती है। लेकिन पेच यहाँ है: एक मशीन बनाना आसान है; किसी विशिष्ट कार्य के लिए सबसे छोटी, सबसे कुशल मशीन बनाना एक दुःस्वप्न है। यह यह जानने जैसा है कि आप विमान से न्यूयॉर्क से लंदन जा सकते हैं, लेकिन एक ऐसे भूलभुलैया में सबसे छोटा रास्ता खोजने की कोशिश करना जहाँ हर मोड़ पिछले मोड़ पर निर्भर करता है। वर्षों तक, शोधकर्ताओं ने सोचा कि यदि हम वास्तविक हार्डवेयर की सभी भौतिक सीमाओं को हटा दें (जैसे कि ऐसे तार जो आपस में नहीं टकरा सकते या विशिष्ट कनेक्शन जो गायब हैं) और हर तार को दूसरे से बात करने दें, तो क्या डेटा को पुनर्व्यवस्थित करने के लिए न्यूनतम CNOT गेटों की संख्या ज्ञात करना आसान हो जाएगा? या क्या यह अभी भी एक कम्प्यूटेशनल राक्षस बना रहेगा?

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

इसे सिद्ध करने के लिए, लेखकों ने केवल यादृच्छिक सर्किट नहीं देखे; उन्होंने दो बहुत अलग दुनियाओं के बीच एक चतुर पुल बनाया। एक तरफ एक क्लासिक, कुख्यात रूप से कठिन पहेली है जिसे वर्टेक्स कवर (Vertex Cover) कहा जाता है। कल्पना कीजिए कि एक पार्टी है जहाँ आप लोगों का एक छोटा समूह आमंत्रित करना चाहते हैं ताकि पार्टी में होने वाला प्रत्येक 'हैंडशेक' (हाथ मिलाना) कम से कम आपके समूह के एक व्यक्ति से जुड़ा हो। उस सबसे छोटे समूह को खोजना कठिन है। दूसरी ओर क्वांटम दुनिया के CNOT गेट्स हैं। लेखकों ने एक विशिष्ट गणितीय "अनुवाद" बनाया जो किसी भी पार्टी (ग्राफ) को एक विशिष्ट क्वांटम सर्किट (मैट्रिक्स) में बदल देता है।

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

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

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

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

संक्षेप में, यह पेपर उस दरवाजे को बंद कर देता है जिसे कई लोग खुला रहने की उम्मीद कर रहे थे। यह पुष्टि करता है कि क्वांटम सर्किट को अनुकूलित करने की कठिनाई केवल खराब हार्डवेयर या सीमित कनेक्शनों का परिणाम नहीं है। यह कठिनाई गणित में ही रची-बसी है। एक आदर्श, घर्षण रहित दुनिया में भी, जहाँ हर तार हर दूसरे तार से बात कर सकता है, CNOT गेटों का उपयोग करके डेटा को पुनर्व्यवस्थित करने का सबसे कुशल तरीका खोजना एक ऐसा कार्य है जिसके लिए संभवतः हमेशा उससे कहीं अधिक कंप्यूटिंग शक्ति की आवश्यकता होगी जितनी हमारे पास होने की हम कभी आशा कर सकते हैं। लेखकों ने केवल यह सुझाव नहीं दिया; उन्होंने एक कठोर गणितीय तर्क के साथ इसे सिद्ध किया जो तब भी कायम रहता है जब आप अतिरिक्त तारों का उपयोग करते हैं या नियमों को थोड़ा बदलते हैं। सबसे छोटे क्वांटम सर्किट की यात्रा, जैसा कि पता चला है, एक ऐसी भूलभुलैया है जिसमें कोई शॉर्टकट नहीं है।

तकनीकी सारांश: CNOT-दूरी (CNOT-Distance) सभी-से-सभी कनेक्टिविटी (all-to-all connectivity) के तहत NP-complete है

समस्या विवरण
यह शोध पत्र CNOT-दूरी (CNOT-Distance) समस्या की गणनात्मक जटिलता (computational complexity) को संबोधित करता है। एक स्पष्ट रूप से प्रतिनिधित्व की गई व्युत्क्रमणीय बाइनरी मैट्रिक्स $A \in GL(N, 2)$ और एक पूर्णांक $K$ दिए जाने पर, यह समस्या पूछती है कि क्या $A$ को $N$ निश्चित, लेबल वाले तारों (wires) पर अधिकतम $K$ CNOT गेट्स के सर्किट द्वारा कार्यान्वित किया जा सकता है, जिसमें सभी-से-सभी कनेक्टिविटी (all-to-all connectivity) हो। मॉडल में कोई अतिरिक्त तार (ancillary wires) नहीं माने गए हैं (हालांकि अतिरिक्त वेरिएंट्स पर विचार किया गया है), कोई कैंसलेशन-मुक्त (cancellation-free) बाधाएं नहीं हैं, और कोई निर्धारित गेट क्रम (gate ordering) नहीं है। लक्ष्य $A$ को संश्लेषित करने के लिए आवश्यक न्यूनतम गेट गणना (ट्रांसवेक्शन के जनरेटर के रूप में Cayley ग्राफ में शब्द लंबाई/word length) निर्धारित करना है।

जबकि गॉसियन एलिमिनेशन (Gaussian elimination) $O(N^2)$ का ऊपरी बाउंड प्रदान करता है और बेहतर एल्गोरिदम वर्स्ट-केस बाउंड्स के लिए मौजूद हैं, किसी विशिष्ट इंस्टेंस के लिए सटीक न्यूनतम गेट गणना खोजने की जटिलता अनसुलझी रही है। पिछले हार्डनेस परिणाम प्रतिबंधित टोपोलॉजी, विशिष्ट इनपुट एनकोडिंग वाले पैरिटी नेटवर्क, या क्लिफोर्ड+T (Clifford+T) सहित गेट सेट्स पर केंद्रित रहे हैं। फिक्स्ड-लेबल, ऑल-टू-ऑल CNOT संश्लेषण की विशिष्ट हार्डनेस एक खुला प्रश्न था।

कार्यप्रणाली (Methodology)
लेखक मिनिमम वर्टेक्स कवर (Minimum Vertex Cover) समस्या से रिडक्शन (reduction) के माध्यम से NP-पूर्णता (NP-completeness) सिद्ध करते हैं।

लक्ष्य मैट्रिसेस का निर्माण:
एक दिए गए ग्राफ $G = (V, E)$ के लिए, लेखक एक विशिष्ट अपर-यूनिट्राइएंगुलर (upper-unitriangular) मैट्रिक्स $A_G \in GL(2|V| + |E| + 1, 2)$ का निर्माण करते हैं। मैट्रिक्स एक सेट ऑफ वायर्स पर कार्य करता है जिसमें एक विशिष्ट तार $z$ , प्रत्येक वर्टेक्स $v \in V$ के लिए वायर जोड़े $(q_v, x_v)$ , और प्रत्येक एज $e \in E$ के लिए एक तार $y_e$ शामिल है। रूपांतरण इस प्रकार परिभाषित है:
- $q'_v = q_v + z$
- $x'_v = x_v + q_v$
- $y'_e = y_e + z + x_u + x_v$ (एज $e=\{u,v\}$ के लिए)
सटीक दूरी पहचान (Exact Distance Identity):
मूल प्रमाण इस सटीक पहचान को स्थापित करता है:
$\ell_{\text{CNOT}}(A_G) = 2|V| + 2|E| + \tau(G)$
जहाँ $\tau(G)$ ग्राफ $G$ के मिनिमम वर्टेक्स कवर का आकार है।
ऊपरी बाउंड निर्माण (Upper Bound Construction):
लेखक प्रदर्शित करते हैं कि कोई भी वर्टेक्स कवर $C$ , $2|V| + 2|E| + |C|$ की लंबाई वाला CNOT सर्किट प्रदान करता है। इस निर्माण में, चयनित वर्टेक्स वायर्स अस्थायी रूप से घटना वाले एज आउटपुट्स (incident edge outputs) के लिए $z$ का योगदान वहन करते हैं, जो प्रभावी रूप से आवश्यक पैरिटी (parities) को लागू करते हैं।
प्रोजेक्शन-कॉन्ट्रैक्शन द्वारा निचला बाउंड (Lower Bound via Projection-Contraction):
निचला बाउंड (lower bound) एक नवीन योगदान है। लेखक दिखाते हैं कि $A_G$ को लागू करने वाला कोई भी मनमाना CNOT सर्किट (कैंसलेशन और इंटरमीडिएट पुन: उपयोग के साथ भी) एक XOR निर्देशित अचक्रीय ग्राफ (DAG) में "अनफोल्ड" किया जा सकता है। प्रोजेक्शन (विशिष्ट इनपुट्स को शून्य पर सेट करना) और कॉन्ट्रैक्शन (समान प्रोजेक्टेड मानों वाले नोड्स को मर्ज करना) को लागू करके, वे सर्किट के "रिवर्सिबल बुककीपिंग" घटकों को व्यवस्थित रूप से हटा देते हैं।
- वर्टेक्स इनपुट्स को प्रोजेक्ट करने से $2|V|$ नोड्स हट जाते हैं।
- प्राइवेट एज इनपुट्स को प्रोजेक्ट करने से $|E|$ नोड्स हट जाते हैं।
- शेष संरचना एक XOR स्ट्रेट-लाइन प्रोग्राम है जो रूपों के सेट $F_G = \{z + x_u + x_v \mid \{u,v\} \in E\}$ को कंप्यूट करता है।
- बॉयर-मैथ्यूज-पेराल्टा लेम्मा (Boyar-Matthews-Peralta lemma) के बाइनरी स्पेशलाइजेशन का उपयोग करते हुए, शेष प्रोग्राम की लंबाई कम से कम $|E| + \tau(G)$ दिखाई गई है।
- इन सबको मिलाकर निचला बाउंड $L \ge 2|V| + 2|E| + \tau(G)$ प्राप्त होता है।
एंसिलरी रोबस्टनेस (Ancillary Robustness):
लेखक सिद्ध करते हैं कि क्लीन (clean) या बोरोड (borrowed) एंसिलरी वायर्स की किसी भी परिमित संख्या को जोड़ने से इस परिवार के मैट्रिसेस के लिए इष्टतम गेट गणना कम नहीं होती है। प्रोजेक्शन-कॉन्ट्रैक्शन तर्क इन मामलों में भी विस्तारित होता है, जहाँ एंसिलरी वेरिएबल्स को प्रोजेक्शन के लिए अतिरिक्त इनपुट्स के रूप में माना जाता है।

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

NP-पूर्णता (NP-Completeness): CNOT-दूरी समस्या NP-पूर्ण है। यह उन अत्यधिक प्रतिबंधित इंस्टेंस के लिए भी सत्य है जहाँ:
- $A$ अपर-यूनिट्राइएंगुलर है।
- प्रत्येक रो (row) का हैमिंग वेट (Hamming weight) 4 से अधिक नहीं है।
- $A$ का सटीक ऑर्डर 4 है (अर्थात, $(A-I)^3=0$ और $A^4=I$ )।
- गेट बजट $K < 2N$ है।
सटीक गणना की कठिनाई (Hardness of Exact Computation): सटीक CNOT दूरी $\ell_{\text{CNOT}}(A)$ की गणना करना NP-हार्ड है।
अनुमान लगाने की कठिनाई (Hardness of Approximation):
- एडिटिव (Additive): किसी भी निश्चित एडिटिव कांस्टेंट $c$ के भीतर दूरी का अनुमान लगाना NP-हार्ड है।
- मल्टीप्लिकेटिव (Multiplicative): अनुकूलन समस्या APX-hard है (क्यूबिक ग्राफ्स पर मिनिमम वर्टेक्स कवर से L-रिडक्शन के माध्यम से), जिसका अर्थ है कि यदि P=NP नहीं है, तो कोई पॉलीनोमियल-टाइम एप्रोक्सिमेशन स्कीम (PTAS) मौजूद नहीं है।
एंसिलरी इनवेरियेंस (Ancillary Invariance): निर्मित $A_G$ परिवार के लिए, न्यूनतम गेट गणना एंसिलिया-मुक्त, क्लीन-एंसिलिया, और बोरोड-एंसिलिया मॉडल्स के लिए समान है।
कंस्ट्रक्टिव डिकोडर (Constructive Decoder): रिडक्शन में एक पॉलीनोमियल-टाइम डिकोडर शामिल है जो, $A_G$ के लिए किसी भी CNOT सर्किट को दिए जाने पर, $G$ के लिए एक वर्टेक्स कवर निकालता है जिसका आकार सर्किट लंबाई के एक कांस्टेंट फैक्टर से बंधा होता है। APX-हार्डनेस के लिए L-रिडक्शन स्थापित करने के लिए यह महत्वपूर्ण है।

महत्व और दावे

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

परिणाम ट्रेक्टेबल (tractable) और इंट्रैक्टेबल (intractable) संश्लेषण के बीच की सीमा को स्पष्ट करते हैं:

समस्या स्पार्स (sparse), स्ट्रक्चर्ड मैट्रिसेस (अपर-यूनिट्राइएंगुलर, कम हैमिंग वेट के साथ) के लिए भी कठिन बनी रहती है।
कठिनाई एंसिलरी वायर्स (क्लीन या बोरोड) के उपयोग के बावजूद बनी रहती है, बशर्ते उन्हें बहाल (restore) किया जाना चाहिए।
प्रोजेक्शन-कॉन्ट्रैक्शन तकनीक मनमाने रिवर्सिबल कार्यान्वयन से गैर-रिवर्सिबल कर्नेल (जैसे XOR कॉम्प्लेक्सिटी) निकालने का एक सामान्य तरीका प्रदान करती है, जो यह सुझाव देता है कि कैंसलेशन और इंटरमीडिएट पुन: उपयोग मौलिक कॉम्बिनेटरियल कठिनाई को दरकिनार नहीं कर सकते।

लेखक नोट करते हैं कि जबकि यह परिणाम किसी भी आर्किटेक्चर फैमिली के लिए NP-हार्डनेस को दर्शाता है जो पूर्ण द्विदिश ग्राफ (complete bidirected graph) को एम्बेड कर सकती है (रिडक्शन की यूनिफॉर्मिटी प्रॉपर्टी के माध्यम से), यह विशिष्ट फिक्स्ड स्पार्स टोपोलॉजी (जैसे पाथ या स्टार) के लिए जटिलता को निर्धारित नहीं करता है, क्योंकि जनरेटिंग सेट को बदलने से डिस्टेंस मेट्रिक पूरी तरह से बदल जाता है।

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