Квантовый компьютер не сможет экспоненциально обогнать обычный при решении задач, где входные данные почти случайны и лишены особой математической структуры. Это не просто очередное ограничение — это доказательство, полученное искусственным интеллектом.
В ноябре 2026 года стартап Physical Superintelligence (PSI) в США объявил о доказательстве гипотезы, которую в 2011 году сформулировали Скотт Ааронсон из Техасского университета в Остине и Андрис Амбайнис из Латвийского университета. Гипотеза утверждала: для полиномов низкой степени, принимающих значения от 0 до 1 на булевом кубе, всегда найдётся переменная с заметным влиянием. Доказательство нашла внутренняя исследовательская система PSI на основе непубличной модели Anthropic. Полный текст прошёл проверку в системе Lean, а экспозицию подготовили исследователи Стэнфорда — Гай Бланк, Джордан Доктер, Кармен Страссл и Ли-Ян Тан.
Система работала четыре дня: сначала получила полное доказательство, затем дважды его улучшила, и каждый вариант Lean принял без ошибок. Это не эксперимент на квантовом процессоре, а чисто математическое доказательство в области теории сложности запросов. Оно показывает, что квантовый алгоритм, делающий T запросов к входу, можно с высокой точностью смоделировать классически на большинстве случайных входов, используя лишь полиномиальное число запросов.
Представьте огромный склад с миллиардами ящиков, где нужный предмет лежит в случайном месте без подсказок. Классический поиск перебирает ящики один за другим. Квантовый мог бы, казалось, заглянуть во все сразу — но доказательство показывает, что без особой структуры, как в алгоритме Шора для факторизации, такое «взглядывание» даёт лишь полиномиальное ускорение, а не экспоненциальное. Влияние одной переменной в полиноме гарантирует, что случайный вход почти всегда можно предсказать по малому числу битов.
Результат меняет представления о границах квантового превосходства. Теперь ясно: для задач без встроенной структуры — случайных графов, случайных функций — экспоненциального выигрыша ждать не стоит. Квантовые компьютеры сохраняют преимущество там, где структура есть, как в криптографии или оптимизации с особыми свойствами. Практическое строительство устройств это не отменяет, но направляет усилия на поиск именно таких структурированных задач.
Статья в New Scientist от 12 ноября 2026 года и препринт на arXiv от 8 ноября подробно описывают ход доказательства и его следствия для соотношения классов BPP и BQP в мире случайных оракулов.
Квантовое превосходство теперь чётче очерчено: оно реально, но требует не случайности, а скрытой закономерности.


