اثبات دو قضیه ریاضی و فیزیک کوانتوم از مسیر یک اثبات در علوم کامپیوتر

دانشمندان کامپیوتر یک مرز جدید در دانش محاسباتی قابل تایید ایجاد کردند. برای این کار، آن‌ها مسایل بزرگ باز در مکانیک کوانتومی و ریاضیات محض را حل کردند.

منتشرشده در: مجله Quanta Magazine در تاریخ ۴ مارچ ۲۰۲۰
نویسنده: Kevin Hartnett
لینک مقاله اصلی: https://www.quantamagazine.org/landmark-computer-science-proof-cascades-through-physics-and-math-20200304/

در سال ۱۹۳۵ آلبرت انیشتین، که با بوریس پودولسکی و ناتان روزن کار می‌کرد، با این احتمال دست و پنجه نرم کرد که قوانین جدید فیزیک کوانتومی نشان می‌دهد که دو ذره می‌توانند حتی در فواصل طولانی گرفتار یا هم‌بسته شوند.

سال بعد، آلن تورینگ اولین نظریه عمومی محاسبات را فرمول‌بندی کرد و ثابت کرد که مشکلی وجود دارد که کامپیوترها هرگز قادر به حل آن نخواهند بود.

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

اثبات جدید نشان می‌دهد که کامپیوترهای کوانتومی که با بیت‌ها یا کیوبیت های کوانتومی درهم گره خورده، محاسبه می‌شوند، نسبت به کامپیوترهای کلاسیک صفر و یکی، می‌توانند به صورت نظری برای تایید پاسخ‌ها به مجموعه‌ای از مسایل بسیار گسترده استفاده شوند. تطابق بین درهم‌تنیدگی و محاسبات یک شوک برای بسیاری از محققان به وجود آورد.

میگل ناوایکوس، که در موسسه نور شناسی کوانتوم و اطلاعات کوانتوم در وین به مطالعه فیزیک کوانتوم می‌پردازد، می‌گوید: «این یک شگفتی کامل بود.»

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

در پایان، نتایج مانند دومینو آبشاری می‌شوند.

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

مشکلات تصمیم ناپذیر

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

به طور معمول، برنامه‌های کامپیوتری ورودی دریافت می‌کنند و خروجی تولید می‌کنند. اما گاهی در حلقه‌های نامحدود گیر می‌افتند و برای همیشه در همان چرخه می‌چرخند. وقتی این اتفاق در خانه می‌افتد، تنها یک کار باقی می‌ماند.

به گفته یوئن: « شما باید به صورت دستی برنامه را بکشید. فقط آن را قطع کنید.»

تورینگ ثابت کرد که هیچ الگوریتم تمام هدفی وجود ندارد که بتواند تعیین کند که آیا یک برنامه کامپیوتری برای همیشه متوقف خواهد شد یا نه. شما باید برنامه را اجرا کنید تا متوجه شوید.

ویلیام اسلوفسترا ریاضی دان دانشگاه واترلو گفت: «شما یک میلیون سال منتظر بوده‌اید و یک برنامه متوقف نشده است. آیا فقط باید دو میلیون سال صبر کنید؟ هیچ راهی برای تعیین آن وجود ندارد.»

به بیان فنی، تورینگ ثابت کرد که این مساله توقف تصمیم ناپذیر است - حتی قدرتمندترین کامپیوتر قابل‌تصور نمی‌تواند آن را حل کند.

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

در نهایت، هر مشکلی دو سوال بزرگ مطرح می‌کند: «حل آن چقدر سخت است؟ و تایید اینکه پاسخ درست است چقدر دشوار است؟»

بازجویی برای تایید

زمانی که مشکلات نسبتا ساده هستند، می‌توانید خودتان پاسخ را چک کنید. اما زمانی که آن‌ها پیچیده‌تر می‌شوند، حتی چک کردن پاسخ می‌تواند کار دشواری باشد. با این حال، در سال ۱۹۸۵ دانشمندان علوم کامپیوتر متوجه شدند که این امکان وجود دارد که اعتماد به نفس خود را گسترش دهند که یک پاسخ درست است حتی زمانی که شما نمی‌توانید آن را خودتان تایید کنید.

این روش از منطق بازجویی پلیس پیروی می‌کند.

اگر یک مظنون یک داستان مفصل می‌گوید، قاعدتا شما نمی‌توانید برای تایید تمام جزئیات به دنیای او بروید. اما با پرسیدن سوالات درست، می‌توانید مظنون خود را در یک دروغ دستگیر کنید و یا اعتماد به نفس خود را افزایش دهید و داستان بررسی می‌کنید.

در علوم کامپیوتر، دو طرف در یک بازجویی یک کامپیوتر قدرتمند هستند که راه حلی را برای یک مساله - معروف به مدعی - و یک کامپیوتر کم‌قدرت‌تر که می‌خواهد از مدعی سوال کند تا تعیین کند که آیا پاسخ درست است یا خیر، پیشنهاد می‌کنند. این کامپیوتر دوم تایید‌کننده نامیده می‌شود.

برای مثال ساده، تصور کنید که شما کوررنگ هستید و شخص دیگری (مدعی) ادعا می‌کند که دو تیله رنگ‌های مختلفی دارند. شما نمی‌توانید این ادعا را خودتان بررسی کنید، اما از طریق بازجویی هوشمندانه می‌توانید تشخیص دهید که آیا این حقیقت دارد یا نه.

دو تیله را پشت سرت بگذار و آن‌ها را با هم قاطی کن. سپس از مدعی بخواهید به شما بگوید کدام به کدام است. اگر آن‌ها واقعا رنگ‌های مختلفی دارند، مدعی باید هر بار به طور صحیح به سوال پاسخ دهد. اگر تیله‌ها در واقع هم‌رنگ باشند - یعنی شبیه هم به نظر برسند - مدعی نیمی از زمان اشتباه حدس می‌زند.

ویدیک گفت: «اگر ببینیم که بیش از نیمی از اوقات موفق می‌شوید، کاملا مطمئن هستم که آن‌ها یک رنگ نیستند.»

با پرسیدن سوالات اولیه، می‌توانید راه‌حل را برای یک کلاس وسیع‌تر از مشکلات خودتان بررسی کنید.

تو یک میلیون سال منتظر بودی و برنامه متوقف نشد. آیا فقط باید دو میلیون سال صبر کنید؟ هیچ راهی برای گفتن نیست
ویلیام اسلوفسترا ، دانشگاه واترلو

در سال ۱۹۸۸، دانشمندان علوم کامپیوتر در نظر گرفتند که چه اتفاقی می‌افتد وقتی که دو مدعی راه‌حل‌هایی برای مشکل مشابه پیشنهاد می‌کنند. هر چه باشد، اگر دو مظنون دارید که از آن‌ها بازجویی کنید، حل یک جرم یا بررسی جرم یک راه‌حل آسان‌تر است، چون می‌توانید آن‌ها را در مقابل یکدیگر بازی کنید.

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

به طور مشابه، محققان نشان دادند که با بازجویی جداگانه از دو مدعی در مورد پاسخ‌های آن‌ها، شما می‌توانید به سرعت راه‌حل‌ها را برای یک دسته از مشکلات حتی بزرگ‌تر از زمانی که تنها یک مدعی برای بازجویی دارید، بررسی کنید.

پیچیدگی محاسباتی ممکن است کاملا نظری به نظر برسد، اما همچنین ارتباط نزدیکی با دنیای واقعی دارد. منابعی که کامپیوترها برای حل و تایید مشکلات نیاز دارند - زمان و حافظه - اساسا فیزیکی هستند. به همین دلیل، اکتشافات جدید در فیزیک می‌تواند پیچیدگی محاسباتی را تغییر دهد.

ناتاراجان گفت: «اگر شما یک مجموعه فیزیک متفاوت، مانند کوانتوم را به جای کلاسیک انتخاب کنید، یک نظریه پیچیدگی متفاوت از آن به دست می‌آورید.»

برهان جدید آخرین نتیجه دانشمندان کامپیوتر قرن بیست و یکم است که با یکی از عجیب‌ترین ایده‌های فیزیک قرن بیستم روبرو هستند: درهم‌تنیدگی.

حدسیه تعبیه کانز (Connes Embedding Conjecture)

وقتی دو ذره درگیر می‌شوند، در واقع بر یکدیگر تاثیر نمی‌گذارند - آن‌ها هیچ رابطه علی ندارند. انیشتین و همکارانش در مقاله ۱۹۳۵ خود به این ایده پرداختند. بعد از آن، فیزیکدانان و ریاضی دانان تلاش کردند تا یک روش ریاضی برای توصیف معنای واقعی پیچیدگی پیدا کنند.

با این حال، این تلاش کمی گنگ به نظر می‌رسید. دانشمندان با دو مدل ریاضی متفاوت برای درهم‌تنیدگی مواجه شدند - و واضح نبود که آن‌ها با هم برابر باشند.

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

اولین راه مدل‌سازی درهم‌تنیدگی این بود که ذرات را به صورت فضایی جدا از یکدیگر در نظر بگیریم. یکی در زمین است، و دیگری در مریخ؛ فاصله میان آن‌ها چیزی است که مانع علیت می‌شود. این مدل محصول تانسور نامیده می‌شود.

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

زمانی که ترتیب انجام دو عمل بر نتیجه تاثیر نمی‌گذارد، عملیات "تخفیف" می‌یابد: نتیجه ضرب ۳ در ۲ مشابه ۲ در ۳ است. در این مدل دوم، ذرات وقتی درهم گره می‌خورند که خواص آن‌ها به هم مرتبط باشد اما ترتیبی که شما اندازه‌گیری خود را انجام می‌دهید مهم نیست: ذره A را اندازه‌گیری کنید تا مومنتوم ذره B را پیش‌بینی کنید یا برعکس. در هر صورت، شما جواب مشابهی می‌گیرید. این مدل عملگر رفت و آمد مدل درهم‌تنیدگی نامیده می‌شود.

قابلیت تایید این نوع مدل واقعا عجیب و غریب است.
هنری یوئن، دانشگاه تورنتو

هر دو توصیف درهم‌تنیدگی از آرایه‌های اعداد تشکیل‌شده در ردیف‌ها و ستون‌هایی به نام ماتریس‌ها استفاده می‌کنند. مدل ضرب تانسور از ماتریس‌هایی با تعداد متناهی سطر و ستون استفاده می‌کند. مدل عملگر جابجایی از یک شی عمومی‌تر استفاده می‌کند که مانند یک ماتریس با تعداد بی‌نهایت سطر و ستون عمل می‌کند.

با گذشت زمان، ریاضی دانان شروع به مطالعه این ماتریس‌ها به عنوان موضوع مورد علاقه خود کردند، کاملا جدا از هر گونه ارتباط با دنیای فیزیکی. به عنوان بخشی از این کار، ریاضی دانی به نام آلن کانز در سال ۱۹۷۶ حدس زد که می‌توان بسیاری از ماتریس‌های با ابعاد نامحدود را با ماتریس‌های با ابعاد متناهی تقریب زد. این یکی از مفاهیم حدسیه «تعبیه کانز» است.

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

با این حال، راه‌حل برای هر دو مشکل به طور کلی از مکان سومی بدست آمد.

نمایش بازی فیزیک

در دهه ۱۹۶۰، یک فیزیکدان به نام جان بل، آزمونی را برای تعیین اینکه آیا درهم‌تنیدگی یک پدیده فیزیکی واقعی است یا صرفا یک تصور نظری مطرح کرد. این آزمون شامل نوعی بازی بود که نتایج آن نشان می‌دهد که آیا چیزی بیش از فیزیک غیرکوانتومی در حال کار است یا خیر.

دانشمندان علوم کامپیوتر بعدها متوجه شدند که این تست در مورد درهم‌تنیدگی می‌تواند به عنوان ابزاری برای تایید پاسخ‌های مشکلات بسیار پیچیده نیز مورد استفاده قرار گیرد.

اما اول، برای اینکه ببینیم بازی‌ها چطور کار می‌کنند، بیایید دو بازیکن به نام‌های آلیس و باب و یک شبکه ۳ در ۳ را تصور کنیم. داور، آلیس را در یک ردیف قرار می‌دهد و به او می‌گوید که در هر کادر ۰ یا ۱ را وارد کند تا ارقام به یک عدد فرد برسند. باب یک ستون می‌گیرد و باید آن را پر کند تا به یک عدد زوج برسد. آن‌ها در صورتی برنده می‌شوند که همان عدد را در جایی قرار دهند که ردیف او و ستون او با هم تداخل داشته باشند. آنها اجازه ندارند با هم مکالمه‌ یا ارتباطی داشته باشند.

تحت شرایط عادی، بهترین کاری که آن‌ها می‌توانند انجام دهند این است که ۸۹ درصد از وقت خود را برنده شوند. اما تحت شرایط کوانتومی، آن‌ها می‌توانند بهتر عمل کنند.

آلیس و باب را تصور کنید که یک جفت ذرات به‌هم‌چسبیده را تقسیم کردند. آن‌ها اندازه‌گیری‌ها را بر روی ذرات مربوطه خود انجام می‌دهند و از نتایج برای دیکته کردن این که آیا در هر جعبه ۱ یا ۰ بنویسند استفاده می‌کنند. از آنجا که ذرات درگیر هستند، نتایج اندازه‌گیری آن‌ها در حال هم‌بسته شدن است، که به این معنی است که پاسخ‌های آن‌ها به خوبی با هم مرتبط خواهد بود به این معنی که آن‌ها می‌توانند بازی را در ۱۰۰٪ زمان برنده شوند.

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

یوئن گفت: «مردم در طول سال‌ها آزمایش‌هایی انجام داده‌اند که نشان می‌دهد این چیز ترسناک واقعی است.»

همانند تجزیه و تحلیل هر بازی، ممکن است بخواهید بدانید که بازیکنان تا چه حد می‌توانند یک بازی غیر محلی را برنده شوند، به شرطی که بتوانند بهترین بازی را انجام دهند. برای مثال، با بازی solitaire می‌توانید محاسبه کنید که هر چند وقت یک‌بار کسی که به خوبی بازی می‌کند برنده می‌شود.

اما در سال ۲۰۱۶، ویلیام اسلوفترا ثابت کرد که هیچ الگوریتم کلی برای محاسبه حداکثر احتمال برد دقیق برای همه بازی‌های غیر محلی وجود ندارد. بنابراین محققان از خود می‌پرسیدند: آیا می‌توانید حداقل درصد برد بیشینه را تخمین بزنید؟

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

این الگوریتم ها جواب‌های دقیق تری را در مدت‌زمان طولانی تری تولید می‌کنند. اگر پیش‌بینی Tsirelson درست باشد، و دو مدل واقعا معادل باشند، کف و سقف باید به هم نزدیک شوند، و در یک مقدار واحد برای درصد برد بیشینه محدود شوند.

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

در کار جدیدشان، پنج محقق از این سوال استفاده کردند - درباره اینکه آیا سقف و کف به هم می‌پیوندند و مشکل Tsirelson درست است یا غلط - برای حل یک سوال جداگانه در مورد اینکه چه زمانی می توان جواب یک مساله محاسباتی را تایید کرد.

کمک درهم گره خورده

در اوایل دهه ۲۰۰۰، دانشمندان علوم کامپیوتر به این فکر افتادند که: چگونه این کار دامنه مشکلاتی که شما می‌توانید بررسی کنید را تغییر می‌دهد اگر شما از دو مدعی که ذرات گرفتار را به اشتراک می‌گذارند، بازجویی کنید؟

بیشتر آن‌ها تصور می‌کردند که این درهم‌تنیدگی در برابر تایید عمل می‌کند. به هر حال، دو مظنون اگر وسیله‌ای برای هماهنگی پاسخ‌های خود داشتند، زمان بهتری برای گفتن یک دروغ منسجم داشتند.

اما در طول چند سال گذشته، دانشمندان علوم کامپیوتر متوجه شده‌اند که عکس آن درست است: با پرس و جو از افرادی که ذرات درهم را به اشتراک می‌گذارند، شما می‌توانید دسته بسیار بزرگتری از مشکلات را نسبت به آنچه که می‌توانید بدون درگیر شدن بررسی کنید.

ویدیک گفت: «انسجام راهی برای ایجاد همبستگی است که فکر می‌کنید ممکن است به دروغ گفتن یا تقلب کردن آن‌ها کمک کند. اما در واقع می‌توانید از آن به نفع خود استفاده کنید.»

برای درک این که چگونه، شما ابتدا باید مقیاس تقریبا دیگرجهانی مشکلات را درک کنید که می‌توانید راه‌حل آن‌ها را از طریق این روند تعاملی بررسی کنید.

یک گراف را تصور کنید - مجموعه‌ای از نقاط (ریوس) که با خطوط (یال‌ها) به هم متصل شده‌اند. شما ممکن است بخواهید بدانید که آیا رنگ‌آمیزی راس‌ها با سه رنگ ممکن است، به طوری که هیچ کدام از راس‌های متصل به یک یال رنگ یکسانی نداشته باشند. اگر بتوانید، نمودار "سه رنگی" است.

اگر یک جفت لوازم پیچیده شده را به دست یک گراف بسیار بزرگ بدهید و آن‌ها گزارش دهند که می‌تواند سه‌رنگ باشد، شما شگفت‌زده خواهید شد: آیا راهی برای تایید پاسخ آن‌ها وجود دارد؟

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

اما حتی این استراتژی بازجویی هم با شکست مواجه می‌شود چون گراف‌ها واقعا بزرگ می‌شوند - با یال‌ها و ریوس بیشتری نسبت به اتم‌ها در جهان. حتی وظیفه بیان یک سوال خاص ("به من رنگ راس XYZ را بگو") بیشتر از آن چیزی است که شما، بررسی‌کننده، می‌توانید مدیریت کنید: مقدار داده‌های مورد نیاز برای نام گذاری یک راس خاص بیشتر از آن چیزی است که می‌توانید در حافظه کاری خود نگه دارید.

اما درهم‌تنیدگی این امکان را برای کسانی فراهم می‌کند که خودشان به این پرسش‌ها پاسخ دهند.

به گفته رایت، بررسی‌کننده مجبور نیست سوالات را محاسبه کند. بررسی‌کننده مدعیان را مجبور می‌کند تا سوالات را برای آن‌ها محاسبه کنند.

بررسی‌کننده می‌خواهد که مدعیان رنگ‌های راس‌های متصل را گزارش کنند. اگر ریوس متصل نباشند، پاسخ به سوالات هیچ چیزی در مورد این که آیا گراف سه‌رنگ است یا نه نخواهد گفت. به عبارت دیگر، بررسی‌کننده از پیش تنظیم‌شده می‌خواهد که سوالات مرتبط را بپرسد: یکی از پیش تنظیم‌شده در مورد راس ABC و دیگری در مورد راس XYZ می‌پرسد. امید است که دو راس به هم متصل باشند، با وجود اینکه هیچ کدام از مدعیان از پیش نمی‌دانند که دیگری در مورد کدام راس فکر می‌کند. (همانطور که آلیس و باب امیدوارند همان تعداد را در یک میدان پر کنند، با اینکه هیچ کدام نمی‌دانند از کدام سطر یا ستون دیگری سوال شده‌است).

همه این افکار از یک زمان سرچشمه می‌گرفت. خیلی خوب است که آن‌ها دوباره به این شکل دراماتیک به یکدیگر باز می‌گردند
هنری یوئن، دانشگاه تورنتو

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

ویدیک گفت: «ما قصد داریم از گرفتاری برای تخلیه تقریبا همه چیز بر روی کارکنان استفاده کنیم. ما کاری می‌کنیم که آن‌ها خودشان سوالات را انتخاب کنند.»

در پایان این روش، لوازم هر کدام یک رنگ را گزارش می‌کنند. بررسی‌کننده بررسی می‌کند که آیا آن‌ها یک‌سان هستند یا خیر. اگر گراف واقعا سه رنگ دارد، متریک‌ها هرگز نباید یک رنگ را گزارش کنند.

یوئن گفت: «اگر سه رنگ وجود داشته باشد، رنگ کنندگان می‌توانند شما را متقاعد کنند که یک رنگ وجود دارد.»

همانطور که مشخص شد، این رویه تایید نمونه دیگری از یک بازی غیرمحلی است. اگر مدعی شما را متقاعد کند که راه‌حل آن‌ها درست است، برنده می‌شود.

در سال ۲۰۱۲، ویدیک و تسوشی ایتو ثابت کردند که ممکن است انواع مختلفی از بازی‌های غیر محلی با لوازم پیچیده بازی کنند تا پاسخ حداقل به همان تعداد مشکلاتی که شما می‌توانید با بازجویی از دو کامپیوتر کلاسیک بررسی کنید را تایید کنند. به این معنی که استفاده از گیره‌های گرفتار شده در برابر تایید کار نمی‌کند. و سال گذشته، ناتاراجان و رایت ثابت کردند که تعامل با ارایه‌دهنده‌های درگیر در واقع کلاس مشکلاتی را گسترش می‌دهد که می توان آن‌ها را تایید کرد.

اما دانشمندان علوم کامپیوتر طیف کاملی از مشکلات را که می توان به این روش آن‌ها را تایید کرد، نمی‌دانستند. البته تا حالا.

یک آبشار از عواقب

پنج دانشمند کامپیوتر در مقاله جدیدشان ثابت کردند که بازجویی از حافظه‌های گیرافتاده این امکان را فراهم می‌کند که پاسخ‌های مربوط به مسایل غیرقابل‌حل از جمله مساله توقف را بررسی کنند.

یوئن گفت: «قابلیت تایید این نوع مدل واقعا شگفت‌انگیز است.»

اما مشکل توقف نمی‌تواند حل شود. و این واقعیت جرقه‌ای است که دلیل نهایی را در حرکت قرار می‌دهد.

تصور کنید که شما یک برنامه را در اختیار یک جفت مدعی می‌گذارید. از آن‌ها می‌خواهید به شما بگویند که آیا متوقف خواهد شد یا نه. شما آماده هستید تا پاسخ آن‌ها را از طریق یک نوع بازی غیر محلی بررسی کنید: مدعیان سوالاتی را ایجاد می‌کنند و براساس هماهنگی بین پاسخ‌های آن‌ها "برنده" خواهند شد.

اگر برنامه در واقع متوقف شود، مدعی باید بتواند این بازی را ۱۰۰ % زمان ببرد - شبیه به این که اگر یک گراف در واقع سه رنگ باشد، مدعی درهم گره خورده هرگز نباید یک رنگ را برای دو راس متصل گزارش کند. اگر متوقف نشود، مدعیان تنها باید شانس برنده شدن در نیمی از مواقع را داشته باشند.

این بدان معناست که اگر کسی از شما بخواهد که احتمال برد ماکزیمم تقریبی برای یک نمونه خاص از این بازی غیر محلی را تعیین کنید، ابتدا باید مساله توقف را حل کنید. و حل مشکل توقف غیر ممکن است. که به این معنی است که محاسبه احتمال برد ماکزیمم تقریبی برای بازی‌های غیر محلی، درست مانند مساله توقف، تصمیم ناپذیر است.

این به نوبه خود به این معنی است که پاسخ به مساله Tsirelson خیر است - دو مدل درهم‌تنیدگی معادل نیستند. زیرا اگر چنین بود، شما می‌توانستید کف و سقف را با هم نیشگون بگیرید تا احتمال برنده شدن تقریبی را محاسبه کنید. دیوید پرز - گارسیا از دانشگاه کامپلومنت مادرید گفت:«چنین الگوریتمی وجود ندارد، بنابراین دو مدل باید متفاوت باشند.»

این مقاله جدید ثابت می‌کند که دسته‌ای از مسایل که می توان از طریق تعاملات با پروورهای کوانتومی درهم، دسته‌ای به نام MIP، آن‌ها را تایید کرد، دقیقا با دسته‌ای از مسایل که سخت‌تر از مساله توقف نیستند، کلاسی به نام RE، برابر است. عنوان مقاله به اختصار آن را بیان می‌کند: "MIP* = RE".

دانشمندان علوم کامپیوتر در طول اثبات اینکه دو گروه پیچیدگی برابر هستند، ثابت کردند که مشکل Tsirelson غلط است، که به دلیل کار قبلی، به این معنی است که گره‌های تعبیه حدس نیز غلط هستند. برای محققان در این زمینه‌ها، شگفت‌انگیز بود که پاسخ به چنین مشکلات بزرگی از مدرک به ظاهر نامرتبط در علوم کامپیوتر حذف شود.

ناواکوس، که در قبلی خود را در ارتباط با مشکل تسیرلسون و کونز که حدس را در کنار هم قرار داده بودند، نوشته بود: «اگر من مقاله‌ای ببینم که می‌گوید MIP * = re، فکر نمی‌کنم هیچ ربطی به کار من داشته باشد.» گفت « این برای من یک سورپرایز کامل بود.»

فیزیک‌دانان و ریاضی‌دانان کوانتومی تازه شروع به هضم برهان کرده‌اند. قبل از این کار، ریاضی‌دانان تعجب کرده بودند که آیا می‌توانند با تقریب ماتریس‌های نامتناهی با استفاده از ماتریس‌های بزرگ با ابعاد محدود به جای آن، از آن‌ها دور شوند. حالا، از آنجا که حدس و گمان‌های محاط شده اشتباه است، آن‌ها می‌دانند که نمی‌توانند.

اسلوفترا گفت: «نتیجه آن‌ها نشان می‌دهد که این غیرممکن است»

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

ناتاراجان گفت: «من شخصا ریاضیدان نیستم. من فرمولاسیون اصلی حدسیه تعبیه کان را خوب درک نمی‌کنم»

او و همکارانش پیش‌بینی می‌کنند که ریاضی دانان این نتیجه جدید را به زبان زمینه خود ترجمه خواهند کرد. ویدیک در یک پست بلاگ این اثبات را اعلام کرد و نوشت: «من شک ندارم که در نهایت نظریه پیچیده‌ای برای به دست آوردن نتایج صرفا ریاضی مورد نیاز نخواهد»

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

این مقاله توسط ربات ترجمه مقاله تخصصی ترجمیار و به صورت خودکار ترجمه شده و مورد بازبینی و ویرایش محدود انسانی قرار گرفته است.