Quantum Byzantine agreement
બીઝેન્ટાઇન ફોલ્ટ ટોલરન્ટ પ્રોટોકોલ એ એલ્ગોરિધમ્સ છે જે ડિસ્ટ્રિબ્યુટેડ એલ્ગોરિધમ્સમાં મનસ્વી પ્રકારની નિષ્ફળતાઓ માટે મજબૂત છે. બીઝેન્ટાઇન કરાર પ્રોટોકોલ આ કાર્યનો એક આવશ્યક ભાગ છે. બીઝેન્ટાઇન પ્રોટોકોલનું સતત-સમયનું ક્વોન્ટમ સંસ્કરણ, નીચે વર્ણવેલ છે. પરિચય બીઝેન્ટાઇન કરાર પ્રોટોકોલ એ ડિસ્ટ્રિબ્યુટેડ કમ્પ્યુટિંગમાં એક પ્રોટોકોલ છે. તેનું નામ 1982માં લેમ્પોર્ટ, શોસ્તાક અને પીઝ દ્વારા ઘડવામાં આવેલી સમસ્યા પરથી લેવામાં આવ્યું છે, જે પોતે એક ઐતિહાસિક સમસ્યાનો સંદર્ભ છે. બીઝેન્ટાઇન સેનાને વિભાગોમાં વહેંચવામાં આવી હતી, જેમાં દરેક વિભાગનું નેતૃત્વ નીચેના ગુણધર્મો ધરાવતા જનરલ દ્વારા કરવામાં આવતું હતુંઃ દરેક જનરલ કાં તો બીઝેન્ટાઇન રાજ્ય પ્રત્યે વફાદાર અથવા દેશદ્રોહી હોય છે. બધા જનરલો સંદેશા મોકલીને અને પ્રાપ્ત કરીને વાતચીત કરે છે. માત્ર બે આદેશો છેઃ હુમલો અને પીછેહઠ. બધા વફાદાર સેનાપતિઓએ કાર્યવાહીની એક જ યોજના પર સંમત થવું જોઈએઃ હુમલો અથવા પીછેહઠ. ખરાબ જનરલોના નાના રેખીય અપૂર્ણાંકથી પ્રોટોકોલ નિષ્ફળ ન થવું જોઈએ (અપૂર્ણાંક કરતાં ઓછું). (અશક્યતા પરિણામના પુરાવા માટે જુઓ). આ સમસ્યાને સામાન્ય રીતે કમાન્ડિંગ જનરલ અને વફાદાર લેફ્ટનન્ટના રૂપમાં પુનરાવર્તિત કરવામાં આવે છે, જેમાં જનરલ વફાદાર અથવા દેશદ્રોહી હોય છે અને નીચેની મિલકતો ધરાવતા લેફ્ટનન્ટ માટે સમાન હોય છે. બધા વફાદાર લેફ્ટનન્ટ એક જ હુકમનું પાલન કરે છે. જો કમાન્ડિંગ જનરલ વફાદાર હોય, તો બધા વફાદાર લેફ્ટનન્ટ તે મોકલેલા આદેશનું પાલન કરે છે. કમાન્ડિંગ જનરલ સહિત સખત રીતે ઓછા અપૂર્ણાંક દેશદ્રોહી છે. બીઝેન્ટાઇન નિષ્ફળતા અને સ્થિતિસ્થાપકતા અલ્ગોરિધમ અથવા પ્રોટોકોલમાં નિષ્ફળતાઓને ત્રણ મુખ્ય પ્રકારોમાં વર્ગીકૃત કરી શકાય છેઃ અલ્ગોરિધમમાં બીજું અમલ પગલું લેવામાં નિષ્ફળતાઃ આને સામાન્ય રીતે "ફેલ સ્ટોપ" ફોલ્ટ તરીકે ઓળખવામાં આવે છે. યોગ્ય રીતે ચલાવવામાં રેન્ડમ નિષ્ફળતાઃ આને "રેન્ડમ ફોલ્ટ" અથવા "રેન્ડમ બીઝેન્ટાઇન" ફોલ્ટ કહેવામાં આવે છે. એક મનસ્વી નિષ્ફળતા જ્યાં અલ્ગોરિધમ પગલાંઓને યોગ્ય રીતે ચલાવવામાં નિષ્ફળ જાય છે (સામાન્ય રીતે કેટલાક વિરોધીઓ દ્વારા આખા અલ્ગોરિધમને નિષ્ફળ બનાવવા માટે ચતુરાઈથી) જેમાં અગાઉના બે પ્રકારના ખામીઓનો પણ સમાવેશ થાય છે; આને "બીઝેન્ટાઇન ફોલ્ટ" કહેવામાં આવે છે. બીઝેન્ટાઇન સ્થિતિસ્થાપક અથવા બીઝેન્ટાઇન ફોલ્ટ સહિષ્ણુ પ્રોટોકોલ અથવા અલ્ગોરિધમ એ એક અલ્ગોરિધમ છે જે ઉપર ઉલ્લેખિત તમામ પ્રકારની નિષ્ફળતાઓ માટે મજબૂત છે. ઉદાહરણ તરીકે, બહુવિધ બિનજરૂરી પ્રોસેસરો સાથે સ્પેસ શટલ આપવામાં આવે તો, જો પ્રોસેસરો વિરોધાભાસી ડેટા આપે છે, તો કયા પ્રોસેસરો અથવા પ્રોસેસરોના સમૂહો પર વિશ્વાસ કરવો જોઈએ? ઉકેલને બીઝેન્ટાઇન ફોલ્ટ ટોલરન્ટ પ્રોટોકોલ તરીકે ઘડી શકાય છે. અલ્ગોરિધમનો સ્કેચ આપણે અહીં એસિંક્રોનસ અલ્ગોરિધમનો સ્કેચ બનાવીશું અલ્ગોરિધમ બે તબક્કામાં કામ કરે છેઃ તબક્કો 1 (સંચાર તબક્કો): આ રાઉન્ડમાં તમામ સંદેશાઓ મોકલવામાં આવે છે અને પ્રાપ્ત થાય છે. સિક્કો પલટી નાંખવાનો પ્રોટોકોલ એ એક એવી પ્રક્રિયા છે જે બે પક્ષો એ અને બી કે જેઓ એકબીજા પર વિશ્વાસ કરતા નથી, તેમને કોઈ ચોક્કસ વસ્તુ જીતવા માટે સિક્કો ફેંકવાની મંજૂરી આપે છે. બે પ્રકારના સિક્કા પલટણ પ્રોટોકોલ નબળા સિક્કા પલટણ પ્રોટોકોલ છેઃ બે ખેલાડીઓ એ અને બી શરૂઆતમાં કોઈ ઇનપુટ્સ સાથે શરૂ થાય છે અને તેઓએ અમુક મૂલ્યની ગણતરી કરવી પડે છે અને કોઈપણ પર છેતરપિંડીનો આરોપ મૂકવા સક્ષમ બનવું પડે છે. જો A અને B પરિણામ પર સંમત થાય તો પ્રોટોકોલ સફળ થાય છે. પરિણામ 0 ને એ વિજેતા અને 1 ને બી વિજેતા તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. પ્રોટોકોલમાં નીચેના ગુણધર્મો છેઃ જો બંને ખેલાડીઓ પ્રમાણિક હોય (તેઓ પ્રોટોકોલનું પાલન કરે છે), તો તેઓ પ્રોટોકોલના પરિણામ માટે સાથે સંમત થાય છે. જો એક ખેલાડી પ્રમાણિક હોય (એટલે કે, અન્ય ખેલાડી તેની અથવા તેણીની સ્થાનિક ગણતરીમાં પ્રોટોકોલથી મનસ્વી રીતે વિચલિત થઈ શકે છે), તો પછી બીજો પક્ષ મહત્તમ સંભાવના સાથે જીતે છે. બીજા શબ્દોમાં કહીએ તો, જો બી અપ્રમાણિક છે, તો પછી, અને જો એ અપ્રમાણિક છે, તો પછી. એક મજબૂત સિક્કો ફ્લિપિંગ પ્રોટોકોલઃ મજબૂત સિક્કો ફ્લિપિંગ પ્રોટોકોલમાં, ધ્યેય તેના બદલે રેન્ડમ બીટ ઉત્પન્ન કરવાનો છે જે કોઈપણ ચોક્કસ મૂલ્ય 0 અથવા 1 થી દૂર છે. સ્પષ્ટપણે, પૂર્વગ્રહ સાથેનો કોઈપણ મજબૂત સિક્કો પલટી મારવાનો પ્રોટોકોલ સમાન પૂર્વગ્રહ સાથે નબળા સિક્કા પલટી મારવા તરફ દોરી જાય છે. ચકાસી શકાય તેવી ગુપ્ત વહેંચણી એક ચકાસી શકાય તેવી ગુપ્ત વહેંચણી પ્રોટોકોલઃ એ (એન, કે) ગુપ્ત વહેંચણી પ્રોટોકોલ એન ખેલાડીઓના સમૂહને ગુપ્ત શેર કરવાની મંજૂરી આપે છે, જેમ કે માત્ર કે અથવા વધુ ખેલાડીઓની કોરમ જ રહસ્ય શોધી શકે છે. રહસ્યની વહેંચણી (ગુપ્ત ટુકડાઓનું વિતરણ) કરનાર ખેલાડીને સામાન્ય રીતે વેપારી તરીકે ઓળખવામાં આવે છે. ચકાસી શકાય તેવો ગુપ્ત વહેંચણી પ્રોટોકોલ મૂળભૂત ગુપ્ત વહેંચણી પ્રોટોકોલથી અલગ છે જેમાં ખેલાડીઓ દૂષિત વેપારીની હાજરીમાં પણ તેમના શેર સુસંગત છે કે કેમ તે ચકાસી શકે છે. ખેલાડી રાઉન્ડ 1 માટે ફેલ-સ્ટોપ પ્રોટોકોલ ક્વોન્ટમ સિક્કો ફ્લિપ ક્યુબિટ્સ પર GHZ સ્થિતિ પેદા કરે છે અને એક ભાગ રાખીને th ખેલાડીને th ક્યુબિટ મોકલે છે. તમામ ખેલાડીઓ વચ્ચે કુદિટ્સનું વિતરણ કરો તમામ ખેલાડીઓ પાસેથી ક્વોન્ટમ સંદેશાઓ મેળવો અને આગામી સંદેશાવ્યવહાર રાઉન્ડની રાહ જુઓ, આમ વિરોધીને કયા સંદેશાઓ પસાર કરવામાં આવ્યા હતા તે પસંદ કરવા માટે દબાણ કરે છે. રાઉન્ડ 2: રાઉન્ડ I માં પ્રાપ્ત થયેલ તમામ ક્યુબિટ્સને માપો (પ્રમાણભૂત આધારમાં). રાઉન્ડના "નેતા" તરીકે સૌથી વધુ નેતા મૂલ્ય (મનસ્વી રીતે તૂટી ગયેલા સંબંધો) ધરાવતા ખેલાડીને પસંદ કરો. નેતાના સિક્કાને પ્રમાણભૂત આધારમાં માપો. ક્વોન્ટમકૉઇનફ્લિપ પ્રોટોકોલનું આઉટપુટ સુયોજિત કરો = નેતાના સિક્કાનું માપન પરિણામ. બીઝેન્ટાઇન પ્રોટોકોલ રેન્ડમ સિક્કો બનાવવા માટે દરેક ખેલાડીને [0, n-1] શ્રેણીમાં એક પૂર્ણાંક સોંપે છે અને દરેક ખેલાડીને તેની પોતાની રેન્ડમ ID પસંદ કરવાની મંજૂરી નથી કારણ કે દરેક ખેલાડી દરેક અન્ય ખેલાડી માટે રેન્ડમ નંબર પસંદ કરે છે અને ચકાસી શકાય તેવી ગુપ્ત વહેંચણી યોજનાનો ઉપયોગ કરીને તેનું વિતરણ કરે છે. આ તબક્કાના અંતે ખેલાડીઓ સંમત થાય છે કે કયા રહસ્યો યોગ્ય રીતે શેર કરવામાં આવ્યા હતા, પછી રહસ્યો ખોલવામાં આવે છે અને દરેક ખેલાડીને મૂલ્ય સોંપવામાં આવે છે. જેમાં ક્વોન્ટમ વેરિફાયબલ સિક્રેટ શેરિંગ પ્રોટોકોલ (ક્યુ. વી. એસ. એસ.) નો ઉપયોગ કરીને રાજ્યને એન્કોડ કરવામાં આવે છે. અમે રાજ્યને વહેંચી શકતા નથી કારણ કે ખરાબ ખેલાડીઓ રાજ્યને બરબાદ કરી શકે છે. ખરાબ ખેલાડીઓને આમ કરવાથી રોકવા માટે અમે ક્વોન્ટમ વેરિફાયબલ સિક્રેટ શેરિંગ (ક્યુ. વી. એસ. એસ.) નો ઉપયોગ કરીને રાજ્યને એન્કોડ કરીએ છીએ અને દરેક ખેલાડીને ગુપ્તતાનો તેમનો હિસ્સો મોકલીએ છીએ. અહીં ફરીથી ચકાસણી માટે બીઝેન્ટાઇન કરારની જરૂર છે, પરંતુ કરારને ગ્રેડ-કાસ્ટ પ્રોટોકોલ દ્વારા બદલવો પૂરતો છે. ગ્રેડ-કાસ્ટ પ્રોટોકોલ એ ગ્રેડ-કાસ્ટ પ્રોટોકોલમાં વ્યાખ્યાઓનો ઉપયોગ કરીને નીચેના ગુણધર્મો હોય છે અનૌપચારિક રીતે, ગ્રેડેડ બ્રોડકાસ્ટ પ્રોટોકોલ એ "ડીલર" (જે પ્રસારણ કરે છે) તરીકે ઓળખાતા નિયુક્ત ખેલાડી સાથેનો એક પ્રોટોકોલ છે જેમ કેઃ જો વેપારી સારો હોય, તો તમામ ખેલાડીઓને સમાન સંદેશ મળે છે. જો વેપારી ખરાબ હોય તો પણ, જો કોઈ સારો ખેલાડી સંદેશ સ્વીકારે છે, તો બધા સારા ખેલાડીઓને સમાન સંદેશ મળે છે (પરંતુ તેઓ તેને સ્વીકારી શકે છે કે નહીં). પ્રોટોકોલ P ને શ્રેણીબદ્ધ પ્રસારણ પ્રાપ્ત કરવા માટે કહેવામાં આવે છે, જો પ્રોટોકોલની શરૂઆતમાં, નિયુક્ત ખેલાડી D (વેપારી તરીકે ઓળખાતો) મૂલ્ય v ધરાવે છે, અને પ્રોટોકોલના અંતે, દરેક ખેલાડી એક જોડીને એવી રીતે બહાર કાઢે છે કે જે નીચેના ગુણધર્મો ધરાવે છેઃ જો D પ્રમાણિક હોય, તો દરેક પ્રમાણિક ખેલાડી માટે = v અને = 2. કોઈપણ બે પ્રમાણિક ખેલાડીઓ માટે. (સુસંગતતા) કોઈપણ બે પ્રમાણિક ખેલાડીઓ માટે અને, જો અને પછી. ક્યુ. વી. એસ. એસ. પ્રોટોકોલના ચકાસણી તબક્કા માટે બાંયધરી આપે છે કે સારા વેપારી માટે સાચી સ્થિતિ એન્કોડ કરવામાં આવશે, અને કોઈપણ, સંભવતઃ ખામીયુક્ત વેપારી માટે, અમુક ચોક્કસ સ્થિતિ પુનઃપ્રાપ્તિ તબક્કા દરમિયાન પુનઃપ્રાપ્ત કરવામાં આવશે. અમે નોંધ્યું છે કે અમારા બીઝેન્ટાઇન ક્વોન્ટમ સિક્કો ફ્લિપ પ્રોટોકોલના હેતુ માટે પુનઃપ્રાપ્તિનો તબક્કો ઘણો સરળ છે. દરેક ખેલાડી ક્યુ. વી. એસ. એસ. ના પોતાના હિસ્સાને માપે છે અને અન્ય તમામ ખેલાડીઓને શાસ્ત્રીય મૂલ્ય મોકલે છે. ચકાસણી તબક્કો ઉચ્ચ સંભાવના સાથે બાંહેધરી આપે છે કે, ખામીયુક્ત ખેલાડીઓની હાજરીમાં તમામ સારા ખેલાડીઓ સમાન શાસ્ત્રીય મૂલ્ય (જે સમાન મૂલ્ય છે જે એન્કોડેડ સ્થિતિના સીધા માપનથી પરિણમશે) મેળવશે. ટિપ્પણીઓ 2007 માં, બાયઝેન્ટાઇન કરાર માટે ક્વોન્ટમ પ્રોટોકોલ પ્રાયોગિક રીતે ચાર-ફોટોન ધ્રુવીકરણ-ગૂંથાયેલી સ્થિતિનો ઉપયોગ કરીને દર્શાવવામાં આવ્યો હતો. આ દર્શાવે છે કે ક્લાસિકલ બીઝેન્ટાઇન એગ્રીમેન્ટ પ્રોટોકોલનું ક્વોન્ટમ અમલીકરણ ખરેખર શક્ય છે. સંદર્ભો ક્વોન્ટમ માહિતી વિજ્ઞાન ક્રિપ્ટોગ્રાફી ડિસ્ટ્રિબ્યુટેડ કમ્પ્યુટિંગ પ્રોબ્લેમ્સ ફોલ્ટ ટોલરન્સ એન્જિનિયરિંગ નિષ્ફળતા ગણતરીનો સિદ્ધાંત