कंप्यूटर वैज्ञानिक परीक्षण ज्ञान के दायरे का विस्तार करते हैं

कंप्यूटर-चेक किए गए कार्यों का ब्रह्मांड बड़ा हो गया है। किस गुप्त घटक के लिए धन्यवाद? क्वांटम उलझाव के कारण।

कल्पना कीजिए कि कोई आपके पास आया और उसने कहा कि उसके पास एक आभूषण है जो ब्रह्मांड के गुप्त रहस्यों को प्रकट कर सकता है। आपको इसमें रुचि हो सकती है, लेकिन आपके लिए इस पर विश्वास करना कठिन होगा। आप इस बात की पुष्टि करना चाहते हैं कि ओरेकल सच कह रहा है।

यह कंप्यूटर विज्ञान की मुख्य समस्या है। कुछ कार्यों को समय की उचित मात्रा में हल करना बहुत मुश्किल है। लेकिन उनके फैसलों को सत्यापित करना आसान है। इसे देखते हुए, कंप्यूटर वैज्ञानिक जानना चाहते हैं: कोई कार्य कितना जटिल हो सकता है, जिसके समाधान को अभी भी सत्यापित किया जा सकता है?

यह पता चला है कि इस सवाल का जवाब है: लगभग अकल्पनीय रूप से जटिल।

एक पेपर में जो अप्रैल 2019 में दिखाई दिया, दो कंप्यूटर विज्ञान विशेषज्ञों ने मौलिक रूप से "हल करना मुश्किल, सत्यापित करना आसान" की श्रेणी में गिरने वाले कार्यों की संख्या में मौलिक रूप से वृद्धि की। वे एक ऐसी विधि का वर्णन करते हैं जो किसी को लगभग असंगत जटिलता की समस्याओं के समाधान को सत्यापित करने की अनुमति देता है। "यह पागल लगता है," थॉमस विडिक ने कहा, कैलिफोर्निया इंस्टीट्यूट ऑफ टेक्नोलॉजी के एक आईटी विशेषज्ञ जो इस काम में शामिल नहीं हैं।

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

नया काम, वास्तव में, हमें उस सर्वशक्तिमान ओरेकल पर लाभ देता है। भले ही ओरेकल समस्याओं के लिए आपको तैयार समाधान देने का वादा करता है, जिनकी समाधान संभावनाएं आपकी क्षमताओं से परे हैं, फिर भी यह जांचने का एक तरीका है कि क्या ओरेकल सच कह रहा है।

ब्रह्मांड के अंत तक

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



तीन रंगों का कार्य हल करना मुश्किल है। सामान्य स्थिति में, लंबों के रंग की खोज के लिए आवश्यक समय (या यह निर्धारित करना कि इस तरह के रंग मौजूद नहीं हैं) ग्राफ़ के बढ़ते आकार के साथ तेजी से बढ़ता है। यदि, कहते हैं, 20 कोने के साथ एक ग्राफ के लिए एक समाधान खोजने में 3 ²⁰ ns लगते हैं - यानी, कुछ सेकंड, तो 60 कोने वाले ग्राफ़ के लिए खोज करने के लिए 3 ⁶⁰ ns लगेगा, जो कि ब्रह्मांड की वर्तमान आयु का 100 गुना है।

लेकिन मान लीजिए कि किसी ने तीन रंगों से गिनती को चित्रित करने का दावा किया है। इस आवेदन के सत्यापन में अधिक समय नहीं लगेगा। आपको बस एक-एक करके सभी शीर्षों के चारों ओर जाने की जरूरत है, उनसे जुड़े कोने का अध्ययन करना। जैसे-जैसे ग्राफ का आकार बढ़ता है, इस जांच का समय धीरे-धीरे बढ़ता है - बहुपद के रूप में। नतीजतन, एक कंप्यूटर को 60 वर्टिकल के ग्राफ के रंग की जांच करने में अधिक समय नहीं लगता है, क्योंकि यह 20 वर्टिकल के ग्राफ की जांच करता है।

मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी के भौतिक विज्ञानी जॉन राइट ने कहा, "तीन रंगों में सही रंगों के साथ, अपने प्रदर्शन का परीक्षण करना आसान है," उन्होंने कहा, जिन्होंने कैलटेक के आनंद नटराजन के साथ मिलकर यह काम लिखा था।

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

सही सवाल

नटराजन और राइट के काम से पहले, निरीक्षण की शक्ति दो बड़ी छलांगों में बढ़ गई।

पहले को समझने के लिए, कल्पना करें कि आप रंगों में अंतर नहीं करते हैं। कोई आपके सामने टेबल पर दो क्यूब्स रखता है, और पूछता है कि क्या वे एक ही रंग या अलग हैं। यह कार्य आपके लिए असंभव है। इसके अलावा, आप इस समस्या के समाधान के लिए किसी और के सही होने की पुष्टि नहीं कर सकते।

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

यदि क्यूब्स अलग-अलग रंगों के हैं, तो यह एक बहुत ही सरल प्रश्न है। यह कहावत C A को पहचानती है, यदि यह एक लाल घन कहे, और इसे हर बार सही ढंग से निर्धारित करेगा।

हालांकि, यदि क्यूब्स एक ही रंग के हैं - और उन्हें अलग-अलग कहने में कहावत गलत है - तो कहावत केवल अनुमान लगा सकती है कि कौन सा है। इसलिए, वह क्यूब ए को केवल 50% मामलों में सही ढंग से निर्धारित करने में सक्षम होगा। अपने फैसले के बारे में नीतिवचनकर्ता से लगातार सवाल करके, आप पुष्टि कर सकते हैं कि क्या यह सही है।


आनंद नटराजन और जॉन राइट

"परीक्षक ने प्रश्नकर्ता को प्रश्न भेज सकते हैं," राइट ने कहा, "और शायद बातचीत के अंत में, परीक्षक उत्तर के बारे में अधिक आश्वस्त होगा।"

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

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

राइट ने कहा, "दोनों संदिग्ध वितरित सुसंगत कहानी नहीं बना पाएंगे, क्योंकि वे नहीं जानते कि अन्य उत्तर क्या हैं।"

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

इस दृष्टिकोण का उपयोग करना, उदाहरण के लिए, ग्राफ़ के अनुक्रम के लिए तीन रंगों में ग्राफ़ को रंगने की शुद्धता की पुष्टि करने के लिए संभव है, जो एनपी से ग्राफ़ की तुलना में बहुत तेज़ी से आकार में बढ़ता है। एनपी में, ग्राफ़ के आकार में रैखिक रूप से वृद्धि होती है - कोने की संख्या 1 से 2 तक बढ़ सकती है, 3 से 4 तक हो सकती है, और इसी तरह - ताकि ग्राफ़ का आकार रंग की जांच करने के लिए आवश्यक समय की मात्रा से अधिक बड़ा न हो। लेकिन एमआईपी में, ग्राफ वर्टिकल की संख्या 2 ¹ से 2 ² , 2 ³ , 2 ⁴ , और इसी तरह तेजी से बढ़ती है।

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

एमआईपी में, परीक्षक के पास एक प्रोग्राम चलाने के लिए पर्याप्त मेमोरी होती है जो हमें यह निर्धारित करने की अनुमति देती है कि क्या ग्राफ के दो कोने एक किनारे से जुड़े हुए हैं - और वह यह सुनिश्चित करने के लिए परीक्षकों के उत्तरों को सत्यापित कर सकता है कि रंग सही है।

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

नटराजन और राइट के नए काम के पास इस सवाल का जवाब है।

क्वांटम ट्रिक

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

अपने नए काम में, नटराजन और राइट एक परिदृश्य पर विचार करते हैं जिसमें दो अलग-अलग क्वांटम कंप्यूटर शामिल होते हैं, जिनमें से एक के साथ दूसरे के क्वैट्स के साथ भ्रमित होते हैं।

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

वास्तव में, जब दो उलझे हुए क्वांटम कंप्यूटर के साथ परिदृश्य का पहली बार 2003 में अनावरण किया गया था, तो कंप्यूटर वैज्ञानिकों ने सुझाव दिया कि उलझाव सत्यापन की संभावना को कम करेगा। विदिक ने कहा, "मेरी सहित सभी की स्पष्ट प्रतिक्रिया यह थी कि इस मामले में सिद्ध करने वालों के पास अधिक अवसर थे।" "वे अपने उत्तरों को जोड़ने के लिए भ्रम की स्थिति का उपयोग कर सकते हैं।"

लेकिन, शुरुआती निराशावाद के बावजूद, विदिक ने इसके विपरीत साबित होने की कोशिश में कई साल बिताए। 2012 में, उन्होंने और Tsuyoshi Ito ने साबित किया कि पेचीदा क्वांटम कंप्यूटरों का उपयोग करके MIP में सभी कार्यों का परीक्षण करने की क्षमता मौजूद है।

अब, नटराजन और राइट ने साबित कर दिया है कि स्थिति और भी बेहतर है: पेचीदगी की मदद से, समस्याओं के बिना भी एक बड़ा वर्ग साबित हो सकता है। उलझी हुई क्वांटम कंप्यूटरों के बीच कनेक्शन को सत्यापनकर्ता के लाभ के लिए उलट करना संभव है।

यह समझने के लिए कि यह कैसे करना है, एमआईपी से उन ग्राफ़िक्स के रंग की जांच करने की प्रक्रिया को याद करें जिनके आकार तेजी से बढ़ते हैं। पूरे ग्राफ़ को संग्रहीत करने के लिए परीक्षक के पास पर्याप्त मेमोरी नहीं है, लेकिन उसके पास दो जुड़े हुए कोने निर्धारित करने के लिए पर्याप्त मेमोरी है, और परीक्षकों से इन कोने के रंग के बारे में एक प्रश्न पूछने के लिए।

नटराजन और राइट द्वारा विचार की जाने वाली समस्याओं की श्रेणी में - एनईईएक्सपी, जिसे दो बार घातीय समय कहा जाता है - एमआईपी की तुलना में ग्राफ़ का आकार और भी तेज़ी से बढ़ता है। एनईईएक्सपी में ग्राफ "डबल घातीय दर" पर बढ़ता है। दो - 2 ¹ , 2 ² , 2 ³ , 2 ⁴ , और इतने पर की डिग्री के रूप में बढ़ने के बजाय - रेखांकन की संख्या दो की डिग्री के रूप में बढ़ती है - 2 ^{2 1} , 2 ^{2 2} , 2 ^{2 3} , 2 ^{2 4} , और इसी तरह। नतीजतन, रेखांकन जल्दी से इतना बड़ा हो जाता है कि निरीक्षक अब जुड़े हुए जोड़ की एक जोड़ी भी नहीं खोज पाता है।

नटराजन ने कहा, "वर्टेक्स को पहचानने के लिए 2 ⁿ बिट्स की जरूरत होती है, जो कि मेमोरी में वेरिफ़ायर की तुलना में अधिक होता है।" हालांकि, नटराजन और राइट ने यह साबित कर दिया कि तीन रंगों में डबल-एक्सपोनेंशियल ग्राफ के रंग की जांच करना संभव है, यहां तक ​​कि यह निर्धारित करने की क्षमता के बिना कि किन सबूतों के लिए सबूत मांगने की आवश्यकता है। तथ्य यह है कि आप स्वयं को सही प्रश्नों का चयन करने वाले साबित कर सकते हैं।

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

"उलझे हुए राज्य साझा संसाधन हैं," राइट ने कहा। "हमारा पूरा प्रोटोकॉल यह समझना है कि परस्पर संबंधित मुद्दों को बनाने के लिए इस साझा संसाधन का उपयोग कैसे करें।"

यदि क्वांटम कंप्यूटर भ्रमित होते हैं, तो उनकी पसंद का संबंध सहसंबंधित होगा, और तीन रंगों में रंग की जांच के लिए प्रश्नों का सही सेट देना होगा।

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

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

विद्या ने कहा, "हमें साबित करने वालों को भूलने की जरूरत है, और यह मुख्य बात है कि नटराजन और राइट ने अपने काम में मदद की।" "वे माप के माध्यम से सूचना को मिटाने के लिए मजबूर करते हैं।"

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

और अब जब उन्होंने ऐसा किया है, तो यह स्पष्ट नहीं है कि अगली सत्यापन क्षमता सीमा कहां है। जॉर्जिया इंस्टीट्यूट ऑफ टेक्नोलॉजी के एक आईटी विशेषज्ञ लांस फोर्टनू ने कहा, "यह बहुत आगे हो सकता है।" "वे अगला कदम उठाने का अवसर छोड़ते हैं।"