Вариационные алгоритмы: VQE и QAOA

Первый квантовый компьютер с 50 кубитами появился в 2017 году. Через шесть месяцев исследователи Гарварда опубликовали статью: точный расчёт энергии H2 на квантовом железе IBM. Использовали два кубита и сорок строчек Python. Результат отличался от точного значения на 0.01%. Это сделал не специальный 'химический' алгоритм, а простой шаблон: подготовить состояние короткой схемой, измерить, оптимизировать на ноутбуке. Шаблон называется VQE и стал главным рабочим инструментом NISQ-эпохи.

• **IBM Quantum**: VQE для расчёта энергии BeH2 на 12 кубитах (2017) - первая публикация о квантовой химии на железе
• **Google AI**: QAOA на 23 кубитах для Max-Cut на 23-вершинных графах (2020) - демонстрация масштабирования
• **JPMorgan Chase**: исследовательский pilot QAOA для оптимизации портфелей - не для продакшна, но для прокачки команды на квантовых концепциях
• **Volkswagen + D-Wave**: вариационная оптимизация маршрутов такси в Лиссабоне - бенчмарк, без коммерческого преимущества над классикой

VQE: Variational Quantum Eigensolver

В 2014 году Алан Аспуру-Гузик и Питер Лав опубликовали алгоритм, обходящий главную проблему ранних квантовых методов химии: phase estimation требовал миллионов идеальных гейтов, недостижимых на NISQ-устройствах. **VQE** разделяет задачу на две части. Квантовый процессор готовит пробное состояние `|psi(theta)>` короткой параметризованной схемой и измеряет среднее `<psi(theta)|H|psi(theta)>` для гамильтониана H. Классический оптимизатор обновляет параметры theta. Вариационный принцип гарантирует: минимум этого среднего - верхняя граница для основной энергии E0. Никакой phase estimation; глубина схемы ограничена когерентным временем железа.

Гамильтониан молекулы раскладывается в сумму операторов Паули: H = sum_i c_i * P_i, где P_i - тензорные произведения {I, X, Y, Z}. Каждый член P_i измеряется отдельно (разные базисы измерения), результаты складываются с весами c_i. Для молекулы H2 на минимальном базисе - 15 Паули-членов. Это делает VQE bottleneck-ом не количество гейтов, а количество измерений (shots): для химической точности 1 мЭВ требуется ~10^6 - 10^9 shots на оценку.

Главное препятствие VQE на масштабе - **barren plateaus**: для случайной инициализации параметров в глубокой схеме градиент экспоненциально малеет с числом кубитов, и оптимизатор застревает в плоской ландшафте. Это не баг конкретного оптимизатора, а свойство гильбертова пространства. Современные стратегии: structured initialization (начало рядом с известным решением), layer-wise training (поэтапное добавление слоёв), problem-inspired ansaetze (UCCSD для химии).

QAOA: Quantum Approximate Optimization

**QAOA** (Эдвард Фархи, 2014) - вариационный алгоритм для комбинаторной оптимизации. Задача формулируется как минимизация булевой функции, переписывается в гамильтониан Изинга: H_C = sum_ij J_ij Z_i Z_j + sum_i h_i Z_i. Алгоритм чередует два унитарных оператора p раз: U_C(gamma) = exp(-i*gamma*H_C) - 'фазовый оператор' закладывает информацию о целевой функции; U_B(beta) = exp(-i*beta*sum_i X_i) - 'смешивающий оператор' исследует соседние конфигурации. Параметры (gamma_1, beta_1, ..., gamma_p, beta_p) оптимизируются классически по среднему <H_C>. При p -> infinity QAOA сходится к точному решению (адиабатическая теорема); при малых p даёт хорошее приближение.

Канонический пример - Max-Cut: дан граф, найти разрез вершин на два множества, максимизирующий число рёбер между ними. Гамильтониан: H_C = sum_{(i,j) in E} (1 - Z_i Z_j) / 2. QAOA p=1 для регулярных графов даёт коэффициент аппроксимации 0.6924, что лучше наивной случайной разметки (0.5), но хуже классического алгоритма Гёманса-Уильямсона (0.878). Превосходство QAOA над лучшим классическим алгоритмом до сих пор не показано ни для одной задачи - это открытый вопрос.

Эмпирически QAOA параметры (gamma, beta) часто переносятся с маленьких задач на большие: оптимальные значения для p=1 на графе из 6 вершин остаются близкими к оптимальным для 100 вершин на схожих графах. Это позволяет тренировать на классически решаемых instances и применять на квантово-интересных размерах без полной оптимизации.

Общая вариационная схема и измерение значений

VQE и QAOA - частные случаи общей вариационной схемы. Любой variational quantum algorithm состоит из трёх блоков: (1) параметризованная схема U(theta) на квантовом железе; (2) измерение целевой функции - чаще всего ожидание гамильтониана <psi(theta)|H|psi(theta)>; (3) классический оптимизатор обновляет theta для минимизации. Структура и есть универсальный фреймворк NISQ-эпохи: квантовое железо даёт то, что классически дорого (контролируемая суперпозиция, запутанность), классическое - то, что квантово дорого (gradient descent, line search).

Оценка градиента в variational алгоритмах: **parameter-shift rule** даёт точный градиент через измерения. Для rotation-гейтов вида exp(-i*theta*P/2): dE/dtheta = (E(theta + pi/2) - E(theta - pi/2)) / 2. То есть, чтобы получить градиент по одному параметру, нужно дважды запустить ту же схему с разными значениями theta. Для схемы с n параметрами - 2n запусков. Это делает gradient descent дорогим, но реализуемым.

Альтернатива градиентным методам - **SPSA** (Simultaneous Perturbation Stochastic Approximation): оценивает градиент стохастически за 2 квантовых запуска вместо 2n. Точность ниже, но при шумных измерениях SPSA часто оказывается практичнее точного градиента, потому что разница между noisy gradients за n шагов и noisy SPSA за 1 шаг почти не различима, а вычислительная стоимость падает в n раз.

Гибридный цикл и практические ограничения

Вариационный цикл выполняется в чередовании двух сред: квантовый процессор готовит и измеряет состояния, классический хост агрегирует измерения и принимает решения по обновлению параметров. На практике это означает сетевой round-trip между классическим контроллером и QPU за каждый шаг оптимизации. Современные QPU поддерживают пакетную отправку схем (batch jobs), но всё равно итерации идут со скоростью нескольких десятков в минуту - на порядки медленнее CPU-вычислений. Это устанавливает практический лимит: классическая оптимизация должна сходиться за ~100-1000 шагов, иначе суммарное время сделает алгоритм непригодным.

Шум квантового железа меняет ландшафт оптимизации. Шумная оценка энергии E_noisy(theta) - это не E(theta) + Gaussian, а сложное искажение, зависящее от theta. Минимум E_noisy может отличаться от минимума E. Стратегия mitigation: zero-noise extrapolation (запуск на разных уровнях шума с экстраполяцией к нулю), probabilistic error cancellation (применение обратного канала). Это удорожает каждую оценку в 5-50 раз, но критично для приемлемой точности на современном железе.

Где сегодня реально применяется VQE/QAOA: (1) бенчмарки и обучение алгоритмов на железе - доказательство-концепции для химических молекул H2, LiH, BeH2; (2) MaxCut и SAT в финансовой оптимизации портфелей (D-Wave, Quantinuum); (3) исследовательские задачи материаловедения. Production-выигрыша над классическими методами пока нет ни в одном применении, но и фундаментального запрета на quantum advantage в этих задачах не доказано.

Ключевые идеи

• **VQE** оценивает основную энергию гамильтониана через короткую параметризованную схему U(theta) + классическую минимизацию <psi(theta)|H|psi(theta)>; обходит требования phase estimation к когерентности
• **QAOA** - вариационный алгоритм для комбинаторной оптимизации с проблемно-заданным ansatz: чередование exp(-i*gamma*H_C) и exp(-i*beta*H_M), сходимость к точному решению при p -> infinity
• **Parameter-shift rule** даёт точный градиент через 2 запуска на параметр; SPSA - стохастическая альтернатива с 2 запусками независимо от размерности
• **Bottleneck NISQ-вариационных алгоритмов**: шум, ограниченное число shots, barren plateaus, время на одно evaluation; quantum advantage над классикой пока не показано

Связанные темы

Variational алгоритмы пересекаются с несколькими областями за пределами чистой квантовой механики:

• Квантовая коррекция ошибок — Quantum error mitigation для VQE/QAOA - облегчённая версия full error correction; цель та же, но без оверхеда логических кубитов
• Классическая оптимизация — VQE/QAOA опираются на SPSA, COBYLA, gradient descent с adaptive learning rate - тот же инструментарий, что и в ML
• Адиабатическая квантовая вычислительная парадигма — QAOA - дискретизация адиабатического алгоритма; теорема об адиабатической эволюции обосновывает сходимость при p -> infinity

Вопросы для размышления

• Почему за десять лет исследований VQE/QAOA не было показано quantum advantage ни для одной практической задачи?
• Parameter-shift rule даёт точный градиент, но цена - 2n запусков. Какие компромиссы между точностью и стоимостью оценки градиента имеет смысл искать?
• Если бы у вас был доступ к 1000-кубитному NISQ-устройству на час - какую вариационную задачу вы бы запустили первой и почему?

Связанные уроки

• qc-12 — QAOA строится на Квантовых воротах и схемах
• qc-14 — VQE/QAOA - основа квантового машинного обучения
• opt-13 — Многокритериальная оптимизация и QAOA решают схожие задачи комбинаторики
• ml-09-gradient-descent — Вариационный подход аналогичен градиентному спуску в классике
• prob-04-bayes — Вероятностные измерения квантовых систем требуют Байесовского мышления
• la-01-vectors-intro