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

Breaking the quantum barriers for Graph Collision

यह शोध पत्र $\widetilde O(n^{92/139})$ और $\widetilde O(n^{11/17})$ की जटिलताओं वाले बेहतर क्वांटम क्वेरी एल्गोरिदम प्रस्तुत करके ग्राफ कोलिजन समस्या के लिए अनुमानित $\Omega(n^{2/3})$ निचली सीमा का खंडन करता है, साथ ही एक नई $\Omega(\sqrt{n\log n}$ निचली सीमा भी स्थापित करता है जो पॉजिटिव एडवर्सरी विधि की बाधा को पार करती है।

मूल लेखक: Arjan Cornelissen, Amin Shiraz Gilani, Shiva Kintali, François Le Gall, Subhasree Patro, Xingyu Zhou

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

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

CC BY 4.0

मूल लेखक: Arjan Cornelissen, Amin Shiraz Gilani, Shiva Kintali, François Le Gall, Subhasree Patro, Xingyu Zhou

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

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

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

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

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

जहाँ समस्या की कठिनाई की ऊपरी सीमा (upper bound) को कम किया गया, वहीं शोधकर्ताओं ने निचली सीमा (lower bound) को बढ़ाने पर भी काम किया, यह सुनिश्चित करते हुए कि समस्या अत्यधिक सरल न हो। लंबे समय तक, सरल क्वांटम तकनीकें केवल यह सिद्ध कर सकती थीं कि समस्या के लिए बिंदुओं की संख्या के वर्गमूल (square root) के बराबर प्रश्नों की आवश्यकता होती है। इसने आसान निचली सीमा और कठिन ऊपरी सीमा के बीच एक अंतर पैदा कर दिया था। टीम ने एक सीमित गणितीय स्थान में बिंदुओं और रेखाओं की ज्यामिति पर आधारित एक बहुत ही विशिष्ट, जटिल नेटवर्क का निर्माण करके इस अंतर को पाट दिया। इस नेटवर्क में, दो बिंदु अधिकतम एक रेखा निर्धारित करते हैं, और दो रेखाएं अधिकतम एक बिंदु पर मिलती हैं। उन्होंने एक ऐसी स्थिति बनाई जहाँ एकल चिह्नित कनेक्शन को खोजना असाधारण रूप से कठिन है, जिसके लिए बिंदुओं की संख्या के वर्गमूल से थोड़ा अधिक, विशेष रूप से एक लघुगणकीय कारक (logarithmic factor) से गुणा किया गया प्रश्नों की आवश्यकता होती है। यह सिद्ध करता है कि समस्या वास्तव में सरल क्वांटम विधियों की तुलना में कठिन है, जो इनपुट आकार के वर्गमूल जितनी तेज़ समाधान की संभावना को खारिज करती है।

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

शोधकर्ताओं ने स्थापित क्वांटम उपकरणों को सूचना के संगठन की नवीन रणनीतियों के साथ जोड़कर ये परिणाम प्राप्त किए। उन्होंने 'क्वांटम वॉक्स' (quantum walks) नामक एक तकनीक का उपयोग किया, जो कंप्यूटर को एक तरंग-समान तरीके से नेटवर्क के माध्यम से घूमकर अन्वेषण करने की अनुमति देता है, ताकि टकराव (collisions) का परीक्षण किया जा सके। उन्होंने नमूनाकरण (sampling) की एक विधि का भी उपयोग किया, जहाँ कंप्यूटर जानकारी एकत्र करने के लिए यादृच्छिक बिंदुओं को चुनता है, और इन नमूनों का उपयोग पूरे नेटवर्क की तस्वीर बनाने के लिए करता है बिना हर एक बिंदु की जाँच किए। नमूनाकरण की लागत और परीक्षण की लागत के बीच सावधानीपूर्वक संतुलन बनाकर, उन्होंने कुल पूछे गए प्रश्नों को न्यूनतम करने के लिए एल्गोरिदम को अनुकूलित किया। निचली सीमा के लिए, उन्होंने 'एडवर्सरी मेथड' (adversary method) के रूप में ज्ञात एक परिष्कृत गणितीय ढांचे का उपयोग किया, जिसमें विभिन्न इनपुट के बीच अंतर करने की कठिनाई को मापने के लिए एक मैट्रिक्स का निर्माण शामिल है। इसने उन्हें यह सिद्ध करने की अनुमति दी कि कोई भी क्वांटम एल्गोरिदम, चाहे वह कितना भी चतुर क्यों न हो, उनके विशिष्ट नेटवर्क समस्या को गणना की गई संख्या से कम प्रश्नों के साथ हल नहीं कर सकता।

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

तकनीकी सारांश: ग्राफ कोलिजन के लिए क्वांटम बाधाओं को तोड़ना

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

ग्राफ कोलिजन (Graph Collision) समस्या एक ज्ञात सरल अनडिरेक्टेड ग्राफ $G = (V, E)$ पर परिभाषित है जिसमें $n$ वर्टिस (vertices) हैं। इनपुट एक बिट स्ट्रिंग $x \in \{0, 1\}^V$ है जो चिह्नित वर्टिस के एक सेट $M = \{v : x_v = 1\}$ को निर्दिष्ट करती है। कार्य यह निर्णय लेना है कि क्या कोई किनारा (edge) $uv \in E$ मौजूद है जिसके दोनों छोर चिह्नित हैं (अर्थात, $u, v \in M$ )। गणना की लागत केवल इनपुट बिट्स $x$ के प्रश्नों (queries) की संख्या द्वारा मापी जाती है; ज्ञात ग्राफ संरचना से संबंधित सभी संचालन निःशुल्क हैं।

इस कार्य से पूर्व, मनमाने ग्राफों के लिए सर्वोत्तम ज्ञात क्वांटम क्वेरी अपर बाउंड $\tilde{O}(n^{2/3})$ था, जिसे एम्बिएनिस (Ambignez) के क्वांटम वॉक का उपयोग करके मैग्निएज़, संथा और सेज़ेडी (Magniez, Santha, and Szegedy) द्वारा प्राप्त किया गया था। सर्वोत्तम ज्ञात लोअर बाउंड $\Omega(\sqrt{n})$ था, जो अनस्ट्रक्चर्ड सर्च से प्राप्त हुआ था। इसने एक महत्वपूर्ण अंतर छोड़ दिया था, जहाँ कई शोधकर्ताओं ने अनुमान लगाया था कि कुछ ग्राफ परिवारों के लिए $\Omega(n^{2/3})$ इष्टतम हो सकता है या सभी ग्राफों के लिए $\tilde{O}(\sqrt{n})$ एल्गोरिदम मौजूद हो सकता है।

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

यह शोध पत्र तीन प्राथमिक योगदान प्रस्तुत करता है: दो क्वांटम एल्गोरिदम जो $O(n^{2/3})$ की बाधा को तोड़ते हैं, छोटे पॉजिटिव सर्टिफिकेट वाले फलनों (functions) के लिए एक सामान्यीकरण, और एक लोअर बाउंड जो $\Omega(\sqrt{n})$ की बाधा को तोड़ता है।

1. $O(n^{2/3})$ अपर बाउंड को तोड़ना

लेखक एक क्वांटम एल्गोरिदम विकसित करते हैं जो $\tilde{O}(n^{11/17})$ क्वेरी कॉम्प्लेक्सिटी के साथ ग्राफ कोलिजन को हल करता है। दृष्टिकोण नेबरहुड एस्टीमेशन (neighborhood estimation), थ्रेशोल्डिंग (thresholding), और एज एक्सट्रैक्शन (edge extraction) से जुड़ी एक बहु-चरणीय रणनीति पर निर्भर करता है।

एस्टिमेशन और थ्रेशोल्डिंग: मूल विचार प्रत्येक वर्टेक्स के लिए चिह्नित पड़ोसियों (marked neighbors) की संख्या का अनुमान लगाना है बिना सभी बिट्स को क्वेरी किए। इनपुट बिट्स का नमूना लेकर और ग्राफ संरचना पर लीस्ट-स्क्वेयर्स मिनिमाइजेशन समस्या को हल करके, एल्गोरिदम एक सेट $S$ का निर्माण करता है जिसके नेबरहुड काउंट्स वास्तविक चिह्नित नेबर काउंट्स का अनुमान लगाते हैं।
पार्टिशनिंग (Partitioning): एक थ्रेशोल्ड $\tau$ $τ$ का उपयोग करते हुए, एल्गोरिदम किनारों को दो सेटों में विभाजित करता है:
1. एक सेट $P$ के भीतर किनारे: वे वर्टिस जिनका अनुमानित कम चिह्नित नेबर काउंट है। इस सबग्राफ में "मार्क्ड वॉल्यूम" (चिह्नित वर्टिस की डिग्री का योग) एस्टीमेशन एरर द्वारा सीमित है।
2. कम से कम एक छोर $P$ के बाहर वाले किनारे: नेगेटिव इनपुट पर, $P$ के बाहर के वर्टिस के पास बड़ा एस्टीमेशन एरर होना चाहिए। यह ऐसे वर्टिस की संख्या को सीमित करता है, जिससे शेष किनारों का मार्क्ड वॉल्यूम सीमित हो जाता है।
प्रीप्रोसेसिंग और एक्सट्रैक्शन: एस्टिमेटर्स के वेरिएंस को नियंत्रित करने के लिए, एल्गोरिदम ग्राफ को प्रीप्रोसेस करता है। यह मार्क्ड वॉल्यूम को कम करने के लिए वर्टिस का नमूना लेता है, उच्च-डिग्री वाले वर्टिस से जुड़े किनारों को हटा देता है, और "डेंस नेबरहुड्स" (दो अत्यधिक कनेक्शन वाले वर्टिस के नेबरहुड्स के बीच के किनारे) निकालता है। इन निकाले गए सबग्राफों का क्वांटम वॉक का उपयोग करके अलग से परीक्षण किया जाता है, जबकि शेष ग्राफ को एस्टीमेशन रूटीन के साथ प्रोसेस किया जाता है।
रिफाइनमेंट (Refinement): प्रारंभिक एल्गोरिदम $\tilde{O}(n^{92/139})$ प्राप्त करता है। एक परिष्कृत संस्करण (अनुभाग 4) बाइटाइट रिडक्शन और चिह्नित वर्टिस के अधिक परिष्कृत सैंपलिंग का उपयोग करके मार्क्ड वॉल्यूम और डिग्री को पुनरावृत्ति से कम करता है। इससे अंतिम बाउंड $\tilde{O}(n^{11/17})$ प्राप्त होता है।

2. छोटे पॉजिटिव सर्टिफिकेट वाले फलनों का सामान्यीकरण

यह शोध पत्र ग्राफ कोलिजन के परिणाम को एक व्यापक श्रेणी के बूलियन फलनों तक विस्तारित करता है।

रिडक्शन: $q$ आकार के अल्फाबेट से $n$ प्रतीकों पर कोई भी (आंशिक) बूलियन फलन $f$ , जहाँ प्रत्येक पॉजिटिव इनपुट का सर्टिफिकेट आकार अधिकतम 2 है, उसे $nq$ वर्टिस पर ग्राफ कोलिजन समस्या में बदला जा सकता है।
परिणाम: यह $\tilde{O}((nq)^{11/17})$ का क्वेरी बाउंड प्रदान करता है।
महत्व: यह बड़े अल्फाबेट पर एलिमेंट डिस्टिंक्टनेस (element distinctness) के लिए ज्ञात $\Omega(n^{2/3})$ लोअर बाउंड के विपरीत है (जिसमें भी सर्टिफिकेट साइज 2 है)। यह परिणाम दर्शाता है कि अल्फाबेट का आकार $q$ सर्टिफिकेट-आधारित लोअर बाउंड के लिए एक महत्वपूर्ण कारक है; $q = O(n^{1/33-\epsilon})$ के लिए, जटिलता $o(n^{2/3})$ है।

3. $\Omega(\sqrt{n})$ लोअर बाउंड को तोड़ना

लेखक सिद्ध करते हैं कि $\Omega(\sqrt{n})$ की बाधा सभी ग्राफों के लिए टाइट नहीं है, जिससे $\Omega(\sqrt{n} \log n)$ का लोअर बाउंड स्थापित होता है।

निर्माण: लोअर बाउंड का निर्माण एक परिमित क्षेत्र $\mathbb{F}_q^2$ पर पॉइंट्स और नॉन-वर्टिकल लाइन्स के इंसिडेंस ग्राफ (incidence graph) का उपयोग करके किया गया है। इस ग्राफ में $n = 2q^2$ वर्टिस और $q^3$ किनारे हैं।
एडवर्सरी मेथड (Adversary Method): प्रमाण जनरल एडवर्सरी बाउंड (नेगेटिव वेट्स की अनुमति देने वाला) का उपयोग करता है, जो पॉजिटिव एडवर्सरी मेथड की सीमा को पार करता है जो सर्टिफिकेट साइज 2 वाले फलनों के लिए $O(\sqrt{n})$ पर रुक जाता है।
तकनीक: लेखक बिना किसी चिह्नित किनारे वाले इनपुट की तुलना ठीक एक "प्लांटेड" (planted) चिह्नित किनारे वाले इनपुट से करके एक एडवर्सरी मैट्रिक्स का निर्माण करते हैं। वे एक परिष्कृत "प्लांटिंग" वितरण का उपयोग करते हैं और एडवर्सरी रेशियो के हर (denominator) को फुलाने वाले योगदानों को रद्द करने के लिए एडिटिव और मल्टीप्लिकेटिव करेक्शन (मैट्रिक्स $C$ और $D$ के माध्यम से) का उपयोग करते हैं। प्रतिबंधित मैट्रिसेस के नॉर्म (norm) को बांधने के लिए परिमित क्षेत्र के ज्यामितीय गुण (दो बिंदु अधिकतम एक रेखा निर्धारित करते हैं, दो रेखाएं अधिकतम एक बिंदु पर मिलती हैं) अत्यंत महत्वपूर्ण हैं।

परिणाम

अपर बाउंड: एक क्वांटम एल्गोरिदम उच्च संभावना के साथ किसी भी $n$ -वर्टेक्स ग्राफ पर $\tilde{O}(n^{11/17})$ क्वेरी का उपयोग करके ग्राफ कोलिजन को हल करता है (थ्योरम 1.1)।
लोअर बाउंड: $n$ -वर्टेक्स ग्राफों का एक परिवार मौजूद है जिसके लिए ग्राफ कोलिजन की क्वांटम क्वेरी कॉम्प्लेक्सिटी $\Omega(\sqrt{n} \log n)$ है (थ्योरम 1.2)।
अल्फाबेट सेंसिटिविटी: आकार $q$ के अल्फाबेट पर अधिकतम 2 के पॉजिटिव सर्टिफिकेट कॉम्प्लेक्सिटी वाले फलनों के लिए, क्वांटम क्वेरी कॉम्प्लेक्सिटी $\tilde{O}((nq)^{11/17})$ है। यह $o(n^{2/3})$ है जब $q = O(n^{1/33-\epsilon})$ हो।

महत्व और दावे

यह शोध पत्र इस दावे का खंडन करता है कि मनमाने ग्राफों पर ग्राफ कोलिजन के लिए $\Omega(n^{2/3})$ इष्टतम क्वेरी कॉम्प्लेक्सिटी है। $11/17 \approx 0.647$ (जो $2/3 \approx 0.667$ से कम है) एक्सपोनेंट वाला एल्गोरिदम प्रदान करके, लेखक प्रदर्शित करते हैं कि $O(n^{2/3})$ बाउंड इस समस्या के लिए एक मौलिक बाधा नहीं है।

इसके विपरीत, $\Omega(\sqrt{n} \log n)$ का लोअर बाउंड मनमाने ग्राफों के लिए $O(\sqrt{n})$ एल्गोरिदम की संभावना को खारिज करता है, जिससे $\sqrt{n}$ के ट्रिवियल लोअर बाउंड और नए अपर बाउंड के बीच के अंतर को कम किया गया है, हालांकि $\sqrt{n} \log n$ और $n^{11/17}$ के बीच एक अंतर बना हुआ है।

यह कार्य सर्टिफिकेट स्ट्रक्चर के महत्व को भी उजागर करता है, यह दिखाते हुए कि छोटे सर्टिफिकेट वाले फलनों के लिए, अल्फाबेट का आकार जटिलता को महत्वपूर्ण रूप से प्रभावित कर सकता है, जिससे बड़े-अल्फाबेट लोअर बाउंड द्वारा सूचित की गई गति से तेज़ एल्गोरिदम संभव होते हैं।

नोट: लेखक कोर प्रूफ आइडियाज प्रस्तावित करने, $13/20$ एक्सपोनेंट वाला प्रारंभिक एल्गोरिदम विकसित करने, और $92/139$ तथा $11/17$ तक रिफाइनमेंट करने के साथ-साथ लोअर बाउंड के निर्माण में जेनेरेटिव एआई (GPT-6 Astra) के उपयोग को स्पष्ट रूप से स्वीकार करते हैं। वे सभी गणितीय दावों के लिए पूर्ण जिम्मेदारी रखते हैं।