ИИ-система на модели Anthropic доказала гипотезу о квантовом ускорении
Система стартапа PSI доказала гипотезу о пределах квантовых компьютеров, не решённую с 2008 года. Соавтор гипотезы Скотт Ааронсон считает доказательство верным.
Исследовательская система стартапа Physical Superintelligence1 (PSI) на непубличной модели Anthropic нашла доказательство гипотезы Ааронсона — Амбайниса. Эту задачу теории квантовых вычислений не могли решить с 2008 года. Доказательство приняла программа Lean, в которой компьютер проверяет каждый шаг рассуждения.
Почему это важно: гипотеза отвечает на один из базовых вопросов отрасли: может ли квантовый алгоритм в задаче с ответом «да» или «нет» обойтись экспоненциально меньшим числом обращений к данным, чем обычный, если в данных нет скрытой закономерности. По словам соавтора гипотезы Скотта Ааронсона, математики и аспиранты строили вокруг неё целые исследовательские программы. Одна из попыток доказательства, которую он разбирал в блоге в 2019 году, оказалась ошибочной.
Повод: PSI объявила о результате 6 ноября. В тот же день она выложила на arXiv препринт на 60 страниц, а на GitHub — запись доказательства для Lean. Единственный автор статьи — сотрудник стартапа Дэвид Туртуреан: он собрал систему, поставил ей задачу и запустил работу. Над задачей трудились сразу несколько экземпляров модели. Полное доказательство появилось на третий день. Потом систему направили на смежные открытые задачи, и по пути она дважды усилила результат. Теорема гарантирует: если вероятность ответа «да» у квантового алгоритма меняется от входа к входу, то хотя бы от одного элемента входных данных она зависит заметно. Насколько заметно, задаёт числовая нижняя граница — её система и подняла. Итоговую версию Lean тоже принял. Рецензирование препринт пока не прошёл.
Детали: ещё в исходной работе Ааронсон и Амбайнис показали, что следует из гипотезы. Возьмём квантовый алгоритм, который решает задачу с ответом «да» или «нет» и обращается к входным данным определённое число раз. Вероятность того, что он ответит «да», почти на всех входах можно приближённо вычислить и на обычном компьютере. Обращений к данным для этого понадобится больше, но их число растёт полиномиально, то есть как степень от числа обращений квантового алгоритма, а не экспоненциально. Значит, выигрыш больше степенного, в том числе экспоненциальный, возможен, только если у данных есть структура: например, заранее известно, что вход устроен определённым образом. Доказательство опирается на план математиков Шахара Ловетта и Цзяпэна Чжана. Недостающее в этом плане неравенство система заменила новым и доказала.
Что говорят: 8 ноября Ааронсон написал в своём блоге, что сам в доказательстве ещё не разобрался, но верит ему: его принял Lean, а эксперты-люди уже его разобрали и поняли. Со слов PSI он называет модель «внутренней моделью Claude». Какую роль сыграла она, а какую — обвязка стартапа, то есть управляющая моделью программная надстройка, Ааронсон, по его словам, не знает. Он признаётся, что «разочарован, что люди не успели ухватить эту гипотезу раньше роботов», хотя за несколько лет они почти наверняка справились бы. Группа Ли-Ян Тана из Стэнфорда, которая в августе доказала частный случай гипотезы, назвала работу PSI «огромным результатом»; эти слова опубликовал сам стартап.
«Я больше не эксперт по собственной гипотезе»
Скотт Ааронсон, теоретик квантовых вычислений, соавтор гипотезы
Но: выводы из результата легко преувеличить. Исследователь ИИ Педро Домингос из Вашингтонского университета написал в соцсети X, что теперь «мечта о квантовом превосходстве2 мертва». Ааронсон возразил: доказательство исключает лишь один вид превосходства — в задачах с ответом «да» или «нет» на случайных входах. Что такого превосходства нет, и так предполагали. На алгоритм Шора3 для разложения чисел на множители и на моделирование физики и химии результат, по словам Ааронсона, «не влияет никак». К тому же теорема ограничивает только число обращений к данным, а не полное время вычислений, отмечает издание The Quantum Insider.
Сооснователь Anthropic Джек Кларк, чья компания сделала модель, написал в своей рассылке Import AI4, что мир уже на ранней стадии сингулярности. Так он называет период, «когда технологический и научный прогресс идёт быстрее, чем мы, люди, успеваем его разобрать и осмыслить», и работу PSI он считает тому примером. Ааронсон в своём посте признаётся, что «устал от бесконечных чудес из пещеры Аладдина» — решений давних открытых задач, которые неизвестно когда удастся переварить.