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

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

परिचय

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

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

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

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

बीजान्टिन विफलता और लचीलापन

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

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

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

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

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

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

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

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

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

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

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

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

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

खिलाड़ी के लिए प्रोटोकॉल क्वांटम सिक्का फ्लिप $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$ qubits और भेजें $k$वें qubit को $k$वें खिलाड़ी एक भाग रखता है
2. राज्य उत्पन्न करें $|\mathrm {Leader} _{i}\rangle ={\tfrac {1}{n^{3/2}}}\sum \nolimits _{a=1}^{n^{3}}|a,a,\ldots ,a\rangle$ पर $n$ क्यूडिट्स (क्वांटम-कंप्यूटिंग घटक जो कई क्वैबिट से सुसंगत हैं), 1 और के बीच की संख्याओं का एक समान सुपरपोजिशन $n^{3}$. वितरित करें $n$ सभी खिलाड़ियों के बीच बातचीत# सभी खिलाड़ियों से क्वांटम संदेश प्राप्त करें और अगले संचार दौर की प्रतीक्षा करें, इस प्रकार प्रतिद्वंद्वी को यह चुनने के लिए मजबूर किया जाए कि कौन से संदेश पारित किए गए थे।
3. राउंड 2: सभी को मापें (मानक आधार में)। $\mathrm {Leader} _{j}$ राउंड I में प्राप्त क्विबिट्स। राउंड के लीडर के रूप में उच्चतम लीडर वैल्यू (मनमाने ढंग से टूटे हुए संबंध) वाले खिलाड़ी का चयन करें। मानक आधार में नेता के सिक्के को मापें।
4. क्वांटमकॉइनफ्लिप प्रोटोकॉल का आउटपुट सेट करें: $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_{i}$ एक जोड़ी आउटपुट करता है $(\mathrm {value} _{i},\mathrm {confidence} _{i})$ जैसे कि निम्नलिखित गुण मौजूद हों:

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

1. यदि D ईमानदार है, तो $\mathrm {value} _{i}$ = वी और $\mathrm {confidence} _{i}$ = प्रत्येक ईमानदार खिलाड़ी के लिए 2 $P_{i}$.
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}}$ क्यूवीएसएस प्रोटोकॉल का सत्यापन चरण यह गारंटी देता है कि एक अच्छे डीलर के लिए सही स्थिति को एन्कोड किया जाएगा, और किसी भी, संभवतः दोषपूर्ण डीलर के लिए, पुनर्प्राप्ति चरण के दौरान कुछ विशेष स्थिति को पुनर्प्राप्त किया जाएगा। हम ध्यान दें कि हमारे बीजान्टिन क्वांटम सिक्का फ्लिप प्रोटोकॉल के प्रयोजन के लिए पुनर्प्राप्ति चरण बहुत सरल है। प्रत्येक खिलाड़ी QVSS के अपने हिस्से को मापता है और अन्य सभी खिलाड़ियों को शास्त्रीय मूल्य भेजता है। सत्यापन चरण, उच्च संभावना के साथ, की उपस्थिति की गारंटी देता है $t<{\tfrac {n}{4}}$ दोषपूर्ण खिलाड़ी, सभी अच्छे खिलाड़ी समान शास्त्रीय मूल्य पुनर्प्राप्त करेंगे (जो वही मूल्य है जो एन्कोडेड स्थिति के प्रत्यक्ष माप के परिणामस्वरूप होगा)।

टिप्पणियाँ

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