⚛️ quantum physics

Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation are NP-hard for Low-T-Depth Quantum Circuits

यह शोधपत्र सिद्ध करता है कि लॉगारिदमिक टी-डेप्थ (logarithmic T-depth) वाले क्लिफोर्ड+टी (Clifford+T) सर्किट के लिए एक्ज़ैक्ट नॉन-आइडेंटिटी चेक (Exact Non-Identity Check - ENIC) का निर्णय लेना एनपी-हार्ड (NP-hard) बना रहता है, जिससे ऐसे सर्किटों के लिए कुशल गेट-टेलीपोर्टेशन-आधारित इंडिस्टिंग्विशेबिलिटी ओब्फस्केशन (indistinguishability obfuscation) की संभावना खारिज हो जाती है जब तक कि P=NP न हो।

मूल लेखक: Joshua Nevin

प्रकाशित 2026-09-25

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

CC BY 4.0

मूल लेखक: Joshua Nevin

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

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

जोशुआ नेविन का एक हालिया अध्ययन इन क्वांटम सर्किट्स की सीमाओं की जांच करके इस आशावाद को चुनौती देता है। यह शोध गेट्स के एक मानक सेट से बने विशिष्ट वर्ग के सर्किट्स पर केंद्रित है, जिसमें 'T-गेट' नामक एक विशेष ऑपरेशन शामिल है, जो क्वांटम कंप्यूटरों को शक्तिशाली बनाने के लिए आवश्यक है लेकिन साथ ही प्रबंधित करने में भी कठिन है। यह अध्ययन इस बात की जांच करता है कि क्या यह कुशलतापूर्वक निर्धारित करना संभव है कि दो अलग-अलग क्वांटम सर्किट वास्तव में बिल्कुल एक जैसा काम कर रहे हैं या नहीं, जिसे 'एक्जैक्ट नॉन-आइडेंटिटी चेक' (Exact Non-Identity Check) कहा जाता है। यदि यह चेक करना आसान होता, तो यह पहले बताए गए सुरक्षित, छिपे हुए प्रोग्राम बनाने की दिशा में एक महत्वपूर्ण कदम होता। नेविन का कार्य सिद्ध करता है कि इन कठिन T-गेट्स के बहुत कम "डेप्थ" (depth) वाले सर्किट्स के लिए—अर्थात, संचालन बहुत कम क्रमिक चरणों में होते हैं—यह चेक न केवल कठिन है, बल्कि वर्तमान विधियों के साथ इसे कुशलतापूर्वक हल करना गणितीय रूप से असंभव (intractable) है, यह मानते हुए कि P, NP के बराबर नहीं है। यह पेपर प्रदर्शित करता है कि इन सर्किट्स की जांच की कठिनाई गणित की एक क्लासिक, अनसुलझी समस्या से जुड़ी है जिसमें कोड के भार (weights) शामिल हैं, जिसे गणनात्मक रूप से कठिन माना जाता है।

इस खोज का मूल आधार यह है कि कैसे शोधकर्ताओं ने दो असंबंधित दुनियाओं को जोड़ा: क्वांटम गेट्स का व्यवहार और त्रुटि सुधार (error correction) में उपयोग किए जाने वाले बाइनरी कोड के गुण। टीम ने दिखाया कि जब आप एक नेटवर्क के माध्यम से सूचना को टेलीपोर्ट करने के तरीके पर आधारित विधि का उपयोग करके एक क्वांटम सर्किट को छिपाने की कोशिश करते हैं, तो सर्किट के थोड़े से भी जटिल होने पर उसके व्यवहार को सत्यापित करने के लिए आवश्यक प्रयास विस्फोटक रूप से बढ़ जाता है। विशेष रूप से, उन्होंने पाया कि भले ही एक सर्किट में कठिन T-गेट्स के लॉगरिदमिक (logarithmic) संख्या में चरण हों, यह निर्धारित करना कि क्या वह वास्तव में एक सरल, खाली ऑपरेशन के समान है, NP-हार्ड नामक कम्प्यूटेशनल चुनौतियों के वर्ग की सबसे कठिन समस्याओं को हल करने जितना कठिन है। इसका अर्थ है कि जब तक कंप्यूटर विज्ञान में कोई मौलिक सफलता नहीं होती जो हमें इन कठिन समस्याओं को जल्दी हल करने की अनुमति दे (विशेष रूप से, जब तक P = NP नहीं होता), तब तक इन विशिष्ट प्रकार के क्वांटम सर्किट्स को कुशलतापूर्वक ओब्फस्केट करने का कोई तरीका नहीं है।

शोधकर्ता इस निष्कर्ष पर इस प्रकार पहुँचे कि उन्होंने क्वांटम समस्या को बाइनरी स्ट्रिंग्स और लीनियर कॉम्बिनेशन की भाषा में अनुवादित किया। उन्होंने एक ऐसी स्थिति का निर्माण किया जहाँ एक क्वांटम ऑपरेशन के गुणांक (coefficients), जो यह वर्णन करते हैं कि सर्किट सूचना को कैसे परिवर्तित करता है, एक बाइनरी कोड के 'वेट डिस्ट्रीब्यूशन' (weight distribution) का प्रतिनिधित्व कर सकते हैं। इस संदर्भ में, "वेट" (weight) का अर्थ डेटा की एक स्ट्रिंग में गैर-शून्य तत्वों की संख्या है। अध्ययन ने सिद्ध किया कि लो-डेप्थ (low-depth) सर्किट्स के लिए इन गुणांकों की गणना करना, एक कोड में विशिष्ट पैटर्न की गिनती करने के समान है, जो कि एक अत्यंत कठिन कार्य माना जाता है। यह दिखाकर कि क्वांटम समस्या सीधे इस कठिन काउंटिंग समस्या पर मैप होती है, लेखक ने प्रभावी रूप से कुशल समाधान की संभावना को खारिज कर दिया। उन्होंने प्रदर्शित किया कि 2021 में प्रस्तावित प्रोटोकॉल, जो बहुत कम T-गेट्स वाले सर्किट्स के लिए अच्छा काम करता था, उसे थोड़े अधिक जटिल संरचनाओं वाले सर्किट्स तक विस्तारित नहीं किया जा सकता है क्योंकि वह गणनात्मक कठिनाई की दीवार से टकरा जाएगा।

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

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

तकनीकी सारांश: कम T-डेप्थ वाले क्वांटम सर्किट के लिए सटीक गैर-तत्समता जाँच (Exact Non-Identity Check) और गेट-टेलीपोर्टेशन-आधारित अनडिस्टिंगविशेबिलिटी ऑबफस्केशन (Indistinguishability Obfuscation) NP-हार्ड हैं

समस्या विवरण
यह शोध पत्र क्लिफोर्ड और $T$ गेट्स (Clifford+ $T$ सर्किट्स) से बने क्वांटम सर्किट के संदर्भ में दो परस्पर संबंधित समस्याओं की कम्प्यूटेशनल जटिलता की जांच करता है। पहली समस्या सटीक गैर-तत्समता जाँच (Exact Non-Identity Check - ENIC) है, जो यह पूछती है कि क्या एक दिया गया $n$ -क्यूबिट क्वांटम सर्किट $C$ बिल्कुल पहचान ऑपरेटर (identity operator) के बराबर है (अर्थात, $C = e^{i\theta}I^{\otimes n}$ )। दूसरी समस्या गेट-टेलीपोर्टेशन-आधारित अनडिस्टिंगविशेबिलिटी ऑबफस्केशन (qiO) की व्यवहार्यता से संबंधित है।

2021 में, ब्रॉडबेंट और काज़मी ने क्वांटम सर्किट के कम्प्यूटेशनल अनडिस्टिंगविशेबिलिटी ऑबफस्केशन के लिए एक प्रोटोकॉल प्रस्तावित किया था। इस प्रोटोकॉल की दक्षता इस बात पर निर्भर करती है कि यूनिटरी $C P_x C^\dagger$ (जहाँ $P_x$ एक बेल-मेज़रमेंट परिणाम के अनुरूप पाउली ऑपरेटर है) का विवरण शास्त्रीय रूप से (classically) कुशलतापूर्वक कैसे निकाला जा सकता है। यह कार्य कम से कम यह निर्धारित करने जितना कठिन है कि क्या दो सर्किट पूर्णतः समतुल्य हैं। जबकि ब्रॉडबंट और काज़मी ने दिखाया कि उनका प्रोटोकॉल लॉगरिदमिक संख्या में $T$ -गेट्स (लॉगरिदमिक $T$ -काउंट) वाले क्लिफोर्ड+ $T$ सर्किट्स के लिए कुशल है, लॉगरिदमिक $T$ -डेप्थ (कम से कम एक $T$ गेट वाले समय चरणों की संख्या) वाले सर्किट्स के लिए जटिलता का प्रश्न खुला रह गया था। यह शोध पत्र इस बात को संबोधित करता है कि क्या ENIC और संबंधित कंजुगेट-एनकोडिंग कार्य, $O(\log n)$ के कम $T$ -डेप्थ वाले सर्किट्स तक सीमित होने पर भी सुलभ (tractable) रहते हैं।

कार्यप्रणाली
लेखक एक रिडक्शनिस्ट दृष्टिकोण (reductionist approach) का उपयोग करता है, जो कोडिंग थ्योरी की समस्याओं, विशेष रूप से बाइनरी लीनियर कोड्स के कोडवर्ड वेट्स (codeword weights) से क्वांटम सर्किट की समस्याओं की जटिलता को जोड़ता है।

कंजुगेट-एनकोडिंग और पाउली एक्सपेंशन: शोध पत्र $C P_x C^\dagger$ के रूप के यूनिटरीज के पाउली विस्तार (Pauli expansion) का विश्लेषण करता है। यह इन यूनिटरीज के एक "कंजुगेट-एनकोडिंग" की अवधारणा पेश करता है, जो केवल उनकी कार्यक्षमता (functionality) पर निर्भर एक शास्त्रीय विवरण है। ऐसे एनकोडिंग की दक्षता पाउली गुणांकों (Pauli coefficients) को गणना करने की क्षमता से जुड़ी हुई है।
कोडिंग थ्योरी में रिडक्शन: शोध पत्र विशिष्ट क्लिफोर्ड+ $T$ $T$ सर्किट्स (विशेष रूप से "PC-सर्किट्स") का निर्माण करता है जिनके पाउली गुणांक बाइनरी लीनियर कोड्स के वेट एन्यूमरेटर पॉलिनोमिअल्स (weight enumerator polynomials) को विशिष्ट बिंदुओं (जैसे $1/\sqrt{2}$ $1/ 2$ ) पर मूल्यांकित करते हैं।
- यह पत्र डेप्थ- $d$ प्रेजेंटेशन को परिभाषित करता है, जो एक पाउली पर लागू किए गए क्लिफोर्ड और $T$ परतों के अनुक्रम का प्रतिनिधित्व करने वाला एक डेटा स्ट्रक्चर है।
- यह एक रिकर्सिव फॉर्मूला (प्रपोजिशन 12) स्थापित करता है जो दिखाता है कि डेप्थ- $d$ प्रेजेंटेशन के पाउली गुणांक डेप्थ- $(d-1)$ प्रेजेंटेशन के गुणांकों से कैसे संबंधित होते हैं।
- विशिष्ट $T$ -डेप्थ वाले सर्किट्स के सावधानीपूर्वक निर्माण द्वारा, लेखक यह प्रदर्शित करता है कि परिणामी यूनिटरी विस्तार के गुणांक बाइनरी लीनियर कोड के कोडवर्ड्स के $1/\sqrt{2}$ की घातों के योग के अनुरूप होते हैं।
कठोरता संबंधी धारणाएं (Hardness Assumptions): यह शोध पत्र बाइनरी कोड्स के ज्ञात कठोरता परिणामों पर निर्भर करता है:
- एक विशिष्ट वेट वाले कोडवर्ड को खोजना बाइनरी कोड के लिए NP-कंप्लीट है (थ्योरम 8)।
- वेट डिस्ट्रीब्यूशन की गणना करना (और इस प्रकार वेट एन्यूमरेटर पॉलिनोमियल्स) #P-हार्ड है (थ्योरम 9)।
- लेखक पाउली विस्तार में फेजेस (phases) पर नियंत्रण बनाए रखते हुए इन कोडिंग समस्याओं को क्वांटम सर्किट सेटिंग में एम्बेड करने के लिए एक विशिष्ट परिवार "1-रेमेंडर मैट्रिसेस" (1-remainder matrices) का परिचय देता है।

मुख्य योगदान और परिणाम
यह शोध पत्र निम्नलिखित मुख्य परिणाम स्थापित करता है (थ्योरम 6):

कम T-डेप्थ पर ENIC की NP-कठोरता: जबकि $T$ -डेप्थ 2 ( $T^2$ ) वाले सर्किट्स के लिए ENIC को बहुपद समय (polynomial time) में हल किया जा सकता है, निर्णय समस्या (decision problem) $T$ -डेप्थ $O(\log n)$ वाले सर्किट्स के लिए NP-हार्ड हो जाती है। विशेष रूप से, एक स्थिरांक $K$ मौजूद है जिसके लिए $T^{K \log n}$ डोमेन पर ENIC NP-हार्ड है।
संबंधित समस्याओं की कठोरता: SUPPORT (यह निर्धारित करना कि क्या $C P_x C^\dagger$ के विस्तार में एक विशिष्ट पाउली गैर-शून्य गुणांक के साथ दिखाई देता है) और COMMUTE (यह निर्धारित करना कि क्या $C P_x C^\dagger = P_x$ ) जैसी समस्याएं भी $T^{K \log n}$ डोमेन पर NP-हार्ड दिखाई गई हैं।
गुणांक गणना की #P-कठोरता: पाउली गुणांक के सटीक मान (CONJUGATE) की गणना करने की कार्यात्मक समस्या $T^3$ डोमेन पर #P-हार्ड है।
ऑबफस्केशन के निहितार्थ: ये परिणाम दर्शाते हैं कि, जब तक $P \neq NP$ नहीं है, गेट-टेलीपोर्टेशन-आधारित अनडिस्टिंगविशेबिलिटी ऑबफस्केशन (ब्रॉडबेंट और काज़मी, 2021) के प्रोटोकॉल को लॉगरिदमिक $T$ -डेप्थ वाले क्लिफोर्ड+ $T$ सर्किट्स के लिए कुशल प्रोटोकॉल के रूप में विस्तारित नहीं किया जा सकता है। बाधा (bottleneck) आवश्यक कंजुगेट-एनकोडिंग (अर्थात $C P_x C^\dagger$ का विवरण) उत्पन्न करने की शास्त्रीय कठिनाई में है।

महत्व और दावे
यह शोध पत्र ENIC की कठोरता का एक नया, स्वतंत्र प्रमाण प्रदान करने का दावा करता है, जो ज्ञात जटिलता परिदृश्य को सामान्य सर्किट्स से कम $T$ -डेप्थ वाले सर्किट्स तक विस्तारित करता है। इसका महत्व यहाँ है:

ऑबफस्केशन प्रोटोकॉल को सीमित करना: यह प्रभावी रूप से यह नियम बनाता है कि $P \neq NP$ मानते हुए, लॉगरिदमिक $T$ -डेप्थ वाले क्लिफोर्ड+ $T$ सर्किट्स के लिए गेट-टेलीपोर्टेशन-आधारित कम्प्यूटेशनल अनडिस्टिंगविशेबिलिटी ऑबफस्केशन की संभावना नहीं है। यह महत्वपूर्ण है क्योंकि यह प्रोटोकॉल शास्त्रीय ऑबफस्केशन से क्वांटम ऑबफस्केशन बनाने के लिए प्राथमिक उम्मीदवार था।
क्वांटम और क्लासिकल जटिलता को जोड़ना: यह कार्य क्वांटम सर्किट विश्लेषण और शास्त्रीय कोडिंग थ्योरी को जोड़ता है, यह प्रदर्शित करता है कि कम-डेप्थ वाले क्वांटम सर्किट्स में पाउली गुणांकों की बीजगणितीय संरचना कठिन कोडिंग-थ्योरेटिक समस्याओं को एनकोड करती है।
जटिलता सीमाओं को परिष्कृत करना: यह ज्ञात सुलभ और अगम्य (intractable) क्षेत्रों के बीच के अंतर को कम करता है। यह दिखाता है कि जहाँ $T$ -डेप्थ 2 आसान है, वहीं कठोरता लॉगरिदमिक डेप्थ वाले क्षेत्र में उभरती है, जो फॉल्ट-टोलरेंट क्वांटम कंप्यूटिंग के लिए प्रासंगिक है जहाँ $T$ -गेट्स महंगे होते हैं।

खुले प्रश्न
शोध पत्र यह नोट करते हुए समाप्त होता है कि कठोरता की सटीक सीमा अभी भी स्पष्ट नहीं है। यह सवाल उठाता है कि क्या ENIC स्थिर $T$ -डेप्थ ( $T^{O(1)}$ ) के लिए NP-हार्ड बना रहता है या क्या यह $T$ -डेप्थ 3 के लिए बहुपद-समय (polynomial-time) के लिए हो जाता है। यह यह भी सुझाव देता है कि SUPPORT समस्या की कठोरता "फॉर्मल कोड इक्विवेलेंस" (दो कोड्स के समान वेट एन्यूमरेटर होने का निर्णय लेना) से जुड़ी हो सकती है, जो कोड इक्विवेलेंस समस्या का एक संस्करण है और ग्राफ़ आइसोमोर्फिज्म (Graph Isomorphism) से संबंधित ज्ञात है।

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