⚛️ quantum physics

Oracle Separations in the Fourier Hierarchy

यह शोध पत्र यह सिद्ध करके एक खुले प्रश्न का समाधान करता है कि प्रत्येक स्थिरांक $k \ge 2$ के लिए, एक ऐसा ओरेकलल (oracle) अस्तित्व में है जिसके सापेक्ष फूरियर पदानुक्रम (Fourier hierarchy) का $(k+1)$ -वाँ स्तर $k$ -वें स्तर को सख्ती से समाहित करता है, जो यह प्रदर्शित करता है कि प्रत्येक अतिरिक्त हैडामार्ड परत (Hadamard layer) कम्प्यूटेशनल शक्ति को सख्ती से बढ़ाती है, भले ही चरण (phase) और मानक ओरेकल एक्सेस के बीच अंतर किया जा रहा हो।

मूल लेखक: Atul Mantri

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

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

CC BY 4.0

मूल लेखक: Atul Mantri

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

क्वांटम कंप्यूटिंग के क्षेत्र में, वैज्ञानिक लगातार यह समझने की कोशिश कर रहे हैं कि इन मशीनों की वास्तविक सीमाएं क्या हैं। इस जांच के केंद्र में एक मौलिक प्रश्न है: केवल एक विशिष्ट प्रकार के ऑपरेशन के अधिक स्तर (layers) जोड़कर एक क्वांटम कंप्यूटर को कितनी शक्ति प्राप्त होती है? इसे समझने के लिए, कल्पना करें कि एक क्वांटम कंप्यूटर संभावनाओं की तरंगों का उपयोग करके सूचना को नियंत्रित करने वाली एक मशीन है। अधिकांश समय, ये मशीनें मानक गणनाएं करती हैं, लेकिन कभी-कभी इन्हें "सुपरपोजिशन" (superposition) की स्थिति बनाने की आवश्यकता होती है, जहाँ सूचना का एक एकल बिट एक साथ कई अवस्थाओं में मौजूद होता है। यही उनकी अद्वितीय शक्ति का स्रोत है। हालाँकि, इन सुपरपोजिशन को बनाना और बनाए रखना कठिन और कम्प्यूटेशनल संसाधनों के मामले में महंगा है। शोधकर्ता लंबे समय से यह जानना चाहते थे कि क्या शक्ति का एक सख्त पदानुक्रम (hierarchy) है, जहाँ इस विशेष ऑपरेशन का केवल एक और स्तर जोड़ने से मशीन उन समस्याओं को हल करने में सक्षम हो जाती है जो पहले असंभव थीं, चाहे समस्या में कितने भी अन्य संसाधन क्यों न झोंक दिए जाएं। 'फूरियर पदानुक्रम' (Fourier hierarchy) के रूप में जानी जाने वाली यह पहेली लगभग दो दशकों से सैद्धांतिक कंप्यूटर विज्ञान में एक केंद्रीय पहेली रही है।

वर्षों से, यह ज्ञात था कि इस ऑपरेशन का बिल्कुल पहला स्तर शास्त्रीय रैंडमाइज्ड (classical randomized) कंप्यूटरों की शक्ति के बराबर था, जबकि दूसरा स्तर बड़ी संख्याओं के गुणनखंड (factoring) जैसी प्रसिद्ध समस्याओं को हल करने के लिए पर्याप्त शक्तिशाली था। लेकिन उसके बाद क्या हुआ? क्या तीसरे स्तर ने संभावनाओं की एक नई दुनिया खोली, या शक्ति स्थिर हो गई? वर्जीनिया टेक के एक शोधकर्ता अतुल मंत्री ने अब इस प्रश्न का उत्तर एक विशिष्ट गणितीय ढांचे के भीतर एक निश्चित "हाँ" के साथ दिया है। एक नए अध्ययन में, मंत्री सिद्ध करते हैं कि इस पदानुक्रम के प्रत्येक स्तर के लिए, सुपरपोजिशन का एक और स्तर जोड़ना एक ऑरेकल (oracle) के सापेक्ष मशीन की कम्प्यूटेशनल शक्ति को सख्ती से बढ़ाता है। इसका अर्थ यह है कि इन कृत्रिम परिदृश्यों के भीतर, पदानुक्रम अनंत और निरंतर बढ़ता हुआ है; ऐसा कोई बिंदु नहीं है जहाँ अधिक परतें जोड़ने से कंप्यूटर की क्षमता बढ़ना रुक जाए।

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

यह अध्ययन क्वांटम कंप्यूटरों द्वारा सूचना तक पहुँचने के दो तरीकों के बीच एक सूक्ष्म लेकिन महत्वपूर्ण अंतर को भी स्पष्ट करता है। एक विधि, जिसे 'फेज क्वेरी' (phase query) कहा जाता है, उत्तर को लिखे बिना मशीन की आंतरिक स्थिति को बदल देती है। दूसरी ओर, एक मानक क्वेरी, उत्तर को एक रजिस्टर में लिखती है, जिससे मशीन उस उत्तर के आधार पर अपने तर्क की शाखाएं (branching logic) बना सकती है। शोध यह प्रदर्शित करता है कि परतों की समान संख्या पर, मानक क्वेरी विधि फेज क्वेरी विधि की तुलना में स्पष्ट रूप से अधिक शक्तिशाली है। ऐसा इसलिए है क्योंकि उत्तर लिखने की क्षमता मशीन को ऐसे निर्णय लेने की अनुमति देती है जिन्हें केवल फेज-आधारित विधि, समान मात्रा में सुपरपोजिशन के साथ भी, दोहरा नहीं सकती। यह खोज इन दोनों एक्सेस मॉडलों की सापेक्ष शक्ति के बारे में एक लंबे समय से चल रहे विवाद को सुलझाती है और दिखाती है कि उत्तर को रिकॉर्ड करने की क्षमता एक वास्तविक कम्प्यूटेशनल लाभ प्रदान करती है जिसे केवल फेज परिवर्तनों द्वारा सिम्युलेट नहीं किया जा सकता।

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

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

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

तकनीकी सारांश: फूरियर पदानुक्रम में ओरेकल पृथक्करण (Oracle Separations in the Fourier Hierarchy)

समस्या विवरण
फूरियर पदानुक्रम ( $FH_k$ ), जिसे शी (2005) द्वारा पेश किया गया था, क्वांटम गणनाओं को इस आधार पर वर्गीकृत करता है कि वे कितने वैश्विक हैडामार्ड स्तरों (फूरियर गहराई) का उपयोग करती हैं। इन स्तरों के बीच, सर्किट आधार-संरक्षण संचालन (परम्यूटेशन और फेज़ अटैचमेंट) करता है लेकिन नए सुपरपोजिशन नहीं बना सकता। यह पदानुक्रम $FH_0 \subseteq FH_1 \subseteq FH_2 \subseteq \dots$ के रूप में परिभाषित है। जबकि मानक-क्वेरी मॉडल में $FH_0 = P$ और $FH_1 = BPP$ है, और $FH_2$ फैक्टोरिंग और साइमन की समस्या (Simon's problem) को समाहित करता है, यह एक खुला प्रश्न था कि क्या प्रत्येक अतिरिक्त हैडामार्ड स्तर गणना शक्ति को सख्ती से बढ़ाता है। शी ने अनुमान लगाया था कि सभी $k \ge 0$ के लिए $FH_k \subsetneq FH_{k+1}$ होगा और उन्होंने पहले चरण के रूप में क्रमिक स्तरों के बीच ओरेकल पृथक्करण (oracle separations) की मांग की थी। इस कार्य से पूर्व, किसी भी स्तर $k \ge 2$ के लिए कोई पृथक्करण ज्ञात नहीं था।

कार्यप्रणाली (Methodology)
लेखक दो अलग-अलग क्वेरी मॉडलों में प्रत्येक स्थिरांक $k \ge 2$ के लिए ओरेकल पृथक्करण का निर्माण करके इस प्रश्न को हल करता है:

फेज़-क्वेरी मॉडल (Phase-query model): क्वेरी एक आधार अवस्था को एक चिह्न से गुणा करती है ( $F(x)|x\rangle \to (-1)^{F(x)}|x\rangle$ )।
मानक-क्वेरी मॉडल (Standard-query model): क्वेरी उत्तर को एक रजिस्टर में लिखती है ( $|y\rangle|b\rangle \to |y\rangle|b \oplus F(y)\rangle$ )।

कार्यप्रणाली का मुख्य आधार फोरेलेशन (Forrelation) समस्या है, विशेष रूप से इसका $K$ -गुना सामान्यीकरण, जो फूरियर रूपांतरणों के साथ बारी-बारी से चलने वाले बूलियन फलनों की एक श्रृंखला के बीच सहसंबंध को मापता है। लेखक निम्नलिखित संरचनात्मक अंतर्दक्षताओं और उपकरणों का उपयोग करता है:

विषम बनाम सम फोरेलेशन (Odd vs. Even Forrelation): लेखक फोरेलेशन क्रम $K$ की समता (parity) का लाभ उठाता है। वे दिखाते हैं कि $(2k-1)$ -गुना फोरेलेशन (विषम क्रम) को गहराई $k+1$ वाले $k$ गहराई के दो हिस्सों में विभाजित करने वाले कंट्रोल-क्यूबिट इंटरफेरेंस टेस्ट (या स्वैप टेस्ट) का उपयोग करके $k+1$ फूरियर गहराई पर हल किया जा सकता है। इसके विपरीत, $(2k-2)$ -गुना फोरेलेशन (सम क्रम) गहराई $k$ पर हल करने योग्य है।
अनुकूलनशीलता द्वारा गहराई का अनुकरण (Simulation of Depth by Adaptivity - Phase Model): एक प्रमुख संरचनात्मक लेम्मा यह प्रदर्शित करता है कि फेज़-क्वेरी मॉडल में $q$ क्वेरी करने वाला कोई भी $FH_k$ सर्किट $k-1$ राउंड की अनुकूलनशीलता (adaptivity) और प्रति राउंड $q$ समानांतर क्वेरी वाले क्वांटम क्वेरी एल्गोरिदम द्वारा सटीक रूप से अनुकरण किया जा सकता है। यह लेखक को बाउंडेड-राउंड एल्गोरिदम (गिरिश आदि, 2024) पर साहित्य से लोअर बाउंड्स आयात करने की अनुमति देता है।
फूरियर ग्रोथ बाउंड्स (Fourier Growth Bounds): लोअर बाउंड्स स्वीकृति प्रायिकता के फूरियर भार (Fourier weight) पर निर्भर करते हैं।
- फेज़ मॉडल के लिए, सिमुलेशन लेम्मा समस्या को $k-1$ राउंड एल्गोरिदम के फूरियर विकास को बांधने तक सीमित कर देता है। लेखक बंसल-सिन्हा मानदंड (Bansal–Sinha criterion) लागू करता है, यह दिखाते हुए कि गहराई- $k$ वाले सर्किट्स का फूरियर भार इतना धीरे बढ़ता है कि वे संरचित फोरेलेशन वितरणों को यूनिफॉर्म वितरणों से अलग नहीं कर पाते जब क्रम $K = 2k-1$ हो।
- मानक मॉडल के लिए, राउंड सिमुलेशन विफल हो जाता है क्योंकि मानक क्वेरी पिछले उत्तरों के आधार पर अनुकूलनशील ब्रांचिंग (adaptive branching) की अनुमति देती है। लेखक एक नई तकनीक विकसित करता है: प्रत्येक आधार-संरक्षण ब्लॉक को उसके निर्णय वृक्ष (decision tree) के लीव्स के माध्यम से गुणनखंडित करना। यह सीधे फूरियर ग्रोथ बाउंड प्रदान करता है, जो अनुकूलनशील मानक-क्वेरी सर्किट्स के लिए थोड़ा कमजोर (k पर चरघांकी रूप से निर्भर) है, जिसके लिए उच्च फोरेलेशन क्रम ( $K = 2k+1$ ) की आवश्यकता होती है।
ओरेकल निर्माण (Oracle Construction): वितरण अंतराल (distributional gaps) को वर्स्ट-केस ओरेकल पृथक्करण में बदलने के लिए, लेखक सफलता की प्रायिकता को बढ़ाने के लिए एक डायरेक्ट प्रोडक्ट निर्माण (कई फोरेलेशन इंस्टेंस का OR) का उपयोग करता है, जिसके बाद एक हाइब्रिड तर्क और डायगोनलाइजेशन का उपयोग करके एक एकल ओरेकल परिवार $O$ का निर्माण किया जाता है जो सभी यूनिफॉर्म $FH_k$ परिवारों को हरा देता है लेकिन एक $FH_{k+1}$ सर्किट द्वारा निर्णायक होता है।

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

निकटवर्ती-स्तर पृथक्करण (Adjacent-Level Separations - Phase Model): प्रत्येक स्थिरांक $k \ge 2$ के लिए, एक ओरेकल $O$ मौजूद है जिससे $FH^O_k \subsetneq FH^O_{k+1}$ होता है। पृथ करने वाली समस्या $(2k-1)$ -गुना फोरेलेशन इंस्टेंस का OR है। यह $O_k(1)$ क्वेरी के साथ गहराई $k+1$ पर हल करने योग्य है लेकिन किसी भी गहराई- $k$ वाले सर्किट के लिए विफल हो जाता है जो $N^{c_k}$ क्वेरी (जहाँ $c_k = \Theta(1/k^2)$ ) तक करता है।
निकटवर्ती-स्तर पृथक्करण (Adjacent-Level Separations - Standard Model): इसी प्रकार, प्रत्येक $k \ge 2$ के लिए, एक ओरेकल $O$ है जिससे $FH^O_{k,std} \subsetneq FH^O_{k+1,std}$ होता है। यहाँ पृथ करने वाली समस्या $(2k+1)$ -गुना फोरेलेशन का OR है। अनुकूलनशील मानक-क्वेरी के कारण लोअर बाउंड के लिए एक अलग ग्रोथ विश्लेषण की आवश्यकता होती है।
क्वेरी मॉडलों का पृथक्करण (Separation of Query Models): यह पत्र सिद्ध करता है कि मानक-क्वेरी मॉडल समान फूरियर गहराई पर फेज़-क्वेरी मॉडल की तुलना में अधिक शक्तिशाली है। विशेष रूप से, प्रत्येक $k \ge 2$ के लिए, $FH^O_k \subsetneq FH^O_{k,std}$ है। पृथ करने वाली समस्या $(2k-1)$ -गुना फोरेलेशन का OR है, जिसे मानक गहराई $k$ हल कर सकता है (मध्य बिट को पढ़कर) लेकिन फेज़ गहराई $k$ नहीं कर सकता।
BQP से पृथक्करण (Separation from BQP): लेखक दिखाता है कि सभी सीमित फूरियर गहराई स्तरों का यूनियन एक ओरेकल के सापेक्ष $BQP$ में सख्ती से समाहित है। विशेष रूप से, $K = \Theta(\log n)$ क्रम वाला फोरेलेशन $BQP$ में है लेकिन इसे हल करने के लिए $\approx \frac{1}{4} \log_2 n$ तक की फूरियर गहराई की आवश्यकता होती है, जो यह दर्शाता है कि $\left(\bigcup_k FH_k\right)^O \subsetneq BQP^O$ ।
गैर-सापेक्षिकरण (Non-Relativization): यह पत्र प्रदर्शित करता है कि निकटवर्ती-स्तर का प्रश्न सापेक्षिकृत (relativize) नहीं होता है। जबकि ऊपर दिए गए पृथक्करण विशिष्ट ओरेकल के सापेक्ष मान्य हैं, एक PSPACE-पूर्ण ओरेकल मौजूद है जिसके सापेक्ष सभी $k \ge 2$ के लिए $FH_k = PSPACE$ है। अतः, अनरिलेटिवइज्ड सेटिंग में शी के अनुमान को हल करने के लिए गैर-सापेक्षिक (non-relativizing) तकनीकों की आवश्यकता है।

महत्व और दावे
यह पत्र दावा करता है कि उसने सभी स्तरों $k \ge 2$ के लिए दोनों मानक क्वेरी मॉडलों में शी के "निकटवर्ती-स्तर प्रश्न" को हल कर दिया है, जो 2005 से खुला प्रश्न बना हुआ था। इसका महत्व निम्नलिखित में निहित है:

संरचनात्मक लक्षण वर्णन: फूरियर गहराई और क्वेरी अनुकूलनशीलता के बीच एक सटीक संबंध स्थापित करना (विशेष रूप से, कि फेज़-क्वेरी गहराई $k$ , $k-1$ समानांतर क्वेरी राउंड के बराबर है)।
कार्यप्रणालीगत प्रगति: अनुकूलनशील मानक-क्वेरी सर्किट्स के लिए फूरियर विकास को बांधने के लिए एक निर्णय-वृक्ष गुणनखंड (decision-tree factorization) तकनीक पेश करना, जो गैर-अनुकूलनशील सेटिंग्स से परे फूरियर वेट पद्धति का विस्तार करती है।
पदानुक्रम स्थान (Hierarchy Placement): फूरियर पदानुक्रम को शास्त्रीय वर्गों ( $P, BPP, PH$ ) और पूर्ण क्वांटम शक्ति ( $BQP$ ) के सापेक्ष स्थान देना। यह पुष्टि करता है कि दूसरा स्तर ( $FH_2$ ) एक ओरेकल के सापेक्ष पॉलीनोमियल हाइरार्की (PH) से आगे निकल जाता है, फिर भी पूरा पदानुक्रम $BQP$ से काफी कमजोर है।
अनरिलेटिवइज्ड अनुमान पर विनम्रता: लेखक स्पष्ट रूप से कहता है कि उनके परिणाम शी के अनरिलेटिवइज्ड अनुमान ( $FH_k \neq FH_{k+1}$ बिना ओरेकल के) को हल नहीं करते हैं, क्योंकि कोलैप्सिंग ओरेकल का अस्तित्व यह सिद्ध करता है कि सापेक्षिकीय तकनीकें इस उद्देश्य के लिए अपर्याप्त हैं।

यह कार्य फूरियर पदानुक्रम की एक पूर्ण ओरेकल-सैद्धांतिक तस्वीर प्रदान करता है, जो प्रत्येक स्तर पर इसकी शुद्धता की पुष्टि करता है और क्वांटम इंटरफेरेंस के लिए संसाधन के रूप में हैडामार्ड स्तरों की शक्ति को स्पष्ट करता है।

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