Искусственный интеллект помог доказать математическую гипотезу, которую учёные пытались решить почти два десятилетия. Результат устанавливает важное ограничение для квантовых компьютеров: при решении определённых задач на случайных данных они не смогут получать огромное преимущество перед обычными машинами. Четверо математиков уже изучили доказательство и подготовили подробное объяснение.
История началась с вопроса, который Скотт Ааронсон и Андрис Амбайнис поставили ещё в 2008 году. Учёные хотели понять, обязательно ли квантовому компьютеру нужны особые закономерности в данных, чтобы справляться с задачами гораздо быстрее классического. Математики подозревали, что без скрытого порядка добиться колоссального ускорения невозможно, но доказать предположение никак не удавалось.
Представим длинную последовательность из нулей и единиц. Компьютеру нужно изучить последовательность и ответить на определённый вопрос, например, обладает ли набор заданным свойством. Обычный алгоритм последовательно проверяет отдельные биты, а квантовый благодаря суперпозиции может обращаться к нескольким позициям одновременно. В некоторых задачах разница оказывается огромной: квантовому алгоритму хватает сравнительно небольшого числа обращений, тогда как классическому приходится проверять несравнимо больше данных.
Однако столь впечатляющее квантовое преимущество обычно появляется благодаря особому устройству задачи. В последовательности может скрываться повторяющийся рисунок или другая закономерность, которую квантовый алгоритм умеет находить. Ааронсон и Амбайнис предположили, что при отсутствии подобных особенностей обычный компьютер сможет приблизиться к результату квантового без чрезмерного увеличения числа обращений к данным.
Доказательство нашёл математик Дэвид Туртуреан с помощью исследовательской системы компании Physical Superintelligence (PSI). Разработчики подключили к собственной программной платформе закрытую модель Anthropic и поручили ей поиск решения. По информации PSI, уже на третий день система построила полное доказательство, а позднее дважды улучшила результат.
Ключ к решению нашёлся в математическом описании квантовых алгоритмов. Вероятность определённого ответа можно выразить формулой, которая зависит от значений входных битов. Исследователи доказали, что если вероятность заметно меняется при изменении данных, обязательно найдётся хотя бы один бит с достаточно сильным влиянием на результат. Последовательно проверяя наиболее важные биты, обычный алгоритм сможет приблизительно воспроизвести поведение квантового для подавляющего большинства входных последовательностей.
Главная тонкость касается самого понятия скорости. Математики сравнивают количество обращений к данным, а не время выполнения программы на реальном процессоре. Доказательство показывает, что число запросов классического алгоритма можно ограничить некоторой фиксированной степенью числа запросов квантового алгоритма при заданной точности. Полностью измерить затраты на вычисления такой подход не позволяет.
Разработчики проверили математические рассуждения с помощью Lean. Программа разбирает доказательство на отдельные логические шаги и проверяет, следует ли каждый вывод из заданных правил. Такой метод помогает обнаруживать ошибки, которые легко пропустить при чтении длинных математических выкладок. Однако компьютерная проверка не освобождает специалистов от необходимости убедиться, что формально доказанное утверждение точно соответствует исходной гипотезе.
За дополнительную проверку взялись Гай Бланк, Джордан Доктер, Кармен Штрассле и Ли-Ян Тан. Математики изучили найденное решение и подготовили 30-страничный разбор доказательства, разделив сложные рассуждения на четыре основных этапа. Авторы объяснили, как новая работа объединяет методы из разных разделов математики, и ради более понятного изложения отказались от некоторых строгих численных оценок первоначального результата.
Сам Скотт Ааронсон тоже прокомментировал решение гипотезы. Математик признал, что пока не разобрался во всех деталях, однако считает доказательство правильным. Уверенность ему придают машинная проверка и работа специалистов, которые уже изучили математические рассуждения.
Ааронсон отдельно предупредил, что открытие не ставит крест на квантовых вычислениях. Знаменитый алгоритм Шора, позволяющий квантовым компьютерам эффективно раскладывать большие числа на простые множители, по-прежнему сохраняет свои возможности. Математическое ограничение также не мешает использовать квантовые процессоры для моделирования молекул, химических реакций и физических процессов. Доказательство охватывает определённый класс задач с ответами «да» или «нет» и оценивает число обращений к данным.
Для математиков решение закрывает вопрос, который оставался открытым почти два десятилетия. Но история примечательна ещё и способом получения результата. Исследовательская система с ИИ сумела объединить известные математические идеи, построить новое доказательство и пройти формальную проверку. Теперь специалисты могут изучать готовое решение и выяснять, какие ещё задачи удастся решить тем же способом.