سیستم تحقیق فیزیکال سوپراینتلیجنس (PSI) نخستین اثبات کامل و ماشین‌بررسی‌شده حدس آارونسون-آمباینیس را تحویل داد — یک مسئله محاسبه کوانتومی که از سال ۲۰۰۸ باز مانده بود. اثبات در لین ۴ (Lean 4) بدون هیچ جایگزین اثبات یا اکسیوم اضافه‌ای پذیرفته شد و از طریق بررسی‌های هسته‌ای مستقل تأیید گردید.
حدس آارونسون-آمباینیس و تفوق کوانتومی
حدس به پرسش بنیادین می‌پردازد: کامپیوترهای کوانتومی کی می‌توانند بر ماشین‌های کلاسیک تفوق نمایی کسب کنند؟ اسکات آارونسون و آندریس آمباینیس در ۲۰۰۸ پیش‌بینی کردند که هر چندجمله‌ای محدود و کم‌مرتبه متغیری با تأثیر بالا دارد. با این فرض، اثبات کردند هر الگوریتم کوانتومی با T پرسش روی اکثر ورودی‌ها با تعداد پرسش‌های چندجمله‌ای کلاسیک قابل شبیه‌سازی است — بنابراین تفوق نمایی برای مسائل بدون ساختار منتفی می‌شود. نتیجه PSI اکنون این حدس را با کران تأثیر صریح تثبیت می‌کند: اگر واریانس (variance) یک چندجمله‌ای مرتبه d حداقل اپسیلون باشد، مختصاتی وجود دارد با تأثیر حداقل (۸ ریشه ۱۵ / (۱۲۵ پی به توان ۴)) · اپسیلون به توان ۵/۲ / d⁶، و در نتیجه حداقل (اپسیلون بر d) به توان ۷.
نحوه ساخت و تأیید اثبات
اثبات بر برنامهٔ شاخر لوت و جیاپنگ ژانگ مبتنی است که از گواهی‌های کسری (fractional certificates) و مجموعه‌های سطح (level sets) استفاده می‌کرد. سیستم PSI نابرابری حدسی در آن برنامه را با یک نابرابری تمام‌جفتی (all-pairs inequality) جدید جایگزین کرد که از یک بیژکشن مبتنی بر دترمینان (determinant-based bijection) مشتق شده است. این جفتی‌سازی فراتر از لم پروانه‌ای رایمر (Reimer's Butterfly Lemma) می‌رود با محدود کردن تعداد توافق تنظیمات جفتی روی هر مختصات — کرانِ ضروری برای نابرابری جدید.
توسعه رسمی اثبات را به چهار بخش تقسیم می‌کند: استخراج نابرابری تمام‌جفتی از دترمینان و بیژکشن، یکپارچه‌سازی بر مجموعه‌های سطح، میانگین‌گیری بر مختصات، و برقراری کران سطر با کران حساسیت نقطه‌ای (pointwise sensitivity bound).
جزئیات فنی کلیدی:
- اعلان‌های مخزن از طریق هسته لین و lean4lean — یک پیاده‌سازی مستقلِ بررسی نوع — بازپخش شدند
- یک مقایسه‌گر sandboxed با استفاده از نانودا (nanoda) و هسته‌های لین، چهار تئورم نهایی را پذیرفت
- روی ماشین دوم، مقایسه‌گر یک راه‌حل کوچک صحیح را پذیرفت و چهار راه‌حل عمداً نادرست را رد کرد
- مقاله خوانا برای انسان خودِ ماشین‌بررسی‌شده نیست؛ هسته لین، کامپایلر، تعاریف مث‌لب (Mathlib) و ماشین‌های بررسی همچنان بخشی از پایه اعتماد (trusted base) هستند
نقش انسان‌ها و بازبینی کارشناسی
دیوید تورتورین از کادر فنی PSI سیستم تحقیق را توسعه و اجرا کرد، مسئله را محدود کرد، مدل را برای بسته‌بندی پیش‌نویس اول پرامپت کرد، و آن پیش‌نویس را برای صحت مرور نمود. مخزن فاش می‌کند که مدل‌های هوش مصنوعی عبارات ریاضی، پیش‌نویس اول، و رسمی‌سازی لین را تولید کرده‌اند. جیم هالورسون اثبات را حسابرسی کرد، و فیلیا شاناهان بر رسمی‌سازی نظر داد.
این اعلامیه پس از مقاله ۱۹ اوت ۲۰۲۶ گی بلان، جردان داکتر، کارمن استرااسل، و لی-یانگ تان می‌آید که پیامد شبیه‌سازی کلاسیک برای الگوریتم‌های کوانتومی موازی (parallel quantum algorithms) را حل کرد — اثبات کرد الگوریتم t-پرسش، d-دور روی اکثر ورودی‌ها با t^(O(d²)) پرسش کلاسیک قابل شبیه‌سازی است. چهار نویسنده تمام اثبات PSI را خوانده، نظر داده‌اند، و یک تشریح کوتاه‌تر برای کارشناسان در حال تدوین هستند.
در ارزیابی منتشرشده توسط PSI، محققان نوشتند: «این یک نتیجه عظیم است. یک حدس دهه‌ها را حل می‌کند با پیامدهای مهم برای ماهیت مسائلی که تفوق کوانتومی می‌پذیرند. اثبات بر چندین خط کار در تحلیل توابع بول و ترکیبیات احتمالاتی استوار است و به شکلی جادویی هم‌آهنگ شده‌اند.» این رویکرد به نتایج اخیر در مدل Mythos 5 پیوسته است که کاربردهای عملی کوانتوم را تسهیل می‌کند.
پیامدها برای محاسبه کوانتومی و تأیید رسمی
نتیجه مرز بین محاسبه کوانتومی و کلاسیک برای مسائل بدون ساختار را بازتعریف می‌کند. با تأیید اینکه تفوق نمایی کوانتومی نیازمند ساختار قابل استثمار است، جستجوی میدان برای مزیت کوانتومی را روی مسائل با ویژگی‌های جبری یا دوره‌ای خاص — مانند فاکتور کردن، لگاریتم‌های گسسته، و مسائل زیرگروه پنهان (hidden subgroup problems) — متمرکز می‌کند، نه توابع جعبه‌سیاه عمومی.
برای تأیید رسمی، این دستاورد نشان می‌دهد که سیستم‌های هوش مصنوعی اکنون می‌توانند نه تنها اسکچ اثبات بلکه رسمی‌سازی‌های کامل و هسته‌تأییدشده در لین ۴ بدون ترم‌های اثباتِ نوشته‌شده توسط انسان تولید کنند. تقسیم کار تیز است: هسته‌های مستقل استدلال کدشده را تأیید می‌کنند، در حالی که کارشناسان انسانی همچنان باید تأیید کنند که بیان رسمی با حدس اصلی هم‌خوانی دارد و تشریح غیررسمی مقاله را ارزیابی کنند.
گام بعدی شما
- مخزن عمومی لین ۴ و مقاله را برای مرور مستقل بررسی کنید
- تشریح کارشناسی آتی بلان، داکتر، استرااسل، و تان را برای درک هسته ترکیبیاتی اثبات رصد کنید
- پیامدهای این کران تأثیر صریح را برای طراحی الگوریتم‌های کوانتومی جدید ارزیابی نمایید
گفتگو