دانشمندان علوم کامپیوتر مرز «دانش تصدیق‌پذیر» را گسترش می‌دهند!

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

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

فوتینو

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

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

در مقاله‌ای که در ماه آوریل ۲۰۱۹ منتشر شد، ۲ دانشمند علوم رایانه، جان رایت و آناند ناتاراجان، به نحو بسیار زیاد، تعداد مسائلی که در سبد «دشوار برای حل کردن اما آسان برای راستی آزمایی» قرار می‌گیرند را افزایش دادند. آنها روشی را تعریف کردند که بررسی و صحت‌سنجی پاسخ‌های مسائل با درجه پیچیدگیِ تقریبا «درک نشدنی» را ممکن می‌سازد.

نتایج این پژوهش بر کامپیوترهای کوانتومی اعمال گردید. در واقع این شیوه جدید، به ما دستمایه‌ی قدرتمندی در برابر آن پیشگوی قدرتمند میدهد! یعنی حتی اگر آن پیشگوی کذایی وعده‌ی این را داده که پاسخهای مسائل فوق بشری را ارائه کند، با این پژوهش جدید، هنوز یک راه برای اطمینان یافتن از اینکه پیشگو صادق است یا کاذب وجود دارد.
هنگامی که یک مساله حل کردنش دشوار اما صحت‌سنجی راه حل آن آسان است، بدین معنی است که یافتن راه حل برای آن بسیار طولانی خواهد بود اما تصدیق اینکه راهکار ارائه شده صحیح است یا نه، امری نه چندان زمان‌بر است. در دهه ۱۹۷۰ دانشمندان کامپیوتر نام این دسته از مسائل را به اختصار «NP» نامیدند. از آن زمان، NP حریصانه ترین و متمرکزترین دسته از مطالعات علوم رایانه است.
در این پروژه، ناتاراجان و رایت همّ خود را معطوف به سناریویی کردند که شامل دو کامپیوتر کوانتومی مجزا و جدا از یکدیگر است که «کیوبیت»های در‌هم‌تنیده‌شده را با هم به اشتراک می‌گذارند.
ناتاراجان و رایت اثبات کردند که این وضعیت از تمام سناریوها برای اعتبار سنجی NPها بهتر و کارامدتر است. در واقع دسته‌ای بسیار وسیعتر از مسائل با استفاده از کامپیوترهای «در هم تنیده شده»، میتواند صدق سنجی شوند.
البته این ایده‌ی درخواست از خودِ رایانه‌ها برای صحت‌سنجی راه‌حل‌های ارائه شده توسط خودشان، به نظر احمقانه می‌آید! اما ناتاراجان و رایت اثبات کرده‌اند که ابدا چنین نیست. دلیلشان هم «درهم‌تنیدگی کوانتومی» است…

این نوشتار، چکیده ترجمه‌ای از مقاله زیر:

computer scientists expand the frontier of verifiable knowledge