⚛️ क्वांटम भौतिकी

$\mathsf{EQP}\subseteq\mathsf{IP}$ Does Not Relativize

यह शोधपत्र एक पुनरावर्ती ऑरेकल (recursive oracle) का निर्माण करता है जिसके सापेक्ष $\mathsf{EQP}$ में एक यूनरी भाषा (unary language) मौजूद है जो $\mathsf{IP}$ (या $\mathsf{PH}$ ) में नहीं है, जिससे सटीक सहसंबंध वादों (exact correlation promises) वाले एक परिष्कृत फोरलेशन (Forrelation) समस्या के माध्यम से सटीक क्वांटम बहुपद समय (exact quantum polynomial time) और इंटरैक्टिव प्रूफ सिस्टम के बीच एक गैर-सापेक्षिक पृथक्करण (non-relativizing separation) स्थापित होता है।

मूल लेखक: Sinan Oral, Supartha Podder

प्रकाशित 2026-11-10

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

CC BY 4.0

मूल लेखक: Sinan Oral, Supartha Podder

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

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

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

उनकी खोज का मूल "फोरलेशन" (Forrelation) नामक एक गणितीय पहेली के इर्द-गिर्द घूमता है। संख्याओं की दो सूचियों की कल्पना करें, जहाँ प्रत्येक संख्या या तो धनात्मक है या ऋणात्मक। पहेली यह पूछती है कि ये दो सूचियाँ एक विशिष्ट गणितीय रूपांतरण के माध्यम से एक-दूसरे से कितनी निकटता से संबंधित हैं। इस नए अध्ययन में, शोधकर्ताओं ने पहेली के एक ऐसे संस्करण पर ध्यान केंद्रित किया जहाँ सूचियों के बीच का संबंध ठीक आधा या ठीक ऋणात्मक आधा होने का वादा किया गया है। एक क्वांटम कंप्यूटर बॉक्स से जानकारी मांगकर केवल तीन बार में यह निर्धारित कर सकता है कि इन दोनों में से कौन सा मामला सत्य है। यह एक नाजुक हस्तक्षेप पैटर्न (interference pattern) बनाकर ऐसा करता है, जहाँ एक परिदृश्य में बॉक्स से मिलने वाले उत्तर एक-दूसरे को रद्द कर देते हैं और दूसरे परिदृश्य में एक-दूसरे को सुदृढ़ करते हैं, जिससे एक स्पष्ट, निश्चित उत्तर मिलता है।

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

शोधकर्ता इन "रिपेयर्ड" (repaired) वितरणों को बनाने में सफल रहे। उन्होंने सिद्ध किया कि इन सटीक समायोजनों को करने के बाद भी, परिणामी सूचियाँ वर्तमान जटिलता सिद्धांत (complexity theory) के भीतर काम करने वाले किसी भी क्लासिकल कंप्यूटर के लिए अविभेद्य बनी रहीं। इसमें वे कंप्यूटर शामिल हैं जो इंटरैक्टिव प्रूफ (interactive proofs) चलाते हैं, जहाँ एक सत्यापनकर्ता (verifier) एक शक्तिशाली प्रवर (prover) से प्रश्न पूछता है, और वे कंप्यूटर जो पॉलीनोमियल हाइरार्की (polynomial hierarchy) के भीतर काम करते हैं, जो जटिल तार्किक समस्याओं का एक विस्तृत वर्ग है। प्रमाण ने दिखाया कि संदेशों का आदान-प्रदान चाहे कितनी भी बार किया गया हो या तार्किक तर्क कितना भी गहरा क्यों न हो, क्लासिकल कंप्यूटर विश्वसनीय रूप से दो प्रकार की सूचियों के बीच अंतर नहीं कर सका। इसके विपरीत, क्वांटम कंप्यूटर केवल तीन क्वेरीज़ के साथ उन्हें पूर्ण निश्चितता के साथ अलग कर सकता था।

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

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

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

तकनीकी सारांश: EQP ⊆ IP सापेक्षतावादी नहीं है

समस्या विवरण
यह शोध पत्र इस प्रश्न को संबोधित करता है कि क्या क्वांटम जटिलता वर्गों (complexity classes) का शास्त्रीय इंटरैक्टिव प्रूफ सिस्टम के भीतर समावेशन सापेक्षतावादी (relativize) है। विशेष रूप से, यह जांच करता है कि क्या एक मनमाने ऑरेकल (oracle) के सापेक्ष $EQP$ (वह निर्णय समस्या जो सटीक रूप से क्वांटम बहुपद समय में हल की जा सकती है) $IP$ (इंटरैक्टिव प्रूफ) और $PH$ (पॉलिनोमियल हाइरार्की) के भीतर समाहित है। जबकि यह ज्ञात है कि अनरिलेटिवाइज्ड (unrelativized) दुनिया में $BQP \subseteq PSPACE = IP$ है, बाउलैंड, हुआंग, नटराजन, शालिट और ताल [BHNST26] ने हाल ही में यह दिखाते हुए यह सिद्ध किया है कि यह समावेशन सापेक्षतावादी नहीं है, जिसके लिए उन्होंने एक ऐसा ऑरेकल $O$ निर्मित किया जिसके लिए $BQP^O \not\subseteq IP^O$ है। यह शोध पत्र उस पृथक्करण को सटीक क्वांटम सेटिंग तक विस्तारित करता है, यह सिद्ध करते हुए कि एक रिकर्सिव (recursive) ऑरेकल $O$ मौजूद है जिसके लिए $EQP^O \not\subseteq IP^O$ और $EQP^O \not\subseteq PH^O$ है।

कार्यप्रणाली
लेखक एक रिकर्सिव बूलियन ऑरेकल $O$ और एक यूनरी भाषा $L$ का निर्माण करते हैं जो इन वर्गों को अलग करती है। यह पृथक्करण फोरेलेशन (Forrelation) समस्या के एक संस्करण पर आधारित है, जो दो बूलियन फलनों $f, g: \{0, 1\}^n \to \{\pm 1\}$ के बीच अंतर करती है, जो दूसरे के फूरियर ट्रांसफॉर्म के साथ उनके सामान्यीकृत सहसंबंध (normalized correlation) पर आधारित है।

सटीक प्रतिज्ञा (Exact Promise): पिछले कार्यों के विपरीत, जो अनुमानित सहसंबंधों (approximate correlations) का उपयोग करते थे, यह शोध पत्र सटीक प्रतिज्ञा पर ध्यान केंद्रित करता है जहाँ फोरेलेशन मान बिल्कुल $+1/2$ या $-1/ -1/2$ होता है।
क्वांटम एल्गोरिदम: एक समान बहुपद-समय क्वांटम एल्गोरिदम निर्मित किया गया है जो इस प्रतिज्ञा को निश्चितता के साथ ठीक तीन फेज़ क्वेरीज़ (phase queries) का उपयोग करके हल करता है। एल्गोरिदम एक मानक एक-क्वेरी इंटरफेरेंस टेस्ट पर एम्प्लीट्यूड एम्प्लीफिकेशन (amplitude amplification) का उपयोग करता है।
शास्त्रीय अविभेद्यता (Classical Indistinguishability): मुख्य तकनीकी चुनौती $E_{n, \sigma}$ (जहाँ $\sigma \in \{+1, -1\}$ ) प्रायिकता वितरणों का निर्माण करना है जो बिल्कुल प्रतिज्ञा सेटों $L_{n, \sigma}$ (जहाँ फोरेलेशन $\sigma/2$ है) पर समर्थित हैं, ताकि ये वितरण किसी भी संसाधन-बद्ध शास्त्रीय परीक्षण (चाहे वह इंटरैक्टिव वेरीफायर हो या बाउंडेड-डेप्थ सर्किट) द्वारा यूनिफॉर्म वितरण से अविभेद्य हों।

मुख्य तकनीकी योगदान
यह शोध पत्र निरंतर गाऊसी वितरणों (Gaussian distributions) और सटीक असतत (discrete) प्रतिज्ञा सेटों के बीच के अंतर को पाटने के लिए एक नवीन "रिपेयर विधि" (repair method) पेश करता है, जो अविभेद्यता को बनाए रखते हुए कार्य करती है:

गाऊसी संदर्भ और सशर्त स्वतंत्रता (Gaussian Reference and Conditional Independence): निर्माण एक गाऊसी-साइन वितरण $G_{n, \sigma}$ से शुरू होता है और एक सशर्त उत्पाद वितरण $P_{n, \sigma}$ की ओर संक्रमण करता है। इस चरण में अंतर्निहित गाऊसीय चरों के परिमाण को स्वतंत्र गाऊसीय चरों से बदलना शामिल है ताकि, $f$ के साइन वेक्टर पर सशर्त होने पर, $g$ के साइन स्वतंत्र हों।
काउंट रिपेयर (Count Repair): सटीक फोरेलेशन प्रतिज्ञा (फूरियर गुणांकों के भारित साइन के योग पर एक पूर्णांक प्रतिबंध) को लागू करने के लिए, लेखक "काउंट रिपेयर" प्रक्रिया पेश करते हैं। वे $f$ के फूरियर गुणांकों के आधार पर निर्देशांकों को "वेट बिन्स" (weight bins) में विभाजित करते हैं। प्रत्येक बिन के भीतर, वे वैश्विक ऊर्जा प्रतिबंध को सटीक रूप से संतुष्ट करने के लिए धनात्मक साइन की संख्या को नियत रूप से समायोजित करते हैं।
अविभेद्यता संरक्षण (Indistinguishability Preservation): यह शोध पत्र सिद्ध करता है कि यह रिपेयर प्रक्रिया शास्त्रीय परीक्षणों के स्वीकृति प्रायिकता को महत्वपूर्ण रूप से परिवर्तित नहीं करती है।
- कॉन्वेक्स टेस्ट्स (Convex Tests) के लिए (जो इंटरैक्टिव प्रूफ का मॉडल हैं): लेखक सशर्त माध्यों और परीक्षणों के लिप्सचिट्ज़ गुण (Lipschitz property) पर आधारित एक कपलिंग तर्क का उपयोग करते हैं। वे दिखाते हैं कि बिन काउंट में भिन्नात्मक परिवर्तन इतना छोटा है कि अपेक्षा अंतर नगण्य है।
- बूलियन टेस्ट्स (Boolean Tests) के लिए (जो $PH$ का मॉडल हैं): वे "प्रतिबंध-स्थिर क्रिटिकैलिटी" (restriction-stable criticality) की अवधारणा का उपयोग करते हैं। बिन थ्रेशोल्ड के आसपास अनिश्चितता की एक संकीर्ण खिड़की छोड़कर, वे एक रैंडम रिस्ट्रिक्शन (random restriction) का निर्माण करते हैं जो रिपेयर्ड वितरण और उत्पाद वितरण दोनों को उच्च प्रायिकता के साथ विस्तारित करता है। यह रैंडम रिस्ट्रिक्शन के तहत निर्णय वृक्ष की गहराई (decision tree depth) के ज्ञात बंधों को लागू करने की अनुमति देता है।
विश्लेषणात्मक उपकरण: यह शोध पत्र परिमाणों को बदलने और सहप्रसरणों (covariances) को इंटरपोलेट करने से उत्पन्न त्रुटियों को बांधने के लिए लिंडबर्ग विधि (Lindeberg method) और प्राइस के फॉर्मूला (Price's formula) का उपयोग करता है, जिससे यह सुनिश्चित होता है कि गाऊसी संदर्भ से सटीक वितरण में संक्रमण केवल लुप्त होने वाले त्रुटि पदों (vanishing error terms) के साथ होता है।

परिणाम
मुख्य परिणाम प्रमेय 1.1 है: एक रिकर्सिव बूलियन ऑरेकल $O$ और एक यूनरी भाषा $L$ मौजूद हैं जैसे कि:

$L \in EQP^O$ (एक 3-क्वेरी सटीक क्वांटम एल्गोरिदम द्वारा निर्धारित)।
$L \notin IP^O$ ।
$L \notin PH^O$ ।

यह पृथक्करण निजी यादृच्छिकता (private randomness) और अनियंत्रित प्रूवर्स (unrestricted provers) वाले इंटरैक्टिव प्रूफ और पूरी पॉलिनोमियल हाइरार्की के लिए मान्य है। प्रमाण यह दिखाने पर निर्भर करता है कि किसी भी निश्चित शास्त्रीय उम्मीदवार (वेरीफायर या सर्किट) के लिए, एक पर्याप्त बड़ा इनपुट लेंथ मौजूद है जहाँ उम्मीदवार सटीक वितरणों $E_{n, +}$ और $E_{n, -}$ को यूनिफॉर्म वितरण से पहचानने में विफल रहता है, और फलस्वरूप प्रतिज्ञा सेटों को पहचानने में विफल रहता है।

महत्व
यह शोध पत्र बाउलैंड एट अल. [BHNST26] के $BQP$ से $EQP$ तक के ऑरेकल पृथक्करण को मजबूत करने का दावा करता है। यह महत्वपूर्ण है क्योंकि $EQP$ उन समस्याओं के वर्ग का प्रतिनिधित्व करता है जिन्हें शून्य त्रुटि प्रायिकता के साथ क्वांटम कंप्यूटरों द्वारा हल किया जा सकता है, जो बाउंडेड-एरर क्लास $BQP$ की तुलना में एक सख्त आवश्यकता है। यह परिणाम दर्शाता है कि $BQP \subseteq IP$ के सापेक्षतावादी न होने का अवरोध सुदृढ़ है और तब भी बना रहता है जब क्वांटम एल्गोरिदम के लिए सटीक होना आवश्यक हो।

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

लेखक स्पष्ट रूप से बताते हैं कि पृथक्करण एक रिकर्सिव ऑरेकल के माध्यम से प्राप्त किया गया है जिसे निर्णायक प्रतिज्ञा सेटों (decidable promise sets) के विस्तृत खोज (exhaustive search) के माध्यम से निर्मित किया गया है, जिससे यह सुनिश्चित होता है कि ऑरेकल कंप्यूटेबल है, हालांकि यह आवश्यक रूप से पॉलिनोमियल-टाइम कंप्यूटेबल नहीं है। यह कार्य नए प्रयोगात्मक कार्यान्वयन या सैद्धांतिक जटिलता ढांचे के बाहर अनुप्रयोगों का प्रस्ताव नहीं करता है।

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