حدس Aaronson-Ambainis با کمک هوش مصنوعی اثبات شد
خلاصهٔ کاملتر
تیم Physical Superintelligence (PSI) اعلام کرده که حدس Aaronson-Ambainis حالا یه قضیهٔ اثباتشدهست. این حدس رو Scott Aaronson و Andris Ambainis سال ۲۰۰۸ مطرح کردن و یکی از مسئلههای اصلی نظریهٔ پیچیدگی کوانتومی حساب میشد. به گفتهٔ PSI، اثبات رو یه سیستم تحقیقاتی داخلی پیدا کرده که روی زیرساخت خودشون و با چند نمونه از یه مدل غیرعمومی Anthropic اجرا شده.
سؤال اصلی این بود: کامپیوتر کوانتومی کِی میتونه نمایی سریعتر از کامپیوتر معمولی باشه؟ مثلاً الگوریتم Shor (سال ۱۹۹۴) اعداد بزرگ رو خیلی سریع تجزیه میکنه، ولی فقط چون مسئله یه الگوی تکرارشونده داره. حالا ثابت شده که روی ورودیهای تصادفی، کامپیوتر کوانتومی در بهترین حالت فقط بهصورت چندجملهای (polynomial، یعنی نه نمایی) سریعتره. یعنی برتری بزرگ کوانتومی بدون ساختار خاص تو ورودی وجود نداره.
سرعت رو اینجا با تعداد «نگاه» میسنجن، یعنی چند بار کامپیوتر باید رشتهٔ ورودی از 0 و 1 رو بخونه. قبلاً ثابت شده بود که احتمال «بله» گفتن کامپیوتر کوانتومی بعد از T نگاه، یه چندجملهای با درجهٔ حداکثر 2T هست که مقدارش بین 0 و 1 میمونه. حدس میگفت تو چنین چندجملهایای همیشه یه بیت هست که influence بالایی داره، یعنی عوض کردنش بهطور میانگین مقدار رو حسابی جابهجا میکنه. با این ضمانت، کامپیوتر معمولی میتونه رفتار کامپیوتر کوانتومی رو با تعداد نگاه نهچندان بیشتر تقلید کنه.
طبق مقاله، سیستم روز سوم اجرا یه اثبات کامل داشت و Lean (یه proof assistant که کامپیوتر توش تکتک قدمها رو چک میکنه) قبولش کرد. بعد سیستم دو بار نتیجه رو بهتر کرد. کران نهایی میگه influence یه بیت حداقل حدود (v/d)^7 هست که v واریانس و d درجهٔ چندجملهایه. اثبات روی طرح Shachar Lovett و Jiapeng Zhang ساخته شده و یه نامساوی جدید جای بخش حدسی اون طرح رو گرفته. برای این نامساوی هم از ایدهٔ Butterfly Lemma دیوید ریمر استفاده شده.
تیمی از Stanford که آگوست ۲۰۲۶ یه حالت خاص از همین حدس رو ثابت کرده بودن، حالا دارن اثبات کامل رو میخونن و یه نسخهٔ کوتاهتر براش مینویسن. اونا این نتیجه رو «خیلی بزرگ» توصیف کردن که یه حدس قدیمی و مهم رو حل میکنه. مسئولیت درستی مقاله با David Turturean هست که سیستم رو ساخته و اجرا کرده.
نکات کلیدی:
- حدس Aaronson-Ambainis از سال ۲۰۰۸ باز بود و حالا اثبات شده.
- نتیجه: روی ورودی تصادفی، برتری کوانتومی فقط چندجملهایه، نه نمایی.
- اثبات رو سیستم PSI با یه مدل غیرعمومی Anthropic تو روز سوم اجرا پیدا کرد.
- ابزار Lean نسخهٔ نهایی اثبات رو تأیید کرده.
- کران نهایی: influence یه بیت حداقل (v/d)^7 هست.




