MIP * = RE: कंप्यूटर विज्ञान के क्षेत्र से युगांतरकारी साक्ष्य जो भौतिकी और गणित में डोमिनोज़ प्रभाव का कारण बने

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

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





एमआईपी * = आरई ने उन्हें संयुक्त किया, जिससे कंप्यूटर विज्ञान, भौतिकी और गणित के क्षेत्र में कई समस्याओं का समाधान हुआ।

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

मिगुएल नवस्क्यू , वियना में क्वांटम ऑप्टिक्स और क्वांटम सूचना संस्थान में क्वांटम भौतिकी के छात्र हैं। "यह एक पूर्ण आश्चर्य था," उन्होंने कहा, सबूत पर टिप्पणी करते हुए।

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

परिणामस्वरूप, गणित और भौतिकी में साक्ष्य को लागू करने के परिणामों ने डोमिनोज़ प्रभाव जैसा कुछ किया।

“सभी विचार समान अवधि के हैं। हेनरी यूएन का कहना है कि उन्हें फिर से इतने शानदार तरीके से साथ आना अच्छा लगता है) टोरंटो विश्वविद्यालय से - साक्ष्य के सह-लेखकों में से एक। इसके अलावा उस से इस काम में Chzhenfen जी (भाग लिया जी की Zhengfeng ) प्रौद्योगिकी सिडनी, जॉन राइट (विश्वविद्यालय से जॉन राइट ऑस्टिन में टेक्सास विश्वविद्यालय से), आनंद नटराजन ( आनंद नटराजन ) और थॉमस विडिक ( थॉमस Vidick द्वारा ) कैलिफोर्निया प्रौद्योगिकी संस्थान से। सभी पाँच वैज्ञानिक कंप्यूटर विज्ञान के क्षेत्र में काम करते हैं।

अघुलनशील समस्याएं

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

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

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

हेनरी यूएन, थॉमस विडिक, झेंगफेंग जी, आनंद नटराजन, जॉन राइट

"आपने एक लाख साल इंतजार किया, और कार्यक्रम बंद नहीं हुआ। शायद आपको बस 2 मिलियन साल इंतजार करना होगा? इसे पहले से बताने का कोई तरीका नहीं है, "- विलियम स्लोफ़स्ट्रा ( विलियम स्लॉफ़स्ट्रा ), वाटरलू विश्वविद्यालय के एक गणितज्ञकहते हैं।

तकनीकी दृष्टिकोण से ट्यूरिंग ने साबित कर दिया कि शटडाउन समस्या अकल्पनीय है। यहां तक ​​कि सबसे शक्तिशाली कंप्यूटर जिसे आप कल्पना कर सकते हैं कि वह इसे संभालने में सक्षम नहीं है।

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

नतीजतन, कोई भी समस्या शोधकर्ताओं के लिए दो बड़े सवाल खड़ी करती है: “इसे हल करना कितना कठिन है? यह पुष्टि करने में कठिनाई क्या है कि परिणामस्वरूप समाधान सही है? "

पूछताछ के माध्यम से निर्णय की जांच

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

सत्यापन विधि पुलिस पूछताछ के तर्क का अनुसरण करती है।

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

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

एक साधारण उदाहरण पर विचार करें। मान लीजिए कि कोई व्यक्ति (सत्यापनकर्ता) कलर ब्लाइंडनेस से पीड़ित है। कोई और (गवाह) का दावा है कि दो गेंदों को अलग-अलग रंगों में चित्रित किया गया है और एक दूसरे से अलग नहीं हैं। सत्यापनकर्ता इस कथन को स्वयं सत्यापित नहीं कर सकता है। लेकिन, चालाकी से पूछताछ करने पर, वह फिर भी पता लगा सकता है कि क्या वास्तव में ऐसा है।

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

थॉमस विडिक का कहना है कि यदि अब तक आधे से अधिक नीतिवचन के उत्तर सही निकले हैं, तो किसी को बहुत विश्वास हो सकता है कि गेंदों के अलग-अलग रंग हैं।

कहावत प्रश्न पूछकर, आप समस्याओं के व्यापक वर्ग के समाधानों को सत्यापित कर सकते हैं, जबकि आप स्वयं को सत्यापित कर सकते हैं।

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

थॉमस विडिक के अनुसार, यह सत्यापनकर्ता को अधिक प्रभाव देता है। वह पूछताछ करता है, संबंधित सवाल पूछता है, जवाबों को क्रॉस-चेक करता है। यदि संदिग्ध सच कह रहे हैं, तो उनके जवाब एक-दूसरे से अधिकतर समय मेल खाना चाहिए। अगर वे झूठ बोलते हैं, तो उनके जवाब अक्सर अलग हो जाएंगे।

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

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

आनंद नटराजन का कहना है कि अगर हम गणनाओं के शास्त्रीय भौतिक आधार से दूर जाते हैं और क्वांटम तंत्र की तरह पूरी तरह से कुछ अलग करते हैं, तो हमें कम्प्यूटेशनल जटिलता का एक नया सिद्धांत भी मिलेगा।

नई साक्ष्य 21 वीं सदी के कंप्यूटर वैज्ञानिकों की एक टक्कर का अंतिम परिणाम है जो पिछली शताब्दी के भौतिकी के सबसे अजीब विचारों में से एक है - क्वांटम उलझाव के विचार के साथ।

कॉन की समस्या

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

हालांकि, इन प्रयासों के मिश्रित परिणाम आए हैं। वैज्ञानिकों ने दो अलग-अलग गणितीय मॉडलों के साथ उलझाव का सामना किया है। हालांकि, यह स्पष्ट नहीं था कि ये मॉडल एक-दूसरे के बराबर हैं या नहीं।

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

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

लेकिन कुछ स्थितियों में, संस्थाओं का कारण पृथक्करण पूरी तरह से स्पष्ट नहीं है। नतीजतन, गणितज्ञ कार्य-कारण स्वतंत्रता का वर्णन करने के एक दूसरे, अधिक सामान्य तरीके से पहुंचे।

जब जिस क्रम में दो ऑपरेशन किए जाते हैं, वह परिणाम को प्रभावित नहीं करता है, तो ऑपरेशन को कम्यूटेटिव कहा जाता है: 3x2 2x3 के समान है। इस दूसरे मॉडल में, कणों को उलझाया जाता है जब उनके गुण सहसंबद्ध होते हैं, लेकिन जिस क्रम में माप किए जाते हैं वह कोई फर्क नहीं पड़ता। कण B की गति की भविष्यवाणी करने के लिए, और इसके विपरीत कण A पर माप ले सकते हैं। किसी भी मामले में, परिणाम समान होगा। इसे कम्यूटेशन ऑपरेटर उलझाव मॉडल कहा जाता है।

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

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

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

लेकिन इन दोनों समस्याओं का हल पूरी तरह से अप्रत्याशित जगह से आया।

खेल भौतिकी

1960 के दशक में, भौतिक विज्ञानी जॉन बेल ने यह निर्धारित करने के लिए एक परीक्षण किया कि क्या क्वांटम उलझाव एक वास्तविक भौतिक घटना है, न कि एक सैद्धांतिक अवधारणा। परीक्षण ने एक गेम की तरह कुछ का उपयोग किया, जिसके परिणामों ने यह पता लगाना संभव किया कि क्या कुछ तंत्र जो खेल के दौरान सामान्य भौतिकी के काम से संबंधित नहीं हैं।

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

लेकिन आगे बढ़ने से पहले, चलिए खेल के बारे में बात करते हैं। कल्पना कीजिए कि दो खिलाड़ी हैं: ऐलिस और बॉब, और एक 3x3 खेल का मैदान भी। प्रस्तुतकर्ता ऐलिस को एक पंक्ति प्रदान करता है और उसे प्रत्येक सेल में 0 या 1 दर्ज करने का संकेत देता है, ताकि उनकी राशि एक विषम संख्या दे। बॉब को एक कॉलम मिलता है जिसमें शून्य और लोगों को भरना पड़ता है ताकि उनकी राशि एक सम संख्या दे सके। यदि वे उस स्थान पर उसी संख्या में जीतेंगे, जहां पंक्ति और स्तंभ प्रतिच्छेद करते हैं। उसके साथ संवाद करना असंभव है।

सामान्य परिस्थितियों में, वे जो सबसे अच्छा कर सकते हैं वह 89% समय जीतता है। लेकिन अगर आप क्वांटम उलझाव के कारक को ध्यान में रखते हैं, तो उनकी संभावना में सुधार होता है।

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

यदि सेल में अलग-अलग संख्याएं हैं जहां पंक्ति और स्तंभ प्रतिच्छेद करते हैं, तो खेल खो जाता है। यदि वे समान हैं - जीत गए हैं।

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

हेनरी यूएन का कहना है कि वर्षों से, वैज्ञानिकों ने इन भयावह घटनाओं की वास्तविकता को साबित करने के लिए प्रयोग किए हैं।

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

लेकिन 2016 में, विलियम स्लॉफ़स्ट्रा ने साबित कर दिया कि सभी गैर-स्थानीय खेलों के लिए जीतने की सटीक अधिकतम संभावना की गणना के लिए कोई सामान्य एल्गोरिथ्म नहीं है । परिणामस्वरूप, शोधकर्ताओं ने सवाल पूछा: क्या कम से कम लगभग जीत की अधिकतम प्रतिशत गणना करना संभव है ?

कंप्यूटर वैज्ञानिक ऊपर वर्णित क्वांटम उलझाव के दो मॉडलों का उपयोग करते हुए जवाब में आए। दसियों उत्पाद मॉडल का उपयोग करने वाला एल्गोरिथ्म सभी गैर-स्थानीय खेलों के लिए जीतने की अधिकतम संभावना की अनुमानित गणना के लिए न्यूनतम मूल्य निर्धारित करता है। स्विचिंग ऑपरेटर के मॉडल का उपयोग करने वाला एक अन्य एल्गोरिदम अधिकतम मूल्य निर्धारित करता है।

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

लेकिन अगर ज़र्लसन की परिकल्पना सच नहीं है, और दो मॉडल समकक्ष नहीं हैं, तो, हेनरी यूएन के अनुसार, ऊपरी और निचले सीमा हमेशा अलग हो जाएंगे। और गैर-स्थानीय खेलों के लिए जीत के अनुमानित प्रतिशत की गणना करने का कोई तरीका भी नहीं होगा।

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

जटिल मदद

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

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

लेकिन अगले कुछ वर्षों में, यह स्पष्ट हो गया कि विपरीत कथन सत्य था: "पूछताछ" से यह साबित होता है कि जिनके पास जटिल कण हैं, समस्याओं के एक बहुत व्यापक वर्ग को साबित किया जा सकता है जब ऐसे कण नहीं होते हैं।

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

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

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

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

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

लेकिन यह भी पूछताछ की रणनीति ब्रह्मांड में परमाणुओं की तुलना में अधिक चेहरे और कोने के साथ विशाल रेखांकन पर काम नहीं करेगी। यहां तक ​​कि एक विशिष्ट प्रश्न पूछना ("मुझे XYZ शीर्ष का रंग बताओ") किसी समस्या के समाधान को सत्यापित करने की कोशिश करने वाले व्यक्ति के लिए एक असहनीय समस्या बन जाती है। किसी विशेष वर्टेक्स के नाम को निर्दिष्ट करने के लिए आवश्यक डेटा की मात्रा उस वर्धक से अधिक है जो उसके पास उपलब्ध मेमोरी में स्टोर हो सकती है।

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

“सत्यापनकर्ता को सवालों का जवाब देने की आवश्यकता नहीं है। सत्यापनकर्ता इन प्रश्नों को स्वतंत्र रूप से तैयार करने और उन्हें जवाब देने के लिए समर्थकों को मजबूर करता है, ”जॉन राइट कहते हैं।

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

यदि दो प्रूफ़र्स पूरी तरह से स्वतंत्र रूप से इस तरह के प्रश्नों को तैयार करेंगे, तो उन्हें कनेक्टेड (सहसंबद्ध) कोने का चयन करने के लिए मजबूर करने के लिए कोई तंत्र नहीं होगा, ऐसा करने से सत्यापनकर्ता को अपने उत्तरों को सत्यापित करने की अनुमति मिलती है। लेकिन ऐसा सहसंबंध वास्तव में वही है जो क्वांटम उलझाव को प्राप्त कर सकता है।

थॉमस विडिक का कहना है कि वे गवाहों को व्यावहारिक रूप से सभी मामलों को संदर्भित करने के लिए पेचीदगियों का उपयोग करने जा रहे हैं। वैज्ञानिकों ने परीक्षकों को अपने स्वयं के प्रश्नों का चयन करने के लिए बनाया है।

इस प्रक्रिया के अंत में, प्रूफ़रों में से प्रत्येक एक वर्टेक्स रंग की रिपोर्ट करता है। सत्यापनकर्ता जांचता है कि ये अलग-अलग रंग हैं या नहीं। यदि ग्राफ़ वास्तव में "त्रि-रंग" है, तो परीक्षकों को कभी भी एक ही रंग की रिपोर्ट नहीं करनी चाहिए।

हेनरी यूएन के अनुसार, यदि ग्राफ़ "तीन-रंग" है, तो परीक्षक शोधकर्ता को यह समझाने में सक्षम होंगे कि यह वास्तव में ऐसा है।

जैसा कि यह निकला, यह सत्यापन प्रक्रिया गैर-स्थानीय खेल का एक और उदाहरण है। सबूत "जीत" यदि वे शोधकर्ता को आश्वस्त करते हैं कि उनका निर्णय सही है।

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

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

दूरगामी प्रभाव

अपने नए काम में, पांच वैज्ञानिकों ने साबित कर दिया कि भ्रमित गवाहों का "पूछताछ" एक बंद समस्या के समाधान सहित, अकल्पनीय समस्याओं के समाधान को सत्यापित करना संभव बनाता है।

हेनरी यूएन का कहना है कि इस प्रकार के मॉडल में अकल्पनीय सत्यापन क्षमताएं हैं।

लेकिन रुकने का काम असम्भव है। और यह तथ्य ड्राइविंग बल था जिसके कारण अंतिम प्रमाण मिला।

कल्पना कीजिए कि आपने कार्यक्रम को कुछ भ्रमित गवाहों को सौंप दिया है। आपने उनसे पूछा कि क्या यह कार्यक्रम कभी रुकेगा। आप किसी प्रकार के गैर-स्थानीय खेल के माध्यम से उनके उत्तरों को सत्यापित करने के लिए तैयार हैं। सबूत उनकी प्रतिक्रियाओं के समन्वय के आधार पर सवाल और "जीत" उत्पन्न करते हैं।

यदि कार्यक्रम वास्तव में बंद हो जाता है, तो समर्थकों को 100% मामलों में गेम जीतने में सक्षम होना चाहिए। यह एक ग्राफ के साथ एक उदाहरण के समान है - अगर यह वास्तव में "तीन-रंग" है, तो सजायाफ्ता सिद्धों को कभी भी जुड़े हुए कोने के लिए एक ही रंग की रिपोर्ट नहीं करनी चाहिए। यदि कार्यक्रम कभी भी बंद नहीं होता है, तो परीक्षकों को केवल 50% मामलों में ही जीतना चाहिए।

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

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

डेविड पेरेज़-गार्सिया का कहना है कि ऐसा एल्गोरिथ्म मौजूद नहीं हो सकता है, परिणामस्वरूप दो [मॉडल] अलग-अलग होने चाहिए।

नया काम यह साबित करता है कि समस्याओं का वर्ग जिनके समाधान को जटिल क्वांटम प्रूफरों की मदद से सत्यापित किया जा सकता है, एमआईपी * नामक एक वर्ग, उन समस्याओं के वर्ग के बराबर है जो स्टॉप समस्या - क्लास आरई से अधिक जटिल नहीं हैं। कागज के शीर्षक में इसका संक्षिप्त संकेत है: "MIP * = RE"।

इस प्रमाण के क्रम में कि दो जटिलता वर्ग समान हैं, वैज्ञानिकों ने Tsirelson परिकल्पना को झूठा साबित कर दिया, जो कि पिछले काम के लिए धन्यवाद, इसका अर्थ है कि कॉन परिकल्पना भी झूठी है।

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

मिगुएल नवाज़केज़ का कहना है कि यदि उन्होंने हेडिंग एमआईपी * = आरई के साथ एक लेख देखा, तो उन्होंने सोचा नहीं होगा कि उनके काम में कुछ सामान्य था। वह ज़िरलसन और कॉन की परिकल्पनाओं को जोड़ने वाले पहले के काम के सह-लेखक थे। उसके लिए, यह एक पूर्ण आश्चर्य था।

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

"उनके परिणाम बताते हैं कि यह संभव नहीं है," विलियम स्लॉफ़स्ट्रा ने कहा।

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

“व्यक्तिगत रूप से, मैं एक गणितज्ञ नहीं हूँ। आनंद नटराजन कहते हैं, "मैं कॉन परिकल्पना के शुरुआती प्रारूप को अच्छी तरह से नहीं समझता।"

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

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

"ऐसे कई काम हैं जिनके लेखक केवल सोच रहे हैं कि दो जटिल क्वांटम प्रमाणों का उपयोग करके सत्यापन प्रक्रिया की संभावनाएं क्या हैं। अब हम जानते हैं कि यह प्रक्रिया कितनी शक्तिशाली है। यह कहानी समाप्त हो गई है, ”आनंद नटराजन कहते हैं।

प्रिय पाठकों! सबूत MIP * = RE का अर्थ उस क्षेत्र के लिए है जिसमें आप काम करते हैं?