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

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

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

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

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

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

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

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

शोधकर्ताओं का कार्य क्वांटम प्रॉपर्टी टेस्टिंग में क्या संभव है, इसकी सीमाओं को भी स्पष्ट करता है। बाइपार्टाइटनेस के लिए एक्सपोनेंशियल स्पीडअप की संभावना को खारिज करके, उन्होंने एक ऐसे प्रश्न को हल किया जो डेढ़ दशक से अधिक समय से खुला था। उनका प्रमाण इस बात की गहरी समझ पर निर्भर करता है कि क्वांटम एल्गोरिदम डेटा की संरचना के साथ कैसे अंतःक्रिया करते हैं, जिसमें परिष्कृत गणितीय उपकरणों का उपयोग करके यह दिखाया गया है कि एल्गोरिदम की नेटवर्क को "देखने" की क्षमता प्रश्न पूछने की संख्या द्वारा मौलिक रूप से सीमित है। यह अध्ययन यह सुझाव नहीं देता है कि क्वांटम कंप्यूटर इन कार्यों के लिए बेकार हैं; बल्कि, यह उनकी शक्ति की सटीक सीमा को परिभाषित करता है। क्वांटम स्पीडअप वास्तविक और मूल्यवान है, लेकिन यह क्यूब रूट द्वारा सीमित है।

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

लेख इस बात पर ध्यान देते हुए समाप्त होता है कि हालांकि क्वेरी कॉम्प्लेक्सिटी का मुख्य प्रश्न सुलझ गया है, फिर भी कुछ सूक्ष्म विवरण शेष हैं। जटिलता में लॉगरिदमिक कारकों की सटीक संख्या अभी भी एक खुला प्रश्न है, और जटिलता की विशिष्ट मापदंडों पर निर्भरता भी। हालाँकि, प्राथमिक परिणाम अडिग है: बाइपार्टाइटनेस और एक्सपेंशन टेस्टिंग के लिए क्वांटम क्वेरी कॉम्प्लेक्सिटी नेटवर्क के आकार के क्यूब रूट के पास अनुकूलतम (near-optimal) है। यह खोज क्वांटम ग्राफ एल्गोरिदम के अध्ययन में एक लंबे अध्याय के समापन का संकेत देती है, जो अनिश्चितता को एक सटीक गणितीय सीमा से बदल देती है। यह सैद्धांतिक कंप्यूटर विज्ञान में कठोर प्रमाण की शक्ति का एक प्रमाण है, जो यह दिखाता है कि क्वांटम मैकेनिक्स के क्षेत्र में भी, दुनिया की संरचना के बारे में सीखने की गति पर सख्त सीमाएँ होती हैं।