⚛️ quantum physics

One-Query Quantum Algorithms for the Index- $q$ Hidden Subgroup Problem

यह शोध पत्र इंडेक्स- $q$ हिडन सबग्रुप प्रॉब्लम (Hidden Subgroup Problem) को प्रस्तुत करता है और एक सिंगल-क्वेरी क्वांटम एल्गोरिदम पेश करता है जो किसी भी एबेलियन संरचना के लिए इंडेक्स 1 और $q$ वाले सबग्रुप्स के बीच अंतर करता है, जबकि साथ ही विशिष्ट चक्रीय और संरचनात्मक स्थितियों के तहत सबग्रुप की सटीक पहचान करने में सक्षम बनाता है जो $q \in \{2, 3\}$ के लिए बिना किसी शर्त के संतुष्ट होती हैं।

मूल लेखक: Amit Te'eni, Yaron Oz, Eliahu Cohen

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

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

CC BY 4.0

मूल लेखक: Amit Te'eni, Yaron Oz, Eliahu Cohen

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

कल्पना कीजिए कि आप एक जासूस हैं जो एक काले डिब्बे (black box) के भीतर छिपे रहस्य को सुलझाने की कोशिश कर रहे हैं। यह काला डिब्बा (जिसे "ओरेकल" कहा जाता है) एक इनपुट लेता है और आपको एक आउटपुट देता है, लेकिन आप नहीं जानते कि यह कौन सा नियम उपयोग करता है। आपका लक्ष्य कम से कम अनुमान लगाकर उस नियम का पता लगाना है।

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

यह शोध पत्र एक सरल प्रश्न पूछता है: क्या प्रिज्म वास्तव में आवश्यक है, या यह केवल यह बताने का एक सुविधाजनक तरीका है कि क्या हो रहा है?

यहाँ उनके निष्कर्षों का रोजमर्रा के उदाहरणों के साथ विवरण दिया गया है:

1. पुराने नियम: DJ बनाम BV

लेखक दो प्रसिद्ध क्वांटम पहेलियों को देखते हैं:

डेउश-जोज़ा (DJ) पहेली: कल्पना कीजिए कि एक मशीन है जो या तो हमेशा "हाँ" कहती है (स्थिर/constant) या "हाँ" आधे समय कहती है और "नहीं" आधे समय (संतुलित/balanced)। शोध पत्र दिखाता है कि इसे हल करने के लिए आपको वास्तव में प्रिज्म की आवश्यकता नहीं है। आपको बस एक "निष्पक्ष" स्विच की आवश्यकता है जो हर संभावना के साथ समान व्यवहार करता है। प्रिज्म (QFT) काम तो करता है, लेकिन यह अखरोट तोड़ने के लिए हथौड़े का उपयोग करने जैसा है; कोई भी उपकरण जो एक निष्पक्ष मिश्रण बनाता है, उतना ही अच्छा काम करता है।
बर्नस्टीन-वज़िरानी (BV) पहेली: यह थोड़ा कठिन संस्करण है जहाँ मशीन एक विशिष्ट गुप्त कोड (एक सबग्रुप) छिपाती है। यहाँ, प्रिज्म अनिवार्य है। छिपे हुए पैटर्न को स्पष्ट रूप से देखने का यही एकमात्र तरीका है।

2. नई पहेली: "इंडेक्स-q" रहस्य

लेखकों ने एक नई, सामान्यीकृत पहेली बनाई है जिसे इंडेक्स-q हिडन सबग्रुप प्रॉब्लम कहा जाता है।

सेटअप: आपके पास लोगों का एक समूह (डोमेन) है। वहाँ एक गुप्त सबग्रруп (समूह के भीतर एक छोटा क्लब) है।
रहस्य: आपको यह निर्धारित करना है कि क्या गुप्त क्लब पूरे समूह का हिस्सा है (इंडेक्स 1) या वह समूह का एक विशिष्ट अंश है (इंडेक्स $q$ )।
लक्षत: उस गुप्त क्लब के सटीक सदस्यों को खोजना।

3. बड़ी खोज: एक अनुमान ही काफी है

लेखकों ने एक नया क्वांटम एल्गोरिदम डिज़ाइन किया है जो इस पहेली को एक ही अनुमान (एक क्वेरी) के साथ हल करता है।

निर्णय (हाँ/नहीं): उन्होंने सिद्ध किया है कि आप किसी भी तरह से आउटपुट लेबल करें, आप एक ही बार में बता सकते हैं कि गुप्त क्लब पूरा समूह है या केवल एक अंश। इसके लिए आपको प्रिज्म की आवश्यकता नहीं है; बस एक निष्पक्ष मिश्रण ही पर्याप्त है।
पहचान (वे कौन हैं?): वास्तव में गुप्त क्लब के सदस्यों का नाम लेने के लिए, आपको आमतौर पर प्रिज्म (QFT) की आवश्यकता होती है। हालाँकि, लेखकों ने एक विशेष स्थिति पाई है:
- यदि गुप्त क्लब समूह को एक चक्रीय (cyclic) पैटर्न में विभाजित करता है (जैसे कि एक घड़ी का चेहरा जहाँ संख्याएँ घूमकर वापस आती हैं) और आउटपुट लेबल को उस घड़ी के पैटर्न में व्यवस्थित किया जा सकता है, तो एक ही अनुमान पूरे क्लब को पूरी तरह से पहचानने के लिए पर्याप्त है।
- जादुई संख्याएँ: यह स्वतः ही काम करता है यदि अंश (fraction) 2 या 3 है।
  - इंडेक्स 2: सिक्के उछालने की तरह (Heads/Tails)। आप आउटपुट को कैसे भी लेबल करें, आप एक ही बार में गुप्त क्लब को ढूंढ सकते हैं।
  - इंडेक्स 3: तीन-तरफा पासे (three-sided die) की तरह। फिर से, एक शॉट ही काफी है।
- सीमा: यदि अंश 4 या उससे अधिक है, और समूह एक साधारण घड़ी के चेहरे जैसा नहीं है, तो एक अनुमान पूरी तरह निश्चित होने के लिए पर्याप्त नहीं है। आप भाग्यशाली हो सकते हैं, लेकिन आप गारंटी नहीं दे सकते।

4. यह क्यों महत्वपूर्ण है (शोर-किटाव तुलना)

एक पुराना, प्रसिद्ध तरीका (शोर-किटाव) है जो प्रिज्म का उपयोग करता है। यह कई नमूने लेने और उन्हें औसत निकालने जैसा है, जैसे कि सिक्के को 1,000 बार उछालकर उसके आकार का अनुमान लगाने की कोशिश करना।

लेखक दिखाते हैं कि उनके विशिष्ट "इंडेक्स-q" पहेली के लिए, पुराना तरीका एक एकल प्रयास के लिए अक्षम है। यह विफल हो सकता है या गलत उत्तर दे सकता है।
उनका नया तरीका एक सुपर-सटीक स्कैनर की तरह है जो केवल एक नज़र में (यदि पहेली "चक्रीय" शर्त को पूरा करती है) हर बार सही उत्तर देता है।

5. कड़ियों को जोड़ना

बर्नस्टीन-वज़िरानी (BV) एल्गोरिदम वास्तव में इस नए "इंडेक्स-2" पहेली का एक विशेष मामला है।

BV एल्गोरिदम मूल रूप से "इंडेक्स-2" समस्या का समाधान है जहाँ समूह बिट्स (0 और 1) से बना है।
इस नए दृष्टिकोण से BV को देखकर, लेखक दिखाते हैं कि वहां "प्रिज्म" (हैडामार्ड ट्रांसफॉर्म) आवश्यक है क्योंकि यह स्वाभाविक रूप से एक चक्रीय संरचना (mod 2) के बारे में है।

सारांश

यह शोध पत्र जटिल गणित को हटाकर यह स्पष्ट करता है कि:

कभी-कभी (जैसे DJ पहेली में), "प्रिज्म" केवल एक भव्य वर्णन है; एक सरल निष्पक्ष स्विच काम करता है।
कभी-कभी (जैसे BV पहेली में), "प्रिज्म" ही गुप्त को अनलॉक करने की कुंजी है।
उन्होंने पहेलियों के एक व्यापक वर्ग (इंडेक्स-q) के लिए एक सार्वभौमिक वन-शॉट एल्गोरिदम बनाया है। यदि पहेली में "घड़ी जैसा" (चक्रीय) ढांचा है, तो आप एक ही क्वेरी के साथ इसे हल कर सकते हैं और 100% निश्चित हो सकते हैं। यदि ऐसा नहीं है, तो आप केवल एक प्रयास में सटीक उत्तर की गारंटी नहीं दे सकते।

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

तकनीकी सारांश: इंडेक्स- $q$ हिडन सबग्रुप प्रॉब्लम के लिए एक-क्वेरी क्वांटम एल्गोरिदम

समस्या की परिभाषा
यह शोध पत्र बीजगणितीय संरचना (algebraic structure), विशेष रूप से क्वांटम फूरियर ट्रांसफॉर्म (QFT) की भूमिका को संबोधित करता है, जो क्वांटम क्वेरी एल्गोरिदम में महत्वपूर्ण है। यह परिमित एबेलियन समूहों (finite abelian groups) के लिए हिडन सबग्रुप प्रॉब्लम (HSP) पर केंद्रित है। लेखक एक विशिष्ट संस्करण पेश करते हैं जिसे इंडेक्स- $q$ HSP कहा जाता है। इस समस्या में, एक ऑरेकल फंक्शन $f: G \to X$ एक सबग्रुप $H \le G$ को छिपाता है। यह वादा (promise) किया गया है कि सबग्रुप का इंडेक्स, $[G:H]$ , या तो $1 $है (अर्थात$ H=G $) या एक ज्ञात पूर्णांक$ q > 1$ है। लक्ष्य दोहरा है:

निर्णय (Decision): यह निर्धारित करना कि इंडेक्स $1 $है या$ q$।
पहचान (Identification): यदि संभव हो, तो ऑरेकल के एक ही क्वेरी का उपयोग करके सटीक रूप से छिपे हुए सबग्रुप $H$ की पहचान करना।

लेखक एल्गोरिदम की सफलता के लिए आवश्यक बीजगणितीय संरचना और विशिष्ट गेट-लेवल कार्यान्वयन (जैसे, क्यूबिट-आधारित सर्किट) के बीच अंतर करते हैं। वे नोट करते हैं कि जबकि QFT शोर (Shor) और साइमन (Simon) जैसे ऐतिहासिक एल्गोरिदम के केंद्र में है, डेक्युच-जोस (Deutsch–Jozsa - DJ) जैसे सरल संदर्भों में इसकी आवश्यकता हमेशा स्पष्ट नहीं होती है।

कार्यप्रणाली (Methodology)
लेखक एक एकीकृत ढांचा विकसित करते हैं जो डेक्युच-जोस-होयर (DJH) एल्गोरिदम और बर्नस्टीन-वेज़िरानी (BV) एल्गोरिदम का सामान्यीकरण करता है, जबकि उन्हें मानक शोर-किटाव (Shor–Kitaev) दृष्टिकोण के साथ विरोधाभास प्रस्तुत करता है।

संरचना और कार्यान्वयन का पृथक्करण: लेखक तर्क देते हैं कि DJ एल्गोरिदम के लिए डोमेन पर समूह संरचना या QFT की अंतर्निहित आवश्यकता नहीं है। इसके बजाय, इसे एक यूनिटरी $V$ की आवश्यकता होती जिसका पहला कॉलम एक "डेमोक्रेटिक सुपरपोजिशन" (समान आयाम/uniform amplitudes) है। यह इसे समूह होने का अनुमान लगाए बिना निरंतर (constant) और संतुलित (balanced) कार्यों के बीच अंतर करने की अनुमति देता है।
इंडेक्स- $q$ एल्गोरिदम:
- सेटअप: एल्गोरिदम हिल्बर्ट स्पेस $\mathbb{C}^G$ पर कार्य करता है। यह कैरेक्टर बेसिस में ट्रिवियल कैरेक्टर स्टेट $|\rho_0\rangle$ के साथ शुरू होता है।
- प्री-प्रोसेसिंग: एक यूनिफॉर्म सुपरपोजिशन बनाने के लिए इनवर्स QFT ( $F^\dagger$ ) लागू किया जाता है।
- ऑरेकल क्वेरी: एक फेज ऑरेकल लागू किया जाता है। "शिफ्ट-टू-फेज" ट्रिक (सेक्शन II.A) का उपयोग करके, शिफ्ट ऑरेकल $U_f^{\text{shift}}$ को कोडोमेन $X$ के एक गैर-तुच्छ कैरेक्टर $\chi$ का उपयोग करके फेज ऑरेकल $U_f^{\text{phase}}$ में परिवर्तित किया जाता है। अवस्था $\sum_g \chi(f(g)) |g\rangle$ बन जाती है।
- पोस्ट-प्रोसेसिंग: समूह $G$ पर एक QFT ( $F$ ) लागू किया जाता है। परिणामी अवस्था फंक्शन $\chi \circ f$ का फूरियर ट्रांसफॉर्म होती है।
- मापन (Measurement): कैरेक्टर बेसिस में मापन से एक कैरेक्टर $\rho$ प्राप्त होता है। एल्गोरिदम आउटपुट के रूप में $H' = \ker \rho$ देता है।
सटीक पहचान के लिए शर्तें:
एकल क्वेरी द्वारा निश्चितता के साथ $H$ की पहचान करने के लिए (अर्थात, $\ker \rho = H$ ), विशिष्ट शर्तें पूरी होनी चाहिए:
- कोटिएंट ग्रुप (quotient group) $G/H$ का क्रम $q$ के लिए चक्रीय (cyclic) होना चाहिए (या $1$ होने पर ट्रिवियल)।
- आउटपुट अल्फाबेट $X$ को $\mathbb{Z}/q\mathbb{Z}$ के अनुकूल (compatible) संरचना से सुसज्जित होना चाहिए, जो एफाइन रीलेबलिंग (ऑटोमोर्फिज्म और कांस्टेंट शिफ्ट) तक सीमित है।
- फेज ऑरेकल के लिए उपयोग किया जाने वाला कैरेक्टर $\chi$ , $f$ के इमेज पर निष्ठावान (faithful) होना चाहिए।

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

अनंर्तिक निर्णय (Unconditional Decision): शोध पत्र एक एकल-क्वेरी एल्गोरिदम प्रस्तुत करता है जो कोडोमेन $X$ के किसी भी एबेलियन स्ट्रक्चर के लिए इंडेक्स $1 $और इंडेक्स$ q$ के बीच हमेशा अंतर कर सकता है। यह DJH निर्णय क्षमता का सामान्यीकरण करता है।
छोटे $q$ के लिए सटीक पहचान: लेखक सिद्ध करते हैं कि $q \in \{2, 3\}$ $q \in {2, 3}$ के लिए, सटीक पहचान की शर्तें स्वतः पूरी हो जाती हैं, चाहे आउटपुट अल्फाबेट $X$ $X$ की लेबलिंग कैसी भी हो।
- $q=2$ के लिए, 2-तत्व वाले सेट की कोई भी लेबलिंग एक स्वैप (ऑटोमोर्फिज्म) के माध्यम से $\mathbb{Z}/2\mathbb{Z}$ के अनुकूल होती है।
- $q=3$ के लिए, 3-तत्व वाले सेट की कोई भी लेबलिंग ऑटोमोर्फिज्म और शिफ्ट के माध्यम से $\mathbb{Z}/3\mathbb{Z}$ के अनुकूल होती है।
- फलस्वरूप, इंडेक्स-2 और इंडेक्स-3 HSP को ऑरेकल के आउटपुट स्ट्रक्चर पर अतिरिक्त वादों के बिना, एक ही क्वेरी में सटीक पहचान के साथ हल किया जा सकता है।
बर्नस्टीन-वेज़िरानी एक विशेष मामला के रूप में: शोध पत्र दिखाता है कि बर्नस्टीन-वेज़िरानी समस्या इंडेक्स-2 HSP का एक उदाहरण है जहाँ $G = (\mathbb{Z}/2\mathbb{Z})^n$ है। BV एल्गोरिदम को इंडेक्स- $q$ एल्गोरिदम के एक विशिष्ट कार्यान्वयन के रूप में दिखाया गया है, जो हैडामार्ड ट्रांसफॉर्म ( $(\mathbb{Z}/2\mathbb{Z})^n$ पर QFT) का उपयोग करता है।
BV में न्यूनीकरण (Reduction to BV): लेखक दिखाते हैं कि किसी भी मनमाने परिमित एबेलियन समूह $G$ पर किसी भी इंडेक्स-2 HSP को $(\mathbb{Z}/2\mathbb{Z})^n$ पर बर्नस्टीन-वेज़िरानी समस्या में बदला जा सकता है, जिसके लिए सबग्रुप $2G = \{g+g \mid g \in G\}$ को कोटिएंट किया जाता है। यह निहित करता है कि किसी भी इंडेक्स-2 HSP को हल करने के लिए डेप्थ-वन हैडामार्ड ट्रांसफॉर्म पर्याप्त है, न कि $G$ के लिए समर्पित QFT की आवश्यकता है।
शोर-किटाव के साथ तुलना: पेपर उनके एकल-क्वेरी दृष्टिकोण की तुलना शोर-किटाव सैंपलिंग पद्धति से करता है। जबकि शोर-किटाव कई क्वेरी के माध्यम से उच्च संभावना के साथ $H$ को पुनः प्राप्त कर सकता है, एक एकल नमूना (sample) से सटीक पहचान की गारंटी नहीं दी जा सकती है। एकल नमूने के लिए सफलता की संभावना अधिकतम $\phi(q)/q$ ( $\phi$ यूलर टोटिएंट फंक्शन है) है, और यह पूरी तरह विफल हो जाता है यदि $G/H$ गैर-चक्रीय (non-cyclic) है। इसके विपरीत, प्रस्तावित एल्गोरिदम बताई गई संरचनात्मक शर्तों के तहत एक ही क्वेरी में सटीक रिकवरी की गारंटी देता है।

महत्व और दावे

शोध पत्र का दावा है कि यह एबेलियन HSP के लिए "एक-क्वेरी क्वांटम सॉल्वेबिलिटी" की समझ को स्पष्ट करता है। इसका प्राथमिक महत्व निम्नलिखित में है:

QFT की भूमिका को स्पष्ट करना: यह स्पष्ट करता है कि QFT कब एक आवश्यक बीजगणितीय उपकरण है (जैसा कि BV और इंडेक्स- $q$ पहचान में है) और कब यह केवल यूनिफॉर्म कॉलम वाले यूनिटरी के लिए एक सुविधाजनक गणितीय विवरण है (जैसा कि DJ निर्णय में है)।
एकीकृत ढांचा: यह DJ, BV, और शोर-किटाव एल्गोरिदम को इंडेक्स- $q$ HSP के एक सामान्य ढांचे के अंतर्गत रखता है, जिससे यह पता चलता है कि BV एक व्यापक वर्ग की समस्याओं का एक विशेष मामला है जिन्हें एकल क्वेरी के साथ हल किया जा सकता है।
एकल क्वेरी की इष्टतमता (Optimality): यह स्थापित करता है कि $q=2$ और $q=3$ के लिए, बिना किसी अतिरिक्त संरचनात्मक वादे के एकल-क्वेरी सटीक पहचान संभव है, जबकि मानक सैंपलिंग दृष्टिकोण (शोर-किटाव) स्वाभाविक रूप से एकल क्वेरी के लिए संभाव्य (probabilistic) है।

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