अंत में, एक समस्या थी कि केवल क्वांटम कंप्यूटर ही हल कर सकते हैं

वर्षों से, कंप्यूटर वैज्ञानिक एक निश्चित प्रकार के कार्यों की तलाश में हैं, जो केवल एक क्वांटम कंप्यूटर को हल करने में सक्षम होगा, लेकिन भविष्य की पीढ़ियों से भी, एक क्लासिक कंप्यूटर नहीं। और इसलिए उन्होंने उनमें से एक को पाया।

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

रेज, प्रिंसटन विश्वविद्यालय के एक प्रोफेसर और विस्मन इंस्टीट्यूट ऑफ साइंस, साथ ही ताल, एक स्टैनफोर्ड यूनिवर्सिटी पोस्ट-डॉक्टर, ने एक विशेष प्रकार की कम्प्यूटेशनल समस्या की पहचान की। उन्होंने साबित किया, एक चेतावनी के साथ, कि क्वांटम कंप्यूटर प्रभावी रूप से समस्या को हल कर सकते हैं, और पारंपरिक कंप्यूटर हमेशा के लिए अटक जाएंगे, इसे करने की कोशिश कर रहे हैं। कंप्यूटर वैज्ञानिक 1993 से ऐसी समस्या की तलाश कर रहे हैं, जब उन्होंने पहली बार BQP टास्क क्लास की पहचान की , जिसमें सभी कार्य शामिल हैं जो एक क्वांटम कंप्यूटर हल कर सकता है।

तब से, उन्हें PH के रूप में ज्ञात कार्यों के BQP वर्ग के विपरीत होने की उम्मीद थी, जिसमें सभी कार्य शामिल हैं जो किसी भी क्लासिक कंप्यूटर पर किए जा सकते हैं, यहां तक ​​कि भविष्य की कुछ सभ्यता द्वारा विकसित अविश्वसनीय रूप से उन्नत एक भी। इस तरह के विपरीत की संभावना एक समस्या को खोजने पर निर्भर करती है जो बीक्यूपी वर्ग की थी, लेकिन पीएच वर्ग की नहीं। और अब रेज और ताल ने किया है।

यह परिणाम व्यावहारिक दृष्टिकोण से क्वांटम कंप्यूटरों को शास्त्रीय से बेहतर नहीं बनाता है। सबसे पहले, सैद्धांतिक कंप्यूटर वैज्ञानिक पहले से ही जानते हैं कि क्वांटम कंप्यूटर शास्त्रीय कार्यों में सक्षम किसी भी कार्य को हल करने में सक्षम हैं। और इंजीनियर एक उपयोगी क्वांटम मशीन बनाने की समस्या को हल करने के लिए संघर्ष कर रहे हैं। लेकिन रेजा और ताल का काम उन श्रेणियों के बीच के अंतर को प्रदर्शित करता है जिसमें क्वांटम और शास्त्रीय कंप्यूटर स्थित हैं - और वह भी ऐसी दुनिया में जहां शास्त्रीय कंप्यूटर किसी भी सपने की सीमा को पार कर चुके हैं, क्वांटम कंप्यूटर अभी भी उनसे आगे निकल सकते हैं।

क्वांटम वर्ग

सैद्धांतिक सूचना विज्ञान का मूल कार्य कार्यों को जटिलता वर्गों में विभाजित करना है। जटिलता वर्ग में वे सभी कार्य होते हैं जिन्हें किसी विशिष्ट संसाधन से हल किया जा सकता है, जैसे समय या स्मृति।

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

दो प्रसिद्ध कठिनाई वर्ग पी और एनपी हैं। P वे सभी कार्य हैं जिन्हें एक क्लासिक कंप्यूटर जल्दी से हल कर सकता है। (समस्या "संख्या अभाज्य है?" पी के अंतर्गत आता है)। एनपी में वे सभी कार्य शामिल हैं जो एक क्लासिक कंप्यूटर आवश्यक रूप से जल्दी से हल नहीं करता है, लेकिन मौजूदा समाधान की शुद्धता, जिनमें से कोई भी इसे जल्दी से जांच सकता है। ("संख्या के प्रमुख कारक क्या हैं?" एनपी के अंतर्गत आता है)। वैज्ञानिकों का मानना ​​है कि कक्षाएं पी और एनपी अलग हैं, लेकिन इस अंतर को साबित करने का काम इस क्षेत्र में खुली समस्याओं में सबसे कठिन और सबसे महत्वपूर्ण है।


PH में एक NP होता है जिसमें P होता है। BQP एक वर्ग PH से अलग होता है?

1993 में, कंप्यूटर वैज्ञानिक ईथन बर्नस्टीन और उमेश वज़ीरानी ने एक नई जटिलता वर्ग को परिभाषित किया, जिसे उन्होंने BQP कहा, या "क्वांटम-बहुपद समय त्रुटि प्रायिकता सीमा।" उन्होंने कक्षा को सभी निर्णय लेने वाले कार्यों के रूप में परिभाषित किया - उत्तर "हाँ" या "नहीं" के साथ कार्य - क्वांटम कंप्यूटर प्रभावी रूप से हल करने में सक्षम हैं। लगभग उसी समय, उन्होंने साबित कर दिया कि क्वांटम कंप्यूटर उन सभी कार्यों को हल करने में सक्षम हैं जो शास्त्रीय हैं। यही है, बीक्यूपी में पी में निहित सभी कार्य शामिल हैं।

व्यक्तिगत कार्य वर्गों का एक और उदाहरण। सेल्समैन की समस्या यह पूछती है कि क्या कुछ शहरों से होकर गुजरने वाला मार्ग एक निश्चित दूरी से कम है। ऐसा कार्य एनपी में है। एक अधिक कठिन कार्य यह पूछता है कि क्या यह दूरी इन शहरों के माध्यम से सबसे छोटा रास्ता है। ऐसा कार्य PH में है।

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

"पीएच जटिलता की सबसे सरल कक्षाओं में से एक है, जो ऑस्टिन में टेक्सास विश्वविद्यालय के एक आईटी विशेषज्ञ स्कॉट आरोनसन ने कहा। "तो हम शास्त्रीय जटिलता की दुनिया में क्वांटम कंप्यूटिंग की जगह जानना चाहते हैं।"

दो कठिनाई वर्गों को अलग करने का सबसे अच्छा तरीका एक समस्या को खोजने के लिए है, जिनमें से एक में शामिल है और दूसरे में शामिल नहीं है। हालांकि, मौलिक और तकनीकी बाधाओं के संयोजन के कारण, इस तरह के कार्य को खोजना बहुत मुश्किल था।

आरोनसन ने कहा कि ऐसा काम खोजने के लिए जो बीक्यूपी से संबंधित है, लेकिन पीएच से नहीं, आपको कुछ ऐसा परिभाषित करने की जरूरत है, जो "एक क्लासिक कंप्यूटर, परिभाषा के अनुसार, प्रभावी ढंग से उत्तर की जांच भी नहीं कर सकता।" "यह उन कई कार्यों को समाप्त करता है जो हम कंप्यूटर विज्ञान में काम करते हैं।"

ओरैकल पूछें

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


दौड़ा दौड़ा आया

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

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

इसके बजाय, कंप्यूटर विज्ञान में कुछ और मापा जा रहा है, जिसे कम्प्यूटेशनल समय की समझ प्रदान करना माना जाता है जिसे सीधे मापा नहीं जा सकता है। वैज्ञानिकों ने प्रश्न का उत्तर देने के लिए "ओरेकल" के लिए कंप्यूटर कॉल की संख्या की गणना की। तांडव सुराग देने के लिए लगता है। हम नहीं जानते कि वह उन्हें कैसे प्राप्त करता है, लेकिन हम जानते हैं कि वे विश्वसनीय हैं।

यदि आपका कार्य यह पता लगाना है कि क्या दो यादृच्छिक संख्या जनरेटर के बीच एक गुप्त संबंध है, तो आप "जैसे प्रत्येक जनरेटर की छठी संख्या क्या होगी?" फिर आपको समस्या को हल करने के लिए प्रत्येक कंप्यूटर द्वारा आवश्यक संकेतों की संख्या के आधार पर कंप्यूटिंग शक्ति की तुलना करने की आवश्यकता है। एक कंप्यूटर जिसे अधिक संकेत की आवश्यकता होती है, वह धीमी गति से चलता है।

“एक अर्थ में, हम इस मॉडल को बहुत बेहतर समझते हैं। वह कंप्यूटिंग के बारे में जानकारी के बारे में अधिक बात करती है, “ताल ने कहा।


अविशई ताल

रेजा और ताल का नया काम यह साबित करता है कि एक क्वांटम कंप्यूटर को एक शास्त्रीय की तुलना में एक विच्छेदन समस्या को हल करने के लिए बहुत कम सुराग की आवश्यकता होगी। इसके अलावा, क्वांटम कंप्यूटर को केवल एक संकेत की आवश्यकता होती है, इस तथ्य के बावजूद कि PH में ऐसी समस्या को हल करने के लिए एल्गोरिदम नहीं है, यहां तक ​​कि असीमित संख्या में संकेत भी। "इसका मतलब है कि एक अत्यंत कुशल क्वांटम एल्गोरिथ्म है जो इस तरह की समस्या को हल करता है," रेज ने कहा। "लेकिन अगर हम केवल शास्त्रीय एल्गोरिदम पर विचार करते हैं, तो भले ही हम शास्त्रीय एल्गोरिदम के बहुत शीर्ष वर्गों के लिए जाएं, वे इसके साथ सामना नहीं कर पाएंगे।" यह साबित करता है कि ओरेकल के साथ, सहसंबंध बीक्यूपी से संबंधित कार्यों को संदर्भित करता है, लेकिन पीएच को नहीं।

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

BQP और PH वर्गों के अलग होने की खबरें तेजी से फैलीं। "क्वांटम जटिलता की दुनिया गूंज रही है," काम के प्रकाशन के अगले दिन जॉर्जिया प्रौद्योगिकी विश्वविद्यालय के एक आईटी विशेषज्ञ लांस फोर्टनू ने लिखा ।

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

"भले ही पी, एनपी के बराबर था, यहां तक ​​कि इस तरह के एक मजबूत धारणा के साथ," फोर्टनू ने कहा, "क्वांटम कंप्यूटर अब भी पकड़ में नहीं आएंगे।"