⚛️ quantum physics

On Quantum Perceptron Learning via Quantum Search

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

मूल लेखक: Xiaoyu Sun (Aix-Marseille Université, CNRS, LIS, Marseille, France), Mathieu Roget (Aix-Marseille Université, CNRS, LIS, Marseille, France), Giuseppe Di Molfetta (Aix-Marseille Université, CNRS, LIS

प्रकाशित 2026-06-23✓ Author reviewed ⓘ

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

CC BY 4.0

मूल लेखक: Xiaoyu Sun (Aix-Marseille Université, CNRS, LIS, Marseille, France), Mathieu Roget (Aix-Marseille Université, CNRS, LIS, Marseille, France), Giuseppe Di Molfetta (Aix-Marseille Université, CNRS, LIS, Marseille, France, Institut Universitaire de France, Paris, France), Hachem Kadri (Aix-Marseille Université, CNRS, LIS, Marseille, France)

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

कल्पना कीजिए कि आप एक विशाल, बहु-आयामी भूलभुलैया (maze) में एक विशिष्ट छिपे हुए खजाने को खोजने की कोशिश कर रहे हैं। मशीन लर्निंग की दुनिया में, यह "खजाना" एक आदर्श नियम (जिसे परसेप्ट्रॉन/perceptron कहा जाता है) है जो डेटा को दो समूहों में विभाजित कर सकता है (जैसे लाल गेंदों को नीली गेंदों से अलग करना)।

यह शोध पत्र इस बारे में है कि कैसे क्वांटम कंप्यूटर हमें इस नियम को शास्त्रीय (classical) कंप्यूटरों की तुलना में बहुत तेज़ी से खोजने में मदद कर सकते हैं, लेकिन यह उस बड़ी गलती को भी ठीक करता है जिसे वैज्ञानिक पहले क्वांटम कंप्यूटरों के काम करने के तरीके के बारे में समझते थे।

यहाँ उनकी यात्रा का सरल विवरण दिया गया है:

1. समस्या: "छोटे कमरे" की गलती

लंबे समय तक, वैज्ञानिकों का मानना था कि यदि आप उच्च-आयामी स्थान (भूलभुलैया) में यादृच्छिक रूप से (randomly) एक तीर फेंकते हैं, तो आपके पास "वर्जन स्पेस" (Version Space)—वह छोटा, सुरक्षित क्षेत्र जहाँ आदर्श सॉर्टिंग नियम स्थित है—को हिट करने का अच्छा मौका होता है। उन्हें लगा कि यह संभावना मोटे तौर पर "मार्जिन" (कि लाल और नीली गेंदें कितनी स्पष्ट रूप से अलग हैं) के समानुपाती है।

लेखकों का सुधार:
लेखकों (सन, रोगेट, आदि) ने महसूस किया कि यह एक बहुत बड़ी गलत गणना थी।

उपमा (Analogy): कल्पना कीजिए कि "वर्जन स्पेस" स्विस चीज़ (Swiss cheese) के एक विशाल ब्लॉक में पनीर की एक बहुत पतली स्लाइस है। 2D दुनिया (एक सपाट शीट) में, उस स्लाइस को हिट करना आसान हो सकता है। लेकिन जैसे-जैसे आप आयाम (dimensions) जोड़ते हैं (चीज़ के ब्लॉक को ऊंचा, चौड़ा और गहरा बनाते हैं), वह स्लाइस असंभव रूप से पतली होती जाती है।
परिणाम: उच्च-आयामी स्थानों में, आदर्श नियम खोजने की संभावना घातांकीय रूप से (exponentially) गिर जाती है। यह केवल "कठिन" नहीं है; यह रेगिस्तान में रेत के एक विशिष्ट कण को खोजने जैसा है जो लगातार बढ़ता जा रहा है।
प्रभाव: इसका मतलब है कि एक प्रसिद्ध पुराना क्वांटम एल्गोरिदम (QVSP) वास्तव में जटिल, उच्च-आयामी डेटा के मामले में उतना तेज़ नहीं था जितना कि सबको लगता था। जो "स्पीडअप" उन्होंने वादा किया था, वह खराब गणित के कारण एक भ्रम था।

2. नया समाधान: दो क्वांटम "स्काउट्स" (Scouts)

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

रणनीति A: हाइब्रिड स्काउट (HCP-RW)

यह एक क्लासिकल कंप्यूटर और एक क्वांटम कंप्यूटर के बीच की टीम वर्क है।

यह कैसे काम करता है: "वर्जन स्पेस" को एक सिकुड़ते हुए कमरे के रूप में सोचें। हर बार जब एल्गोरिदम एक गलती पाता है (जैसे एक लाल गेंद जिसे गलती से नीला मान लिया गया है), तो वह एक कटिंग प्लेन (cutting plane) का उपयोग करके कमरे का वह हिस्सा काट देता है जहाँ वह नियम नहीं हो सकता। यह काटने की प्रक्रिया ही वास्तव में सुरक्षित स्थान को कम करती है।
क्वांटम बूस्ट: कमरे में गलती खोजने के लिए पैदल चलने के बजाय, क्वांटम कंप्यूटर ग्रोवर सर्च (Grover's Search) (एक क्वांटम टॉर्चलाइट) का उपयोग करता है ताकि पूरे कमरे को तुरंत स्कैन किया जा सके और गलती की ओर इशारा किया जा सके।
"हिट-एंड-रन" की भूमिका: अगले कट की तैयारी के लिए, एल्गोरिदम को यह जानने की आवश्यकता होती है कि शेष सुरक्षित स्थान का केंद्र कहाँ है। इसके लिए वे हिट-एंड-रन (Hit-and-Run) नामक तकनीक का उपयोग करते हैं। हिट-एंड-रन एक रैंडम वॉक एल्गोरिदम है जिसका उपयोग एक समान स्थिर वितरण (uniform stationary distribution) तैयार करने के लिए किया जाता है। वर्तमान बिंदु से, यह एक दिशा चुनता है, सीमा से टकराता है, और परिणामी कॉर्ड (chord) के साथ चलता है। यह रैंडम सैंपल पॉइंट्स के अंकगणितीय माध्य (arithmetic mean) की गणना करके एक अनुमानित सेंट्रॉइड (centroid) का अनुमान लगाने की अनुमति देता है, जिसका उपयोग अगले दौर में कटिंग प्लेन के लिए किया जाता है। संक्षेप में, हिट-एंड-रन अगले सबसे अच्छे कट को खोजने के लिए आवश्यक सैंपलिंग को सक्षम बनाता है।
परिणाम: यह पुराने तरीके से तेज़ है, लेकिन जैसे-जैसे आयाम बढ़ते हैं, इसमें अभी भी बहुत अधिक "चलने" (कंप्यूटेशनल स्टेप्स) की आवश्यकता होती है।

रणनीति B: पूरी तरह से क्वांटम घोस्ट (QCP-QW)

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

यह कैसे काम करता है: एक इंसान के कमरे में चलने के बजाय, "एक्सप्लोरर" एक क्वांटम वेव (Quantum Wave) है।
जादू: एल्गोरिदम क्वांटम वॉक्स (Quantum Walks) का उपयोग करता है। कल्पना कीजिए कि एक लहर एक समय में सभी दिशाओं में एक साथ भूलभुलैया में फैल रही है, बजाय इसके कि कोई व्यक्ति एक समय में एक रास्ता चले।
लाभ: क्वांटम लाभ उच्च-आयामी स्थानों में अधिक तेज़ी से समान स्थिर वितरण तैयार करने में निहित है। ध्यान दें कि सुरक्षित क्षेत्र शास्त्रीय एल्गोरिदम की तरह ही उसी दर से सिकुड़ता है, जिसके लिए O*(D) राउंड की आवश्यकता होती है।
परिणाम: यह हाइब्रिड स्काउट की तुलना में काफी तेज़ है, विशेष रूप से जैसे-जैसे डेटा अधिक जटिल (उच्च आयामों वाला) होता जाता है। यह समाधान खोजने के लिए आवश्यक चरणों की संख्या में भारी बढ़त प्रदान करता है।

3. पकड़: यह अभी के लिए सैद्धांतिक है

लेखक अपनी सीमाओं के बारे में बहुत ईमानदार हैं।

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

सारांश

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

तकनीकी सारांश: क्वांटम सर्च के माध्यम से क्वांटम परसेप्ट्रॉन लर्निंग

समस्या विवरण

यह शोध पत्र उच्च-आयामी फीचर स्पेस में परसेप्ट्रॉन को प्रशिक्षित करने की सैद्धांतिक कम्प्यूटेशनल जटिलता को संबोधित करता है। जबकि क्लासिकल ऑनलाइन परसेप्ट्रॉन एल्गोरिदम $O(1/\gamma^2)$ अपडेट्स (जहाँ $\gamma$ ज्यामितीय मार्जिन है) में अभिसरित होता है, इसकी क्वेरी जटिलता एक कमजोर ऑनलाइन लर्निंग सेटिंग (जहाँ उदाहरणों को $N$ आकार के डेटासेट से लिया जाता है) में $N$ के साथ रैखिक रूप से स्केल करती है। पिछले क्वांटम दृष्टिकोण, विशेष रूप से कपूर एट अल. (2016) द्वारा प्रस्तावित क्वांटम वर्जन स्पेस परसेप्ट्रॉन (QVSP), वर्ज़न स्पेस (उन सभी हाइपरप्लेन का सेट जो डेटा को पूरी तरह से वर्गीकृत करते हैं) से वैध हाइपरप्लेन को सैंपल करने के लिए ग्रोवर के सर्च का लाभ उठाकर इसमें सुधार करने का प्रयास करते थे।

हालाँकि, लेखक QVSP विश्लेषण में एक महत्वपूर्ण त्रुटि की पहचान करते हैं: यह धारणा कि एक मानक सामान्य वितरण (standard normal distribution) से एक वैध हाइपरप्लेन को सैंपल करने की प्रायिकता मार्जिन के साथ रैखिक रूप से $\Theta(\gamma)$ स्केल करती है। यह शोध पत्र तर्क देता है कि यह धारणा $D > 2$ आयामों के लिए गलत है, जहाँ प्रायिकता वास्तव में $\Omega(\gamma^D)$ के रूप में स्केल होती है, जिससे एक आयामी निर्भरता उत्पन्न होती है जो वर्स्ट-केस परिदृश्यों में प्रस्तावित क्वांटम स्पीडअप को निष्प्रभावी कर देती है।

कार्यप्रणाली और योगदान

यह शोध पत्र दो मुख्य योगदान देता है: मौजूदा क्वांटम परसेप्ट्रॉन मॉडल का सुधारात्मक विश्लेषण और दो नए क्वांटम-उन्नत कटिंग-प्लेन एल्गोरिदम का प्रस्ताव।

1. वर्जन स्पेस सैंपलिंग का सुधारा गया विश्लेषण

लेखक $D$ आयामों में एक मानक सामान्य वितरण $\mathcal{N}(0, I)$ से एक परफेक्ट क्लासिफायर को सैंपल करने की प्रायिकता का कठोरता से पुन: परीक्षण करते हैं।

सुधार: वे सिद्ध करते हैं कि एक सैंपल किए गए वेक्टर के वर्जन स्पेस के भीतर गिरने की प्रायिकता वर्स्ट-केस में $\Omega(\gamma^D)$ के रूप में स्केल होती है (स्थिर $D \ge 2$ के लिए), न कि पूर्व में दावा किए गए $\Theta(\gamma)$ के रूप में।
निहितार्थ: इसका अर्थ यह है कि QVSP एल्गोरिदम की क्वेरी जटिलता, इस प्रायिकता को बढ़ाने के लिए ग्रोवर के सर्च का उपयोग करते समय, वर्स्ट-केस में $O^*(N/\sqrt{\gamma^D})$ के रूप में स्केल करती है। $D$ पर यह घातांकीय (exponential) निर्भरता QVSP को उच्च-आयामी डेटा के लिए अप्रभावी बना देती है जिसमें छोटा मार्जिन हो।
सूक्ष्म अंतर: लेखक नोट करते हैं कि लो-रैंक डेटासेट के लिए (जहाँ अंतर्निहित आयाम $r \ll D$ है), जटिलता $\Omega(\gamma^r)$ के रूप में स्केल हो सकती है, जो यह सुझाव देती है कि वर्स्ट-केस बाउंड एक विशिष्ट काउंटर-एग्जांपल है न कि सभी डेटा संरचनाओं के लिए एक सार्वभौमिक सीमा।

2. प्रस्तावित क्वांटम-उन्नत कटिंग-प्लेन एल्गोरिदम

मार्जिन और आयामी निर्भरता को संबोधित करने के लिए, लेखक दो एल्गोरिदम प्रस्तावित करते हैं जो कटिंग-प्लेन (CP) पद्धति पर आधारित हैं, जो परसेप्ट्रॉन लर्निंग को एक फजीबिलिटी (feasibility) समस्या के रूप में पुनर्गठित करती है। ये एल्गोरिदम एक "कमजोर ऑनलाइन लर्निंग" ढांचे का उपयोग करते हैं जहाँ उदाहरणों को ओरैकल्स के माध्यम से एक्सेस किया जाता है।

A. हाइब्रिड क्वांटम-क्लासिकल कटिंग-प्लेन रैंडम वॉक (HCP-RW)

तंत्र: यह एल्गोरिदम क्लासिकल कटिंग-प्लेन लॉजिक को क्वांटम सैंपलिंग के साथ जोड़ता है। यह गलत वर्गीकृत उदाहरणों की पहचान करने के लिए ग्रोवर के सर्च का उपयोग करता है (जो एक सेपरेशन ओरैकल के रूप में कार्य करता है) और घटते हुए कॉनवेक्स फिक्सेबल क्षेत्र (वर्जन स्पेस) के भीतर बिंदुओं को सैंपल करने के लिए एक क्लासिकल हिट-एंड-रन रैंडम वॉक का उपयोग करता है।
जटिलता: यह मार्जिन निर्भरता $O^*(D \log(1/\gamma))$ और क्वेरी निर्भरता $O^*(\sqrt{N})$ प्राप्त करता है।
सीमा: मेंबरशिप ओरैकल और हिट-एंड-रन वॉक के क्लासिकल कार्यान्वयन के कारण अंकगणितीय जटिलता (arithmetic complexity) अभी भी उच्च ( $O^*(D^7 \log(1/\gamma))$ ) बनी रहती है, जिसके लिए $O(D^3)$ मिक्सिंग स्टेप्स की आवश्यकता होती है।

B. पूर्णतः-क्वांटम कटिंग-प्लेन क्वांटम वॉक (QCP-QW)

तंत्र: यह एक पूर्णतः क्वांटम एल्गोरिदम है जहाँ डेटासेट और मॉडल (वेट स्पेस पर वितरण) दोनों को क्वांटम अवस्थाओं के रूप में दर्शाया जाता है।
- यह क्लासिकल हिट-एंड-रन रैंडम वॉक को सेजेडी क्वांटम वॉक (Szegedy quantum walk) से बदल देता है।
- यह मॉडल के सेंट्रॉइड और कोवेरिएंस मैट्रिक्स को क्वांटम स्टेट को कोलैप्स किए बिना अपडेट करने के लिए नॉन-डिस्ट्रक्टिव क्वांटम मीन एस्टीमेशन और एफ़ाइन ट्रांसफॉर्मेशन एस्टीमेशन का उपयोग करता है।
- यह कॉनवेक्स बॉडी के भीतर सैंपलिंग प्रक्रिया को तेज करने के लिए क्वांटम वॉक सर्च (मैग्नीज़ एट अल., 2007) का लाभ उठाता है।
जटिलता: QCP-QW एल्गोरिदम HCP-RW की तुलना में अंकगणितीय और क्वेरी जटिलता स्केलिंग में $O^*(D^{1.5})$ के कारक से सुधार करता है। कुल क्वेरी जटिलता $O^*(D \log(1/\gamma) \cdot (\sqrt{N} + D^{4.5}\sqrt{\log(1/\gamma)}))$ द्वारा सीमित है, जिसमें अंकगणितीय संचालन हाइब्रिड दृष्टिकोण की तुलना में काफी कम हैं।
आउटपुट: एल्गोरिदम वर्जन स्पेस पर एक समान वितरण का प्रतिनिधित्व करने वाला एक क्वांटम स्टेट $|\pi_r\rangle$ आउटपुट करता है, जिसका उपयोग स्वैप टेस्ट जैसी तकनीकों के माध्यम से वर्गीकरण के लिए किया जा सकता है।

मुख्य परिणाम और जटिलता सीमाएँ

शोध पत्र आदर्श, शोर-मुक्त (noise-free) क्वांटम कम्प्यूटेशनल मॉडलों के तहत निम्नलिखित सैद्धांतिक सीमाएँ स्थापित करता है:

QVSP सुधार: एक वैध हाइपरप्लेन को सैंपल करने की प्रायिकता $\Omega(\gamma^D)$ है, न कि $\Theta(\gamma)$ । फलस्वरूप, QVस्प (QVSP) की क्वेरी जटिलता वर्स्ट-केस में $O^*(N/\sqrt{\gamma^D})$ है, जो एक गंभीर "डायमेंशनलिटी का अभिशाप" (curse of dimensionality) को उजागर करती है।
HCP-RW:
- अपडेट्स: $O^*(D \log(1/\gamma))$ ।
- क्वेरी जटिलता: $O^*(D \log(1/\gamma) \cdot (\sqrt{N} + D^{4.5}\sqrt{\log(1/\gamma)}))$ ।
- अंकगणितीय जटिलता: $O^*(D^7 \log(1/\gamma))$ ।
QCP-QW:
- यह फजीबिलिटी समस्याओं के लिए इष्टतम संख्या में सेपरेशन ओरकल कॉल्स ( $\Omega^*(D)$ ) प्राप्त करता है और साथ ही $O^*(D \log(1/\gamma))$ की मार्जिन निर्भरता को बनाए रखता है।
- यह क्वांटम वॉक का उपयोग करके सैंपलिंग के लिए HCP-RW की तुलना में अंकगणितीय संचालन और क्वेरी स्केलिंग में $O^*(D^{1.5})$ की बढ़त प्रदान करता है।

महत्व और दावे

लेखक इस कार्य को क्वांटम मशीन लर्निंग जटिलता के एक सैद्धांतिक परिशोधन के रूप में प्रस्तुत करते हैं, न कि तत्काल निकट-अवधि कार्यान्वयन के प्रस्ताव के रूप में।

सैद्धांतिक सुधार: शोध पत्र साहित्य में QVSP एल्गोरिदम के संबंध में एक मौलिक त्रुटि को हल करने का दावा करता है, यह प्रदर्शित करते हुए कि पिछले $O^*(N/\sqrt{\gamma})$ जटिलता के दावे त्रुटिपूर्ण ज्यामितीय धारणाओं पर आधारित थे।
एल्गोरिद्मिक प्रगति: वर्जन स्पेस सैंपलिंग से कटिंग-प्लेन विधियों की ओर बढ़कर, लेखक यह प्रदर्शित करते हैं कि क्वांटम एल्गोरिदम डेटासेट के आकार पर उप-रैखिक (sublinear) निर्भरता ( $O(\sqrt{N})$ ) प्राप्त कर सकते हैं जबकि मार्जिन निर्भरता को अधिक प्रभावी ढंग से प्रबंधित कर सकते हैं ( $O^*(D \log(1/\gamma))$ )।
क्वांटम लाभ: QCP-QW को एक प्रमाण-के-रूप (proof-of-concept) के रूप में प्रस्तुत किया गया है कि पूर्णतः क्वांटम दृष्टिकोण, क्वांटम वॉक और नॉन-डिस्ट्रक्टिव एस्टीमेशन का उपयोग करके, उच्च-आयामी लीनियर क्लासिफिकेशन के लिए हाइब्रिड क्वांटम-क्लासिकल दृष्टिकोणों की तुलना में अंकगणितीय जटिलता में सैद्धांतिक रूप से बेहतर प्रदर्शन कर सकते हैं।
सीमाएँ: लेखक स्पष्ट रूप से कहते हैं कि ये परिणाम आदर्श, शोर-मुक्त मॉडलों के तहत एसिम्प्टोटिक क्षमता (asymptotic potential) को दर्शाते हैं। वे स्वीकार करते हैं कि नोइज़ी इंटरमीडिएट-स्केल क्वांटम (NISQ) उपकरणों पर व्यावहारिक कार्यान्वयन के लिए एरर करेक्शन और मिटिगेशन की आवश्यकता होगी, जो इस कार्य के दायरे से बाहर है। वे सिमुलेशन और फॉल्ट-टोलरेंट स्कीमों को भविष्य के शोध के लिए टाल देते हैं।