Quantum Byzantine agreement
बीजान्टिन दोष सहिष्णु प्रोटोकॉल एल्गोरिदम हैं जो वितरित एल्गोरिदम में मनमानी प्रकार की विफलताओं के लिए मजबूत हैं। बीजान्टिन समझौता प्रोटोकॉल इस कार्य का एक अनिवार्य हिस्सा है। बीजान्टिन प्रोटोकॉल का निरंतर-समय क्वांटम संस्करण, नीचे वर्णित है। परिचय बीजान्टिन समझौता प्रोटोकॉल वितरित कंप्यूटिंग में एक प्रोटोकॉल है। इसका नाम 1982 में लैम्पोर्ट, शोस्ताक और पीज़ द्वारा तैयार की गई एक समस्या से लिया गया है, जो अपने आप में एक ऐतिहासिक समस्या का संदर्भ है। बीजान्टिन सेना को डिवीजनों में विभाजित किया गया था जिसमें प्रत्येक डिवीजन का नेतृत्व निम्नलिखित गुणों के साथ एक जनरल द्वारा किया जाता थाः प्रत्येक जनरल या तो बीजान्टिन राज्य के प्रति वफादार या गद्दार होता है। सभी जनरल संदेश भेजकर और प्राप्त करके संवाद करते हैं। केवल दो आदेश हैंः हमला और पीछे हटना। सभी वफादार जनरलों को एक ही कार्य योजना पर सहमत होना चाहिएः हमला या पीछे हटना। खराब जनरलों के एक छोटे से रैखिक अंश से प्रोटोकॉल विफल नहीं होना चाहिए (एक अंश से कम)। (असंभवता परिणाम के प्रमाण के लिए देखें)। समस्या को आम तौर पर एक कमांडिंग जनरल और वफादार लेफ्टिनेंट के रूप में समान रूप से दोहराया जाता है, जिसमें जनरल या तो वफादार या गद्दार होता है और निम्नलिखित संपत्तियों वाले लेफ्टिनेंट के लिए भी ऐसा ही होता है। सभी वफादार लेफ्टिनेंट एक ही आदेश का पालन करते हैं। यदि कमांडिंग जनरल वफादार है, तो सभी वफादार लेफ्टिनेंट उसके द्वारा भेजे गए आदेश का पालन करते हैं। कमांडिंग जनरल सहित एक निश्चित रूप से कम अंश गद्दार हैं। बीजान्टिन विफलता और लचीलापन एक एल्गोरिथ्म या प्रोटोकॉल में विफलताओं को तीन मुख्य प्रकारों में वर्गीकृत किया जा सकता हैः एल्गोरिथ्म में एक और निष्पादन कदम उठाने में विफलताः इसे आमतौर पर "फेल स्टॉप" फॉल्ट के रूप में संदर्भित किया जाता है। सही ढंग से निष्पादित करने में यादृच्छिक विफलताः इसे "यादृच्छिक दोष" या "यादृच्छिक बीजान्टिन" दोष कहा जाता है। एक मनमानी विफलता जहां एल्गोरिथ्म चरणों को सही ढंग से निष्पादित करने में विफल रहता है (आमतौर पर पूरे एल्गोरिथ्म को विफल करने के लिए कुछ विरोधी द्वारा चतुराई से) जिसमें पिछले दो प्रकार के दोष भी शामिल हैं; इसे "बीजान्टिन फॉल्ट" कहा जाता है। एक बीजान्टिन लचीला या बीजान्टिन गलती सहिष्णु प्रोटोकॉल या एल्गोरिथ्म एक एल्गोरिथ्म है जो ऊपर उल्लिखित सभी प्रकार की विफलताओं के लिए मजबूत है। उदाहरण के लिए, कई अनावश्यक प्रोसेसर के साथ एक स्पेस शटल को देखते हुए, यदि प्रोसेसर परस्पर विरोधी डेटा देते हैं, तो किस प्रोसेसर या प्रोसेसर के सेट पर विश्वास किया जाना चाहिए? समाधान को बीजान्टिन दोष सहिष्णु प्रोटोकॉल के रूप में तैयार किया जा सकता है। एल्गोरिदम का रेखाचित्र हम यहाँ अतुल्यकालिक एल्गोरिदम का रेखाचित्र तैयार करेंगे एल्गोरिदम दो चरणों में काम करता हैः चरण 1 (संचार चरण): सभी संदेश इस दौर में भेजे और प्राप्त किए जाते हैं। एक सिक्का फ़्लिपिंग प्रोटोकॉल एक ऐसी प्रक्रिया है जो दो पक्षों ए और बी को अनुमति देती है जो एक दूसरे पर भरोसा नहीं करते हैं कि वे किसी विशेष वस्तु को जीतने के लिए एक सिक्का उछाल सकते हैं। दो प्रकार के सिक्का फ़्लिपिंग प्रोटोकॉल कमजोर सिक्का फ़्लिपिंग प्रोटोकॉल हैंः दो खिलाड़ी ए और बी शुरू में बिना किसी इनपुट के शुरू करते हैं और उन्हें कुछ मूल्य की गणना करनी होती है और किसी पर भी धोखाधड़ी का आरोप लगाने में सक्षम होना होता है। प्रोटोकॉल सफल होता है यदि ए और बी परिणाम पर सहमत होते हैं। परिणाम 0 को ए की जीत और 1 को बी की जीत के रूप में परिभाषित किया गया है। प्रोटोकॉल में निम्नलिखित गुण हैंः यदि दोनों खिलाड़ी ईमानदार हैं (वे प्रोटोकॉल का पालन करते हैं), तो वे प्रोटोकॉल के परिणाम पर सहमत होते हैं। यदि खिलाड़ियों में से एक ईमानदार है (यानी, दूसरा खिलाड़ी अपनी स्थानीय गणना में प्रोटोकॉल से मनमाने ढंग से विचलित हो सकता है), तो दूसरा पक्ष अधिक से अधिक संभावना के साथ जीतता है। दूसरे शब्दों में, यदि बी बेईमान है, तो, और यदि ए बेईमान है, तो। एक मजबूत सिक्का फ़्लिपिंग प्रोटोकॉलः एक मजबूत सिक्का फ़्लिपिंग प्रोटोकॉल में, लक्ष्य एक यादृच्छिक बिट का उत्पादन करना है जो किसी विशेष मूल्य 0 या 1 से दूर पक्षपाती है। स्पष्ट रूप से, पूर्वाग्रह के साथ कोई भी मजबूत सिक्का फ़्लिपिंग प्रोटोकॉल उसी पूर्वाग्रह के साथ कमजोर सिक्का फ़्लिपिंग की ओर ले जाता है। सत्यापन योग्य गुप्त साझाकरण एक सत्यापन योग्य गुप्त साझाकरण प्रोटोकॉलः ए (एन, के) गुप्त साझाकरण प्रोटोकॉल एन खिलाड़ियों के एक समूह को एक रहस्य साझा करने की अनुमति देता है, जैसे कि केवल के या अधिक खिलाड़ियों का एक समूह ही रहस्य की खोज कर सकता है। रहस्य साझा करने वाले खिलाड़ी (गुप्त टुकड़ों को वितरित करने वाले) को आमतौर पर व्यापारी के रूप में जाना जाता है। एक सत्यापन योग्य गुप्त साझाकरण प्रोटोकॉल एक बुनियादी गुप्त साझाकरण प्रोटोकॉल से अलग होता है जिसमें खिलाड़ी यह सत्यापित कर सकते हैं कि उनके शेयर एक दुर्भावनापूर्ण व्यापारी की उपस्थिति में भी सुसंगत हैं। खिलाड़ी राउंड 1 के लिए फेल-स्टॉप प्रोटोकॉल प्रोटोकॉल क्वांटम सिक्का फ़्लिप क्यूबिट्स पर जीएचजेड स्थिति उत्पन्न करता है और एक भाग रखते हुए th क्यूबिट को th खिलाड़ी को भेजता है क्यूडिट पर स्थिति उत्पन्न करें (कई क्यूबिट्स के अनुरूप क्वांटम-कंप्यूटिंग घटक), 1 और 1 के बीच की संख्याओं का एक समान सुपरपोजिशन। सभी खिलाड़ियों के बीच क्यूडिट वितरित करें सभी खिलाड़ियों से क्वांटम संदेश प्राप्त करें और अगले संचार दौर की प्रतीक्षा करें, इस प्रकार विरोधी को यह चुनने के लिए मजबूर करें कि कौन से संदेश पारित किए गए थे। राउंड 2: राउंड I में प्राप्त सभी क्यूबिट्स को मापें (मानक आधार में)। दौर के "नेता" के रूप में उच्चतम नेता मूल्य (मनमाने ढंग से टूट गए संबंध) वाले खिलाड़ी का चयन करें। नेता के सिक्के को मानक आधार में मापें। क्वांटमकॉइनफ्लिप प्रोटोकॉलः = नेता के सिक्के के माप परिणाम का आउटपुट निर्धारित करें। बीजान्टिन प्रोटोकॉल एक यादृच्छिक सिक्का उत्पन्न करने के लिए प्रत्येक खिलाड़ी को [0, n-1] की सीमा में एक पूर्णांक निर्धारित करें और प्रत्येक खिलाड़ी को अपनी यादृच्छिक आईडी चुनने की अनुमति नहीं है क्योंकि प्रत्येक खिलाड़ी प्रत्येक दूसरे खिलाड़ी के लिए एक यादृच्छिक संख्या का चयन करता है और इसे एक सत्यापन योग्य गुप्त साझाकरण योजना का उपयोग करके वितरित करता है। इस चरण के अंत में खिलाड़ी इस बात पर सहमत होते हैं कि कौन से रहस्यों को ठीक से साझा किया गया था, फिर रहस्य खोले जाते हैं और प्रत्येक खिलाड़ी को मूल्य सौंपा जाता है इसके लिए निजी सूचना चैनलों की आवश्यकता होती है इसलिए हम यादृच्छिक रहस्यों को सुपरपोजिशन द्वारा प्रतिस्थापित करते हैं। जिसमें राज्य को क्वांटम सत्यापन योग्य गुप्त साझाकरण प्रोटोकॉल (क्यू. वी. एस. एस.) का उपयोग करके कूटबद्ध किया जाता है। हम राज्य को विभाजित नहीं कर सकते क्योंकि खराब खिलाड़ी राज्य को ध्वस्त कर सकते हैं। खराब खिलाड़ियों को ऐसा करने से रोकने के लिए हम क्वांटम वेरिफिएबल सीक्रेट शेयरिंग (क्यू. वी. एस. एस.) का उपयोग करके राज्य को कूटबद्ध करते हैं और प्रत्येक खिलाड़ी को गुप्त का अपना हिस्सा भेजते हैं। यहाँ फिर से सत्यापन के लिए बीजान्टिन समझौते की आवश्यकता होती है, लेकिन समझौते को ग्रेड-कास्ट प्रोटोकॉल द्वारा प्रतिस्थापित करना पर्याप्त है। ग्रेड-कास्ट प्रोटोकॉल एक ग्रेड-कास्ट प्रोटोकॉल में निम्नलिखित गुण होते हैं जो अनौपचारिक रूप से परिभाषाओं का उपयोग करते हैं, एक श्रेणीबद्ध प्रसारण प्रोटोकॉल एक निर्दिष्ट खिलाड़ी के साथ एक प्रोटोकॉल है जिसे "डीलर" (जो प्रसारण करता है) कहा जाता है जैसे किः यदि डीलर अच्छा है, तो सभी खिलाड़ियों को एक ही संदेश मिलता है। भले ही विक्रेता खराब हो, अगर कोई अच्छा खिलाड़ी संदेश को स्वीकार करता है, तो सभी अच्छे खिलाड़ियों को एक ही संदेश मिलता है (लेकिन वे इसे स्वीकार कर सकते हैं या नहीं भी कर सकते हैं)। एक प्रोटोकॉल पी को श्रेणीबद्ध प्रसारण प्राप्त करने के लिए कहा जाता है, यदि प्रोटोकॉल की शुरुआत में, एक नामित खिलाड़ी डी (जिसे डीलर कहा जाता है) एक मान वी रखता है, और प्रोटोकॉल के अंत में, प्रत्येक खिलाड़ी एक जोड़ी को इस तरह से आउटपुट करता है कि निम्नलिखित गुण हैंः यदि डी ईमानदार है, तो प्रत्येक ईमानदार खिलाड़ी के लिए = वी और = 2। किसी भी दो ईमानदार खिलाड़ियों के लिए और। (निरंतरता) किसी भी दो ईमानदार खिलाड़ियों के लिए और, यदि और, तो। क्यू. वी. एस. एस. प्रोटोकॉल के सत्यापन चरण के लिए यह गारंटी है कि एक अच्छे डीलर के लिए सही स्थिति को कूटबद्ध किया जाएगा, और किसी भी, संभवतः दोषपूर्ण डीलर के लिए, वसूली चरण के दौरान कुछ विशेष राज्य की वसूली की जाएगी। हम ध्यान देते हैं कि हमारे बीजान्टिन क्वांटम सिक्का फ़्लिप प्रोटोकॉल के उद्देश्य के लिए पुनर्प्राप्ति चरण बहुत सरल है। प्रत्येक खिलाड़ी क्यू. वी. एस. एस. के अपने हिस्से को मापता है और अन्य सभी खिलाड़ियों को शास्त्रीय मूल्य भेजता है। सत्यापन चरण, उच्च संभावना के साथ, गारंटी देता है कि दोषपूर्ण खिलाड़ियों की उपस्थिति में सभी अच्छे खिलाड़ी समान शास्त्रीय मूल्य प्राप्त करेंगे (जो वही मूल्य है जो एन्कोडेड स्थिति के प्रत्यक्ष माप से होगा)। टिप्पणी 2007 में, बीजान्टिन समझौते के लिए एक क्वांटम प्रोटोकॉल को प्रायोगिक रूप से चार-फोटॉन ध्रुवीकरण-उलझी हुई स्थिति का उपयोग करके प्रदर्शित किया गया था। इससे पता चलता है कि शास्त्रीय बीजान्टिन समझौते प्रोटोकॉल का क्वांटम कार्यान्वयन वास्तव में संभव है। संदर्भ क्वांटम सूचना विज्ञान क्रिप्टोग्राफी वितरित कंप्यूटिंग समस्याएं दोष सहिष्णुता इंजीनियरिंग विफलताएँ गणना का सिद्धांत