Декодер Рида-Соломона для квантового алгоритма DQI стоил около 1,9 миллиона гейтов Тоффоли. Схема, которую нашёл эволюционный поиск в новом исследовании, укладывается примерно в 140 тысяч, то есть в 13 с лишним раз дешевле на самой тяжёлой подзадаче. Никто не рисовал её вручную: варианты предлагала языковая модель Claude Mythos 5, а проверял и оценивал их независимый модуль. Модель не судила о собственной правоте, и в этом суть всей работы.

Работа вышла на arXiv 15 октября 2026 года под заголовком «Discovering state-of-the-art quantum circuits with large language models» (2610.22367). Авторы: Анди Гу (Гарвардский университет и программа Anthropic STEM Fellows), Алекс Кемени (Anthropic), Сюзанна Йелин и Михаил Лукин (Гарвард; Лукин также из QuEra Computing). Идея, которую они проверили: квантовую компиляцию можно доверить LLM, если отделить генерацию идей от проверки результата.

Что такое оценщик-управляемый поиск квантовых схем

Оценщик-управляемый поиск квантовых схем это метод, в котором языковая модель пишет программы, порождающие квантовые схемы, а отдельный модуль проверяет каждую программу на классическом симуляторе и считает её ресурсы. Схемы с лучшими показателями выживают и развиваются дальше.

Проблема, которую решает подход, известна. Обычная программа может посмотреть на промежуточное значение и пойти по нужной ветке. Квантовая схема так не умеет: вход может быть в суперпозиции, поэтому все ветки должны присутствовать в фиксированной последовательности операций, и каждая ветка добавляет стоимость. Вторая сложность это обратимость: промежуточные значения нельзя просто стереть, их нужно вычислить обратно, а до этого они занимают кубиты.

Ручная оптимизация таких подпрограмм дорога и медленна, а автоматические оптимизаторы до сих пор умели только переписывать готовую схему с сохранением поведения, то есть искали вариации одного и того же дизайна. Новый фреймворк стартует с пустой программы: модель сама выбирает алгоритм, представление данных и структуру схемы.

Как устроен эволюционный поиск

Кандидаты кодируются не последовательностями гейтов, а Python-программами, которые схемы строят. Функции, циклы и именованные регистры сохраняют структуру вычисления, поэтому одно концептуальное изменение может перестроить работу всей схемы, а не одного её участка.

Поиск построен на открытом фреймворке OpenEvolve, а предложения генерирует Claude Mythos 5. На старте модель получает только спецификацию задачи, описание модели схем и критерии корректности, после чего придумывает несколько разных семейств алгоритмов. Для декодера Рида-Соломона это были, например, расширенный алгоритм Евклида, алгоритм Берлекэмпа-Массея и декодер Петерсона-Горенштейна-Цирлера. Семейства развиваются параллельно, а лучшие находки периодически переносятся между ними, чтобы удачные идеи не запирались внутри одного подхода.

Внутри семейства варианты хранит архив MAP-Elites: он делит плоскость ресурсов «гейты Тоффоли против кубитов» на ячейки и сохраняет лучшую схему в каждой. Поэтому решение с большим числом гейтов, но малым числом кубитов не выбрасывается и может позже обогнать конкурентов.

Каждая итерация запускает новую сессию агента: он получает родительскую программу, отзыв оценщика, заметки о прошлых попытках и альтернативы из архива. Полную историю поиска модель не видит. Внутри сессии она может прогонять черновики, запрашивать у классического оракула значения нужной функции и делегировать подзадачи вспомогательным агентам, а заканчивается итерация отправкой новой версии программы.

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

Как проверяют корректность и считают стоимость

Проверка опирается на модель kickmix из работы Баббуша и коллег: обратимая классическая логика, диагональные фазовые гейты и измерения, которые позволяют очищать временные кубиты без обратного вычисления. Такие схемы эффективно симулируются на обычном компьютере: вместо 2^n амплитуд симулятор отслеживает битовую строку и фазу.

Для каждого входного состояния оценщик проверяет четыре вещи: выход совпал с целевым, нужные входы не изменились, все вспомогательные кубиты вернулись в ноль, фаза совпала точно. Если полный перебор невозможен, проверка идёт по случайным выборкам, и число испытаний k даёт статистическую гарантию: вероятность ошибки не превышает ln(1/δ)/k с доверием 1-δ.

Стоимость измеряется двумя числами: числом гейтов Тоффоли и пиковым числом кубитов. Гейты Тоффоли требуют дорогих магических состояний и определяют большую часть логической работы, а пиковое число кубитов задаёт размер логического процессора. Их произведение, TQ-стоимость, служит единой мерой для сравнения схем.

Три принципа, которые вывел поиск

Первый принцип: условная маршрутизация вместо условной арифметики. Наивный перевод ветвящегося алгоритма в квантовую схему делает отдельный контролируемый арифметический блок под каждую ветку. Найденные схемы поступают иначе: они маршрутизируют данные. Дешёвые контролируемые обмены расставляют значения по ролям, одно общее арифметическое ядро выполняет дорогую работу, а обратные обмены возвращают результаты на места. На типовом примере с двумя контролируемыми умножениями-сложениями это ровно вдвое сокращает число гейтов Тоффоли.

Второй принцип: восстанавливать историю ветвлений из самих данных. Обратный прогон условного обновления требует знать, какая ветка выполнялась, и наивная реализация копит стек истории, растущий с числом шагов. Но решения часто можно прочитать из текущего состояния регистров. Например, если регистр g на шаге j прибавляет бит b_j, умноженный на 2^j, то бит j итогового значения равен b_j, потому что накопленная сумма всегда меньше 2^j. Схема считывает этот бит при обратном вычислении, и стек не нужен.

Третий принцип: расходовать бюджет отказов. Большинство квантовых алгоритмов допускают малую вероятность ошибки, и этот допуск можно обменять на ресурсы. Редкие тяжёлые входы определяют худший случай по кубитам и гейтам, но если изолировать компоненты, которые их обслуживают (лишние итерации, ячейки стека, арифметические дорожки), то их можно не строить, согласившись на отказ на редких входах.

Флагманский результат: декодер для DQI

DQI, декодированная квантовая интерферометрия (decoded quantum interferometry), превращает задачи оптимизации в задачи декодирования классических кодов, исправляющих ошибки, а квантовая интерференция помогает отличать хорошие решения от плохих. Применение, на котором сосредоточились авторы, это пересечение полиномов (OPI), где DQI даёт сверхполиномиальное ускорение против известных классических алгоритмов. Внутри схемы нужен декодер Рида-Соломона, работающий на суперпозиции входов.

Предыдущая компиляция (Khattar и коллеги) использовала синхронизированный расширенный алгоритм Евклида: около 1,9 миллиона гейтов Тоффоли на решение для локатора. Поиск заменил его рекурсией Берлекэмпа-Массея, которая арифметически намного дешевле (примерно 140 тысяч гейтов), но перезаписывает промежуточные полиномы, а обратимой схеме их нужно где-то хранить.

Обход нашёлся в свободе самой задачи: локатор нужен только с точностью до ненулевого множителя, потому что корни полинома от масштаба не меняются. Схема переписывает обе ветки обновления так, что они делят один арифметический путь, а вытесненные значения восстанавливает из константных коэффициентов. В худшем случае стек истории занимал бы 35 записей (665 кубитов); найденная схема резервирует одну запись на 19 кубитов и допускает отказ на редких входах, вероятность которого под распределением DQI составляет примерно один случай на десять тысяч.

Полный декодер: 440 тысяч гейтов Тоффоли и 1837 кубитов против 5,1 миллиона и 1938 у бейзлайна, то есть 12-кратный выигрыш по TQ-стоимости. Вторая версия, для эрмитовых кодов, вообще не имела обратимой компиляции: наивная реализация оценивалась в 100 миллионов гейтов и 190 тысяч кубитов, а найденная схема укладывается в 930 тысяч гейтов и 2395 кубитов.

Модульная инверсия: divsteps стал обратимым

Модульная инверсия ищет число x такое, что произведение w и x даёт 1 по модулю простого p. Это центральная арифметическая подпрограмма для квантовых алгоритмов теории чисел, включая криптографические. Классический путь, расширенный алгоритм Евклида, требует делений; вариант divsteps заменяет их условными сложениями, вычитаниями и делениями пополам, но на каждом шаге перезаписывает состояние, а обратимой схеме нужно знать, какая из трёх операций выполнялась.

Найденная схема восстанавливает решения из текущих регистров. Обмены ролей опознаются по числу младших нулевых битов вспомогательного коэффициента, и около двух третей решений восстанавливаются простыми проверками. Оставшиеся случаи требуют более тонкого правила: бит решения равен биту j-1 величины, которая получается умножением обновлённого коэффициента g_v на обратный элемент q по модулю 2^j, где q это нечётная часть этого коэффициента. Модель сама сформулировала глобальный инвариант, на котором держится правило, и довела его до доказательства в приложении к статье.

Дальше в дело вступает бюджет отказов. При пороге хранения j=5 в стек попадает лишь 12,4% неоднозначных решений. Схема резервирует 60 записей вместо худших 263, и переполнение случается в 2,4 случаях на миллион инверсий. Ещё один лимит касается времени: худший случай требует 590 шагов, но остановки концентрируются в узком диапазоне, поэтому схема планирует 533 шага и проверяет завершение начиная с 499-го, позволяя отказ на редких выходах за окно.

Полная бенчмарк-схема модульной инверсии занимает 4 миллиона гейтов Тоффоли и 935 кубитов. Предыдущей обратимой компиляции не существовало: divsteps считался непрактичным для обратимых вычислений, и работа меняет этот статус.

Остальные задачи: от химии до калибровочных теорий

Оставшиеся пять задач из восьми показали тот же эффект в меньшем масштабе. Угол поворота для алгоритма HHL подешевел с 16 тысяч гейтов и 300 кубитов до 1348 гейтов и 115 кубитов, 32-кратный выигрыш по TQ. Кулоновский потенциал: с 6355 гейтов и 252 кубитов до 1140 и 142, почти 10-кратный выигрыш. Вычисление гауссовой функции с фиксированной точкой: с 24 тысяч и 362 до 1583 и 139, 39-кратный выигрыш. Таблица подстановок для кластера Fe2S2 в квантовой химии: с 55 тысяч и 139 до 15 тысяч и 126, четыре с лишним раза. Симуляция неабелевой решёточной калибровочной теории: с 1,3 миллиона и 1927 до 170 тысяч и 1859, почти 8-кратный выигрыш.

В каждой из этих задач найденная схема уменьшила и число гейтов, и число кубитов одновременно, а не разменяла одно на другое. Авторы подчёркивают: разрыв между бейзлайнами и найденными схемами показывает, что часть кажущейся дороговизны квантовой арифметики отражает ограничения существующих обратимых конструкций, а не самих алгоритмов.

Почему это важно

Работа продолжает линию эволюционного поиска, в которой LLM предлагает, а внешняя проверка отбирает. Так уже находили новые алгоритмы в комбинаторике и линейной алгебре, а родственные проекты применяют тот же принцип к квантовым кодам коррекции ошибок. Критерий применимости, который формулируют авторы, звучит так: где задача допускает выразительный интерфейс и дешёвую автоматическую проверку, тот же поиск может открыть новые алгоритмы.

Второе следствие касается криптографии. Модульная инверсия и обратимые арифметические примитивы это строительные блоки квантовых алгоритмов для теории чисел, и их удешевление напрямую влияет на оценки ресурсов для задач, связанных с криптоанализом. Одновременно это демонстрация того, что инструменты ИИ становятся частью пайплайна разработки квантового софта.

Смотрят авторы и дальше: алгоритм, логическая схема, код коррекции ошибок, магические состояния и физическая архитектура сильно определяют стоимость друг друга. Оценщик, который умеет протаскивать ошибки и ресурсы через все слои сразу, мог бы позволить LLM проектировать отказоустойчивый стек целиком, а не оптимизировать слои по отдельности.

Часто задаваемые вопросы

Это значит, что ИИ уже сам придумывает квантовые алгоритмы?

Частично. Задачи и спецификации написали люди, но внутри них модель свободно выбирала алгоритмы, представления данных и структуры схем, а в случае модульной инверсии предложила новую обратимую архитектуру. Корректность каждой идеи проверял независимый оценщик, поэтому ошибки модели отсекались автоматически, без участия человека.

Почему ресурсы измеряют именно гейтами Тоффоли и кубитами?

Гейты Тоффоли требуют дорогих не-клиффордовских ресурсов, магических состояний, и потому определяют значительную часть времени выполнения. Пиковое число кубитов задаёт размер логического процессора. Произведение этих величин даёт единую метрику для сравнения схем с разным балансом времени и места.

Схемы уже работают на реальном квантовом компьютере?

Нет, речь о логических схемах для эпохи отказоустойчивых вычислений. Например, полная схема модульной инверсии оценивается в 4 миллиона гейтов Тоффоли и 935 кубитов. Это проектные оценки ресурсов, но именно они определяют, какие алгоритмы станут практичными, когда железо дорастёт до нужного масштаба.

Итог

За одну работу эволюционный поиск с предложениями LLM и независимым оценщиком переписал восемь квантовых подпрограмм: в семи случаях снизились и гейты Тоффоли, и кубиты, а модульная инверсия через divsteps впервые получила практичную обратимую схему. Декодер DQI подешевел в 12 раз, а самая тяжёлая подзадача упала с 1,9 миллиона гейтов до 140 тысяч.

Главный вывод шире квантовой тематики: там, где есть автоматическая проверка, языковая модель может не только писать код, но и находить новые алгоритмические конструкции. Полный текст со всеми восемью задачами и деталями каждого семейства доступен на arXiv (arxiv.org/abs/2610.22367), а про то, как эволюционный поиск алгоритмов устроен изнутри, читайте в разборе «Что эволюционируют ИИ-агенты кода».