Quantum Byzantine agreement
بازنطینی غلطی برداشت کرنے والے پروٹوکول الگورتھم ہیں جو تقسیم شدہ الگورتھم میں صوابدیدی قسم کی ناکامیوں کے لیے مضبوط ہیں۔ بازنطینی معاہدہ پروٹوکول اس کام کا ایک لازمی حصہ ہے۔ بازنطینی پروٹوکول کا مستقل وقت کا کوانٹم ورژن، ذیل میں بیان کیا گیا ہے۔ تعارف بازنطینی معاہدہ پروٹوکول تقسیم شدہ کمپیوٹنگ میں ایک پروٹوکول ہے۔ اس کا نام 1982 میں لیمپورٹ، شوستک اور پیس کے تیار کردہ ایک مسئلے سے لیا گیا ہے، جو خود ایک تاریخی مسئلے کا حوالہ ہے۔ بازنطینی فوج کو ڈویژنوں میں تقسیم کیا گیا تھا جس میں ہر ڈویژن کی قیادت مندرجہ ذیل خصوصیات کے ساتھ ایک جنرل کرتا تھا: ہر جنرل یا تو وفادار ہوتا ہے یا بازنطینی ریاست کا غدار ہوتا ہے۔ تمام جنرل پیغامات بھیج کر اور وصول کر کے بات چیت کرتے ہیں۔ صرف دو کمانڈ ہیں: حملہ اور پیچھے ہٹنا۔ تمام وفادار جرنیلوں کو ایک ہی عملی منصوبے پر متفق ہونا چاہیے: حملہ یا پسپائی۔ خراب جرنیلوں کے ایک چھوٹے سے لکیری حصے کو پروٹوکول کے ناکام ہونے کا سبب نہیں بننا چاہیے (ایک حصہ سے کم)۔ (ناممکن نتیجہ کے ثبوت کے لیے دیکھیں)۔ اس مسئلے کو عام طور پر کمانڈنگ جنرل اور وفادار لیفٹیننٹ کی شکل میں مساوی طور پر دہرایا جاتا ہے جس میں جنرل یا تو وفادار یا غدار ہوتا ہے اور درج ذیل خصوصیات والے لیفٹیننٹ کے لیے بھی ایسا ہی ہوتا ہے۔ تمام وفادار لیفٹیننٹ ایک ہی حکم پر عمل کرتے ہیں۔ اگر کمانڈنگ جنرل وفادار ہے، تو تمام وفادار لیفٹیننٹ اس کے بھیجے گئے حکم کی پابندی کرتے ہیں۔ کمانڈنگ جنرل سمیت سختی سے کم حصہ غدار ہیں۔ بازنطینی ناکامی اور لچک کسی الگورتھم یا پروٹوکول میں ناکامیوں کو تین اہم اقسام میں درجہ بند کیا جا سکتا ہے: الگورتھم میں ایک اور عمل درآمد کا قدم اٹھانے میں ناکامی: اسے عام طور پر "فیل اسٹاپ" فالٹ کہا جاتا ہے۔ صحیح طریقے سے انجام دینے میں بے ترتیب ناکامی: اسے "بے ترتیب غلطی" یا "بے ترتیب بازنطینی غلطی" کہا جاتا ہے۔ ایک من مانی ناکامی جہاں الگورتھم مراحل کو صحیح طریقے سے انجام دینے میں ناکام رہتا ہے (عام طور پر کسی مخالف کے ذریعہ پورے الگورتھم کو ناکام بنانے کے لیے چالاکی سے) جس میں پچھلی دو قسم کی غلطیاں بھی شامل ہوتی ہیں۔ اسے "بازنطینی غلطی" کہا جاتا ہے۔ بازنطینی لچکدار یا بازنطینی غلطی برداشت کرنے والا پروٹوکول یا الگورتھم ایک الگورتھم ہے جو اوپر بیان کردہ ہر قسم کی ناکامیوں کے لیے مضبوط ہے۔ مثال کے طور پر، ایک سے زیادہ بے کار پروسیسرز والی خلائی شٹل کو دیکھتے ہوئے، اگر پروسیسرز متضاد ڈیٹا دیتے ہیں، تو کون سے پروسیسرز یا پروسیسرز کے سیٹوں پر یقین کیا جانا چاہیے؟ اس حل کو بازنطینی غلطی برداشت کرنے والے پروٹوکول کے طور پر وضع کیا جا سکتا ہے۔ الگورتھم کا خاکہ ہم یہاں اسنکرونس الگورتھم کا خاکہ بنائیں گے الگورتھم دو مراحل میں کام کرتا ہے: مرحلہ 1 (مواصلاتی مرحلہ): تمام پیغامات اس دور میں بھیجے اور وصول کیے جاتے ہیں۔ سکے کو پلٹانے کا پروٹوکول ایک ایسا طریقہ کار ہے جو دو فریقوں اے اور بی کو اجازت دیتا ہے جو ایک دوسرے پر بھروسہ نہیں کرتے ہیں کہ وہ کسی خاص شے کو جیتنے کے لیے سکے کو ٹاس کریں۔ سکے پلٹانے کے پروٹوکول کی دو قسمیں ہیں کمزور سکے پلٹانے کے پروٹوکول: دو کھلاڑی اے اور بی ابتدائی طور پر بغیر کسی ان پٹ کے شروع کرتے ہیں اور انہیں کچھ قیمت کا حساب لگانا ہوتا ہے اور کسی پر دھوکہ دہی کا الزام لگانے کے قابل ہونا ہوتا ہے۔ پروٹوکول کامیاب ہوتا ہے اگر A اور B نتیجہ پر متفق ہوں۔ نتیجہ 0 کو A جیتنے اور 1 کو B جیتنے کے طور پر بیان کیا گیا ہے۔ پروٹوکول میں درج ذیل خصوصیات ہیں: اگر دونوں کھلاڑی ایماندار ہیں (وہ پروٹوکول پر عمل کرتے ہیں)، تو وہ پروٹوکول کے نتائج پر اتفاق کرتے ہیں۔ اگر کھلاڑیوں میں سے ایک ایماندار ہے (یعنی، دوسرا کھلاڑی اپنے مقامی حساب میں پروٹوکول سے من مانی طور پر ہٹ سکتا ہے)، تو دوسرا فریق زیادہ سے زیادہ امکان کے ساتھ جیت جاتا ہے۔ دوسرے لفظوں میں، اگر B بے ایمان ہے، تو، اور اگر A بے ایمان ہے، تو۔ ایک مضبوط سکے پلٹنے کا پروٹوکول: ایک مضبوط سکے پلٹنے کے پروٹوکول میں، مقصد اس کے بجائے ایک بے ترتیب بٹ تیار کرنا ہے جو کسی خاص قدر 0 یا 1 سے دور ہے۔ واضح طور پر، تعصب کے ساتھ کوئی بھی مضبوط سکے پلٹنے کا پروٹوکول اسی تعصب کے ساتھ کمزور سکے پلٹنے کا باعث بنتا ہے۔ قابل تصدیق خفیہ شیئرنگ ایک قابل تصدیق خفیہ شیئرنگ پروٹوکول: A (n, k) خفیہ شیئرنگ پروٹوکول n کھلاڑیوں کے ایک سیٹ کو ایک راز شیئر کرنے کی اجازت دیتا ہے، اس طرح کہ صرف k یا اس سے زیادہ کھلاڑیوں کا کورم ہی اس راز کو دریافت کر سکتا ہے۔ راز کا اشتراک کرنے والے کھلاڑی (خفیہ ٹکڑوں کو تقسیم کرنے والے) کو عام طور پر ڈیلر کہا جاتا ہے۔ ایک قابل تصدیق خفیہ شیئرنگ پروٹوکول بنیادی خفیہ شیئرنگ پروٹوکول سے مختلف ہوتا ہے جس میں کھلاڑی اس بات کی تصدیق کر سکتے ہیں کہ بدنیتی پر مبنی ڈیلر کی موجودگی میں بھی ان کے حصص مستقل ہیں۔ کھلاڑی راؤنڈ 1 کے لیے فیل اسٹاپ پروٹوکول کوانٹم کوائن فلپ کیوبیٹس پر جی ایچ زیڈ کی حالت پیدا کرتا ہے اور ایک حصہ رکھتے ہوئے th کیوبیٹ کو th کھلاڑی کو بھیجتا ہے۔ کیوڈیٹس پر حالت پیدا کریں (متعدد کیوبیٹس کے مطابق کوانٹم کمپیوٹنگ اجزاء)، 1 اور 1 کے درمیان نمبروں کی مساوی سپرپوزیشن۔ تمام کھلاڑیوں کے درمیان قادتیں تقسیم کریں تمام کھلاڑیوں سے کوانٹم پیغامات وصول کریں اور اگلے مواصلاتی دور کا انتظار کریں، اس طرح مخالف کو یہ انتخاب کرنے پر مجبور کریں کہ کون سے پیغامات منتقل کیے گئے تھے۔ راؤنڈ 2: راؤنڈ I میں موصول ہونے والے تمام کیوبیٹس کی پیمائش (معیاری بنیاد میں)۔ سب سے زیادہ لیڈر ویلیو (من مانی طور پر ٹوٹے ہوئے تعلقات) والے کھلاڑی کو راؤنڈ کے "لیڈر" کے طور پر منتخب کریں۔ لیڈر کے سکے کی پیمائش معیاری بنیاد میں کریں۔ کوانٹم کوئن فلپ پروٹوکول کا آؤٹ پٹ سیٹ کریں: = لیڈر کے سکے کی پیمائش کا نتیجہ۔ بازنطینی پروٹوکول بے ترتیب سکہ تیار کرنے کے لیے ہر کھلاڑی کو رینج [0, n-1] میں ایک عدد تفویض کریں اور ہر کھلاڑی کو اپنی بے ترتیب آئی ڈی منتخب کرنے کی اجازت نہیں ہے کیونکہ ہر کھلاڑی ہر دوسرے کھلاڑی کے لیے بے ترتیب نمبر منتخب کرتا ہے اور اسے قابل تصدیق خفیہ شیئرنگ اسکیم کا استعمال کرتے ہوئے تقسیم کرتا ہے۔ اس مرحلے کے اختتام پر کھلاڑی اس بات پر متفق ہوتے ہیں کہ کون سے رازوں کو مناسب طریقے سے شیئر کیا گیا تھا، پھر راز کھولے جاتے ہیں اور ہر کھلاڑی کو قیمت تفویض کی جاتی ہے۔ اس کے لیے نجی انفارمیشن چینلز کی ضرورت ہوتی ہے لہذا ہم بے ترتیب رازوں کو سپرپوزیشن سے تبدیل کرتے ہیں۔ جس میں ریاست کو کوانٹم تصدیق شدہ خفیہ شیئرنگ پروٹوکول (کیو وی ایس ایس) کا استعمال کرتے ہوئے انکوڈ کیا جاتا ہے۔ ہم ریاست کو تقسیم نہیں کر سکتے کیونکہ خراب کھلاڑی ریاست کو تباہ کر سکتے ہیں۔ خراب کھلاڑیوں کو ایسا کرنے سے روکنے کے لیے ہم کوانٹم ویریفایبل سیکرٹ شیئرنگ (کیو وی ایس ایس) کا استعمال کرتے ہوئے ریاست کو انکوڈ کرتے ہیں اور ہر کھلاڑی کو راز کا اپنا حصہ بھیجتے ہیں۔ یہاں دوبارہ تصدیق کے لیے بازنطینی معاہدے کی ضرورت ہوتی ہے، لیکن معاہدے کو گریڈ کاسٹ پروٹوکول سے تبدیل کرنا کافی ہے۔ گریڈ کاسٹ پروٹوکول ایک گریڈ کاسٹ پروٹوکول میں مندرجہ ذیل خصوصیات ہوتی ہیں جن کی تعریفیں غیر رسمی طور پر استعمال ہوتی ہیں، ایک درجہ بند نشریاتی پروٹوکول ایک پروٹوکول ہوتا ہے جس میں ایک نامزد کھلاڑی ہوتا ہے جسے "ڈیلر" (وہ جو نشر کرتا ہے) کہا جاتا ہے کہ: اگر ڈیلر اچھا ہے تو تمام کھلاڑیوں کو ایک ہی پیغام ملتا ہے۔ یہاں تک کہ اگر ڈیلر برا ہے، اگر کوئی اچھا کھلاڑی پیغام کو قبول کرتا ہے، تو تمام اچھے کھلاڑیوں کو ایک ہی پیغام ملتا ہے (لیکن وہ اسے قبول بھی کر سکتے ہیں یا نہیں بھی کر سکتے ہیں)۔ ایک پروٹوکول P کو درجہ بند نشریاتی حاصل کرنے کے لیے کہا جاتا ہے اگر، پروٹوکول کے آغاز میں، ایک نامزد کھلاڑی D (جسے ڈیلر کہا جاتا ہے) ایک ویلیو v رکھتا ہے، اور پروٹوکول کے اختتام پر، ہر کھلاڑی ایک جوڑی کو اس طرح آؤٹ پٹ کرتا ہے کہ درج ذیل خصوصیات برقرار رہیں: اگر D ایماندار ہے، تو ہر ایماندار کھلاڑی کے لیے = v اور = 2۔ کسی بھی دو ایماندار کھلاڑیوں کے لیے اور۔ (مستقل مزاجی) کسی بھی دو ایماندار کھلاڑیوں کے لیے اور، اگر اور پھر۔ کیو وی ایس ایس پروٹوکول کے تصدیق کے مرحلے کے لیے اس بات کی ضمانت دیتا ہے کہ ایک اچھے ڈیلر کے لیے صحیح حالت کو انکوڈ کیا جائے گا، اور یہ کہ کسی بھی ممکنہ طور پر ناقص ڈیلر کے لیے، بازیابی کے مرحلے کے دوران کسی خاص ریاست کو بازیافت کیا جائے گا۔ ہم نوٹ کرتے ہیں کہ ہمارے بازنطینی کوانٹم سکے فلپ پروٹوکول کے مقصد کے لیے بازیابی کا مرحلہ بہت آسان ہے۔ ہر کھلاڑی کیو وی ایس ایس کے اپنے حصے کی پیمائش کرتا ہے اور دوسرے تمام کھلاڑیوں کو کلاسیکی قدر بھیجتا ہے۔ تصدیق کا مرحلہ، زیادہ امکان کے ساتھ، اس بات کی ضمانت دیتا ہے کہ ناقص کھلاڑیوں کی موجودگی میں تمام اچھے کھلاڑی ایک ہی کلاسیکی قیمت حاصل کریں گے (جو وہی قیمت ہے جو انکوڈ شدہ حالت کی براہ راست پیمائش کے نتیجے میں ہوگی)۔ تبصرے 2007 میں، بازنطینی معاہدے کے لیے ایک کوانٹم پروٹوکول کا تجرباتی طور پر چار فوٹون پولرائزیشن سے جڑی ہوئی حالت کا استعمال کرتے ہوئے مظاہرہ کیا گیا۔ اس سے ظاہر ہوتا ہے کہ کلاسیکی بازنطینی معاہدے کے پروٹوکول کا کوانٹم نفاذ واقعی قابل عمل ہے۔ حوالہ جات کوانٹم انفارمیشن سائنس کرپٹوگرافی تقسیم شدہ کمپیوٹنگ کے مسائل غلطی رواداری انجینئرنگ کی ناکامیاں حساب کا نظریہ