🔬 भौतिकी

Quantum Query Complexity of Tournament Solutions

यह शोध पत्र विभिन्न टूर्नामेंट समाधानों की क्वांटम क्वेरी जटिलता (quantum query complexity) की जांच करता है, यह प्रदर्शित करते हुए कि जहाँ शास्त्रीय एल्गोरिदम को $\Theta(N^2)$ क्वेरी की आवश्यकता होती है, वहीं क्वांटम एल्गोरिदम टॉप साइकिल ( $\tilde{\Theta}(N)$ ) और कोंडोर्सेट विजेता ( $\tilde{\Theta}(\sqrt{N})$ ) को खोजने के लिए दक्षता में महत्वपूर्ण सुधार कर सकते हैं, और स्ट्रॉन्ग किंग्स तथा अधिकतम आउट-डिग्री वर्टिस जैसे अन्य समाधानों के लिए सटीक सीमाएं स्थापित करते हैं।

मूल लेखक: Pragya Arora, Udit Kumar

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

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

CC BY 4.0

मूल लेखक: Pragya Arora, Udit Kumar

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

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

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

यह अध्ययन विजेता को परिभाषित करने के कई मानक तरीकों पर केंद्रित रहा। क्वांटम दुनिया में खोजने में सबसे आसान है, 'टॉप साइकिल' (top cycle)। यह खिलाड़ियों का सबसे छोटा समूह है जो, एक टीम के रूप में, बाकी सभी को हराता है। शोधकर्ताओं ने दिखाया कि एक क्वांटम एल्गोरिदम इस समूह की पहचान मैचों की एक ऐसी संख्या की जाँच करके कर सकता है जो मोटे तौर पर खिलाड़ियों की संख्या के समानुपाती रूप से बढ़ती है। यह शास्त्रीय आवश्यकता की तुलना में एक महत्वपूर्ण सुधार है, जो खिलाड़ियों की संख्या के वर्ग के साथ बढ़ती है। इस समूह को खोजने के लिए, क्वांटम एल्गोरिदम पहले सभी खिलाड़ियों को उनकी जीत के आधार पर एक एकल रेखा में व्यवस्थित करता है, जो ताश की गड्डी को छाँटने (sorting) के समान एक प्रक्रिया है। फिर यह उस रेखा में सटीक रूप से यह पता लगाने के लिए 'डिवाइड-एंड-कॉन्कर' (divide-and-conquer) रणनीति का उपयोग करता है कि जीतने वाला समूह कहाँ समाप्त होता है। यह दृष्टिकोण इतना कुशल है कि यह एक संबंधित समस्या को भी हल करता है: यह निर्धारित करना कि क्या पूरा टूर्नामेंट 'स्ट्रॉन्गली कनेक्टेड' (strongly connected) है, जिसका अर्थ है कि प्रत्येक खिलाड़ी जीत की एक श्रृंखला के माध्यम से अन्य प्रत्येक खिलाड़ी तक पहुँच सकता है।

इसके विपरीत, एक "कोंडोर्सेट विजेता" (Condorcet winner)—एक ऐसा खिलाड़ी जो सीधे तौर पर सभी को हराता है—को खोजना क्वांटम कंप्यूटर के लिए और भी आसान हो जाता है। शोधकर्ताओं ने प्रदर्शित किया कि ऐसे खिलाड़ी को खिलाड़ियों की संख्या के वर्गमूल के समानुपाती मैचों की जाँच करके पाया जा सकता है। यह शास्त्रीय आवश्यकता से एक नाटकीय कमी है। इस पद्धति में पहले एक "किंग" (king) खोजना शामिल है, एक ऐसा खिलाड़ी जो अधिकतम दो चरणों में किसी भी व्यक्ति तक पहुँच सकता है, और फिर यह जाँच करना कि क्या उस किंग की कोई हार हुई है। यदि किंग की कोई हार नहीं होती है, तो वे कोंडोर्सेट विजेता हैं; यदि उनकी हार होती है, तो ऐसा कोई विजेता मौजूद नहीं है। यह परिणाम पुष्टि करता है कि इस विशिष्ट प्रकार के विजेता के लिए, क्वांटम यांत्रिकी एक शक्तिशाली शॉर्टकट प्रदान करती है।

हालाँकि, कहानी बदल जाती है जब लक्ष्य "कोपलैंड सेट" (Copeland set) को खोजना होता है, जिसमें वे सभी खिलाड़ी शामिल हैं जिनकी जीत की संख्या सर्वाधिक है। यहाँ, शोधकर्ताओं ने सिद्ध किया कि एक क्वांटम कंप्यूटर को कोई लाभ नहीं मिलता है। शीर्ष स्कोर करने वालों के पूरे सेट को खोजने के लिए, क्वांटम कंप्यूटर को अभी भी खिलाड़ियों की संख्या के वर्ग के समानुपाती मैचों की जाँच करनी होगी, जो बिल्कुल एक शास्त्रीय कंप्यूटर के समान है। यह एक आश्चर्यजनक परिणाम है क्योंकि केवल एक शीर्ष स्कोरर को खोजना क्वांटम कंप्यूटर के लिए बहुत आसान है। कठिनाई इसलिए आती है क्योंकि पूरे सेट की पहचान करने के लिए प्रत्येक खिलाड़ी की जीत की गणना अत्यधिक सटीकता के साथ करनी पड़ती है, एक ऐसा कार्य जो क्वांटम यांत्रिकी की समानांतर खोज शक्ति (parallel searching power) से लाभान्वित नहीं होता है।

शोधकर्ताओं ने "अनकवर्ड सेट" (uncovered set) की भी जाँच की, जिसमें वे खिलाड़ी शामिल हैं जो दो या उससे कम चरणों में सभी तक पहुँच सकते हैं। उन्होंने पाया कि इस पूरे समूह को खोजना एक एकल ऐसे खिलाड़ी को खोजने की तुलना में कठिन है, लेकिन पूर्ण कोपलैंड सेट को खोजने की तुलना में आसान है। एक क्वांटम कंप्यूटर को खिलाड़ियों की संख्या की एक दशमलव-पाँच (1.5) घात के समानुपाती मैचों की जाँच करने की आवश्यकता होती है। यह अनकवर्ड सेट को एक मध्य मार्ग में रखता है, जो दर्शाता कि टूर्नामेंट समाधान की कठिनाई एकसमान नहीं है; कुछ आसान हैं, कुछ कठिन हैं, और क्वांटम लाभ तदनुसार भिन्न होता है।

इन सीमाओं को सिद्ध करने के लिए, टीम ने नए गणितीय तर्क विकसित किए। उन्होंने विशेष, कठिन टूर्नामेंट परिदृश्य बनाए जो किसी भी एल्गोरिदम को कई मैचों की जाँच करने के लिए छलने (trick) के लिए डिज़ाइन किए गए थे। यह दिखाकर कि एक क्वांटम कंप्यूटर भी इन विशिष्ट पहेलियों को एक निश्चित न्यूनतम मैचों की जाँच किए बिना हल नहीं कर सकता, उन्होंने आवश्यक कार्य पर दृढ़ निचली सीमाएँ (lower bounds) स्थापित कीं। सबसे अधिक जीत वाले खिलाड़ी को खोजने की समस्या के लिए, उन्होंने एक ज्ञात सीमा का नया, स्व-निहित प्रमाण प्रदान किया, यह प्रदर्शित करते हुए कि कठिनाई गणना (counting) की आवश्यकता से आती है न कि केवल खोजने (searching) से। उनके कार्य स्पष्ट करते हैं कि यद्यपि क्वांटम कंप्यूटर शक्तिशाली हैं, वे हर प्रकार की गणना को तेज़ करने वाला एक जादुई डंडा नहीं हैं। गति (speedup) समस्या की विशिष्ट संरचना पर निर्भर करती है, और टूर्नामेंट समाधान के मामले में, विजेता चुनने के नियम ही यह निर्धारित करते हैं कि क्वांटम मशीन वास्तव में चमक सकती है या नहीं।

तकनीकी सारांश: टूर्नामेंट समाधानों की क्वांटम क्वेरी जटिलता (Quantum Query Complexity)

समस्या की परिभाषा

यह शोध पत्र विभिन्न टूर्नामेंट समाधानों (tournament solutions) की क्वांटम क्वेरी जटिलता की जांच करता है। एक टूर्नामेंट एक निर्देशित ग्राफ (directed graph) है जहाँ प्रत्येक दो विशिष्ट शीर्षों (vertices) के बीच ठीक एक चाप (arc) होता है, जो राउंड-रॉबिन प्रतियोगिताओं या युग्म बहुमत संबंधों (pairwise majority relations) को मॉडल करता है। एक टूर्नामेंट समाधान एक टूर्नामेंट को "विजेता" शीर्षों के गैर-रिक्त सेट (non-empty set) में मैप करता है।

क्वेरी मॉडल में, टूर्नामेंट को अप्रत्यक्ष रूप से दिया जाता है; एक एल्गोरिदम केवल एक किनारे (edge) $(u, v)$ की जांच (query) करके ही उसके ओरिएंटेशन को सीखता है। लागत क्वेरी की संख्या है। जबकि इन समस्याओं के लिए शास्त्रीय (classical) क्वेरी जटिलता अक्सर समान (आमतौर पर $\Theta(N^2)$ ) होती है, यह कार्य अन्वेषण करता है कि क्या क्वांटम एल्गोरिदम (सुपरपोजिशन और ग्रोवर सर्च का उपयोग करते हुए) महत्वपूर्ण गति प्राप्त कर सकते हैं।

अध्ययन किए गए विशिष्ट समाधानों में शामिल हैं:

कॉन्डोरसेट विजेता (Condorcet Winner): एक शीर्ष जो अन्य सभी को हरा देता है।
कोपलैंड सेट (Copeland Set - $CO(T)$ ): अधिकतम आउट-डिग्री वाले शीर्षों का सेट।
अनकवर्ड सेट (Uncovered Set - $UC(T)$ ): "किंग्स" (वे शीर्ष जो दो चरणों के भीतर सभी तक पहुँचते हैं) का सेट।
स्ट्रॉन्ग किंग (Strong King): एक शीर्ष $v$ ऐसा कि प्रत्येक $u$ के लिए जो $v$ को हराता है, $v$ उन शीर्षों की संख्या से अधिक को हराता है जिन्हें $u$ हराता है (विशेष रूप से $p(v,u) > p(u,v)$ )।
टॉप साइकिल (Top Cycle - $TC(T)$ ): अद्वितीय सबसे छोटा प्रभावी सेट (एक ऐसा सेट जहाँ प्रत्येक सदस्य सेट के बाहर के प्रत्येक शीर्ष को हराता है)।

कार्यप्रणाली (Methodology)

लेखक क्वांटम एल्गोरिदम डिजाइन और लोअर-बाउंड (lower-bound) तकनीकों का मिश्रण नियोजित करते हैं:

लोअर बाउंड्स (एडवर्सरी विधि - Adversary Method):
- लोअर बाउंड सिद्ध करने के लिए प्राथमिक उपकरण एम्बैन्स के एडवर्सरी मेथड (Ambainis's adversary method) (प्रमेय 2.13) का उपयोग करना है।
- इसे लागू करने के लिए, लेखक एक नई प्रॉमिस समस्या हेवी-रो (Heavy-Row) पेश करते हैं: एक $m \times m$ बूलियन मैट्रिक्स दिया गया है जहाँ प्रत्येक पंक्ति का भार (weight) $k$ है, सिवाय संभवतः एक पंक्ति के जिसका भार $k+1$ है; निर्णय लें कि क्या कोई हेवी रो मौजूद है।
- वे एडवर्सरी मेथड का उपयोग करके सीधे $Q(\text{Heavy-Row}) = \Omega(m^{3/2})$ सिद्ध करते हैं, जिससे पिछले कार्य [14] में उपयोग किए गए कंपोजिशन थ्योरम से बचा जा सके।
- इस समस्या को विशिष्ट टूर्नामेंटों का निर्माण करके टूर्नामेंट समस्याओं में बदला जाता है जहाँ आउट-डिग्री या संरचनात्मक गुण (जैसे स्ट्रॉन्ग किंग होना) हेवी रो के अस्तित्व पर निर्भर करते हैं।
- कोपलैंड सेट के लिए, वे इसे हेवी-रोज़्स $_k$ (Heavy-Rows $_k$ ) में सामान्यीकृत करते हैं, जहाँ कई पंक्तियाँ भारी हो सकती हैं, ताकि $\Omega(N^2)$ का लोअर बाउंड स्थापित किया जा सके।
- अनकवर्ड सेट के लिए, वे "टाइट" बनाम "डेफिशिएंट" मैट्रिसेस को गिनने वाली एक समस्या टाइट-काउंट (Tight-Count) को परिभाषित करते हैं, ताकि $\Omega(N^{3/2})$ का लोअर बाउंड स्थापित किया जा सके।
अपर बाउंड्स (एल्गोरिदम डिजाइन):
- टॉप साइकिल: एल्गोरिदम पहले $O(N \log N)$ क्वेरी (इंसर्शन सॉर्ट के माध्यम से) का उपयोग करके एक हैमिल्टनियन पाथ (Hamiltonian path) पाता है। टॉप साइकिल इस पाथ के एक प्रीफिक्स (prefix) के अनुरूप होता है। इस प्रीफिक्स के अंत को खोजने की समस्या को एक इंटरवल-कवरिंग समस्या में बदला जाता है, जिसे बैक-एजेस (back-edges) को कुशलतापूर्वक खोजने के लिए डिवाइड-एंड-कॉन्कर (divide-and-conquer) रणनीति के साथ क्वांटम मिनिमम फाइंडिंग (Dürr-Høyer) के संयोजन से हल किया जाता है।
- कॉन्डोरसेट विजेता: एल्गोरिदम एक किंग पाता है ( $[25]$ के $O(\sqrt{N} \text{polylog } N)$ एल्गोरिदम का उपयोग करके) और फिर यह जांचने के लिए ग्रोवर सर्च करता है कि क्या कोई शीर्ष इस किंग को हराता है।
- स्ट्रॉन्ग किंग्स: अपर बाउंड तुरंत इस तथ्य से अनुसरण करता है कि प्रत्येक अधिकतम आउट-डिग्री वाला शीर्ष एक स्ट्रॉन्ग किंग होता है, जो अधिकतम डिग्री वाले शीर्ष को खोजने के $\Theta(N^{3/2})$ एल्गोरिदम का उपयोग करता है।

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

यह शोध पत्र निम्नलिखित क्वांटम क्वेरी जटिलताओं को स्थापित करता है (जहाँ $N$ शीर्षों की संख्या है और $\tilde{O}$ पॉयलॉगैरिथमिक कारकों को छिपाता है):

समस्या	शास्त्रीय जटिलता (Classical Complexity)	क्वांटम जटिलता (Quantum Complexity)	मुख्य परिणाम
कॉन्डोरसेट विजेता	$\Theta(N)$	$\tilde{\Theta}(\sqrt{N})$	महत्वपूर्ण गति; किंग + ग्रोवर द्वारा पाया गया।
टॉप साइकिल	$\Theta(N^2)$	$\tilde{\Theta}(N)$	बड़ी गति। टॉप साइकिल तीन नेस्टेड सेट्स ( $CO \subseteq UC \subseteq TC$ ) में से कंप्यूट करने के लिए सबसे "आसान" है।
मैक्स आउट-डिग्री वर्टेक्स	$\Theta(N^2)$	$\Theta(N^{3/2})$	पूर्व कार्य [14] से मेल खाता है; लेखक हेवी-रो रिडक्शन के माध्यम से स्व-निहित प्रमाण प्रदान करते हैं।
स्ट्रॉन्ग किंग	$\Theta(N^2)$	$\Theta(N^{3/2})$	शास्त्रीय $\Theta(N^2)$ पर बहुपद (polynomial) गति, लेकिन एक एकल किंग ( $\tilde{O}(\sqrt{N})$ ) को खोजने की तुलना में धीमी।
अनकवर्ड सेट (किंग्स)	$\Theta(N^2)$	$\Omega(N^{3/2}), O(N^2)$	सेट समस्या को सिंगल-एलिमेंट समस्या से अलग करता है। सभी किंग्स को खोजना एक किंग को खोजने से कठिन है।
कोपलैंड सेट	$\Theta(N^2)$	$\Theta(N^2)$	कोई गति नहीं। अधिकतम डिग्री वाले शीर्षों के पूरे सेट को कंप्यूट करने के लिए किनारों के एक स्थिर अंश को पढ़ना आवश्यक है, जो शास्त्रीय बाउंड से मेल खाता है।

विशिष्ट तकनीकी निष्कर्ष:

कोपलैंड सेट की कठिनाई: लेखक दिखाते हैं कि जबकि एक एकल कोपलैंड विजेता (अधिकतम डिग्री शीर्ष) खोजने में $\Theta(N^{3/2})$ समय लगता है, ऐसे शीर्षों के पूरे सेट को कंप्यूट करने के लिए $\Theta(N^2)$ क्वेरी की आवश्यकता होती है। यह टॉप साइकिल के विपरीत है, जहाँ सेट को व्यक्तिगत अधिकतम डिग्री शीर्षों की तुलना में तेजी से कंप्यूट किया जाता है।
स्ट्रॉन्ग किंग्स: एक स्ट्रॉन्ग किंग खोजने के लिए $\Theta(N^{3/2})$ क्वेरी की आवश्यकता होती है। यह शास्त्रीय $\Theta(N^2)$ पर एक बहुपद गति है, लेकिन एक जेनेरिक किंग ( $\tilde{O}(\sqrt{N})$ ) को खोजने की तुलना में काफी धीमी है।
टॉप साइकिल एल्गोरिदम: एल्गोरिदम $O(N \log^2 N)$ क्वेरी प्राप्त करता है। यह लॉगरिदमिक कारकों तक इष्टतम है, क्योंकि लोअर बाउंड $\Omega(N)$ है (जो $\Theta(N^2)$ बिट्स पर एक OR फंक्शन को एम्बेड करके प्राप्त किया गया है)।
वैकल्पिक प्रमाण: यह शोध पत्र हेवी-रो समस्या से सीधे रिडक्शन के माध्यम से एक अधिकतम डिग्री शीर्ष खोजने के $\Theta(N^{3/2})$ बाउंड के लिए एक स्व-निहित प्रमाण प्रदान करता है, जो [14] में उपयोग किए गए कंपोजिशन थ्योरम को दरकिनार करता है।

महत्व और दावे

शोध पत्र का दावा है कि टूर्नामेंट समाधानों की क्वांटम क्वेरी जटिलता समान (uniform) नहीं है, जैसा कि शास्त्रीय मामले में होता है।

कठिनाई का पदानुक्रम (Hierarchy of Difficulty): क्वांटम सेटिंग में, सबसे बड़ा समाधान सेट (टॉप साइकिल) कंप्यूट करने में सबसे आसान ( $\tilde{\Theta}(N)$ ) है, जबकि सबसे छोटा (कोपलैंड सेट) सबसे कठिन ( $\Theta(N^2)$ ) है।
सेट बनाम तत्व (Set vs. Element): एक केंद्रीय विषय यह है कि एक पूरे टूर्नामेंट समाधान को कंप्यूट करना उस समाधान के एक एकल सदस्य को खोजने की तुलना में स्पष्ट रूप से कठिन हो सकता है।
- किंग्स के लिए: एक को खोजना $\tilde{O}(\sqrt{N})$ है, लेकिन पूरे सेट (अनकवर्ड सेट) को खोजना $\Omega(N^{3/2})$ है।
- कोपलैंड के लिए: एक को खोजना $\Theta(N^{3/2})$ है, लेकिन पूरे सेट को खोजना $\Theta(N^2)$ है।
संरचनात्मक अंतर्दृष्टि: यह कार्य रेखांकित करता है कि इन समस्याओं की कठिनाई अक्सर गिनती (counting) (डिग्री या विशिष्ट संरचनाओं की गणना करना) से आती है, न कि केवल खोज (searching) से। जबकि ग्रोवर सर्च विशिष्ट तत्वों को खोजने में मदद करता है, गिनती वाली समस्याएं अक्सर उच्च जटिलता बनाए रखती हैं या इनपुट के एक बड़े हिस्से को पढ़ने की मांग करती हैं।

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