Quantum Byzantine agreement
பைசண்டைன் தவறு சகிப்புத்தன்மை நெறிமுறைகள் என்பது விநியோகிக்கப்பட்ட வழிமுறைகளில் தன்னிச்சையான வகையான தோல்விகளுக்கு வலுவான வழிமுறைகளாகும். பைசண்டைன் ஒப்பந்த நெறிமுறை இந்த பணியின் இன்றியமையாத பகுதியாகும். பைசண்டைன் நெறிமுறையின் நிலையான நேர குவாண்டம் பதிப்பு கீழே விவரிக்கப்பட்டுள்ளது. பைசண்டைன் ஒப்பந்த நெறிமுறை என்பது விநியோகிக்கப்பட்ட கணினியில் ஒரு நெறிமுறை ஆகும். இது 1982 ஆம் ஆண்டில் லாம்போர்ட், ஷோஸ்டாக் மற்றும் பீஸ் ஆகியோரால் வகுக்கப்பட்ட ஒரு சிக்கலில் இருந்து அதன் பெயரைப் பெற்றது, இது ஒரு வரலாற்று சிக்கலைக் குறிக்கிறது. பைசண்டைன் இராணுவம் பிரிவுகளாகப் பிரிக்கப்பட்டது, ஒவ்வொரு பிரிவும் பின்வரும் பண்புகளுடன் ஒரு ஜெனரலால் வழிநடத்தப்பட்டதுஃ ஒவ்வொரு ஜெனரலும் பைசண்டைன் அரசுக்கு விசுவாசமாக அல்லது துரோகி. அனைத்து தளபதிகளும் செய்திகளை அனுப்புவதன் மூலமும் பெறுவதன் மூலமும் தொடர்பு கொள்கிறார்கள். இரண்டு கட்டளைகள் மட்டுமே உள்ளனஃ தாக்குதல் மற்றும் பின்வாங்குதல். அனைத்து விசுவாசமான தளபதிகளும் ஒரே செயல் திட்டத்தை ஒப்புக் கொள்ள வேண்டும்ஃ தாக்குதல் அல்லது பின்வாங்கல். மோசமான ஜெனரல்களின் ஒரு சிறிய நேரியல் பின்னம் நெறிமுறை தோல்வியடையக்கூடாது (ஒரு பின்னத்திற்கு குறைவாக). (சாத்தியமற்ற முடிவின் ஆதாரத்தைப் பார்க்கவும்). இந்தப் பிரச்சினை பொதுவாக ஒரு கமாண்டிங் ஜெனரல் மற்றும் விசுவாசமான லெப்டினன்ட்டுகளின் வடிவத்தில் சமமாக மறுபரிசீலனை செய்யப்படுகிறது, ஜெனரல் விசுவாசமாகவோ அல்லது துரோகியாகவோ இருப்பதோடு, பின்வரும் சொத்துக்களைக் கொண்ட லெப்டினன்ட்டுகளுக்கும் இது பொருந்தும். அனைத்து விசுவாசமான லெப்டினன்ட்களும் ஒரே உத்தரவை நிறைவேற்றுகிறார்கள். கமாண்டிங் ஜெனரல் விசுவாசமாக இருந்தால், விசுவாசமான லெப்டினன்ட்கள் அனைவரும் அவர் அனுப்பும் உத்தரவுக்குக் கீழ்ப்படிகிறார்கள். கமாண்டிங் ஜெனரல் உட்பட கண்டிப்பாக குறைவான பகுதியினர் துரோகிகள். பைசண்டைன் தோல்வி மற்றும் பின்னடைவு ஒரு வழிமுறை அல்லது நெறிமுறையில் உள்ள தோல்விகளை மூன்று முக்கிய வகைகளாக வகைப்படுத்தலாம்ஃ வழிமுறையில் மற்றொரு செயல்பாட்டு நடவடிக்கையை எடுக்கத் தவறியதுஃ இது பொதுவாக "ஃபெயில் ஸ்டாப்" தவறு என்று குறிப்பிடப்படுகிறது. சரியாக செயல்படுத்த ஒரு சீரற்ற தோல்விஃ இது ஒரு "சீரற்ற தவறு" அல்லது "சீரற்ற பைசண்டைன்" தவறு என்று அழைக்கப்படுகிறது. வழிமுறை படிகளை சரியாக செயல்படுத்தத் தவறும் ஒரு தன்னிச்சையான தோல்வி (பொதுவாக முழு வழிமுறையையும் தோல்வியடையச் செய்ய சில எதிரிகளால் புத்திசாலித்தனமான வழியில்) இது முந்தைய இரண்டு வகையான தவறுகளையும் உள்ளடக்கியது; இது "பைசண்டைன் தவறு" என்று அழைக்கப்படுகிறது. பைசண்டைன் நெகிழ்திறன் அல்லது பைசண்டைன் தவறு சகிப்புத்தன்மை நெறிமுறை அல்லது வழிமுறை என்பது மேலே குறிப்பிட்டுள்ள அனைத்து வகையான தோல்விகளுக்கும் வலுவான ஒரு வழிமுறையாகும். எடுத்துக்காட்டாக, பல தேவையற்ற செயலிகளுடன் ஒரு விண்வெளி விண்கலம் கொடுக்கப்பட்டால், செயலிகள் முரண்பட்ட தரவைக் கொடுத்தால், எந்த செயலிகள் அல்லது செயலிகளின் தொகுப்புகள் நம்பப்பட வேண்டும்? தீர்வை பைசண்டைன் தவறு சகிப்புத்தன்மை நெறிமுறையாக வடிவமைக்க முடியும். வழிமுறையின் வரைபடம் ஒத்திசைவற்ற வழிமுறையை இங்கே வரைவோம் இந்த வழிமுறை இரண்டு கட்டங்களில் செயல்படுகிறதுஃ கட்டம் 1 (தகவல் தொடர்பு கட்டம்): அனைத்து செய்திகளும் இந்த சுற்றில் அனுப்பப்பட்டு பெறப்படுகின்றன. ஒரு நாணய புரட்டுதல் நெறிமுறை என்பது ஒரு குறிப்பிட்ட பொருளை வெல்ல ஒரு நாணயத்தை வீச ஒருவருக்கொருவர் நம்பாத ஏ மற்றும் பி ஆகிய இரண்டு தரப்பினரை அனுமதிக்கும் ஒரு செயல்முறையாகும். இரண்டு வகையான நாணயம் புரட்டுதல் நெறிமுறைகள் உள்ளன பலவீனமான நாணயம் புரட்டுதல் நெறிமுறைகள்ஃ இரண்டு வீரர்கள் ஏ மற்றும் பி ஆரம்பத்தில் எந்த உள்ளீடுகளும் இல்லாமல் தொடங்குகிறார்கள், மேலும் அவர்கள் சில மதிப்பைக் கணக்கிட வேண்டும், மேலும் யாரையும் மோசடி செய்ததாக குற்றம் சாட்ட முடியும். A மற்றும் B முடிவு குறித்து ஒப்புக் கொண்டால் நெறிமுறை வெற்றிகரமாக இருக்கும். முடிவு 0 என்பது A வெற்றி மற்றும் 1 என்பது B வெற்றி என வரையறுக்கப்படுகிறது. நெறிமுறை பின்வரும் பண்புகளைக் கொண்டுள்ளதுஃ இரு வீரர்களும் நேர்மையாக இருந்தால் (அவர்கள் நெறிமுறையைப் பின்பற்றுகிறார்கள்), பின்னர் அவர்கள் நெறிமுறையின் முடிவை ஏற்றுக்கொள்கிறார்கள். வீரர்களில் ஒருவர் நேர்மையாக இருந்தால் (அதாவது, மற்ற வீரர் தனது உள்ளூர் கணக்கீட்டில் நெறிமுறையிலிருந்து தன்னிச்சையாக விலகக்கூடும்), பின்னர் மற்ற கட்சி அதிகபட்சமாக நிகழ்தகவுடன் வெற்றி பெறுகிறது. வேறு வார்த்தைகளில் கூறுவதானால், B நேர்மையற்றவராக இருந்தால், பின்னர், A நேர்மையற்றவராக இருந்தால், பின்னர். ஒரு வலுவான நாணயம் புரட்டுதல் நெறிமுறைஃ ஒரு வலுவான நாணயம் புரட்டுதல் நெறிமுறையில், அதற்கு பதிலாக 0 அல்லது 1 என்ற குறிப்பிட்ட மதிப்பிலிருந்து விலகி ஒரு சீரற்ற பிட்டை உருவாக்குவதே குறிக்கோள். எந்தவொரு வலுவான நாணய புரட்டுதல் நெறிமுறையும் அதே சார்புடன் பலவீனமான நாணய புரட்டலுக்கு வழிவகுக்கிறது என்பது தெளிவாகிறது. சரிபார்க்கக்கூடிய ரகசிய பகிர்வு ஒரு சரிபார்க்கக்கூடிய ரகசிய பகிர்வு நெறிமுறைஃ A (n, k) ரகசிய பகிர்வு நெறிமுறை n வீரர்களின் தொகுப்பை ஒரு ரகசியத்தைப் பகிர்ந்து கொள்ள அனுமதிக்கிறது, அதாவது k அல்லது அதற்கு மேற்பட்ட வீரர்களின் கோரம் மட்டுமே ரகசியத்தைக் கண்டறிய முடியும். ரகசியத்தைப் பகிர்ந்து கொள்ளும் வீரர் (ரகசியத் துண்டுகளை விநியோகிப்பவர்) பொதுவாக வியாபாரி என்று குறிப்பிடப்படுகிறார். ஒரு சரிபார்க்கக்கூடிய ரகசிய பகிர்வு நெறிமுறை ஒரு அடிப்படை ரகசிய பகிர்வு நெறிமுறையிலிருந்து வேறுபடுகிறது, அதில் வீரர்கள் ஒரு தீங்கிழைக்கும் வியாபாரி முன்னிலையில் கூட தங்கள் பங்குகள் சீராக இருப்பதை சரிபார்க்க முடியும். ரவுண்ட் 1 வீரருக்கான ஃபைல்-ஸ்டாப் புரோட்டோகால் புரோட்டோகால் குவாண்டம் நாணயம் ஃபிளிப் கியூபிட்களில் GHZ நிலையை உருவாக்குகிறது மற்றும் ஒரு பகுதியை வைத்துக்கொண்டு th கியூபிடை th வீரருக்கு அனுப்புகிறது கியூபிட்களில் நிலையை உருவாக்கவும் (குவாண்டம்-கம்ப்யூட்டிங் கூறுகள் பல கியூபிட்களில் சீரானவை), 1 மற்றும் 1 க்கு இடையிலான எண்களின் சமமான மேல்நிலை. அனைத்து வீரர்களிடமிருந்தும் குவாண்டம் செய்திகளைப் பெற்று, அடுத்த தகவல்தொடர்பு சுற்றுக்காக காத்திருங்கள், இதனால் எந்த செய்திகள் அனுப்பப்பட்டன என்பதை எதிரியை தேர்வு செய்ய கட்டாயப்படுத்துகிறது. சுற்று 2: சுற்று I இல் பெறப்பட்ட அனைத்து கியூபிட்களையும் அளவிடுதல் (நிலையான அடிப்படையில்). மிக உயர்ந்த தலைவர் மதிப்பைக் கொண்ட வீரரை (உறவுகள் தன்னிச்சையாக உடைக்கப்பட்டன) சுற்றின் "தலைவர்" என்று தேர்ந்தெடுக்கவும். தலைவரின் நாணயத்தை நிலையான அடித்தளத்தில் அளவிடவும். குவாண்டம் கோயின்ஃப்ளிப் நெறிமுறையின் வெளியீட்டை அமைக்கவும்ஃ = தலைவரின் நாணயத்தின் அளவீட்டு முடிவு. பைசண்டைன் நெறிமுறை ஒரு சீரற்ற நாணயத்தை உருவாக்க ஒவ்வொரு வீரருக்கும் [0, n-1] வரம்பில் ஒரு முழு எண்ணை ஒதுக்குங்கள், ஒவ்வொரு வீரரும் ஒவ்வொரு வீரருக்கும் ஒரு சீரற்ற எண்ணைத் தேர்ந்தெடுத்து சரிபார்க்கக்கூடிய ரகசிய பகிர்வு திட்டத்தைப் பயன்படுத்தி விநியோகிக்கப்படுவதால் ஒவ்வொரு வீரரும் அதன் சொந்த சீரற்ற ஐடியைத் தேர்வு செய்ய அனுமதிக்கப்படுவதில்லை. இந்த கட்டத்தின் முடிவில் எந்த ரகசியங்கள் சரியாக பகிரப்பட்டன என்பதை வீரர்கள் ஒப்புக்கொள்கிறார்கள், பின்னர் ரகசியங்கள் திறக்கப்பட்டு ஒவ்வொரு வீரருக்கும் மதிப்பு ஒதுக்கப்படுகிறது இதற்கு தனியார் தகவல் சேனல்கள் தேவைப்படுகின்றன, எனவே சீரற்ற ரகசியங்களை சூப்பர்போசிஷன் மூலம் மாற்றுகிறோம். இதில் குவாண்டம் சரிபார்க்கக்கூடிய ரகசிய பகிர்வு நெறிமுறையைப் (கியூ. வி. எஸ். எஸ்) பயன்படுத்தி மாநிலம் குறியிடப்பட்டுள்ளது. மோசமான வீரர்கள் மாநிலத்தை சீரழிக்கக்கூடும் என்பதால் எங்களால் மாநிலத்தை விநியோகிக்க முடியாது. மோசமான வீரர்கள் அவ்வாறு செய்வதைத் தடுக்க, குவாண்டம் சரிபார்க்கக்கூடிய ரகசிய பகிர்வு (கியூவிஎஸ்எஸ்) ஐப் பயன்படுத்தி மாநிலத்தை குறியாக்கம் செய்கிறோம், மேலும் ஒவ்வொரு வீரருக்கும் அவர்களின் ரகசியத்தின் பங்கை அனுப்புகிறோம். இங்கே மீண்டும் சரிபார்ப்புக்கு பைசண்டைன் ஒப்பந்தம் தேவைப்படுகிறது, ஆனால் ஒப்பந்தத்தை கிரேடு-காஸ்ட் நெறிமுறையால் மாற்றுவது போதுமானது. கிரேடு-காஸ்ட் நெறிமுறை ஒரு கிரேடு-காஸ்ட் நெறிமுறை பின்வரும் வரையறைகளைப் பயன்படுத்தி பின்வரும் பண்புகளைக் கொண்டுள்ளது முறைசாரா முறையில், ஒரு தரப்படுத்தப்பட்ட ஒளிபரப்பு நெறிமுறை என்பது "டீலர்" (ஒளிபரப்புபவர்) என்று அழைக்கப்படும் ஒரு நியமிக்கப்பட்ட வீரருடன் ஒரு நெறிமுறையாகும்ஃ வியாபாரி நல்லவராக இருந்தால், அனைத்து வீரர்களும் ஒரே செய்தியைப் பெறுகிறார்கள். வியாபாரி மோசமாக இருந்தாலும், சில நல்ல வீரர்கள் செய்தியை ஏற்றுக்கொண்டால், அனைத்து நல்ல வீரர்களும் ஒரே செய்தியைப் பெறுகிறார்கள் (ஆனால் அவர்கள் அதை ஏற்றுக்கொள்ளலாம் அல்லது ஏற்றுக்கொள்ளாமல் போகலாம்). நெறிமுறையின் தொடக்கத்தில், ஒரு நியமிக்கப்பட்ட வீரர் டி (டீலர் என்று அழைக்கப்படுகிறார்) ஒரு மதிப்பு வி வைத்திருந்தால், ஒரு நெறிமுறை பி தரப்படுத்தப்பட்ட ஒளிபரப்பை அடைவதாக கூறப்படுகிறது, மேலும் நெறிமுறையின் முடிவில், ஒவ்வொரு வீரரும் பின்வரும் பண்புகளைக் கொண்டிருக்கும் வகையில் ஒரு ஜோடியை வெளியிடுகிறார்கள்ஃ டி நேர்மையாக இருந்தால், ஒவ்வொரு நேர்மையான வீரருக்கும் = வி மற்றும் = 2. எந்தவொரு இரண்டு நேர்மையான வீரர்களுக்கும் மற்றும். (நிலைத்தன்மை) எந்தவொரு இரண்டு நேர்மையான வீரர்களுக்கும் மற்றும், என்றால், பின்னர். கியூவிஎஸ்எஸ் நெறிமுறையின் சரிபார்ப்பு கட்டத்திற்கு ஒரு நல்ல டீலருக்கு சரியான நிலை குறியிடப்படும் என்றும், எந்தவொரு, தவறான டீலருக்கும், மீட்பு கட்டத்தில் சில குறிப்பிட்ட நிலை மீட்கப்படும் என்றும் உத்தரவாதம் அளிக்கிறது. எங்கள் பைசண்டைன் குவாண்டம் நாணயம் ஃபிளிப் நெறிமுறையின் நோக்கத்திற்காக மீட்பு நிலை மிகவும் எளிதானது என்பதை நாங்கள் கவனிக்கிறோம். ஒவ்வொரு வீரரும் கியூ. வி. எஸ். எஸ்ஸில் தனது பங்கை அளவிடுகிறார்கள் மற்றும் மற்ற அனைத்து வீரர்களுக்கும் பாரம்பரிய மதிப்பை அனுப்புகிறார்கள். சரிபார்ப்பு நிலை, அதிக நிகழ்தகவுடன், தவறான வீரர்களின் முன்னிலையில் அனைத்து நல்ல வீரர்களும் ஒரே கிளாசிக்கல் மதிப்பை மீட்டெடுப்பார்கள் (இது குறியிடப்பட்ட நிலையின் நேரடி அளவீட்டின் விளைவாக ஏற்படும் அதே மதிப்பு). 2007 ஆம் ஆண்டில், பைசண்டைன் ஒப்பந்தத்திற்கான ஒரு குவாண்டம் நெறிமுறை நான்கு-ஃபோட்டான் துருவமுனைப்பு-சிக்கலான நிலையைப் பயன்படுத்தி சோதனை ரீதியாக நிரூபிக்கப்பட்டது. கிளாசிக்கல் பைசண்டைன் ஒப்பந்த நெறிமுறைகளின் குவாண்டம் அமலாக்கம் உண்மையில் சாத்தியமானது என்பதை இது காட்டுகிறது. குறிப்புகள் குவாண்டம் தகவல் அறிவியல் கிரிப்டோகிராஃபி விநியோகிக்கப்பட்ட கணினி சிக்கல்கள் தவறு சகிப்புத்தன்மை பொறியியல் தோல்விகள் கணக்கீட்டு கோட்பாடு