Численные методы
Квантовые алгоритмы
Цели урока
- Понять принципы квантовых вычислений: суперпозиция, запутанность, измерение - и почему считывание квантового состояния ограничивает ускорение
- Освоить алгоритм HHL для квантового решения линейных систем и его реальные ограничения
- Разобраться в VQE/QAOA - вариационных алгоритмах для NISQ-эпохи с parameter shift rule
Предварительные знания
- Автоматическое дифференцирование в ML
Google Sycamore 2019: 200 секунд против 10000 лет Summit - квантовое превосходство задокументировано
- Google Sycamore 2019: 200 секунд против 10000 лет Summit - квантовое превосходство задокументировано
- IBM Quantum: облачный доступ к 127-кубитным процессорам, VQE для квантовой химии
- Google Quantum AI 2023: симуляция модели Кители быстрее Frontier для конкретных задач
- Microsoft Azure Quantum: топологические кубиты и квантовый отжиг для оптимизации логистики
История квантовых вычислений
Ричард Фейнман (1982) предложил квантовые компьютеры для симуляции физики. Питер Шор (1994) создал алгоритм факторизации O(log^3 N) - угрозу RSA-криптографии. Лов Гровер (1996) предложил квадратичное ускорение поиска. Харроу, Хассидим и Ллойд (2009) - алгоритм HHL для СЛАУ. Google Sycamore (2019) - первое квантовое превосходство. VQE (Peruzzo et al., 2014) - начало вариационных алгоритмов для NISQ.
Кубиты, суперпозиция и квантовое ускорение
В 2019 году Google Quantum AI заявил о квантовом превосходстве на 53-кубитном Sycamore: задача выборки из случайной квантовой схемы, требующая 10 000 лет на Summit, решена за 200 секунд. IBM оспорил это - но факт остаётся: квантовые вычисления уже решают задачи, недостижимые классически.
Квантовое ускорение реально только для задач, где: (1) решение можно закодировать в квантовом состоянии, (2) нужна только агрегированная информация (норма, скалярное произведение), а не полный вектор. Иначе O(2^n) измерений уничтожают ускорение.
Почему считывание полного n-кубитного квантового состояния требует экспоненциально много измерений?
Одно измерение: P(x) = |c_x|^2. Получаем одно из 2^n значений x. Для оценки всего распределения с точностью epsilon: O(1/epsilon^2) повторений. Это узкое место - именно поэтому квантовые алгоритмы работают только если нужна агрегированная информация.
Алгоритм HHL: квантовое решение линейных систем
Harrow, Hassidim и Lloyd (2009) предложили квантовый алгоритм решения Ax=b за O(log(N)*kappa^2) вместо классических O(N*kappa). Для N=10^9 и kappa=10^4 это разрыв в миллиарды раз. Но - результат является квантовым состоянием |x>. Считывание классического вектора требует O(N) измерений.
HHL полезен только когда нужны агрегированные свойства решения - норма ||x||, скалярное произведение (x, v), определённые компоненты. Если нужен весь вектор x - классические методы быстрее. Это фундаментальное ограничение, а не техническое.
Когда алгоритм HHL НЕ даёт практического ускорения над классическими методами?
HHL даёт квантовое состояние |x>. Если нужно k компонент вектора, нужно O(k) проекционных измерений. При k=N это O(N) - никакого ускорения. Реальная польза: ||x||^2 за O(1) измерений, скалярное произведение (x,v) за O(1).
VQE и QAOA: вариационные квантовые алгоритмы
Пока квантовые компьютеры с ошибками (NISQ-эра), чистые квантовые алгоритмы (HHL, Shor) недостижимы. Вариационные квантовые алгоритмы (VQA) - гибрид: параметрические квантовые схемы оптимизируются классически. На 2024 год это лучшее, что есть для реальных квантовых устройств.
QAOA (Quantum Approximate Optimization Algorithm) применяется к комбинаторным задачам оптимизации: MaxCut, задача коммивояжёра, планирование. Теоретически даёт ускорение над классическими приближёнными алгоритмами. На практике 2024 года - ограниченным числом кубитов и шумом.
Чем parameter shift rule отличается от конечных разностей для вычисления градиента квантовой схемы?
Для параметра theta в R_y(theta) = exp(-i*theta/2 * Y): dE/dtheta = (E(theta+pi/2) - E(theta-pi/2))/2. Это точный результат (не приближение), вытекающий из структуры вращений. Аналог AD для квантовых вентилей.
Квантовая симуляция: Хамильтоновы системы
Фейнман в 1982 году предложил квантовые компьютеры как симуляторы квантовой физики: 'Nature is quantum, so let's simulate it with quantum'. Квантовая химия (кофактор молибдена нитрогеназы, 111 кубитов классическому алгоритму не хватает), физика конденсированного состояния (модель Хаббарда), ядерная физика - главные мишени.
Google Quantum AI в 2023 году запустил квантовую симуляцию модели Кители на 70 кубитах - быстрее классического суперкомпьютера Frontier для этой конкретной задачи. Microsoft Azure Quantum, IBM Quantum и IonQ - облачные квантовые вычисления уже доступны для исследователей.
Квантовая химия: электронная структура молекул
Молекула азота N2 имеет 14 электронов. Точное моделирование электронной структуры требует учёта 14 x 14 корреляций - 10^14 конфигурационных состояний. VQE на 14 кубитах представляет волновую функцию и оптимизирует параметры схемы. IBM достиг химической точности для N2 на 6 кубитах в 2017 году. Более сложные молекулы (например, нитрогеназа) требуют ~111 кубитов - пока недостижимо с ошибками NISQ.
Почему квантовая симуляция квантовой химии важнее, чем алгоритм HHL для ML?
Для ML через HHL: результат - квантовое состояние, считывание O(N) убивает ускорение. Для квантовой симуляции: вся информация об энергии системы - скаляр, измеримый за O(1/eps^2) повторений. Нет проблемы считывания.
Связь с другими темами
Квантовые алгоритмы пересекаются с линейной алгеброй (HHL = квантовый решатель СЛАУ), FFT (QFT), оптимизацией (VQE/QAOA через parameter-shift gradient) и физическими уравнениями (квантовая симуляция через nm-29 PINNs-идеи). Вариационные алгоритмы оптимизируются классическими методами AD из nm-25.
- Quantum Phase Estimation — Связанная тема
- Operator Splitting Analogy — Связанная тема
- Variational Quantum ML — Связанная тема
Итоги
- Квантовое ускорение реально только для задач с агрегированным результатом: считывание полного квантового вектора требует O(N) измерений и уничтожает логарифмическое ускорение HHL
- HHL: O(log(N)*kappa^2) для Ax=b, но практически полезен только когда нужны ||x||, (x,v), а не полный вектор x
- VQE/QAOA для NISQ-эпохи: параметрические квантовые схемы + классическая оптимизация через parameter shift rule (аналог AD)
- Квантовая симуляция (Фейнман 1982) - главное применение: экспоненциальное ускорение для задач квантовой химии и физики конденсированного состояния
Вопросы для размышления
- Google заявил о квантовом превосходстве для задачи случайной выборки. IBM возразил, что классический алгоритм с большей памятью справится за дни. Что определяет настоящее квантовое превосходство?
- HHL даёт экспоненциальное ускорение для Ax=b, но ограничение считывания часто делает его непрактичным. Назовите конкретные ML-задачи, где HHL реально применим.
- Parameter shift rule вычисляет градиент квантовой схемы за 2 измерения на параметр - точно как reverse-mode AD вычисляет градиент классической функции. Что принципиально разное в этих двух подходах?
Связанные уроки
- nm-25-autodiff — вариационные квантовые алгоритмы оптимизируются через AD классически
- nm-22 — QFT - квантовый аналог классического FFT
- nm-27 — квантовые симуляции требуют квантификации неопределённости