क्वांटम बीजान्टिन अनुबंध

बीजान्टिन दोष सहिष्णुता प्रोटोकॉल (कंप्यूटिंग) एल्गोरिदम हैं जो वितरित एल्गोरिदम में यादृच्छिक प्रकार की विफलताओं के लिए दृढ हैं। अतः बीजान्टिन समझौता प्रोटोकॉल इस कार्य का अनिवार्य भाग है। बीजान्टिन प्रोटोकॉल का निरंतर-समय क्वांटम संस्करण, नीचे वर्णित है।

परिचय

बीजान्टिन दोष सहिष्णुता संचार प्रोटोकॉल वितरित कंप्यूटिंग में प्रोटोकॉल है। इसका नाम 1982 में लैमपोर्ट, शोस्टाक और पीज़ द्वारा तैयार की गई समस्या से लिया गया है। जो स्वयं ऐतिहासिक समस्या का संदर्भ है। इस प्रकार से बीजान्टिन सेना को संभागों में विभाजित किया गया था, प्रत्येक संभाग का नेतृत्व निम्नलिखित गुणों वाले जनरल द्वारा किया जाता था:

• प्रत्येक जनरल या तो बीजान्टिन के प्रति निष्ठावान है या विश्वासघाती है।
• सभी जनरल संदेश भेजकर और प्राप्त करके संवाद करते हैं।
• मात्र दो आदेश हैं: आक्रमण और पीछे हटना।
• सभी निष्ठावान जनरलों को ही कार्य योजना पर सहमत होना चाहिए: आक्षेप करना या पीछे हटना।
• निकृष्ट जनरलों के छोटे से रैखिक अंश के कारण प्रोटोकॉल विफल नहीं होना चाहिए (${\tfrac {1}{3}}$ से अंश कम)।

(असंभव परिणाम के प्रमाण के लिए देखें) समस्या को सामान्यतः कमान जनरल और निष्ठावान लेफ्टिनेंट के रूप में समान रूप से दोहराया जाता है, अतः जिसमें जनरल या तो निष्ठावान होता है या विश्वासघाती होता है और निम्नलिखित गुणों वाले लेफ्टिनेंट के लिए भी यही बात समान होती है।

• सभी निष्ठावान लेफ्टिनेंट ही आदेश का पालन करते हैं।
• यदि कमान जनरल निष्ठावान है, तो सभी निष्ठावान लेफ्टिनेंट उसके द्वारा भेजे गए आदेश का पालन करते हैं।
• कमान जनरल सहित ${\tfrac {1}{3}}$ से निश्चित कम अंश वाले विश्वासघाती हैं।

बीजान्टिन विफलता और नम्यता

इस प्रकार से कलन विधि या संचार प्रोटोकॉल में विफलताओं को तीन मुख्य प्रकारों में वर्गीकृत किया जा सकता है:

1. एल्गोरिदम में और निष्पादन चरण उठाने में विफलता: इसे सामान्यतः "विफल अवरोध" दोष के रूप में जाना जाता है।
2. ठीक रूप से निष्पादित करने में यादृच्छिक विफलता: इसे यादृच्छिक त्रुटि या यादृच्छिक बीजान्टिन त्रुटि कहा जाता है।
3. एक यादृच्छिक विफलता जहां एल्गोरिदम चरणों को ठीक रूप से निष्पादित करने में विफल रहता है (सामान्यतः कुछ विरोधियों द्वारा पूरे एल्गोरिदम को विफल करने के लिए चालाक विधि से) जिसमें पिछले दो प्रकार के दोष भी सम्मिलित होते हैं; इसे बीजान्टिन दोष कहा जाता है।

अतः बीजान्टिन नम्यता या बीजान्टिन दोष सहिष्णुता प्रोटोकॉल या एल्गोरिदम एल्गोरिदम है जो ऊपर उल्लिखित सभी प्रकार की विफलताओं के लिए दृढ है। उदाहरण के लिए, कई निरर्थक प्रोसेसर वाले अंतरिक्ष शटल को देखते हुए, यदि प्रोसेसर परस्पर विरोधी डेटा देते हैं, तो कौन से प्रोसेसर या प्रोसेसर के समूह पर विश्वास किया जाना चाहिए? हल को बीजान्टिन दोष सहिष्णुता प्रोटोकॉल के रूप में तैयार किया जा सकता है।

एल्गोरिदम का स्केच

इस प्रकार से हम यहां अतुल्यकाली एल्गोरिदम का स्केच बनाएंगे एल्गोरिदम दो चरणों में कार्य करता है:

• चरण 1 (संचार चरण):

इस चक्कर में सभी संदेश भेजे और प्राप्त किए जाते हैं।

सिक्का उछालने का प्रोटोकॉल ऐसी प्रक्रिया है जो दो पक्षों A और B को, जो एक-दूसरे पर विश्वास नहीं करते हैं, किसी विशेष वस्तु को जीतने के लिए सिक्का उछालने की अनुमति देती है।

इस प्रकार से सिक्का उछालने के प्रोटोकॉल दो प्रकार के होते हैं

• क्वांटम सिक्का फ़्लिपिंग प्रोटोकॉल: दो खिलाड़ी A और B प्रारंभ में बिना किसी इनपुट के प्रारंभ करते हैं और उन्हें कुछ मान $c_{A},c_{B}\in [0,1]$ की गणना करनी होती है और किसी पर भी छल का आरोप लगाने में सक्षम होना होता है। अतः यदि A और B परिणाम पर सहमत हों तो प्रोटोकॉल सफल होता है। परिणाम 0 को A की जीत और 1 को B की जीत के रूप में परिभाषित किया गया है। इस प्रकार से प्रोटोकॉल में निम्नलिखित गुण हैं:
  • यदि दोनों खिलाड़ी ईमानदार हैं (वे प्रोटोकॉल का पालन करते हैं), तो वे $a,b\in \{0,1\}$ $c_{A}=c_{B}$ के साथ प्रोटोकॉल $Pr(c_{A}=c_{B}=b)={\tfrac {1}{2}}$ के परिणाम पर सहमत होते हैं।
  • यदि खिलाड़ियों में से एक ईमानदार है (अर्थात, दूसरा खिलाड़ी अपने स्थानीय गणना में प्रोटोकॉल से यादृच्छिक रूप से विचलन कर सकता है), तो दूसरा पक्ष अधिकतम ${\tfrac {1}{2}}+\epsilon$ की संभावना के साथ जीतता है। दूसरे शब्दों में, यदि B कुटिल है, तो $Pr(c_{A}=c_{B}=1)\leq {\tfrac {1}{2}}+\epsilon$, और यदि A कुटिल है, तो $Pr(c_{A}=c_{B}=0)\leq {\tfrac {1}{2}}+\epsilon$.
• एक क्वांटम सिक्का फ़्लिपिंग: दृढ सिक्का फ़्लिपिंग प्रोटोकॉल में, लक्ष्य इसके अतिरिक्त यादृच्छिक बिट उत्पन्न करना है जो किसी विशेष मान 0 या 1 से दूर पक्षपाती है। स्पष्ट रूप से, पूर्वाग्रह $\epsilon$ के साथ कोई भी दृढ सिक्का फ़्लिपिंग प्रोटोकॉल उसी पूर्वाग्रह के साथ दुर्बल सिक्का फ़्लिपिंग की ओर ले जाता है।

सत्यापन योग्य गुप्त साझाकरण

• एक सत्यापन योग्य गुप्त साझाकरण प्रोटोकॉल: A (n,k) गुप्त साझाकरण प्रोटोकॉल n खिलाड़ियों के समूह को गुप्त साझा करने की अनुमति देता है, जैसे कि मात्र के या अधिक खिलाड़ियों का कोरम ही गुप्त की खोज कर सकता है। अतः गुप्त को साझा करने (गुप्त टुकड़ों को वितरित करने) वाले खिलाड़ी को सामान्यतः विक्रेता के रूप में जाना जाता है। सत्यापन योग्य गुप्त साझाकरण प्रोटोकॉल मूलभूत गुप्त साझाकरण प्रोटोकॉल से भिन्न होता है जिसमें खिलाड़ी यह सत्यापित कर सकते हैं कि दुर्भावनापूर्ण विक्रेता की उपस्थिति में भी उनके शेयर सुसंगत हैं।

फेल-स्टॉप प्रोटोकॉल

खिलाड़ी $P_{i}$ के लिए प्रोटोकॉल क्वांटम सिक्का फ्लिप

1. चक्कर 1 GHZ स्थिति $|\mathrm {Coin} _{i}\rangle ={\tfrac {1}{\sqrt {2}}}|0,0,\ldots ,0\rangle +{\tfrac {1}{\sqrt {2}}}|1,1,\ldots ,1\rangle$उत्पन्न करता है $n$ क्युबित और एक भाग रखते हुए $k$वें क्युबित को $k$वें खिलाड़ी को भेजें
2. $n$ क्युबि (एकाधिक क्युबित के अनुरूप क्वांटम-कंप्यूटिंग घटक) पर स्थिति $|\mathrm {Leader} _{i}\rangle ={\tfrac {1}{n^{3/2}}}\sum \nolimits _{a=1}^{n^{3}}|a,a,\ldots ,a\rangle$ पउत्पन्न करें, 1 और $n^{3}$ के बीच संख्याओं का एक समान सुपरपोजिशन। सभी खिलाड़ियों के बीच $n$ वितरित करें
3. सभी खिलाड़ियों से क्वांटम संदेश प्राप्त करें और अगले संचार चक्कर की प्रतीक्षा करें, इस प्रकार प्रतिद्वंद्वी को यह चुनने के लिए प्रणोदन किया जाए कि कौन से संदेश पारित किए गए थे।
4. चक्कर 2: चक्कर I में प्राप्त सभी $\mathrm {Leader} _{j}$ क्युबित को मापें (मानक आधार में)। अतः चक्कर के "लीडर" के रूप में उच्चतम लीडर मान (यादृच्छिक रूप से टूटे हुए संबंध) वाले खिलाड़ी का चयन करें।
5. क्वांटमकॉइनफ्लिप प्रोटोकॉल का आउटपुट समूहित करें: लीडर के सिक्के का $v_{i}$ = माप परिणाम।

बीजान्टिन प्रोटोकॉल

एक यादृच्छिक सिक्का उत्पन्न करने के लिए प्रत्येक खिलाड़ी को [0,n-1] श्रेणी में एक पूर्णांक निर्दिष्ट करें और प्रत्येक खिलाड़ी को अपनी स्वयं की यादृच्छिक आईडी चुनने की अनुमति नहीं है क्योंकि प्रत्येक खिलाड़ी $P_{k}$ प्रत्येक दुसरे खिलाड़ी $s{_{k}^{i}}$ के लिए एक यादृच्छिक संख्या $P_{i}$ का चयन करता है और इसे एक सत्यापन योग्य गुप्त साझाकरण योजना का उपयोग करके वितरित करता है।

इस प्रकार से इस चरण के अंत में खिलाड़ी इस बात पर सहमत होते हैं कि कौन से गुप्त ठीक से साझा किए गए थे, फिर गुप्त खोले जाते हैं और प्रत्येक खिलाड़ी $P_{i}$ को मान

$s_{i}=\sum \,{s_{k}^{i}}{\text{for all secrets properly shared}}\mod n$ निर्दिष्ट किया जाता है

अतः इसके लिए निजी सूचना चैनलों की आवश्यकता होती है इसलिए हम यादृच्छिक गोपनीयता को अधिस्थापन $|\phi \rangle ={\tfrac {1}{\sqrt {n}}}\sum \nolimits _{a=0}^{n-1}|a\rangle$ से बदल देते हैं। जिसमें स्थिति को क्वांटम सत्यापन योग्य गुप्त साझाकरण प्रोटोकॉल (क्यूवीएसएस) का उपयोग करके एन्कोड किया गया है। हम स्थिति $|\phi ,\phi ,\ldots \phi \rangle$ को वितरित नहीं कर सकते क्योंकि निकृष्ट खिलाड़ी स्थिति को ध्वस्त कर सकते हैं। निकृष्ट खिलाड़ियों को ऐसा करने से रोकने के लिए हम क्वांटम सत्यापन योग्य गुप्त साझाकरण (क्यूवीएसएस) का उपयोग करके स्थिति को एन्कोड करते हैं और प्रत्येक खिलाड़ी को उनके भाग का गुप्त भेजते हैं। यहां फिर से सत्यापन के लिए बीजान्टिन समझौते की आवश्यकता है, परन्तु श्रेणी-विक्षेप प्रोटोकॉल द्वारा समझौते को प्रतिस्थापित करना पर्याप्त है।

श्रेणी-विक्षेप प्रोटोकॉल

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

1. यद्यपि विक्रेता ठीक है तो सभी खिलाड़ियों को जैसा संदेश मिलता है.
2. यद्यपि विक्रेता निकृष्ट हो, यद्यपि कोई ठीक खिलाड़ी संदेश स्वीकार करता है, तो सभी ठीक खिलाड़ियों को ही संदेश मिलता है (परन्तु वे इसे स्वीकार कर भी सकते हैं और नहीं भी)।

इस प्रकार से एक प्रोटोकॉल P को वर्गीकृत प्रसारण प्राप्त करने के लिए कहा जाता है, यदि प्रोटोकॉल की प्रारम्भ में, एक निर्दिष्ट खिलाड़ी D (डीलर कहा जाता है) एक मान v रखता है, और प्रोटोकॉल के अंत में, प्रत्येक खिलाड़ी $P_{i}$ एक युग्म $(\mathrm {value} _{i},\mathrm {confidence} _{i})$ आउटपुट करता है जैसे कि निम्नलिखित गुण धारण करते हैं:

$(\forall i,\mathrm {confidence} _{i}\in \{0,1,2\})$

1. यदि D ईमानदार है, तो प्रत्येक ईमानदार खिलाड़ी $P_{i}$ के लिए $\mathrm {value} _{i}$ = v और $\mathrm {confidence} _{i}$ = 2।
2. किन्हीं दो ईमानदार खिलाड़ियों के लिए $P_{i}$ और $P_{j},$ $\vert \mathrm {confidence} _{i}-\mathrm {confidence} _{j}\vert \leq 1$.
3. (संगति) किन्हीं दो ईमानदार खिलाड़ियों के लिए $P_{i}$ और $P_{j}$, यदि $\mathrm {confidence} _{i}>0$ और $\mathrm {confidence} _{j}>0$, तो $\mathrm {value} _{i}=\mathrm {value} _{j}$।

$t<{\tfrac {n}{4}}$ के लिए क्यूवीएसएस प्रोटोकॉल का सत्यापन चरण यह गारंटी देता है कि ठीक विक्रेता के लिए उचित स्थिति को एन्कोड किया जाएगा, और किसी भी, संभवतः दोषपूर्ण विक्रेता के लिए, पुनर्प्राप्ति चरण के समय कुछ विशेष स्थिति को पुनर्प्राप्त किया जाएगा। हम ध्यान दें कि हमारे बीजान्टिन क्वांटम सिक्का फ्लिप प्रोटोकॉल के प्रयोजन के लिए पुनर्प्राप्ति चरण बहुत सरल है। प्रत्येक खिलाड़ी क्यूवीएसएस के अपने भाग को मापता है और अन्य सभी खिलाड़ियों को उत्कृष्ट मान भेजता है। सत्यापन चरण उच्च संभावना के साथ गारंटी देता है कि $t<{\tfrac {n}{4}}$ तक के दोषपूर्ण खिलाड़ियों की उपस्थिति में सभी ठीक खिलाड़ी समान उत्कृष्ट मान पुनर्प्राप्त करेंगे (जो वही मान है जो एन्कोडेड स्थिति के प्रत्यक्ष माप के परिणामस्वरूप होगा)।

टिप्पणियाँ

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