Квантовая оптимизация

Оптимизация маршрутов доставки для 50 городов - классические методы работают часами. Конфигурация белковой молекулы с 200 атомами - классический компьютер не справится никогда. Квантовые компьютеры обещают атаковать эти задачи принципиально иначе - через физику суперпозиции и туннелирования. Где реальность, а где хайп?

• **Volkswagen и D-Wave**: оптимизация трафика в Лиссабоне для 1000+ автобусов через QUBO на D-Wave - квантовый отжиг нашёл решения за секунды, сравнимые с SOTA классикой
• **IBM Quantum для химии**: VQE для расчёта энергии молекулы FeMoco (железо-молибденовый кофактор нитрогеназы) - понимание этого белка может революционизировать производство удобрений
• **Google Sycamore**: в 2023 году показал квантовое преимущество в задаче Random Circuit Sampling - первый эмпирически подтверждённый пример, хотя практической задачей не является

QAOA: гибридный квантово-классический алгоритм

**QAOA** (Quantum Approximate Optimization Algorithm, Farhi et al. 2014) - алгоритм для решения комбинаторных задач оптимизации на NISQ (Noisy Intermediate-Scale Quantum) компьютерах. Идея: закодировать задачу в гамильтониан H_C, чередовать квантовые эволюции по H_C и H_B, а параметры (γ, β) оптимизировать классически.

QAOA - **вариационный** алгоритм: мы параметризуем семейство квантовых состояний и оптимизируем параметры. Это гибридная архитектура: квантовый компьютер готовит состояние и измеряет ожидание, классический оптимизатор (Nelder-Mead, SPSA, gradient-based) обновляет параметры (γ, β). Такой подход называют VQA - Variational Quantum Algorithm.

**Barren plateau** - проблема: для случайных инициализаций параметров глубоких VQA градиент экспоненциально мал в числе кубитов n. Ожидание градиента: E[∂C/∂θ] = 0, дисперсия ∝ 2⁻ⁿ. Градиентный спуск становится случайным блужданием. Это аналог vanishing gradient для квантовых схем. Решения: локальная инициализация, специальная структура ансаца, graduated learning.

VQE: поиск основного состояния через вариационный принцип

**VQE** (Variational Quantum Eigensolver, Peruzzo et al. 2014) - квантово-классический алгоритм для нахождения минимального собственного значения (основного состояния) гамильтониана. Главное приложение - квантовая химия: энергия молекулы = минимальное собственное значение молекулярного гамильтониана. На классических компьютерах это exponentially hard; VQE использует квантовый компьютер для оценки энергии.

Для молекулы с N орбиталями гильбертово пространство имеет размер 2^N. Классическая точная диагонализация требует O(4^N) операций - для N=50 это 10^30 операций, недостижимо. VQE использует квантовый компьютер с N кубитами, оценивая E(θ) за O(poly(N)) квантовых операций. Главный вопрос: насколько хорош ансац? Если он не охватывает истинное основное состояние, VQE найдёт только локальный минимум в пространстве ансаца.

Квантовый отжиг: D-Wave и туннелирование

**Квантовый отжиг (Quantum Annealing, QA)** - физически иной подход к оптимизации. Вместо gate-based квантовых вычислений, система физически реализует гамильтониан задачи в супрапроводящих кубитах. Система эволюционирует от простого начального гамильтониана к задачному, используя **квантовое туннелирование** для пересечения энергетических барьеров.

QUBO (Quadratic Unconstrained Binary Optimization): min x^T Q x, x ∈ {0,1}^n. Это стандартный формат для D-Wave. В QUBO можно закодировать: Max-Cut, TSP, portfolio optimization, protein folding, логистические задачи. Ограничения добавляются как штрафы: Ax = b → +λ‖Ax-b‖² в objective. Сложность embedding задачи в граф D-Wave - часто NP-hard сама по себе (minor embedding problem).

Когда квантовая оптимизация выигрывает

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

Честный ответ на 2026 год: **квантовая оптимизация - это будущее, но ещё не настоящее** для большинства практических задач. NISQ устройства слишком шумные для circuit глубины, нужной реальным задачам. Тем не менее VQE уже даёт результаты в квантовой химии, недоступные классике. Область быстро развивается: Google, IBM и IonQ конкурируют за fault-tolerant milestone.

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

• **QAOA**: гибридный алгоритм - квантовый компьютер оценивает ⟨H_C⟩, классический оптимизирует параметры (γ,β); для Max-Cut и других QUBO задач
• **VQE**: вариационный принцип на квантовом компьютере для основного состояния гамильтониана; главное приложение - квантовая химия
• **Квантовый отжиг (D-Wave)**: физическая аналоговая эволюция через туннелирование; специализированное железо для Ising/QUBO задач
• **Квантовое преимущество** для оптимизации - всё ещё открытый вопрос; на 2026 год NISQ ограничен малыми задачами; fault-tolerant QC ~2030+

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

Квантовая оптимизация объединяет квантовую физику с классической теорией сложности:

• Байесовская оптимизация — QAOA параметры (γ,β) оптимизируются классическими методами включая BO - ландшафт целевой функции часто гладкий
• Теоретические гарантии сходимости — Адиабатическая теорема даёт условия сходимости QA; barren plateaus - аналог плохой обусловленности для QAOA
• Оптимизация на многообразиях — Параметры VQE/QAOA живут на многообразии унитарных операторов U(2^n); натуральный градиент на этом многообразии = квантовый Fisher information

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

• Почему barren plateaus - более фундаментальная проблема для VQA, чем шум NISQ-устройств?
• Какой класс задач (NP-hard, BQP, NP-complete) могут решить квантовые компьютеры за полиномиальное время согласно текущим теоретическим знаниям?
• Как проверить, что D-Wave действительно использует квантовое туннелирование, а не просто быстрый классический анилинг?

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

• la-33-la-in-qm