Искусственный интеллект решил 18-летнюю проблему квантовых вычислений — результат проверили в Lean
- PSI заявила, что решила гипотезу Ааронсона—Амбаиниса, сформулированную в 2008 году, за три дня с помощью модели Anthropic и собственной инфраструктуры.
- Доказательство прошло проверку в Lean и две доработки; результат ограничивает квантовое ускорение определённым классом алгоритмов, но не затрагивает алгоритм Шора.
- Работа прошла предварительную экспертизу в Стэнфорде; для подтверждения соответствия формальной версии исходной задаче нужна независимая академическая рецензия.
Почему это важно: Уточнение границы между полиномиальной и экспоненциальной сложностью помогает понять, почему некоторые квантовые протоколы не дают ожидаемого ускорения даже при наличии подходящего оборудования.
Исследовательская компания PSI объявила о решении 18-летней гипотезы Ааронсона-Амбаиниса за три дня. Платформа использовала закрытую модель от Anthropic и собственную инфраструктуру для генерации математического доказательства. Полученный результат был принят в Lean (инструмент проверки логической корректности формальных рассуждений), после чего система дважды доработала вывод до финальной версии.
Гипотеза, сформулированная в 2008 году, определяет условия, при которых квантовые компьютеры способны обеспечить экспоненциальное ускорение по сравнению с классическими. В частности, она касается вопроса о том, можно ли эффективно аппроксимировать алгоритмы со специфической математической структурой на обычном оборудовании. Если утверждение верно, то для широкого класса квантовых задач классическим компьютерам потребуется лишь полиномиальный рост ресурсов (когда затраты увеличиваются предсказуемо) вместо экспоненциального (когда они умножаются на себя) при увеличении масштаба задачи.
Доказательство не означает исчезновение преимуществ квантовых технологий. Оно ограничивает область применения только определённым классом алгоритмов, оставляя нетронутыми специализированные решения, такие как алгоритм Шора для факторизации больших чисел. Уточнение границы между полиномиальной и экспоненциальной сложностью помогает понять, почему некоторые квантовые протоколы не дают ожидаемого скачка производительности даже при наличии соответствующего аппаратного обеспечения.
Работа прошла предварительную экспертизу в Стэнфордском университете*, где группа учёных ранее в августе доказала частный случай этой гипотезы. Университетские специалисты прокомментировали результаты и готовят сокращённое изложение полного доказательства для экспертного сообщества. Lean гарантирует внутреннюю непротиворечивость выводов, однако полная независимая академическая рецензия необходима для подтверждения того, что формализованная версия точно отражает исходную математическую постановку задачи.
Компания PSI, запущенная как платформа для автоматизации научных открытий, продемонстрировала способность автономных систем справляться с фундаментальными проблемами теории вычислений. Успешная верификация требует дальнейшего анализа со стороны мирового сообщества, но результат уже формирует новый стандарт взаимодействия между нейросетевыми моделями и строгой математикой.
© iXBT
