این پایان‌نامه به یکی از پرسش‌های بنیادین در تقاطع علوم رایانه، رمزنگاری و فیزیک کوانتوم می‌پردازد: چگونه می‌توان از یک محاسبه‌گر کلاسیک، درستی اجرای یک محاسبه کوانتومی را توسط دستگاهی ناشناس و بالقوه مخرب، تأیید کرد؟ برای پاسخ به این پرسش، پژوهشگران از «بازی‌های غیرموضعی» استفاده می‌کنند؛ سناریوهایی که در آن دو بازیکن جدا از هم، بدون امکان ارتباط، به سوالاتی پاسخ می‌دهند و همبستگی پاسخ‌هایشان می‌تواند وجود درهم‌تنیدگی کوانتومی را اثبات کند. اما اجرای فیزیکی این بازی‌ها نیازمند جدایی فضایی است که در عمل دشوار است. از سوی دیگر، با ظهور رایانه‌های کوانتومی، نیاز به روش‌هایی برای تأیید محاسبات انجام‌شده روی این دستگاه‌ها، بیش از پیش احساس می‌شود، زیرا کاربران معمولی توانایی بررسی مستقیم صحت محاسبات کوانتومی را ندارند و باید به نوعی به درستی خروجی دستگاه اعتماد کنند. اینجاست که مفهوم بازی‌های غیرموضعی کامپایل‌شده، به‌عنوان یک راه‌حل میانی مطرح می‌شود.

راه‌حل نوآورانه‌ای که در این پژوهش بسط داده می‌شود، «کامپایل» این بازی‌ها است؛ یعنی تبدیل آن‌ها به یک بازی تعاملی تک‌بازیکنه که در آن یک اثبات‌کننده کوانتومی با توان محاسباتی محدود، در برابر یک سنجش‌گر کلاسیک قرار می‌گیرد. این کار با استفاده از رمزنگاری هم‌ریخت (همان‌ریخت) انجام می‌شود تا اثر جدایی فضایی را شبیه‌سازی کند. به‌بیان ساده‌تر، یک سنجش‌گر کلاسیک که به یک دستگاه کوانتومی دسترسی دارد، می‌تواند با اجرای این بازی کامپایل‌شده، از درستی عملکرد دستگاه اطمینان حاصل کند. اما سؤال کلیدی اینجاست: آیا می‌توان اطمینان داشت که یک اثبات‌کننده‌ی سودجو، نتواند از نبود جدایی فیزیکی سوءاستفاده کرده و در بازی کامپایل‌شده با احتمالی بیش از مقدار مجاز در بازی اصلی، برنده شود؟ این همان «درستی کوانتومی» است که کمّی‌کردن آن، هدف غایی این پژوهش محسوب می‌شود. اگر نتوانیم این درستی را کمّی کنیم، عملاً نمی‌توانیم به هیچ تضمینی برای صحت خروجی دستگاه کوانتومی دست یابیم.

پایان‌نامه با ارائه یک چارچوب ریاضی جدید، گامی بلند در جهت کمّی‌سازی این درستی برمی‌دارد. هستهٔ اصلی این چارچوب، مفهوم «تجزیهٔ مجموع مرب‌های خوش‌ساخت» است. این تجزیه، روشی برای اثبات کران‌های بالای احتمال برد در بازی‌های کوانتومی با استفاده از مجموع مرب‌های چندجمله‌ای‌هاست. به عبارت دیگر، اگر بتوانیم یک بازی را به‌صورت یک چندجمله‌ای نمایش دهیم، آنگاه با بیان تفاضل کران بالا و آن چندجمله‌ای به‌صورت مجموع مرب‌های چندجمله‌ای‌های دیگر، می‌توانیم ثابت کنیم که مقدار آن بازی از آن کران تجاوز نمی‌کند. نوآوری در اینجا، تعریف دقیق «خوش‌ساختی» است به‌گونه‌ای که این تجزیه با الزامات رمزنگاری بازی کامپایل‌شده سازگار باشد. به عبارت ساده‌تر، پژوهشگر نشان می‌دهد اگر بتوان یک کران بالا برای بازی اصلی به این شکل خاص اثبات کرد، همان کران (با خطای ناچیز) برای بازی کامپایل‌شده نیز معتبر خواهد بود. این «خطای ناچیز» به پارامتر امنیتی رمزنگاری وابسته است و با افزایش آن، عملاً به صفر میل می‌کند.

برای یافتن سیستماتیک این تجزیه‌های خوش‌ساخت، پژوهشگر یک سلسله‌مراتب جدید از برنامه‌ریزی نیمه‌معین (SDP) به نام «سلسله‌مراتب NPA یک‌سویه» ابداع کرده است. این ابزار قدرتمند به‌صورت خودکار و با افزایش دقت، به جستجوی بهترین کران‌های بالا می‌پردازد. برنامه‌ریزی نیمه‌معین، شاخه‌ای از بهینه‌سازی محدب است که در آن متغیرها ماتریس‌های نیمه‌معین مثبت هستند و به‌طور گسترده در نظریه اطلاعات کوانتومی و رمزنگاری کاربرد دارد. اثبات می‌شود که این سلسله‌مراتب به مقدار کوانتومی واقعی بازی همگرا می‌شود، به این معنا که می‌توان برای هر بازی و هر درجه از دقت، یک گواهی خوش‌ساخت پیدا کرد که بازی کامپایل‌شده را با همان دقت محدود کند. این یعنی برای اولین بار، یک روش محاسباتی تضمین‌شده برای یافتن کران‌های کمی برای همهٔ بازی‌های کامپایل‌شده ارائه شده است. پیش از این، تنها برای بازی‌های خاصی مانند CHSH یا بازی‌های XOR، چنین کران‌هایی وجود داشت و برای بازی‌های عمومی، هیچ روش سیستماتیکی در دسترس نبود.

اهمیت عملی این دستاورد در آن است که وابستگی کران به دست‌آمده به «پارامتر امنیتی» رمزنگاری، صریح و به‌صورت یک تابع ناچیز است. این یعنی با انتخاب پارامتر امنیتی به‌اندازهٔ کافی بزرگ، می‌توان اختلاف احتمال برد در بازی کامپایل‌شده را به‌هر میزان دلخواه کوچک کرد. این ویژگی برای کاربردهای واقعی مانند تأیید محاسبات کوانتونی ابری حیاتی است، چراکه به سنجش‌گر کلاسیک اجازه می‌دهد با اطمینان ریاضی، صحت اجرا را کنترل کند. برای نمونه، فرض کنید یک کاربر بخواهد یک مسئله را به یک رایانه کوانتومی ابری بسپارد. با استفاده از این بازی‌های کامپایل‌شده، کاربر می‌تواند بدون نیاز به درک جزئیات فیزیک کوانتوم، با اجرای چند دور بازی و بررسی نتایج، از درستی محاسبه اطمینان حاصل کند. این روش در مقابل دستگاه‌های کوانتومی مخربی که سعی در فریب دادن سنجش‌گر دارند، مقاوم است.

علاوه بر این چارچوب کلی، پژوهش به یک کلاس مهم از بازی‌ها موسوم به «بازی‌های سطح اول NPA» (که شامل بازی‌های XOR دوتایی می‌شود) می‌پردازد و نشان می‌دهد که برای تمام این بازی‌ها، می‌توان بدون افزایش درجهٔ پیچیدگی، یک تجزیهٔ خوش‌ساخت ساخت. این قضیه، نتایج قبلی را که تنها به بازی‌های خاصی محدود می‌شد، به شکلی چشمگیر تعمیم می‌دهد و اثبات می‌کند که روش پیشنهادی، دست‌کم برای این طیف وسیع از بازی‌ها، کارآمد و عملی است. بازی‌های XOR، دسته‌ای از بازی‌های غیرموضعی هستند که در آن‌ها جواب‌ها بیتی (صفر یا یک) هستند و شرط برنده‌شدن به‌صورت یک معادله خطی روی جمع به‌پیمانهٔ دو تعریف می‌شود. این بازی‌ها به‌خاطر ساختار ساده و در عین حال غنی‌شان، سال‌ها موضوع تحقیق بوده‌اند. مثال‌های عینی مانند بازی «هم‌سانی دوتایی» و یک تعمیم سه‌جوابی از بازی CHSH، قدرت این روش را در عمل به نمایش می‌گذارند. بازی هم‌سانی دوتایی، نمونه‌ای از بازی‌های سطح اول است که در آن سوالات به‌صورت برچسب‌های رأس‌های یک گراف و پاسخ‌ها به‌صورت رنگ‌آمیزی دودویی هستند و شرط برنده‌شدن، هم‌سانی رنگ دو رأس مجاور است.

نکتهٔ قابل‌توجه دیگر، ارائهٔ یک گواهی خوش‌ساخت صریح برای بازی \(\mathcal{B}_3\) است که یک تعمیم سه‌جوابی از بازی معروف CHSH محسوب می‌شود. این بازی در سطح دوم سلسله‌مراتب NPA قرار دارد، یعنی پیچیده‌تر از بازی‌های سطح اول است. موفقیت در ساخت یک تجزیهٔ خوش‌ساخت برای این بازی، نشان‌دهندهٔ قدرت و انعطاف‌پذیری چارچوب پیشنهادی فراتر از ساده‌ترین حالت‌ها است. این دستاورد، نویدبخش آن است که با تعمیم‌های بیشتر، بتوان روش را برای سطوح بالاتر NPA نیز گسترش داد و بدین‌ترتیب، دامنهٔ بازی‌های قابل‌تحلیل را به‌طور قابل‌توجهی افزایش داد. همچنین، کد منبع تولیدشده در این پژوهش به‌عنوان یک ابزار عملی در دسترس جامعهٔ پژوهشی قرار گرفته است که می‌تواند برای یافتن تجزیه‌های خوش‌ساخت برای بازی‌های جدید، مورد استفاده قرار گیرد.

در نهایت، این پایان‌نامه با ایجاد پیوندی مستحکم میان نظریهٔ بازی‌های غیرموضعی، بهینه‌سازی محدب و رمزنگاری کوانتومی، افق تازه‌ای در تأیید محاسبات کوانتومی می‌گشاید. قضیهٔ اصلی آن، که می‌توان آن را «قضیهٔ محاسباتی تسایرلسون» برای بازی‌های کامپایل‌شده نامید، یک کران بالای کمّی و قابل‌حل برای ارزش این بازی‌ها ارائه می‌دهد. این قضیه به‌نوعی نسخهٔ محاسباتی و عملیاتی از قضیهٔ مشهور تسایرلسون است که در نظریه اطلاعات کوانتومی، کران نهایی همبستگی‌های کوانتومی را مشخص می‌کند. این نه تنها درک نظری از محدودیت‌های اثبات‌کننده‌های کوانتومی را عمیق‌تر می‌سازد، بلکه مسیر را برای پیاده‌سازی سیستم‌های تأیید محاسبات کوانتومی امن و کارآمد در دنیای واقعی هموار می‌کند. با گسترش رایانه‌های کوانتومی و افزایش کاربردهای آن‌ها، روش‌هایی از این دست، نقشی حیاتی در ایجاد اعتماد و امنیت در اکوسیستم محاسبات کوانتومی ایفا خواهند کرد. این پژوهش نشان می‌دهد که چگونه ترکیب هوشمندانهٔ ابزارهای ریاضی و رمزنگاری می‌تواند یکی از چالش‌های اساسی عصر کوانتوم را به‌گونه‌ای نظام‌مند و قابل‌تأیید، پشت سر بگذارد.

در کنار همهٔ این دستاوردها، پژوهشگر به‌وضوح به محدودیت‌های کار خود نیز اشاره کرده و مسیرهایی را برای پژوهش‌های آینده ترسیم می‌کند. یکی از مهم‌ترین مسیرهای آتی، تعمیم روش به سطوح بالاتر سلسله‌مراتب NPA و یافتن بازی‌های سطح اول جدید است که دامنهٔ کاربرد روش را گسترش دهد. همچنین، چشم‌انداز بلندمدت‌تر، مطالعهٔ رفتار خواصی فراتر از «ارزش» بازی‌ها، مانند ویژگی‌های خودآزمون‌گری (self-testing) و صلبیت (rigidity) تحت کامپایل است که می‌تواند به درک عمیق‌تری از ماهیت محاسبات کوانتومی و روش‌های تأیید آن منجر شود. این پژوهش، سنگ بنای مستحکمی برای چنین تحقیقات آینده‌ای فراهم آورده و نشان داده که رویکرد مبتنی بر تجزیه‌های خوش‌ساخت، یک مسیر امیدوارکننده برای حل چالش‌های بنیادین در تقاطع رمزنگاری و فیزیک کوانتوم است. مجموعهٔ یافته‌های این پایان‌نامه، نه تنها از منظر نظری حائز اهمیت است، بلکه ابزارهای عملی را نیز در اختیار جامعهٔ پژوهشی قرار می‌دهد تا بتوانند به‌سوی تحقق تأیید محاسبات کوانتومی در مقیاس بزرگ حرکت کنند.

آیا یک کامپیوتر کوانتومی می‌تواند به خودش دروغ بگوید؟

تصور کنید از یک دوست بسیار باهوش می‌خواهید یک محاسبهٔ ریاضی بسیار پیچیده را برای شما انجام دهد، اما نمی‌توانید صحت پاسخ او را بررسی کنید. حالا تصور کنید که این دوست، یک رایانهٔ کوانتومی در ابر باشد و شما فقط یک کامپیوتر معمولی در اختیار دارید. چگونه می‌توانید به خروجی او اعتماد کنید؟ این پایان‌نامه، پاسخی شگفت‌انگیز برای این معما ارائه می‌دهد.

بازی‌هایی برای فریب دادن فیزیک

پژوهشگر با الهام از مفهوم «بازی‌های غیرموضعی» وارد می‌شود؛ سناریوهایی که در آن دو بازیکن جدا از هم، بدون هیچ ارتباطی، به سوالات مشابه پاسخ می‌دهند. فیزیک کوانتوم به این بازیکنان اجازه می‌دهد با استفاده از درهم‌تنیدگی، همبستگی‌هایی فراتر از توان دنیای کلاسیک تولید کنند. اما اجرای این بازی‌ها در دنیای واقعی به جدایی فیزیکی نیاز دارد که همیشه ممکن نیست.

راه‌حل، «کامپایل» کردن این بازی‌ها است. یعنی تبدیل آن‌ها به یک بازی تک‌بازیکنه که در آن، یک اثبات‌کنندهٔ کوانتومی (همان دوست باهوش!) با یک سنجش‌گر کلاسیک (ما!) روبرو می‌شود. این کار با استفاده از رمزنگاری هم‌ریخت انجام می‌شود تا اثر جدایی فضایی شبیه‌سازی شود. اما خطر اینجاست: اثبات‌کنندهٔ سودجو ممکن است از نبود جدایی فیزیکی سوءاستفاده کند و تقلب کند.

قفل ریاضی بر روی تقلب

نوآوری اصلی این پژوهش، ارائهٔ یک «قفل ریاضی» به نام «تجزیهٔ مجموع مرب‌های خوش‌ساخت» است. این یک روش اثبات‌پذیر برای محدود کردن میزان تقلب احتمالی اثبات‌کننده است. به‌بیان ساده، اگر بتوانیم یک کران بالا برای برد در بازی اصلی به این شکل خاص اثبات کنیم، همان کران (با خطایی به کوچکی یک دانهٔ شن در بیابان) برای بازی کامپایل‌شده نیز معتبر خواهد بود.

برای پیدا کردن این قفل‌ها، پژوهشگر از یک ابزار ریاضی به نام «برنامه‌ریزی نیمه‌معین» استفاده کرده و سلسله‌مراتب جدیدی به نام «NPA یک‌سویه» ابداع کرده است. این ابزار به‌صورت خودکار و با افزایش دقت، بهترین کران‌های ممکن را جستجو می‌کند. نکتهٔ شگفت‌انگیز این است که این روش برای همهٔ بازی‌ها کار می‌کند و تنها با افزایش «پارامتر امنیتی» رمزنگاری، می‌توان خطا را به صفر نزدیک کرد.

از تئوری تا عمل: یک گام بزرگ به جلو

پایان‌نامه فراتر از یک چارچوب کلی رفته و برای یک کلاس وسیع از بازی‌ها (معروف به بازی‌های سطح اول NPA که شامل بازی‌های XOR دوتایی نیز می‌شود)، اثبات می‌کند که همیشه می‌توان این قفل ریاضی را بدون افزایش پیچیدگی ساخت. به‌عنوان مثال، این روش با موفقیت روی بازی «هم‌سانی دوتایی» و همچنین یک تعمیم سه‌جوابی از بازی معروف CHSH (که \(\mathcal{B}_3\) نام دارد) پیاده شده است.

نتایج این پژوهش، قضیه‌ای را به اثبات می‌رساند که می‌توان آن را «قضیهٔ محاسباتی تسایرلسون» برای بازی‌های کامپایل‌شده نامید؛ نسخه‌ای عملیاتی از قضیهٔ مشهوری که در فیزیک کوانتوم، کران نهایی همبستگی‌ها را مشخص می‌کند. این یعنی برای اولین بار، یک روش سیستماتیک و تضمین‌شده برای تأیید محاسبات کوانتومی در دسترس است که می‌تواند راه را برای استفادهٔ امن از رایانه‌های کوانتومی ابری هموار کند.

«این پژوهش، سنگ بنای مستحکمی برای تحقیقات آینده در زمینهٔ تأیید محاسبات کوانتومی فراهم می‌آورد و نشان می‌دهد که رویکرد مبتنی بر تجزیه‌های خوش‌ساخت، یک مسیر امیدوارکننده برای حل چالش‌های بنیادین است.»

در نهایت، این پژوهش نه تنها یک مسئلهٔ فنی را حل می‌کند، بلکه درکی عمیق‌تر از ماهیت اطلاعات و اعتماد در عصر کوانتوم به ما می‌دهد. این پایان‌نامه با زبانی دقیق اما قابل‌دسترس، نشان می‌دهد که چگونه می‌توان از قوانین ریاضیات برای محافظت از خود در برابر فریب‌های کوانتومی استفاده کرد.