Перейти к содержимому
The Algotrading Book

Глава 187: QAOA Trading - Квантовая приближённая оптимизация для выбора портфеля

1. Введение

Квантовый алгоритм приближённой оптимизации (QAOA) является одним из наиболее перспективных квантовых алгоритмов ближнего срока для решения задач комбинаторной оптимизации. Первоначально предложенный Фархи, Голдстоуном и Гутманном в 2014 году, QAOA принадлежит к семейству вариационных квантовых алгоритмов, использующих гибридный квантово-классический цикл: параметризованная квантовая схема подготавливает кандидатные решения, а классический оптимизатор настраивает параметры для минимизации функции стоимости.

В контексте трейдинга многие ключевые задачи по своей природе являются комбинаторными. Выбор портфеля с ограничением на кардинальность (выбрать ровно k активов из n), планирование исполнения сделок на нескольких площадках и дискретное распределение активов - всё это NP-трудные задачи, с которыми классические решатели сталкиваются с трудностями по мере роста размера задачи. QAOA предоставляет структурированный подход к исследованию экспоненциально большого пространства решений, используя квантовую суперпозицию и интерференцию.

Эта глава представляет фреймворк QAOA, отображает задачи оптимизации портфеля на него и предоставляет полную реализацию на Rust, которая классически симулирует схемы QAOA. Мы интегрируем данные рынка в реальном времени с биржи Bybit для демонстрации алгоритма на реальных криптовалютных активах. Хотя текущее квантовое оборудование является шумным и ограниченным по количеству кубитов, классическая симуляция QAOA для задач умеренного размера (до ~20 кубитов) является практичной и служит ценным инструментом для понимания и бенчмаркинга этих квантово-вдохновлённых подходов.

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

2. Математические основы

2.1 Кодирование задачи: QUBO и модели Изинга

Большинство задач комбинаторной оптимизации, относящихся к трейдингу, могут быть закодированы как задачи квадратичной безусловной бинарной оптимизации (QUBO):

минимизировать: x^T Q x + c^T x
при условии: x_i in {0, 1}

где Q - матрица n x n, кодирующая парные взаимодействия, c - вектор линейных стоимостей, а x - бинарный вектор решений. Для выбора портфеля x_i = 1 означает, что актив i включён в портфель.

Формулировка QUBO напрямую отображается на гамильтониан Изинга через подстановку x_i = (1 - z_i) / 2, где z_i - операторы Паули-Z с собственными значениями +/-1:

H_C = sum_{i<j} J_{ij} Z_i Z_j + sum_i h_i Z_i + const

Это стоимостной гамильтониан, основное состояние которого кодирует оптимальное решение.

2.2 Структура схемы QAOA

QAOA строит p-слойную параметризованную квантовую схему. Начиная с равномерной суперпозиции |+>^n (все кубиты в состоянии |+>), схема чередует два типа операций:

Стоимостной унитарный оператор (разделение фаз):

U_C(gamma) = exp(-i * gamma * H_C)

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

Смешивающий унитарный оператор (смешивание):

U_M(beta) = exp(-i * beta * H_M)

где H_M = sum_i X_i - смешивающий гамильтониан (сумма операторов Паули-X). Этот оператор “смешивает” амплитуду между различными вычислительными базисными состояниями, позволяя алгоритму исследовать пространство решений.

Полное состояние QAOA с p слоями:

|gamma, beta> = U_M(beta_p) U_C(gamma_p) ... U_M(beta_1) U_C(gamma_1) |+>^n

Алгоритм ищет параметры (gamma_1, …, gamma_p, beta_1, …, beta_p), которые минимизируют:

F(gamma, beta) = <gamma, beta| H_C |gamma, beta>

2.3 Формулировка MaxCut

Каноническим примером для QAOA является задача MaxCut на графе G = (V, E). Стоимостной гамильтониан:

H_C = sum_{(i,j) in E} (1/2)(1 - Z_i Z_j)

Каждый член вносит +1, когда кубиты i и j находятся в разных состояниях (ребро “разрезано”), и 0, когда они совпадают. Задачи оптимизации портфеля могут быть отображены на взвешенный MaxCut или более общие формы QUBO, где структура графа кодирует корреляции активов, а веса кодируют ожидаемую доходность и риск.

2.4 p-слойный ансатц и коэффициент аппроксимации

Параметр p контролирует глубину схемы и выразительность ансатца. Для p = 1 QAOA может достичь коэффициентов аппроксимации не менее 0.6924 для MaxCut на 3-регулярных графах (Farhi et al., 2014). По мере увеличения p QAOA может в принципе достигать сколь угодно хороших коэффициентов аппроксимации, сходясь к точному решению при p, стремящемся к бесконечности.

На практике увеличение p вводит более сложный оптимизационный ландшафт с большим количеством локальных минимумов, требуя аккуратных стратегий инициализации. Распространённый подход - использовать оптимальные параметры от глубины p в качестве начальных приближений для глубины p+1 (передача параметров или “тёплый старт”).

3. Торговое применение

3.1 Выбор портфеля как комбинаторная оптимизация

Рассмотрим n кандидатных активов с ожидаемой доходностью mu_i, попарной ковариацией Sigma_{ij} и ограничением кардинальности на выбор ровно k активов. Задача оптимизации:

минимизировать: -lambda * sum_i mu_i x_i + (1-lambda) * sum_{i,j} Sigma_{ij} x_i x_j
при условии: sum_i x_i = k, x_i in {0, 1}

где lambda - параметр компромисса между риском и доходностью. Ограничение кардинальности sum_i x_i = k обеспечивается через штрафной член:

H_penalty = A * (sum_i x_i - k)^2

где A - большой штрафной коэффициент. Раскрытие этого штрафа даёт дополнительные квадратичные и линейные члены, которые включаются в матрицу QUBO.

Полная целевая функция QUBO становится:

Q_{ij} = (1-lambda) * Sigma_{ij} + A (для i != j)
c_i = -lambda * mu_i + A * (1 - 2k)
constant = A * k^2

3.2 Планирование исполнения сделок

QAOA также может оптимизировать планирование исполнения сделок по временным слотам. Дано n ордеров и T временных слотов, бинарная переменная x_{i,t} = 1 указывает, что ордер i исполняется в слоте t. Функция стоимости включает влияние на рынок (коррелированные сделки в одном слоте увеличивают воздействие) и временной риск (отложенное исполнение увеличивает подверженность ценовому движению).

3.3 Распределение активов с ограничениями кардинальности

Помимо бинарного выбора, многоуровневое распределение активов может быть закодировано с использованием нескольких бинарных переменных на актив. Например, для представления уровней распределения {0%, 25%, 50%, 75%, 100%} каждый актив получает 2 бинарные переменные (кодирующие 4 уровня плюс ноль). QUBO растёт квадратично по количеству бинарных переменных, но остаётся обрабатываемым для симуляции QAOA при умеренном количестве активов.

4. QAOA против классических оптимизаторов

4.1 Когда имеет значение квантовое преимущество?

Для малых размеров задач (n < 20 активов) классические алгоритмы полного перебора или ветвей и границ эффективно решают задачу выбора портфеля. Ценностное предложение QAOA возникает в нескольких сценариях:

  • Крупномасштабные комбинаторные задачи (n > 50 активов со сложными ограничениями), где классические точные решатели сталкиваются с экспоненциальным масштабированием
  • Оптимизация в реальном времени, где QAOA на квантовом оборудовании может обеспечить быстрые приближённые решения
  • Невыпуклые ландшафты, где эффект квантового туннелирования QAOA может покинуть локальные минимумы, ловящие классические оптимизаторы
  • Многокритериальная оптимизация, где квантовая суперпозиция естественно кодирует разнообразные портфели решений

4.2 Текущие ограничения

  • Шум на квантовом оборудовании: Современные устройства NISQ имеют ограниченное время когерентности и точность вентилей, ограничивая практический QAOA до p <= 5-10 слоёв на ~50-100 кубитах
  • Стоимость классической симуляции: Симуляция n кубитов требует 2^n комплексных амплитуд, ограничивая классическую симуляцию QAOA до ~25-30 кубитов
  • Оптимизация параметров: Классический внешний цикл сам может стать дорогостоящим, особенно для больших p, из-за невыпуклого ландшафта
  • Бесплодные плато: Для глубоких схем градиент функции стоимости может стать экспоненциально малым, затрудняя оптимизацию

4.3 Классические альтернативы

Для практической оптимизации портфеля сегодня эти классические подходы остаются конкурентоспособными:

  • Имитация отжига: Исследует пространство решений через термические флуктуации
  • Генетические алгоритмы: Эволюционный поиск с кроссовером и мутацией
  • Метод ветвей и границ: Точный решатель с отсечением (хорошо работает для умеренных n)
  • Релаксация полуопределённого программирования (SDP): Предоставляет границы и приближённые решения

QAOA лучше всего рассматривать как исследовательский инструмент сегодня, с потенциалом квантового преимущества по мере развития оборудования.

5. Описание реализации

Наша реализация на Rust предоставляет полный симулятор QAOA со следующими компонентами:

5.1 Представление вектора состояния

Мы представляем квантовое состояние как комплексный вектор размерности 2^n. Каждое базисное состояние |x> соответствует бинарной строке x = x_1 x_2 … x_n. Вектор состояния хранится как два параллельных массива (действительная и мнимая части) с использованием крейта ndarray для эффективных численных операций.

pub struct QAOASimulator {
    n_qubits: usize,
    state_real: Array1<f64>,
    state_imag: Array1<f64>,
}

5.2 Применение стоимостного гамильтониана

Стоимостной гамильтониан является диагональным в вычислительном базисе. Для каждого базисного состояния |x> унитарный оператор разделения фаз применяет:

// Для каждого базисного состояния вычислить стоимость и применить фазу
for idx in 0..dim {
    let cost = compute_cost(idx, &qubo_matrix, &linear_terms);
    let phase = -gamma * cost;
    let re = state_real[idx];
    let im = state_imag[idx];
    state_real[idx] = re * phase.cos() + im * phase.sin();
    state_imag[idx] = im * phase.cos() - re * phase.sin();
}

5.3 Применение смешивающего гамильтониана

Смешивающий гамильтониан H_M = sum_i X_i применяет вращения X к каждому кубиту независимо. Для одного кубита i вращение exp(-i * beta * X_i) смешивает пары состояний, отличающихся только в бите i.

5.4 Классический оптимизатор

Мы используем симплекс-метод Нелдера-Мида для оптимизации параметров. Этот безпроизводный метод хорошо подходит для QAOA, поскольку:

  • Стоимостной ландшафт невыпуклый с множеством локальных минимумов
  • Вычисление градиента потребовало бы множественных оценок схемы
  • Пространство параметров низкоразмерно (2p параметров)

5.5 Кодирование задачи портфеля

Структура PortfolioProblem инкапсулирует финансовые данные и метод to_qubo() преобразует их в матрицы Q и c, подходящие для QAOA.

6. Интеграция с Bybit

Реализация включает клиент API Bybit, который получает данные kline (свечи) для нескольких торговых пар:

pub async fn fetch_bybit_klines(symbol: &str, interval: &str, limit: usize)
    -> Result<Vec<KlineData>>

Мы получаем дневные свечи для BTCUSDT, ETHUSDT, SOLUSDT и XRPUSDT, затем вычисляем:

  1. Логарифмические доходности: r_t = ln(close_t / close_{t-1})
  2. Ожидаемые доходности: mu_i = mean(r_i) (в годовом выражении)
  3. Ковариационная матрица: Sigma_{ij} = cov(r_i, r_j) (в годовом выражении)

Эти финансовые статистики напрямую подаются в формулировку QUBO оптимизации портфеля. REST API Bybit обеспечивает надёжный, бесплатный доступ к историческим рыночным данным без аутентификации для публичных эндпоинтов:

GET https://api.bybit.com/v5/market/kline?category=spot&symbol=BTCUSDT&interval=D&limit=30

7. Ключевые выводы

  1. QAOA - это вариационный квантовый алгоритм, который отображает задачи комбинаторной оптимизации на параметризованные квантовые схемы. Гибридный квантово-классический цикл чередует подготовку квантового состояния и классическую оптимизацию параметров.

  2. Выбор портфеля естественно отображается на QUBO формулировки, которые может решать QAOA. Ограничения кардинальности, компромиссы между риском и доходностью и корреляционные структуры все кодируются как квадратичные бинарные целевые функции.

  3. Глубина схемы p контролирует компромисс качество-сложность. Мелкие схемы (p=1,2) дают быстрые, но приближённые решения; более глубокие схемы улучшают качество, но сталкиваются с более сложными оптимизационными ландшафтами.

  4. Классическая симуляция QAOA практична для малых задач (до ~20-25 кубитов). Это делает её ценным инструментом исследования и прототипирования даже без квантового оборудования.

  5. Квантовое преимущество для оптимизации портфеля ещё не доказано, но теоретически правдоподобно для крупномасштабных случаев со сложными ограничениями.

  6. Оптимизация Нелдера-Мида хорошо работает для настройки параметров QAOA благодаря низкоразмерной невыпуклой природе параметрического ландшафта.

  7. Интеграция реальных рыночных данных (через API Bybit) заземляет алгоритм в практических сценариях, демонстрируя, что фреймворк кодирования обрабатывает реальные финансовые статистики, включая нетривиальные корреляционные структуры.

  8. Стратегии тёплого старта (передача оптимальных параметров от глубины p к глубине p+1) значительно улучшают сходимость и качество решения на практике.

  9. Фреймворк QUBO универсален для бинарной оптимизации, что означает, что любая комбинаторная торговая задача (планирование, маршрутизация, распределение) может быть закодирована и решена тем же механизмом QAOA.

  10. Rust обеспечивает отличную производительность для классической симуляции QAOA благодаря абстракциям с нулевой стоимостью, безопасности памяти и эффективным численным вычислениям, что делает его подходящим для симуляции схем с до 20+ кубитами.