Исследовательская компания PSI решила гипотезу Ааронсона-Амбаиниса, остававшуюся нерешенной 18 лет. Для генерации математического доказательства платформа использовала закрытую модель Anthropic и собственную инфраструктуру, затратив на работу три дня.
Полученный результат прошел проверку в системе Lean, предназначенной для верификации логической корректности рассуждений. После первичной проверки система дважды дорабатывала вывод до финального состояния. Гипотеза, сформулированная в 2008 году, описывает условия, при которых квантовые компьютеры обеспечивают экспоненциальное ускорение.
Доказательство показывает, что для ряда алгоритмов классическим компьютерам достаточно полиномиального роста ресурсов вместо экспоненциального. Это ограничение касается только определенных классов задач и не затрагивает специализированные решения, такие как алгоритм Шора для факторизации чисел.
Работа прошла предварительную экспертизу в Стэнфордском университете, где в августе ученые доказали частный случай этой гипотезы. Специалисты готовят сокращенное изложение доказательства для экспертного сообщества, чтобы подтвердить соответствие формализованной версии исходной математической постановке задачи.
