Гипотеза Ааронсона — Амбайниса решена за три дня, утверждают авторы

Компания Physical Superintelligence (PSI) заявила о решении 18-летней математической проблемы — гипотезы Ааронсона — Амбайниса, которая касается условий экспоненциального преимущества квантовых алгоритмов по числу обращений к входным данным

Гипотеза, впервые предложенная в 2008 году, касается числа обращений к входным данным при имитации квантовых алгоритмов классическими. Если гипотеза верна, классический алгоритм может приближённо предсказать вероятность ответа «да» квантового алгоритма для почти всех случайных входных строк. Число обращений к данным при этом зависит полиномиально от числа обращений квантового алгоритма.

Система PSI использовала непубличную модель от Anthropic и работала на собственной инфраструктуре компании. Доказательство было принято программой Lean — помощником для проверки логической корректности математических аргументов. Затем система дважды улучшила доказательство, и Lean принял финальную версию.

Пока результат не прошёл полную независимую академическую проверку. Исследователи из Стэнфордского университета изучили некоторые аспекты работы и предоставили обратную связь, однако для подтверждения решения гипотезы потребуется более широкое рассмотрение.

PSI описывает себя как компанию, занимающуюся физическими исследованиями и создающую автоматизированные системы для научных открытий.

Ранее по теме: Частоту ошибок в кубите снизили более чем вдвое

Источник: Interesting Engineering