ИИ подтвердил давно предполагаемый предел квантового преимущества
Искусственный интеллект доказал еще одну гипотезу, десятилетиями дожидавшуюся своего решения — подтвердил отсутствие квантового преимущества в целом классе задач.
Профессор Скотт Ааронсон из Техасского университета в Остине заинтересовался этим вопросом еще в 1999 году. На тот момент было точно известно, что квантовые компьютеры превосходят классические в решении алгоритма Шора для факторизации чисел. Но математики предполагали, что это преимущество дает скрытая структурированность исходных данных.
Ааронсон задался вопросом, могут ли квантовые компьютеры выигрывать и в обратном случае — когда в задаче почти нет структуры, зато много случайности. В 2011 году он и профессор Андрис Амбайнис из Латвийского университета предположили, что как минимум в одном случае ответ отрицательный, — но доказать этого не смогли.
Теперь при помощи модели Anthropic Fable 5.2 стартап Physical Superintelligence нашел доказательство этой гипотезы.
«Это очень четкий математический вопрос, у которого есть последствия для квантовых вычислений, и решать его было настолько трудно, что я сам от него отказался», — признается Амбайнис.
«Возможно, это один из [немногих] оставшихся давних открытых вопросов, за которые стоило браться», — говорит Дэвид Туртуреан, руководивший работой.
Переложили на язык математики
Задача в основе гипотезы Ааронсона–Амбайниса требует, чтобы компьютер ответил на вопрос «да» или «нет», получив огромную, но случайную строку битов. Может ли квантовый компьютер получить ответ, просматривая строку намного меньшее число раз, чем понадобилось бы обычному? Авторы гипотезы предположили, что классический компьютер справился бы с задачей не хуже квантового.
Это свое предположение они выразили в виде математических формул — что породило к нему дополнительный интерес.
«Мы не думали, что это так подхватят. Заинтересовались люди, которые были светилами в своих областях и не интересовались квантовыми вычислениями», — замечает Ааронсон.
Анализ PSI опирается на работы таких математиков. По словам Туртуреана, модели Fable 5.2 понадобилось около четырех дней, чтобы написать доказательство, дважды его улучшить и уточнить, а затем проверить финальную версию в коде Lean.
По просьбе PSI работу ИИ изучили живые математики. «Доказательства совершенно другие — и значительно более трудные. Все еще и связано друг с другом совершенно необычным образом», — прокомментировали они.
Что дальше
Профессор Шахар Ловетт из Калифорнийского университета в Сан-Диего, чья работа была одной из важнейших составляющих доказательства, считает его полезным больше для математиков, нежели для физиков, работающих с квантовыми компьютерами.
Практические последствия решения сомнительны, согласен Ааронсон: «Это закрывает потенциальное направление поиска квантовых ускорений, но оно и так не было перспективным».
Взамен встает другой вопрос — где искать новые задачи, в которых квантовые компьютеры действительно окажутся непревзойденными. По мнению профессора, многие вопросы квантовой информатики, которые лучше всего решать математикой, уже закрыты с помощью ИИ, так что пора формулировать новые.
Для этого и появился PSI, заверил один из его основателей Мэтью Пайнс. Будущее покажет, насколько компания преуспеет в этом.
«Нужен серьезный творческий скачок. Думаю, ИИ это пока не под силу», — подытожил Амбайнис.
